Théorème de Lambek-Moser

Le théorème de Lambek–Moser, dû à Joachim Lambek et Leo Moser en 1954, est un résultat de combinatoire qui donne une description des partitions des entiers naturels en deux ensembles complémentaires (comme par exemple les nombres premiers et les autres), à l'aide de deux fonctions non décroissantes. En particulier, lorsque l'un des ensembles est décrit par une formule explicite donnant son $n$-ème élément, le théorème permet de construire une formule donnant le $n$-ème entier non dans l'ensemble.

Des fonctions aux partitions

Les quatre fonctions $f$, $f^{*}$, $F$, et $F^{*}$, correspondant aux deux suites de Beatty 1, 3, 4, 6, ... et 2, 5, 7, 10, ... , suites des arrondis des multiples de $\varphi$ et de $\varphi +1$, où $\varphi$ est le nombre d'or.

Soit $f$ une fonction allant des entiers naturels non nuls vers les entiers (nuls ou non) non décroissante (chaque valeur de la suite $f(1),f(2),f(3),\dots$ est égale ou supérieure à la précédente) et non bornée. Une telle fonction n'a en général pas d'inverse, puisqu'elle peut sauter des valeurs ; on va définir une fonction $f^{*}$ elle aussi non décroissante et non bornée, aussi proche que possible d'un inverse de $f$ au sens où, pour tout entier $n$,

$$f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.$$

Cela revient à définir $f^{*}(n)$comme le nombre d'entiers $m$ pour lesquels $f(x)<m$ ; il en résulte que $f^{*}{}^{*}=f$. Les représentations de $f$ et $f^{*}$ comme des histogrammes sont symétriques l'une de l'autre par rapport à la première bissectrice $x=y$.

À partir de $f$ et $f^{*}$, on définit deux nouvelles fonctions $F$ et $F^{*}$ par :

$${\begin{aligned}F(n)&=f(n)+n\\F^{*}(n)&=f^{*}(n)+n\\\end{aligned}}$$

La première partie du théorème de Lambek–Moser affirme que chaque entier non nul est atteint une fois et une seule, soit par $F$, soit par $F^{*}$. Autrement dit, les valeurs prises par $F$ et celles prises par $F^{*}$ forment deux sous-ensembles complémentaires d'entiers non nuls. Plus précisément, chacune de ces deux fonctions envoie $n$ sur le $n$-ème élément du sous-ensemble correspondant.

Comme exemple de cette construction, soit $f(n)=n^{2}$. Son inverse dans $\mathbb {R}$ est la fonction racine carrée, dont l'approximation dans les entiers (au sens du théorème de Lambek–Moser) est $f^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor$ (le plus grand entier inférieur ou égal à ${\sqrt {n-1}}$). On a donc $F(n)=n^{2}+n$ et $F^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor +n.$ Pour $n=1,2,3,\dots$, les valeurs def $F$ sont les nombres oblongs

2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...

tandis que celles de $F^{*}$ sont

1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....

ces deux suites forment une partition de $\mathbb {N} ^{*}$ : chaque entier (non nul) appartient à une et une seule des deux. Le théorème de Lambek–Moser affirme que ce phénomène se produit pour tout choix de $f$ ayant les propriétés voulues.

Des partitions aux fonctions

Les deux fonctions $f$ (flèches bleues vers la droite) et $f^{*}$ (flèches rouges) correspondant à la partition des entiers en nombres premiers (2, 3, 5, 7, ...) et non-premiers (1, 4, 6, 8, ...) ; cette visualisation se base sur une méthode due à Angel.

La seconde partie du théorème de Lambek–Moser affirme la réciproque : toute partition des entiers provient de cette construction. Plus précisément, si $S=s_{1},s_{2},\dots$ et $S^{*}=s_{1}^{*},s_{2}^{*},\dots$ sont deux suites croissantes d'entiers complémentaires, il existe deux fonctions $f$ et $f^{*}$ produisant ces suites par la construction précédente : il suffit de définir $f(n)=s_{n}-n$ et $f^{*}(n)=s_{n}^{*}-n$.

Par exemple, pour la partition en nombres pairs et impairs, les fonctions $F(n)$ et $F^{*}(n)$ donnant respectivement le $n$-ème nombre pair ou impair, on obtient$f(n)=F(n)-n=n$ and $f^{*}(n)=F^{*}(n)-n=n-1$ , formant un couple d’inverses au sens précédent. La partition correspondant à la parité du nombre de 1 en représentation binaire (les nombres odieux (en) et les autres) utilise presque les mêmes fonctions, ajustées par les valeurs de la suite de Thue–Morse.

Définition par une limite

Lambek et Moser ont donné une construction directe de $F^{*}$ en partant de $F^{\#}(n)$ , la fonction donnant le nombre de valeurs de $x$ pour lesquelles $F(m)\leq n$; on a alors, pour tout $n$, $F^{*}(n)$ donné par la limite de la suite

$$n,n+F^{\#}(n),n+F^{\#}{\bigl (}n+F^{\#}(n){\bigr )},\dots ,$$

(laquelle devient donc constante à partir d’un certain rang).

Lambek et Moser prennent les nombres premiers comme exemple, prolongeant un travail antérieur de Viggo Brun et Derrick Lehmer. Si $\pi (n)$ est la fonction de compte des nombres premiers, alors le $n$-ème nombre composé (en comptant 1 comme composé) est donné par la limite de la suite

$$n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\bigr )},\dots$$

Pour certaines suites d'entiers, l'expression précédente devient constante après un nombre fixé d'étapes, permettant une formule explicite. Ainsi, le the $n$-ème entier qui n'est pas une puissance $k$-ème est donné par la formule $n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\rfloor$.

Historique et démonstrations

Le théorème fut découvert par Leo Moser et Joachim Lambek, qui le publièrent en 1954. Moser et Lambek disent avoir été inspirés par le travail antérieur Samuel Beatty sur les suites portant son nom, ainsi que par celui de Viggo Brun et Derrick Lehmer au début des années 1930. Edsger Dijkstra a donné une preuve visuelle du résultat, ainsi qu'une preuve basée sur un raisonnement algorithmique.

Résultats analogues

Pour les entiers naturels

Le théorème s'applique avec de légères modifications aux partitions des entiers naturels (nuls ou non). Dans ce cas, chaque partition définit une correspondance de Galois des entiers sur eux-mêmes, c'est-à-dire un couple de fonctions croissantes (au sens large) $(f,f^{*})$ tel que pour tous $x$ et $y$, $f(x)\leq y$ si et seulement si $x\leq f(y)$. Les fonctions $F$ et $F^{*}$ sont alors définies par $F(n)=f(n)+n$ et $F^{*}(n)=f^{*}(n)+n+1$.

Le théorème de Beatty

Le théorème de Beatty (déjà mentionné par Lord Rayleigh en 1894) affirme que pour deux nombres irrationnels positifs $r$ et $s$ tels que ${\tfrac {1}{r}}+{\tfrac {1}{s}}=1$, les deux suites $\lfloor i\cdot r\rfloor$ et $\lfloor i\cdot s\rfloor$ pour $i=1,2,3,\dots$ (obtainues en arrondissant à l'entier inférieur les multiples de $r$ et $s$) sont complémentaires, ce qu'on peut voir comme une application du théorème de Lambek–Moser à $f(n)=\lfloor rn\rfloor -n$ et $f^{\ast }(n)=\lfloor sn\rfloor -n$ ; on a alors $F(n)=\lfloor rn\rfloor$ and $F^{*}(n)=\lfloor sn\rfloor ,$ dont les suites de valeurs sont appelées les « suites de Beatty ».

Voir aussi

• Suite de Hofstadter (la suite Figure-Figure est un exemple d'application du théorème)

Notes

L’argument 1 (valeur 30em) n’existe pas dans le modèle appelé

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lambek–Moser theorem » (voir la liste des auteurs).