Accueil🇫🇷Chercher

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 -ième élément, le théorème permet de construire une formule donnant le -ième entier qui n'est pas dans l'ensemble.

Des fonctions aux partitions

Les quatre fonctions , , , et , correspondant aux deux suites de Beatty 1, 3, 4, 6, ... et 2, 5, 7, 10, ... , suites des arrondis des multiples de et de , où est le nombre d'or.

Soit une fonction allant des entiers naturels non nuls vers les entiers (nuls ou non) croissante (chaque valeur de la suite 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 elle aussi croissante et non bornée, aussi proche que possible d'un inverse de au sens où, pour tout entier ,

Cela revient à définir comme le nombre d'entiers pour lesquels ; il en résulte que [2]. Les représentations de et comme des histogrammes sont symétriques l'une de l'autre par rapport à la première bissectrice [3].

À partir de et , on définit deux nouvelles fonctions et par :

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 , soit par . Autrement dit, les valeurs prises par et celles prises par forment deux sous-ensembles complémentaires d'entiers non nuls. Plus précisément, chacune de ces deux fonctions envoie sur le -ème élément du sous-ensemble correspondant[2].

Comme exemple de cette construction, soit . 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 (le plus grand entier inférieur ou égal à ). On a donc et Pour , les valeurs de sont les nombres oblongs

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

tandis que celles de sont

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

ces deux suites forment une partition de : 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 ayant les propriétés voulues[2].

Des partitions aux fonctions

Les deux fonctions (flèches bleues vers la droite) et (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 et sont deux suites croissantes d'entiers complémentaires, il existe deux fonctions et produisant ces suites par la construction précédente : il suffit de définir et [2].

Par exemple, pour la partition en nombres pairs et impairs, les fonctions et donnant respectivement le -ème nombre pair ou impair, on obtient et , 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 en partant de , la fonction donnant le nombre de valeurs de pour lesquelles ; on a alors, pour tout , donné par la limite de la suite

(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 est la fonction de compte des nombres premiers, alors le -ème nombre composé (en comptant 1 comme composé) est donné par la limite de la suite[6]

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 -ème entier qui n'est pas une puissance -ème est donné par la formule [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) tel que pour tous et , si et seulement si . Les fonctions et sont alors définies par et [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 et tels que , les deux suites et pour (obtenues en arrondissant à l'entier inférieur les multiples de et ) sont complémentaires, ce qu'on peut voir comme une application du théorème de Lambek–Moser à et ; on a alors et dont les suites de valeurs sont appelées les « suites de Beatty »[12].

Voir aussi

Notes

Références

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.