Théorème de Lambek-Moser

Le théorème de Lambek–Moser, dû à Joachim Lambek et Leo Moser en 1954[1], 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 ${\displaystyle n}$-ième élément, le théorème permet de construire une formule donnant le ${\displaystyle n}$-ième entier qui n'est pas dans l'ensemble.

Des fonctions aux partitions

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

Soit ${\displaystyle f}$ une fonction allant des entiers naturels non nuls vers les entiers (nuls ou non) croissante (chaque valeur de la suite ${\displaystyle 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 ${\displaystyle f^{*}}$ elle aussi croissante et non bornée, aussi proche que possible d'un inverse de ${\displaystyle f}$ au sens où, pour tout entier ${\displaystyle n}$, $${\displaystyle f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.}$$ Cela revient à définir ${\displaystyle f^{*}(n)}$ comme le nombre d'entiers ${\displaystyle m}$ pour lesquels ${\displaystyle f(m)<n}$ ; il en résulte que ${\displaystyle f^{*}{}^{*}=f}$[2]. Les représentations de ${\displaystyle f}$ et ${\displaystyle f^{*}}$ comme des histogrammes sont symétriques l'une de l'autre par rapport à la première bissectrice ${\displaystyle x=y}$[3].

À partir de ${\displaystyle f}$ et ${\displaystyle f^{*}}$, on définit deux nouvelles fonctions ${\displaystyle F}$ et ${\displaystyle F^{*}}$ par : $${\displaystyle {\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 ${\displaystyle F}$, soit par ${\displaystyle F^{*}}$. Autrement dit, les valeurs prises par ${\displaystyle F}$ et celles prises par ${\displaystyle F^{*}}$ forment deux sous-ensembles complémentaires d'entiers non nuls. Plus précisément, chacune de ces deux fonctions envoie ${\displaystyle n}$ sur le ${\displaystyle n}$-ème élément du sous-ensemble correspondant[2].

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

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

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

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

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

Des partitions aux fonctions

Les deux fonctions ${\displaystyle f}$ (flèches bleues vers la droite) et ${\displaystyle 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[4].

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 ${\displaystyle S=s_{1},s_{2},\dots }$ et ${\displaystyle S^{*}=s_{1}^{*},s_{2}^{*},\dots }$ sont deux suites croissantes d'entiers complémentaires, il existe deux fonctions ${\displaystyle f}$ et ${\displaystyle f^{*}}$ produisant ces suites par la construction précédente : il suffit de définir ${\displaystyle f(n)=s_{n}-n}$ et ${\displaystyle f^{*}(n)=s_{n}^{*}-n}$[2].

Par exemple, pour la partition en nombres pairs et impairs, les fonctions ${\displaystyle F(n)}$ et ${\displaystyle F^{*}(n)}$ donnant respectivement le ${\displaystyle n}$-ème nombre pair ou impair, on obtient${\displaystyle f(n)=F(n)-n=n}$ et ${\displaystyle 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[5].

Définition par une limite

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

Lambek et Moser prennent les nombres premiers comme exemple, prolongeant un travail antérieur de Viggo Brun et Derrick Lehmer[7]. Si ${\displaystyle \pi (n)}$ est la fonction de compte des nombres premiers, alors le ${\displaystyle n}$-ème nombre composé (en comptant 1 comme composé) est donné par la limite de la suite[6] $${\displaystyle 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 ${\displaystyle n}$-ème entier qui n'est pas une puissance ${\displaystyle k}$-ème est donné par la formule ${\displaystyle n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\rfloor }$[8].

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[7] au début des années 1930. Edsger Dijkstra a donné une preuve visuelle du résultat[9], ainsi qu'une preuve basée sur un raisonnement algorithmique[10].

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) ${\displaystyle (f,f^{*})}$ tel que pour tous ${\displaystyle x}$ et ${\displaystyle y}$, ${\displaystyle f(x)\leq y}$ si et seulement si ${\displaystyle x\leq f(y)}$. Les fonctions ${\displaystyle F}$ et ${\displaystyle F^{*}}$ sont alors définies par ${\displaystyle F(n)=f(n)+n}$ et ${\displaystyle F^{*}(n)=f^{*}(n)+n+1}$[11].

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 ${\displaystyle r}$ et ${\displaystyle s}$ tels que ${\displaystyle {\tfrac {1}{r}}+{\tfrac {1}{s}}=1}$, les deux suites ${\displaystyle \lfloor i\cdot r\rfloor }$ et ${\displaystyle \lfloor i\cdot s\rfloor }$ pour ${\displaystyle i=1,2,3,\dots }$ (obtenues en arrondissant à l'entier inférieur les multiples de ${\displaystyle r}$ et ${\displaystyle s}$) sont complémentaires, ce qu'on peut voir comme une application du théorème de Lambek–Moser à ${\displaystyle f(n)=\lfloor rn\rfloor -n}$ et ${\displaystyle f^{\ast }(n)=\lfloor sn\rfloor -n}$ ; on a alors ${\displaystyle F(n)=\lfloor rn\rfloor }$ et ${\displaystyle F^{*}(n)=\lfloor sn\rfloor ,}$ dont les suites de valeurs sont appelées les « suites de Beatty »[12].

Voir aussi

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

Notes

1. Lambek et Moser 1954.
2. Lambek et Moser 1954; Honsberger 1970, pp. 95–96; Fraenkel 1977.
3. Garry 1997.
4. Angel 1964.
5. Allouche et Dekking 2019.
6. Lambek et Moser 1954; Roberts 1992.
7. Brun 1931; Lehmer 1932.
8. Honsberger 1970, pp. 97–100; Dos Reis et Silberger 1990; Roberts 1992.
9. Dijkstra 1980.
10. Dijkstra 1982.
11. Lambek 1994.
12. Rayleigh 1894; Beatty 1926; Honsberger 1970, pp. 93–95; Chamberland 2017.

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).

• (en) Jean-Paul Allouche et F. Michel Dekking, « Generalized Beatty sequences and complementary triples », Moscow Journal of Combinatorics and Number Theory, vol. 8, n^o 4,‎ 2019, p. 325–341 (DOI 10.2140/moscow.2019.8.325, MR 4026541, arXiv 1809.03424, S2CID 119176190)
• (en) Myer Angel, « Partitions of the natural numbers », Canadian Mathematical Bulletin, vol. 7, n^o 2,‎ 1964, p. 219–236 (DOI 10.4153/CMB-1964-020-1, MR 161826, S2CID 123729929)
• (en) Samuel Beatty, « Problem 3173 », The American Mathematical Monthly, vol. 33, n^o 3,‎ 1926, p. 159 (DOI 10.2307/2300153, JSTOR 2300153); Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159–160, JSTOR:2298716
• (de) Viggo Brun, « Rechenregel zur Bildung der ${\displaystyle n}$-ten Primzahl », Norsk Matematisk Tidsskrift, vol. 13,‎ 1931, p. 73–79 (zbMATH 0003.14902), cité par Lambek et Moser 1954
• (en) Marc Chamberland, Single Digits: In Praise of Small Numbers, Princeton University Press, 2017, 32–33 p. (ISBN 978-0-691-17569-0)
• (en) Edsger Dijkstra, On a theorem by Lambek and Moser, University of Texas, coll. « Report EWD753 », 1980 (lire en ligne)
• (en) Edsger Dijkstra, Theoretical Foundations of Programming Methodology: Lecture Notes of an International Summer School, directed by F. L. Bauer, E. W. Dijkstra and C. A. R. Hoare, vol. 91, D. Reidel Publishing Co., coll. « NATO Advanced Study Institutes Series, Series C – Mathematical and Physical Sciences », 1982, 19–23 p. (DOI 10.1007/978-94-009-7893-5_2, zbMATH 0533.40001)
• (en) A. J. Dos Reis et D. M. Silberger, « Generating nonpowers by formula », Mathematics Magazine, vol. 63, n^o 1,‎ 1990, p. 53–55 (DOI 10.1080/0025570X.1990.11977485, JSTOR 2691513, MR 1042938, lire en ligne)
• (en) Aviezri S. Fraenkel, « Complementary systems of integers », The American Mathematical Monthly, vol. 84, n^o 2,‎ 1977, p. 114–115 (DOI 10.2307/2319931, JSTOR 2319931, MR 429815)
• (en) Y. K. K. Garry, « Inverse sequences and complementary sequences », Mathematical Excalibur, vol. 3, n^o 4,‎ 1997, p. 2 (lire en ligne)
• (en) Yuval Ginosar, « On the Lambek–Moser theorem », Integers, vol. 14,‎ 2014, A09:1–A09:4 (arXiv 1207.5633, lire en ligne)
• (en) Ross Honsberger, Ingenuity in Mathematics, vol. 23, New York, Random House, Inc., coll. « New Mathematical Library », 1970, 93–110 p. (ISBN 0-394-70923-3, MR 3155264)
• (en) Joachim Lambek, « Some Galois connections in elementary number theory », Journal of Number Theory, vol. 47, n^o 3,‎ 1994, p. 371–377 (DOI 10.1006/jnth.1994.1043, MR 1278405)
• (en) Joachim Lambek et Leo Moser, « Inverse and complementary sequences of natural numbers », The American Mathematical Monthly, vol. 61, n^o 7,‎ august–september 1954, p. 454–458 (DOI 10.1080/00029890.1954.11988496, JSTOR 2308078)
• (en) Derrick Lehmer, « An inversive algorithm », Bulletin of the American Mathematical Society, vol. 38, n^o 10,‎ 1932, p. 693–694 (DOI 10.1090/S0002-9904-1932-05496-9, MR 1562488)
• (en) Lord Rayleigh, The Theory of Sound, vol. 1, Macmillan, 1894 (lire en ligne), p. 123
• (en) Joe Roberts, Lure of the Integers, Washington, DC, Mathematical Association of America, coll. « MAA Spectrum », 1992 (ISBN 0-88385-502-X, DOI 10.2307/40148160, JSTOR 40148160, MR 1189138, lire en ligne), p. 11
• (en) Roy E. Wild, « On the number of primitive Pythagorean triangles with area less than n », Pacific Journal of Mathematics, vol. 5,‎ 1955, p. 85–91 (DOI 10.2140/pjm.1955.5.85, MR 67912, lire en ligne)