Théorème des trois longueurs

Une animation montrant les intervalles créés par une rotation d'un nombre irrationnel avec $\theta \approx 0.2882$ et un point de départ $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 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 $x$ est notée $\{x\}=x-\lfloor x\rfloor$.

Une formulation équivalente

On peut aussi considérer des points sur le cercle unité (de circonférence 1). Pour un nombre réel $u$, on note alors $\{u\}$ le point du cercle qui fait un angle $2\pi u$ avec l'axe réel. Les multiples $\{iu\}$ sont alors les points obtenus par rotation d'angle $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 $\alpha =\sqrt{2}$ sont :

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

et on a :

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

Les cinq intervalles ont respectivement les longueurs :

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

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, Modèle:Lien, et John H. Halton. Des preuves plus récentes sont de Tony van Ravenstein et Langevin. Ces derniers dressent en plus un panorama des diverses approches.

Utilisation en algorithmique

En algorithmique, ce théorème assure une bonne répartition des clés dans un hachage par multiplication.

Bibliographie

• Modèle:Plume Modèle:Article (Une autre version est accessible ici
• Modèle:Article.
• Modèle:Article.