Accueil🇫🇷Chercher

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

Une animation montrant les intervalles créés par une rotation d'un nombre irrationnel avec et un point de départ .
Hugo Steinhaus
Vera T. Sós en 2008 à Oberwolfach.

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

  1. Ne pas confondre ce théorème avec le théorème de Banach-Steinhaus d'analyse fonctionnelle.
  2. Alessandri et Berthé 1998, p. 103-104.
  3. van Ravenstein 1988.
  4. Langevin 1991.
  5. Alessandri et Berthé 1998, p. 114.

Bibliographie

  • Document utilisé pour la rédaction de l’article 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).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.