--- title: "Le théorème des trois distances" author: "Stéphane Laurent" date: "2016-02-13" output: html_document --- ```{r setup, include=FALSE} library(knitr) opts_chunk$set(collapse=TRUE, message=FALSE, fig.path="./assets/fig/Thm3D-") cat_print = function(x, ...) { cat(x) } ``` Le théorème des trois distances, ou des trois longueurs, est à propos de la longueur des arcs qu'on obtient lorsqu'on place sur le cercle unité les points $0$, $\alpha$, $2\alpha$, $\ldots$, $n\alpha$, où $\alpha$ est un nombre irrationnel. ## Rappels sur les fractions continues ### Développement fini - nombre rationnel Soient $a_0\geq 0$, $a_1 \geq 1$, $\ldots$, $a_N \geq 1$ des nombres entiers. On définit le nombre rationnel $$ r_N = a_0 + \dfrac{1}{a_1 + \dfrac{1}{\cdots + \dfrac{1}{a_{N-1} + \dfrac{1}{a_N}}}}. $$ Le numérateur $p_N$ et le dénominateur $q_N$ de l'écriture fractionnaire irréductible $r_n = \frac{p_N}{q_N}$ s'obtiennent par récurrence avec les formules suivantes : $$ \begin{cases} p_{-1} = q_{-1} = 0 \\ p_0 = a_0, \, q_0 = 1 \\ p_n = a_n p_{n-1} + p_{n-2}, \, q_n = a_n q_{n-1} + q_{n-2} \end{cases}. $$ Notons qu'on a alors $q_1 = a_1$. Voyons un exemple avec R. On prend $a_0=0$, $a_1=1$, $a_2=2$ et $a_3=3$. ```{r, render=cat_print} a <- c(0, 1, 2, 3) ( rN <- a[1] + 1/(a[2] + 1/(a[3] + 1/a[4])) ) ``` On peut obtenir $r_N$ avec la librairie `contfrac` : ```{r, render=cat_print} library(contfrac) ( rN <- CF(a, finite=TRUE) ) ``` Les entiers $p_n$ et $q_n$ s'obtiennent avec la fonction `convergents` : ```{r} convergents(a) ``` Inversément, si on donne le nombre rationnel $0.7$ on peut obtenir son développement en fraction continue - les $a_n$ : ```{r} as_cf(0.7) ``` Comme on le voit, la fonction `as_cf` donne bien les entiers $a_0=0$, $a_1=1$, $a_2=2$ et $a_3=3$, puis donne des $a_n$ curieux pour $n \geq 4$. Cela vient du fait que `0.7` n'est pas parfaitement encodé en nombre "double" dans R : ```{r, render=cat_print} print(0.7, digits=20) ``` L'algorithme qui calcule les $a_n$ quand on donne un nombre rationnel $x$ est le suivant. Il calcule $$ x_0=x, \, x_n = \frac{1}{\{x_{n-1}\}} $$ en s'arrêtant à l'indice $N$ lorsque $x_N$ est entier, puis calcule $a_n = [x_n]$. ### Développement infini - nombre irrationnel Lorsque $\alpha>0$ est un nombre irrationnel, le même algorithme ne d'arrête jamais, et produit alors une suite ${(a_n)}_{n \geq 0}$ - le développement en fraction continue de $x$. On a aussi les suites ${(p_n)}_{n \geq 0}$ et ${(q_n)}_{n \geq 0}$ définies de la même façon. On note de plus $$ \eta_n = |q_n\alpha-p_n|. $$ La majoration $\eta_n \leq \frac{1}{q_{n+1}}$ est bien connue. ## Écriture $n = mq_k + q_{k-1} + r$ Soit $\alpha \in ]0,1[$ un nombre irrationnel. On note ${(a_n)}_{n \geq 0}$ son développement en fraction continue. Du fait que $\alpha < 1$, le premier "chiffre" $a_0$ est $0$. Tout nombre entier $n \geq a_1+1$ s'écrit de façon unique $$ n = m q_k + q_{k-1} + r $$ où $k \geq 1$, $1 \leq m \leq a_{k+1}$ et $0 \leq r < q_k$. L'entier $k$ est déterminé par $$ q_k + q_{k-1} \,\leq\, n \,<\, q_{k+1} + q _k = a_{k+1}q_k + q_{k-1} + q_k $$ puis $m$ est déterminé par $$ mq_k + q_{k-1} %= (m-1) q_k + q_{k-1} + q_k \,\leq\, n \,<\, mq_k + q_{k-1} + q_k $$ et finalement $$ r = n - (m q_k + q_{k-1}) $$ La fonction ci-dessous retourne $k$, $m$ et $r$, et prend en entrée $(a_1, a_2, \ldots)$ et $n$ : ```{r} f <- function(a, n){ if(n= %s", a[1]+1)) q <- c(1, a[1]) k <- 1; while(q[k+1]+q[k] <= n){ q <- c(q, a[k+1]*q[k+1]+q[k]) k <- k+1 } m <- 1; while(m*q[k] + q[k-1] + q[k] <= n){ m <- m+1 } r <- n-(m*q[k]+q[k-1]) cat(sprintf("k=%s, m=%s, r=%s\n", k-1, m, r)) return(invisible(list(k=k-1, m=m, r=r))) } ``` Prenons par exemple $a_1=2$, $a_2=3$, $a_3=2$, $a_4=4$ (rappelons que $a_0=0$). Cela donne $q_1=2$, $q_2 = 7$, $q_3 = 16$. Et prenons $$ n = 2 \times q_3 + q_2 + 1 = 40 $$ ```{r} f(c(2,3,2,4), 40) ``` ## Théorème des trois distances Soit $\alpha \in ]0,1[$ un nombre irrationnel et $n$ un nombre entier. Si on place successivement les points $0$, $\alpha$, $2\alpha$, $\ldots$, $n\alpha$ sur le cercle unité, on dépasse un tour de cercle du moment que $n \geq a_1+1$. Ces points partitionnent le cercle en un certain nombre d'arcs : ```{r, echo=FALSE, fig.width=3.25, fig.height=3.25, fig.align='center'} alpha <- 0.431657 n <- 10 x <- sapply(0:n, function(i) (i*alpha) %% 1) par(mar=c(0,0,0,0)) plot(cos(2*pi*x), sin(2*pi*x), asp=1, pch=".", axes=FALSE, xlab=NA, ylab=NA) text(cos(2*pi*x), sin(2*pi*x), 0:n) curve(sqrt(1-x^2), from=-1, to=1, lty="dashed", col="yellow", add=TRUE) curve(-sqrt(1-x^2), from=-1, to=1, lty="dashed", col="yellow", add=TRUE) ``` Le *théorème des trois distances*, ou des *trois longueurs*, donne de l'information précise quant à la longueur de ces arcs. Considérons l'écriture de $n$ vue auparavant : $$ n = m q_k + q_{k-1} + r. $$ Il y a deux possibilités : * Si $r=q_k-1$, il y a deux longueurs. La petite est $\eta_k$. La grande est $\eta_{k-1}-m\eta_k$. * Sinon, il y a trois longueurs. Dans l'ordre croissant, la plus petite est $\eta_k$. La seconde est $\eta_{k-1}-m\eta_k$. La troisème, la plus grande est $\eta_{k-1}-(m-1)\eta_k$, c'est la somme des deux autres. L'énoncé de ce théorème donné dans l'article d'[Alessandri et Berthé](http://www.theoremoftheday.org/Docs/3dAlessandriBerthe.pdf) fournit encore plus d'informations : il fournit le nombre d'arcs qui ont chacune de ces longueurs. ### Application : $\epsilon$-filet Dans les deux cas, la plus grande distance est toujours plus petite que $\eta_{k-1}$. On sait par ailleurs, nous l'avons déjà rappelé, que $\eta_{k-1} \leq \frac{1}{q_{k}}$. Choisissant alors $k$ tel que $\frac{1}{q_{k}} < \epsilon$, et $n$ de la forme $n = m q_k + q_{k-1} + r$, le théorème montre alors que l'ensemble $\{0, \alpha, \ldots, n\alpha\}$ intersecte tous les arcs de longueur $\epsilon$.