Théorème des trois longueurs

Une animation montrant les intervalles créés par une rotation d'un nombre irrationnel avec ${\displaystyle \theta \approx 0.2882}$ et un point de départ ${\displaystyle x\approx 0.0789}$.

Hugo Steinhaus

Vera T. Sós en 2008 à Oberwolfach.

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 ${\displaystyle x}$ est notée ${\displaystyle \{x\}=x-\lfloor x\rfloor }$.

Énoncé

Théorème des trois longueurs — Soit ${\displaystyle \alpha >0}$ un nombre irrationnel. Pour tout entier naturel ${\displaystyle n}$, les parties fractionnaires ${\displaystyle \{i\alpha \}}$ des nombres ${\displaystyle i\alpha }$ pour ${\displaystyle i=0,\ldots ,n}$ forment une partition de intervalle ${\displaystyle [0,1]}$ en ${\displaystyle n+1}$ 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 ${\displaystyle u}$, on note alors ${\displaystyle \{u\}}$ le point du cercle qui fait un angle ${\displaystyle 2\pi u}$ avec l'axe réel. Les multiples ${\displaystyle \{iu\}}$ sont alors les points obtenus par rotation d'angle ${\displaystyle 2\pi u}$, 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 ${\displaystyle \alpha ={\sqrt {2}}}$ sont :

${\displaystyle \{\alpha \}={\sqrt {2}}-1}$; ${\displaystyle \{2\alpha \}=2{\sqrt {2}}-2}$ ; ${\displaystyle \{3\alpha \}=3{\sqrt {2}}-4}$; ${\displaystyle \{4\alpha \}=4{\sqrt {2}}-5}$

et on a :

${\displaystyle 0<\{3\alpha \}<\{\alpha \}<\{4\alpha \}<\{2\alpha \}<1}$.

Les cinq intervalles ont respectivement les longueurs :

${\displaystyle 3{\sqrt {2}}-4;\ 3-2{\sqrt {2}};\ 3{\sqrt {2}}-4;\ 3-2{\sqrt {2}};\ 3-2{\sqrt {2}}}$;

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 ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ dans l'intervalle ${\displaystyle ]0,1[}$, les différences entre deux valeurs consécutives de ${\displaystyle n}$ telles que ${\displaystyle \{\alpha n\}<\beta }$ 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 ${\displaystyle \alpha }$, comme c'est réalisé dans l'animation donnée en haut à droite, par rapport aux intervalle ${\displaystyle [0,\beta [}$ et ${\displaystyle [\beta ,1[}$ (le cas montré en haut est celui où ${\displaystyle \alpha =\beta =\theta }$, et correspond aux suites sturmiennes); les longueurs des blocs de 0 et de 1 sont directement liés aux trois lacunes[2].

Preuve

Histoire

Le théorème des trois longueurs 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, 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

• Pascal Alessandri et Valérie Berthé, « Three distance theorems and combinatorics on words », Enseign. Math. (2), vol. 44, n^os 1-2,‎ 1998, p. 103-132 (MR 99i:11056, lire en ligne [archive du 22 février 2014], consulté le 16 février 2014) (Une autre version est accessible ici
• M. Langevin, « Stimulateur cardiaque et suites de Farey », Period. Math. Hungar., vol. 23,‎ 1991, p. 75-86 (MR 93b:11017).
• Tony van Ravenstein, « The three gap theorem (Steinhaus conjecture) », Austral. Math. Soc Ser. A, vol. 45, n^o 3,‎ 1988, p. 360-370 (MR 90a:11076).