Théorème des trois longueurs
Le théorème des trois longueurs, aussi appelé théorème de Steinhaus[1] ou théorème des trois distances, est un théorème de théorie des nombres qui concerne les multiples d'un nombre irrationnel. Il décrit une propriété de la répartition des parties fractionnaires de ces multiples dans l’intervalle [0,1].
Le théorème intervient aussi en combinatoire des mots, notamment dans les mots sturmiens et a des applications dans l’analyse de certains algorithmes de hachage, en informatique.
Le résultat a été conjecturé par Hugo Steinhaus, et une première preuve en a été donnée par Vera Sós.
Le théorème
Le théorème peut être énoncé de manière équivalente comme une propriété de répartition de nombres dans l'intervalle [0,1[ (ou, pour être tout à fait rigoureux, sur le tore à une dimension 1), ou de point sur un cercle de circonférence unité. La partie fractionnaire d'un nombre est notée .
Énoncé
Théorème des trois longueurs — Soit un nombre irrationnel. Pour tout entier naturel , les parties fractionnaires des nombres pour forment une partition de intervalle en intervalles; les longueurs de ces intervalles prennent au plus trois valeurs, et la plus grande est la somme des deux autres.
Une formulation équivalente
On peut aussi considérer des points sur le cercle unité (de circonférence 1). Pour un nombre réel , on note alors le point du cercle qui fait un angle avec l'axe réel. Les multiples sont alors les points obtenus par rotation d'angle , et l'énoncé concerne la longueur des arcs de cercle entre deux points consécutifs : ces longueurs ne prennent que trois valeurs au plus.
Un exemple
Les parties fractionnaires des quatre premiers multiples de sont :
- ; ; ;
et on a :
- .
Les cinq intervalles ont respectivement les longueurs :
- ;
et ces longueurs ne prennent même que deux valeurs dans ce cas.
Théorème des trois lacunes
Le lien entre ce théorème des trois longueurs et la combinatoire des mots est particulièrement apparente dans le résultat suivant, connu sous le nom de théorème des trois lacunes (« three gap theorem » en anglais), qui est équivalent au théorème des trois longueurs et qui peut être considéré comme son « dual » : étant donné deux nombres et dans l'intervalle , les différences entre deux valeurs consécutives de telles que prennent au plus trois valeurs, la plus grande étant la somme des deux autres. On peut en effet construire un codage naturel de l'orbite d'un point du cercle unité par la rotation d'angle , comme c'est réalisé dans l'animation donnée en haut à droite, par rapport aux intervalle et (le cas montré en haut est celui où , et correspond aux suites sturmiennes); les longueurs des blocs de 0 et de 1 sont directement liés aux trois lacunes[2].
Histoire
Le théorème des trois distances a été conjecturé par Hugo Steinhaus; la première preuve a été donnée en 1957 par Vera Sós. Très rapidement, d'autres démonstrations ont été données par S. Świerczkowski, János Surányi (hu), Noel Bryan Slater (de), et John H. Halton. Des preuves plus récentes sont de Tony van Ravenstein[3] et Langevin[4]. Ces derniers dressent en plus un panorama des diverses approches[5].
Utilisation en algorithmique
En algorithmique, ce théorème assure une bonne répartition des clés dans un hachage par multiplication.
Notes et références
- Ne pas confondre ce théorème avec le théorème de Banach-Steinhaus d'analyse fonctionnelle.
- Alessandri et Berthé 1998, p. 103-104.
- van Ravenstein 1988.
- Langevin 1991.
- Alessandri et Berthé 1998, p. 114.
Bibliographie
- Pascal Alessandri et Valérie Berthé, « Three distance theorems and combinatorics on words », Enseign. Math. (2), vol. 44, nos 1-2, , p. 103-132 (MR 99i:11056, lire en ligne [archive du ], consulté le ) (Une autre version est accessible ici
- M. Langevin, « Stimulateur cardiaque et suites de Farey », Period. Math. Hungar., vol. 23, , p. 75-86 (MR 93b:11017).
- Tony van Ravenstein, « The three gap theorem (Steinhaus conjecture) », Austral. Math. Soc Ser. A, vol. 45, no 3, , p. 360-370 (MR 90a:11076).