Théorème de Lambek-Moser

Le théorème de Lambek–Moser, dû à Joachim Lambek et Leo Moser en 1954Modèle:Sfn, est un résultat de théorie des nombres et 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 croissantes. En particulier, lorsque l'un des ensembles est décrit par une formule explicite donnant son Modèle:Nowrap élément, le théorème permet de construire une formule donnant le Modèle:Nowrap entier qui n'est pas dans l'ensemble.

Des fonctions aux partitions

Les quatre fonctions $f$, $f^{*}$, $F$, et $F^{*}$, correspondant aux deux suites de Beatty Modèle:Nowrap et Modèle:Nowrap suites des arrondis des multiples de $\phi$ et de $\phi +1$, où $\phi$ est le nombre d'or.

Soit $f$ une fonction allant des entiers naturels non nuls vers les entiers (nuls ou non) 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 ou prendre plusieurs fois une même valeur ; on va définir une fonction $f^{*}$ elle aussi croissante et non bornée, aussi proche que possible d'un inverse de $f$ au sens où, pour tout entier $n$, $$f(f^{*}(n))<n\le f(f^{*}(n)+1).$$ Cela revient à définir $f^{*}(n)$ comme le nombre d'entiers $m$ pour lesquels $f(m)<n$ ; 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$Modèle:Sfn.

À partir de $f$ et $f^{*}$, on définit deux nouvelles fonctions $F$ et $F^{*}$ par : $$\begin{array}{cc}F(n)& =f(n)+n\\ F^{*}(n)& =f^{*}(n)+n\\ \end{array}$$ 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 $ℝ$ 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 de $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 deuxModèle:Sfn. 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 à AngelModèle:Sfn.

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 Modèle:Nowrap nombre pair ou impair, on obtient$f(n)=F(n)-n=n$ et $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 Modèle:Lien et les autres) utilise presque les mêmes fonctions, ajustées par les valeurs de la suite de Thue–MorseModèle:Sfn.

Définition par une limite

Lambek et Moser ont donné une construction directe de Modèle:Nowrap en partant de $F^{\mathrm{\#}}(n)$ , la fonction donnant le nombre de valeurs de $x$ pour lesquelles $F(m)\le n$; on a alors, pour Modèle:Nowrap $F^{*}(n)$ donné par la limite de la suite $$n,n+F^{\mathrm{\#}}(n),n+F^{\mathrm{\#}}(n+F^{\mathrm{\#}}(n)),\dots ,$$ (laquelle devient donc constante à partir d’un certain rang)Modèle:Nowrap.

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 Modèle:Nowrap nombre composé (en comptant 1 comme composé) est donné par la limite de la suite $$n,n+\pi (n),n+\pi (n+\pi (n)),\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 Modèle:Nowrap entier qui n'est pas une puissance Modèle:Nowrap est donné par la formule $n+\lfloor \sqrt[k]{n+\lfloor \sqrt[k]{n}\rfloor }\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 de 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ésultatModèle:Sfn, ainsi qu'une preuve basée sur un raisonnement algorithmiqueModèle:Sfn.

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)\le y$ si et seulement si $x\le f(y)$. Les fonctions $F$ et $F^{*}$ sont alors définies par $F(n)=f(n)+n$ et $F^{*}(n)=f^{*}(n)+n+1$Modèle:Sfn.

Le théorème de Beatty

Modèle:Article détaillé 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 $\frac{1}{r}+\frac{1}{s}=1$, les deux suites $\lfloor i\cdot r\rfloor$ et $\lfloor i\cdot s\rfloor$ pour $i=1,2,3,\dots$ (obtenues 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$ et $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)

Références

• Modèle:Article
• Modèle:Article
• Modèle:Article; Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159–160, Modèle:Jstor
• Modèle:Article, cité par Modèle:Harvsp
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Article