Nombres et représentations

Les décimales de sont-elles aléatoires ?

Piste rouge Le 8 août 2011  - Ecrit par  Valérie Berthé Voir les commentaires (2)

La question de la représentation des nombres (réels, entiers, complexes...) est centrale, que ce soit en mathématiques ou en informatique. Nous commençons par expliquer deux systèmes classiques : le développement dans une base entière et les fractions continues. Nous verrons comment ils se formulent en termes dynamiques et dans quels sens on peut se demander si les représentations obtenues sont « aléatoires ». Nous évoquerons les réponses obtenues par les mathématiciens depuis le 19ème siècle jusqu’à tout récemment... et les questions qu’ils continuent à se poser.

Parmi les systèmes de représentation les plus utilisés, on trouve la numération en base entière et le développement en fraction continue.

Développement en base dix

L’exemple le plus classique de numération en base entière est celui de la numération en base dix. Un quart s’écrit $0,25$ car $1/4=2/10+5/100$ tandis que $1,141$ représente $1+\frac{1}{10}+\frac{4}{10^2}+\frac{1}{10^3}$. L’informaticien se demande déjà si ces représentations sont commodes pour faire faire les opérations arithmétiques à un processeur. Pour le mathématicien, ces développements finis sont ennuyeux ! Heureusement, il y a des nombres comme $1/11$, pour lequel les choses sont un peu plus compliquées ; on a besoin d’une suite infinie de chiffres :

$ \frac1{11} = 0,0909090909090909090909090909090909\dots $

Plus on a de chiffres, plus on est près de $1/11$ (bien qu’on n’y soit jamais tout à fait).

Erreur

L’erreur se lit sur le développement. En effet, si l’on ne considère que les $2m$ premiers chiffres, l’erreur correspond au reste du développement, qui n’est autre que celui de $1/11$ décalé. Plus précisément, si l’on ne retient que les $n=2m$ premiers chiffres du développement décimal de $1/11$, on peut calculer l’erreur commise : $1/11-9\times 10^{-2}\times \frac{1-10^{-n}}{1-10^{-2}}=\frac{1}{11} \times 10^{-n} < 10^{-n-1}$. L’erreur devient vite très petite mais n’est jamais nulle.

Le développement de $1/11$ ci-dessus est infini mais très simple : on répète indéfiniment le même bloc de deux chiffres $09$. D’autres nombres ont un développement d’aspect beaucoup plus compliqué, par exemple pi s’écrit
(voir aussi l’article de F. Gramain Les décimales de pi)

$ \pi = 3,141592653589793238462643383279502884197169399375105820974944\dots $

Nous verrons bientôt quelles questions le mathématicien peut se poser au sujet de cette suite de chiffres.

Développement en fraction continue

Dans le cas des fractions continues,
on représente un nombre réel $x$ positif
sous la forme suivante \[x= a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{a_4+\cdots}}}}\]
On utilise également la notation $x=[a_0 ; a_1,\cdots,a_n, \cdots]$. Les nombres $a_i$ sont appelés quotients partiels,
ce sont des nombres entiers qui peuvent prendre des valeurs arbitrairement grandes. Les quotients partiels jouent ici le rôle des chiffres dans le développement en base dix.
L’intérêt de ce type de représentation est qu’il permet de produire de très bonnes approximations rationnelles
de $x$ en tronquant cette écriture infinie. Pour plus de détails concernant la qualité ces approximations rationnelles, voir l’article de Wikipédia. Par exemple,
le début du développement de $e$ [1] est donné par

$e= 2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{1+\cdots}}}}=[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, \cdots] $

Approximations rationnelles

On a
$e=[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, \cdots] = 2.71828182\dots$
En tronquant cette écriture, on obtient comme approximations rationnelles :
$[2;1]=2+\cfrac{1}{1}=3,$ $[2;1,2]= 2+\cfrac{1}{1+\cfrac{1}{2}}=8/3= 2,6666\dots ,$
$[2;1,2,1]=2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{1}}}=11/4 =2,75 \ . $
Le $n$-ième terme de la suite des rationnels ainsi produite s’approche de plus en plus de la valeur de $e$.

Pour des exemples de développements en fractions continues de constantes classiques, voir l’article de A. Broise Calendriers et fractions continues.
Ainsi,

$\pi = [3; 7, 15, 1, 292, 1, 1, 1, 12, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, \cdots].$

Les approximations correspondantes de $\pi=3,14159265\dots$ sont les fractions bien connues :
$[3;7]=3+\frac17=22/7=3,142857\dots$,

$[3;7,15]=3+\frac1{7+\frac1{15}}=333/106=3,141509\dots$,

$[3;7,15,1]=3+\frac1{7+\frac1{15+\frac11}}=355/113=3,141593\dots$

Le développement en fraction continue de $\sqrt 2 $ est égal à

$1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}}=[1;2,2,\cdots,2,\cdots].$

Nous montrons ci-dessous comment l’obtenir. Voir aussi l’article de B. Rittaud La porte d’harmonie.

Quelques variations

Il existe de nombreuses variations autour de ces systèmes de numération. On peut ainsi représenter
les nombres réels de l’intervalle $[0,1]$ [2] en base $q$, où $q$ est un nombre entier plus grand que $2$ de la manière suivante :

\[x= \frac{x_1}{q}+\frac{x_2}{q^2}+\frac{x_3}{q^3}+\dots \]
qu’on écrit souvent $\sum _{i \geq 1} x_i q^{-i}$ et
où les chiffres $x_i$ appartiennent à l’ensemble
$\{0,1\cdots,q-1\}$. Quand $q=10$ on retrouve la numération décimale, et on obtient la numération binaire quand $q=2$.
Par exemple, le début du développement binaire de $\sqrt 2$ est
\[1,0110101000001001111\dots\]
De même, la représentation en fraction continue
se décline sous des formes variées : les $1$ peuvent être remplacés par d’autres nombres entiers (positifs ou négatifs), les quotients partiels peuvent prendre des valeurs négatives etc. Les domaines d’application de ces divers types de représentation sont variés, et vont de la théorie des nombres (voir l’article de J. Rehmeyer Les travaux d’Elon Lindenstrauss) à la cryptographie, en passant par l’arithmétique des ordinateurs (voir l’article de V. Lefèvre, J.-M. Muller Erreurs en arithmétique des ordinateurs).

Comment obtenir les chiffres ?

L’une des premières questions qui se pose concernant ces systèmes de représentation est de savoir comment l’on obtient
les chiffres. Il existe pour chacun de ces deux types de développement des procédés algorithmiques simples de production
des chiffres. Ces procédés reposent sur l’usage des parties entières et fractionnaires, ainsi que des opérations arithmétiques élémentaires.

Parties entière et fractionnaire

La partie entière $[y]$ du nombre réel
$y$ désigne l’unique nombre entier $k$ tel que $ k \leq y < k+1$.
La partie fractionnaire $\{y\}$ du nombre réel $y$ désigne $y - [y]$. Elle satisfait
$0 \leq \{y\} < 1$. On a par exemple
\[[2,31]=2, \{2,31\}=0,31,\ \ [3,97]=3, \ \{3,97\}=\{0,9\}, \ [5]=5, \ \{5\}=0.\]

Prenons par exemple le cas de la numération en base $q$. Soit un nombre réel
$x \in [0,1[$. On suppose que la suite des chiffres $(x_i)_i$ de $x= \sum _{i \geq 1} x_i q^{-i}$ ne finit pas avec la suite constante $(q-1)\cdots (q-1)$ [3].
Pour produire le premier chiffre $x_1$ de $x= \sum _{i \geq 1} x_i q^{-i},$
on multiplie tout d’abord $x$ par $q$ :

\[qx=x_1+ \frac{x_2}{q} + \frac{x_3}{q^2} + \frac{x_4}{q^3} + \cdots =x_1+\sum _{i \geq 1} x_{i+1} q^{-i}.\]

On sépare alors dans cette quantité la partie entière
de la partie fractionnaire, ce qui donne

\[x_1=[qx], \quad \{qx\}= \sum _{i \geq 1} x_{i+1} q^{-i}.\]

On a ainsi obtenu un algorithme simple de production de ce premier chiffre qui se décrit comme une transformation de l’intervalle :

\[T_q\colon [0,1] \rightarrow [0,1], \ x \mapsto qx - [ qx]= \{qx\}.\]

Cette transformation permet plus généralement de produire le chiffre $x_i$ comme
$x_i=[ q T_{q}^{i-1}(x)],$ pour tout $ i \geq 1$.

Et pour les fractions continues ?

Considérons maintenant le cas du développement en fraction continue.
Soit $x \in [0,1]$. Le quotient partiel $a_0$ du développement de $x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{a_4+\cdots}}}}$ s’obtient comme
$a_0=[x]$. En effet, on a $[0; a_1,a_2, \cdots, a_n , \cdots] \in [0,1[.$
Il reste donc à savoir déterminer les quotients partiels d’un élément $x \in [0,1[$ (et dans ce cas $a_0=0$).
Comment obtenir le premier quotient partiel $a_1$ du développement de $x$ ?
On a
\[\frac{1}{x}= a_1 + \cfrac{1}{a_2+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{a_4+\cdots}}}}.\]
On en déduit que \[a_1= [ \frac{1}{x} ].\]
Si l’on pose $x_1= \{1/x\}$, on obtient
\[ \frac{1}{x}= a_1+x_1,\] et donc
\[x= \frac{1}{a_1+ x_1}.\]
On a $x_1 \in [0,1[$ et on peut réitérer l’opération sur $x_1$.
Ceci nous amène à introduire là encore une transformation de l’intervalle, appelée
application de Gauss, définie sur $[0,1]$ par
\[T_G\colon x \mapsto \{1/x\} \mbox{ pour } x \neq 0, \quad T_G(0)=0.\]
Cet algorithme produit bien les quotients partiels dans le développement en fraction continue (voir aussi Calendriers et fractions continues).
On vérifie ainsi que les quotients partiels $a_n$ sont obtenus en itérant la transformation $T_G$ :
\[a_n=[ \frac{1}{T^{n-1}x} ] \ \mbox{ pour } n \geq 1.\]

Développement de $\sqrt 2$

Nous pouvons ainsi retrouver de manière élémentaire le fait que le développement en fraction continue de $\sqrt 2 $ est égal à
\[1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}}\ .\]
Posons $x= \sqrt{2}-1$. On a $1/x= \sqrt 2 +1=2,4142135\dots $,
$[1/x]=2$, et
$T_G(x)= 1/x -2= \sqrt{2}-1=x$. Le nombre $x$ est donc un point fixe de $T_G$.
On en déduit que tous les quotients partiels du développement de $\sqrt {2}-1$ sont égaux à $2$.

Hasard et normalité

Les questions qui se posent concernant ces systèmes de représentation sont diverses, et relèvent
de l’arithmétique (voir l’article de
Wikipédia) ou de la théorie (métrique) des nombres (voir l’article de Wikipédia), ou encore
de la théorie des langages formels (voir l’article de Wikipédia) ou de la théorie de la calculabilité (voir l’article de Wikipédia).

Une des questions les plus naturelles concerne le comportement du développement d’un nombre pris au hasard, et en particulier,
les propriétés statistiques de répartition des chiffres produits.
Dans un même ordre d’idées, quel est le comportement d’un nombre « remarquable », par exemple, une des constantes fondamentales classiques $\pi$, $e$, $\sqrt 2$, etc.
Considérons ainsi le développement décimal de $\pi$. La répartition des décimales de $\pi$ simule-t-elle le hasard ?
Peut-on y trouver toute suite finie de nombres ? En particulier, peut-on trouver dans $\pi$ la suite des dates de naissance des reines de France ?
On peut d’ailleurs consulter à ce sujet le site The Pi-search site ainsi que l’article Les décimales de pi.

Quel est le comportement du développement décimal d’un nombre tiré au hasard ?
On peut s’attendre à ce que les chiffres qui apparaissent dans son développement décimal aient tous la même fréquence, à savoir
$1/10$. On peut de plus grouper les chiffres pour considérer les mots qui apparaissent. Un mot est ainsi une suite de chiffres qui apparaissent de manière consécutive. Par exemple, $15926535$ est un mot fini qui apparaît dans le développement décimal de $\pi$, de même, $0909$
apparaît dans celui de $1/11$, alors que $99009$ n’y apparaît pas.
On s’attend donc également à ce que chaque
mot fini composé de $k$ chiffres compris entre 0 et 9
apparaisse avec la fréquence $(1/10)^k$ dans un nombre tiré au hasard. Un nombre dont le développement décimal satisfait cette propriété (les mots de même longueur apparaissant avec la même fréquence) est appelé nombre normal (en base dix).
Le nombre de Champernowne est obtenu en concaténant les écritures en base dix des nombres entiers. Le début de son développement décimal est
\[0, 1 2 34567891011121314151617181920\dots\]
Ce nombre est un nombre normal en base dix.
On obtient de même un nombre normal (en base dix) en concaténant les écritures en base dix des nombres premiers. Le début de son développement décimal est
\[0,235711131719232931\dots \]

Nombre absolument normal

Un nombre est dit normal en base $q$ si son développement en base $q$ est tel que les mots de même longueur apparaissent avec la même fréquence. Un nombre normal dans toute base $q$ est appelé absolument normal.
E. Borel a introduit cette notion en 1909, et a montré que cette propriété caractérisait bien le comportement
typique d’un nombre. En effet, il a montré que presque tous les nombres réels sont absolument normaux (c’est-à-dire que
l’ensemble des nombres réels non normaux est un ensemble de mesure nulle pour la mesure de Lebesgue). Il a fallu alors attendre 1916 pour que
W. Sierpinski produise
le premier exemple de nombre absolument normal.
Il est bien plus aisé de construire des exemples explicites de nombres normaux en base dix, mais qui ne sont pas nécessairement absolument normaux.

Notons qu’il existe une différence importante entre la
normalité prouvée et la normalité soupçonnée.
Il est ainsi conjecturé que les constantes fondamentales comme $e$, $\pi$, $\ln 2$, $\zeta(3)$...
sont des nombres normaux, de même que les nombres algébriques irrationnels
(un nombre algébrique est une racine d’une équation polynomiale à coefficients entiers ; par exemple, $\sqrt 2$ est racine de l’équation $X^2-2=0$).
Il s’agit de questions particulièrement difficiles, la normalité de $\sqrt 2$, par exemple, est toujours considérée comme hors d’atteinte.

Si la normalité correspond soit au comportement typique, soit au comportement des nombres remarquables, cela ne veut pas pour autant dire
que tous les nombres que nous avons l’habitude de manipuler sont normaux.
Ainsi $0$ ou $1/11$ sont bien loin de d’être normaux.

Nombres irrationnels, algébriques et transcendants

Les notions d’irrationalité et d’algébricité permettent également de faire une classification de nature algébrique des nombres. Les nombres les plus simples sont les entiers. Leurs quotients sont les nombres rationnels. Nous avons vu qu’un nombre algébrique est une racine d’une équation polynomiale à coefficients entiers, comme, par exemple, $\sqrt 2$.
Un nombre transcendant est un nombre qui n’est pas algébrique, c’est-à-dire qui n’est pas solution d’une équation polynomiale à coefficients entiers. Par exemple, $\pi$ ou $e$ sont transcendants. Nous allons dans la suite chercher à voir comment cette classification peut se retrouver dans les développements des nombres réels.

Systèmes dynamiques mesurés

Si l’on ne sait pas traiter le cas d’un nombre fixé, comme $\sqrt 2$, le comportement typique (qu’il s’agisse de numération en base entière ou de fractions
continues) est, lui, bien décrit.
Par exemple, on sait comment se comporte la taille d’un quotient partiel en moyenne.
L’étude des transformations $T_{q}$ et $T_G$ (qui produisent les chiffres) permet ainsi de répondre à ces questions.
En effet, nous nous trouvons
dans le cadre de systèmes dynamiques mesurés, c’est-à-dire de transformations munies d’une mesure invariante.
Le théorème ergodique (voir l’article de Wikipédia) permet alors de répondre à ces questions concernant le comportement typique (de presque tout nombre réel). Voir aussi par exemple
Calendriers et fractions continues, Les travaux d’Elon Lindenstrauss pour le cas des fractions continues,
ou encore l’article d’E. Janvresse Quel est le début de ce nombre ? pour la numération usuelle.

Occurrences de mots

Au vu de la difficulté de la question de la normalité, on peut s’intéresser à une condition plus faible. Au lieu de s’intéresser à la fréquence d’apparition des blocs dans
un développement décimal, on peut plus simplement compter les différents blocs de chiffres de longueur donnée $n$ qui apparaissent
dans le développement d’un nombre (on ne compte plus ici combien de fois ils apparaissent, mais s’ils apparaissent au moins une fois). Cette quantité, appelée fonction de complexité, est une notion classique en combinatoire des mots.
Considérons par exemple les premiers chiffres du développement de $\sqrt 2$ en base dix
\[\sqrt 2= 1,4{\underline{ 14}}2{\underline{1 3}}5623 73095 04880 {\underline{16}}887 24209 69807 85696 7{\underline{18}}75 37694 80731 \dots\]
On voit que les $10 $ chiffres allant de $0$ à $9$ apparaissent, de même que les mots de longueur $2$ :
$13,14,16, 18$ (soulignés ci-dessus). En prenant un début de développement décimal plus long, on verrait que les $10$ mots de longueur $2$ commençant par le chiffre $1$
apparaissent effectivement.

Plus précisément, soit $p(n,x)$ le nombre de mots de longueur $n$ que l’on trouve dans le développement décimal du nombre réel $x$. On voit que
$1 \leq p (n,x) \leq 10 ^n$
pour tout $n$. Notons que la complexité $p(n,x)$ d’un nombre rationnel est bornée. En effet, son développement est ultimement périodique (c’est-à-dire périodique à partir d’un certain indice). Ainsi, dans le cas de $1/11$, $p(n,1/11)=2$ pour tout $ n$.

Complexité d’un nombre rationnel

La complexité $p(n,x)$ d’un nombre réel $x$ (avec $x \in [0,1]$) dont le développement décimal est purement périodique est bornée. En effet, dès que la longueur $n$ des mots dépasse celle d’une période, on a $p(n+1,x)=p(n,x)$. Cela vient du fait que tout mot se prolonge toujours de la même manière. Le développement décimal de $1/11$ est purement périodique et admet une période de longueur $2$. On a $p(n,1/11)=2$ pour tout $ n$. Les deux mots qui apparaissent pour $n=2$
sont $09$ et $90$. Le mot $09$ est toujours suivi de $0$ et le mot $90$ de $9$, les mots de longueur $3$ sont donc $090$ et $909$ ; $p(2,1/11)=p(3,1/11)$. On déduit du fait que la complexité $p(n,x)$ d’un nombre réel $x$ dont le développement décimal est purement périodique est bornée qu’elle l’est également si le développement de $x$ est ultimement périodique : on considère
des mots de longueur assez grande incluant la prépériode.

Une conjecture moins forte que celle de la normalité de $\sqrt 2$ peut alors être énoncée comme suit :
la complexité $p(n, \sqrt 2) $ satisfait $p(n,\sqrt 2 )=10^n$ pour tout $n \geq 1$.

Là encore, il s’agit bien d’une conjecture, mais citons néanmoins
le résultat suivant
(voir [4]) qui a permis de faire une avancée récente remarquable sur ce sujet :

Théorème A La complexité $p(n,x)$ de tout nombre algébrique irrationnel $x \in [0,1]$ satisfait \[ \lim _{n \rightarrow + \infty} \frac{p(n,x)}{n} = + \infty. \]

Ce théorème indique donc la complexité d’un nombre algébrique irrationnel ne peut pas être trop faible : pour toute constante $C>0$, il existe un entier $n_0$ à partir duquel $p(x,n) > C\cdot n$ pour tout $n \geq n_0$.
Ce théorème s’applique en particulier à $x=\sqrt 2$. Ce résultat n’est pas propre à la base dix, mais est vrai pour toute base $q$ entière.
Cet énoncé est certes bien plus faible que la normalité conjecturée : on ne fait que compter les mots
et l’on ne prend pas en compte la fréquence avec laquelle ils apparaissent ; de plus, nous sommes également encore loin de la complexité $p(n,x)=10^n$ conjecturée. Nous sommes par exemple bien loin de savoir si la suite des
dates de naissance des reines de France apparaît dans le développement de $x$.
Néanmoins, malgré son apparente simplicité, il s’agit d’un résultat profond, qui repose sur des techniques sophistiquées
d’approximation diophantienne,
et qui a fait l’objet d’une publication dans l’un des journaux les plus cotés
en mathématiques.

Précision requise et théorème de Lochs

Un autre problème naturel consiste à chercher à
comparer les développements décimaux et en fractions continues, en se demandant
quelle est la représentation la plus « compacte ».
Il peut sembler à première vue que la représentation sous forme de fractions continues est plus compacte
que la représentation en base dix. En effet, les quotients partiels peuvent prendre des valeurs arbitrairement grandes.
Une manière de quantifier cette éventuelle différence de comportements consiste à
comparer en moyenne le nombre de chiffres significatifs dont on a besoin dans le développement décimal
pour pouvoir obtenir les premiers quotients partiels. Notons que si deux nombres réels sont suffisamment proches, leurs développements respectifs en fractions continues ont les mêmes premiers
quotients partiels. Fixons maintenant quelques notations. Soit $x \in [0,1]$ un nombre réel, de développement en fraction continue $x=[0 ; a_1,\cdots,a_n, \cdots]$,
et de développement décimal $x = \sum _{i \geq 1} \frac{x_i }{10^i}$. Pour $n \geq 1$, soit $X_n$ la $n$-ième approximation décimale de $x$ :
$X_n = \sum _{i = 1} ^n \frac{x_i }{10^i}$. On définit alors, pour un nombre entier $n$ donné, ${k_n(x)}$ comme le plus grand nombre entier $k$ tel que
les premiers $k$ quotients partiels de $X_n$ sont égaux aux premiers $k$ quotients partiels de $x$.
Le résultat suivant (dû à G. Lochs [5]) décrit le comportement en moyenne (par rapport à $x$) de $k_n(x)/n$
pour presque tout [6] $x \in [0,1]$ :
\[\lim_{n \rightarrow \infty} \frac{k_n(x)}{n}= \frac{ 6 \log 10 \log 2}{\pi ^2} = 0.9702\dots.\]
Ce résultat peut être interprété comme suit : "les $n$ premières décimales déterminent les $n$ premiers
quotients partiels".
En particulier, G. Lochs a montré que les $1000$ premières décimales de $\pi$ donnent les $968$ premiers quotients partiels de
$\pi-3$.

Changements de représentation

On a vu que le développement en fraction continue de $\sqrt 2 $ est égal à
\[1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}}.\]
La complexité attendue du développement décimal de $\sqrt 2$ contraste avec la simplicité
de son développement en fraction continue. On voit, à travers cet exemple, que changer de système de représentation modifie
totalement les propriétés des développements. Il s’agit d’un phénomène que l’on retrouve fréquemment dans ce contexte.
Illustrons-le avec l’exemple suivant.
Travaillons avec la base $2$ pour plus de simplicité.
On se donne une suite infinie $(x_i)_{i \geq 1}$ de chiffres prenant la valeur $0$ ou $1$.
Cette suite peut s’interpréter comme le développement binaire
du nombre réel
\[x= \sum _{i \geq 1} x_i 2^{-i}.\]
La suite $(x_i)_{i \geq 1}$ peut également donner lieu
à une expression formelle [7] \[f(X) =\sum _{i \geq 1} x _i X^{i}.\]
On a alors le très joli résultat suivant qui se trouve être un corollaire du théorème A :

Théorème B Pour tout nombre irrationnel $x \in [0,1]$, de développement binaire $x=\sum_{i\geq 1} x_i2^{-i}$, il est impossible que $x$ et $ f(X)=\sum_{i \geq 1} x_iX^i$ soient l’un et l’autre solution d’une équation polynomiale [8].

Ce théorème signifie que le changement de cadre formel
qui nous fait passer d’une série formelle à un nombre réel détruit l’algébricité. De plus, ce théorème nous permet d’obtenir, dans certains cas, des résultats de transcendance. Rappelons qu’un nombre transcendant est un nombre qui n’est pas algébrique, c’est-à-dire qui n’est pas solution d’une équation polynomiale à coefficients entiers. Comme l’illustre le paragraphe sur la suite
de Prouhet-Thue-Morse, on saura que $x$ est transcendant si on trouve
une équation polynomiale satisfaite par $f(X)$.

Illustration : la suite de Prouhet-Thue-Morse

Illustrons ce résultat avec la suite $(x_n)_{n \in \mathbb{N}}$
égale à la parité de la somme des chiffres du nombre entier $n$ en base $2$ :
\[\mbox{ si } n= \sum_{ k \geq 0 } n_k 2^k, \ n_k \in \{0,1\}, \ x_n = \sum n_k \mbox{ modulo } 2.\]
Cette suite aux propriétés remarquables, appelée suite de Prouhet-Thue-Morse (voir l’article de Wikipédia), a été très largement étudiée. Ses premiers termes sont
\[ 01101001100101101001011001101001 \dots\]
On a \[x_0=0, \ x_{2n}=x_{n} \mbox{ et } x_{2n+1}=1+x_n,\] pour tout nombre entier $n$.

Soit $f(X)=\sum _{i \geq 1} x _i X^{i}=\sum _{i \geq 0} x _i X^{i}$.
Les coefficients de $f(X)$ (appelée série formelle) appartiennent à ${\mathbb F}_2$.
On a alors
les règles de calcul suivantes [9] : $0+0=0,$ $0+1=1,$ $1+1=0$, $0.X=0$, $1.X=X$,
$X^nX^m=X^{n+m}$ (en particulier $a^2=a$ et $(a+b)^2=a^2+(1+1)ab+b^2=a^2+b^2$), et
donc
\[(\sum _{ n\geq 0} u_n X^n)^2=\sum_{n \geq 0} u_{n} X^{2n}.\] On obtient
\[ \begin{array} {ll} f(X)=\sum _{ n\geq 0} x_n X^n &=\sum_{n \geq 0} x_{2n} X^{2n}+\sum_{ n\geq 0} x_{2n+1} X^{2n+1}\\ &=\sum_{n \geq 0} x_{n} X^{2n}+\sum_{ n\geq 0} (1+x_{n}) X^{2n+1}\\ &=(\sum_{n \geq 0} x_{n} X^{n})^2+X(\sum_{ n\geq 0} x_{n} X^{n})^2+ \frac{X}{1+X^2}\\ &=f(X)^2(1+X)+ \frac{X}{1+X^2}. \end{array}\]
On vérifie donc que la série $f(X)$ est algébrique sur $ \mathbb{F}_2(X)$ et est solution de l’équation polynomiale suivante [10]
\[(1+X)^3F(X)^2+F(X)(1+X)^2+X=0,\]
puisque $(1+X)^2=1+X^2$ dans $ \mathbb{F}_2(X)$.
Notons que les coefficients sont des polynômes à coefficients dans $ \mathbb{F}_2$.
On déduit alors du théorème B que le nombre réel $x= \sum _{i \geq 1} x_i 2^{-i}$ est transcendant.

Une esquisse de la preuve du théorème B et suites automatiques

Soit $x \in [0,1]$ un nombre irrationnel. Montrons que si $f(X)$ est algébrique, alors $x$ est transcendant. Il est possible de caractériser la suite des coefficients de séries
formelles algébriques à coefficients dans un corps fini (voir
 [11]). Les séries algébriques sont en effet engendrées très simplement,
par des automates finis (voir l’article de Wikipédia). On montre que ce type de
suite est de faible complexité, où la complexité $p(n)$ compte le nombre des mots longueur $n$ qui apparaissent dans la suite [12]. On conclut alors grâce au théorème A (voir [13]).
Par contraposition, on en déduit que si $x$ est algébrique, alors $f(X)$ ne peut pas être algébrique.
Nous avons donc montré que $x$ et $f(X)$ ne peuvent être simutanément algébriques.

Nous avons donné une formulation de nature algébrique du théorème B.
Ce qui est remarquable, c’est que le théorème B peut également se formuler en termes combinatoires (voir théorème C ci-dessous).

Pour illustrer cette approche combinatoire, considérons la suite de Prouhet-Thue-Morse
(voir l’article de Wikipédia) dont les premiers termes sont
\[ 01101001100101101001011001101001 \dots\]
Remarquons que si on remplace
simultanément chaque « 0 » par « 01 » et chaque « 1 » par « 10 », on obtient
la même suite [14]. On dit que la suite est invariante par substitution.
Elle est même engendrée par cette substitution
que l’on peut itérer à partir de la lettre $0$, produisant une suite infinie de $0$ et de $1$ [15]. Une telle suite est alors dite automatique car on montre qu’elle est engendrée par un automate fini [16]. Le théorème B s’applique
ainsi à une
telle suite :

Théorème C Si la suite des chiffres du développement en base $q$ d’un nombre réel irrationnel est invariante quand on substitue aux lettres des mots de même longueur, alors ce nombre réel est transcendant.

Dès 1968, des résultats similaires ont fait penser aux
mathématiciens qu’un tel théorème devrait exister. Le théorème C a ainsi été conjecturé en 1968 (voir [17]) et
prouvé partiellement en 1988 dans [18]. Mais la preuve de
ce théorème s’est avérée difficile et a demandé... 39 ans pour être complétée.

Cet énoncé est bien dans l’esprit des résultats de normalité précédemment décrits. Le fait que la suite des chiffres présente une trop grande régularité
(ici, elle est engendrée par un procédé élémentaire, une substitution, un automate fini) implique la transcendance (on ne peut plus être solution d’une équation algébrique comme l’est $\sqrt 2$). Le nombre réel $x$ de développement binaire
\[x= 0,01101001100101101001011001101001 \dots\]
est ainsi transcendant.

Nous sommes donc revenus à nos interrogations de départ concernant la normalité conjecturée des algébriques irrationnels.
Que peut-on espérer comme améliorations concernant les théorèmes A, B et C ?
Une amélioration déjà significative serait
de pouvoir montrer qu’un nombre irrationnel dont la suite des chiffres
décimaux contient un nombre quadratique de mots et est de plus engendrée par une substitution [19]
est transcendant. Une conjecture « ultime » serait de pouvoir montrer la transcendance de tout nombre réel irrationnel dont le développement décimal admet une complexité $p(n,x)$ qui satisfait $p(n,x) < 10^n$ pour tout $n$ [20].
Nous sommes encore bien loin d’un tel résultat puisque l’on ne sait même pas si, pour tout nombre réel algébrique irrationnel,
les $10$ chiffres $0,1, \cdots,9$ apparaissent dans son développement décimal (même si une réponse positive à cette question est conjecturée)
 [21] !

Post-scriptum :

Un très grand merci à J. Buzzi pour ses nombreuses remarques et ses ajouts dont la pertinence a grandement aidé à améliorer la lisibilité de ce texte, ainsi qu’à François Gramain, Jérôme Poineau, Massy Soedirman, Samia Rémondière et Alban Carretero pour leur relecture attentive et leurs suggestions variées.

Article édité par Jérôme Buzzi

Notes

[1La constante $e$ (voir l’article de Wikipédia) joue un rôle presque aussi important que $\pi$ pour les mathématiciens. Il s’agit de la base des logarithmes naturels.

[2On peut toujours se ramener à l’intervalle $[0,1]$ en multipliant le réel $x$ que l’on souhaite développer, par une puissance adéquate $(1/q)^k$ de $1/q$, de telle sorte que $q^{-k} x \in [0,1[$ avec $k$ nombre entier.

[3Un développement
en base $q$ dont les chiffres sont ultimement égaux à $q-1$ est dit impropre.

[4B. Adamczewski, Y. Bugeaud, On the complexity of algebraic numbers I. Expansion
in integer bases,
Annals of Math. 165 (2007), 547—565.

[5G. Lochs, Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch, Abh. Math. Sem. Univ. Hamburg
27 (1964), 142—144.

[6Presque tout signifie que l’ensemble des nombres réels de $[0,1]$ qui satisfont cette propriété est un ensemble de mesure $1$ pour la mesure de Lebesgue.

[7Il s’agit d’une série
formelle de Laurent à coefficients dans le corps à deux éléments $\mathbb{F}_2(=\mathbb{Z}/2\mathbb{Z})$ : ce type d’expression formelle ne prend pas en compte les problèmes usuels de convergence des séries de nombres réels (comme les séries qui sont décrites par exemple dans
l’article de Jean-Paul Allouche Sommes de séries de nombres réels).

[8dont les coefficients pour l’équation satisfaite par $f(X)$ sont eux-mêmes des polynômes à coefficients dans $\mathbb{F}_2$, alors que pour l’équation satisfaite par $x$, ce sont des nombres entiers.

[9On utilise ici le fait que la caractéristique est $2$.

[10On remplace $f$ par $F$ dans l’équation suivante.

[11G. Christol, T. Kamae, M. Mendès France, and G. Rauzy, Suites algébriques,
automates et substitutions
, Bull. Soc. Math. France 108 (1980), 401—419.

[12La complexité $p(n)$ d’une suite automatique est d’ordre de croissance linéaire ; il existe une constante $C$ telle que $p(n) \leq C\cdot n$ pour tout $n $.

[13B. Adamczewski, Y. Bugeaud, On the complexity of algebraic numbers I. Expansion
in integer bases, Annals of Math. 165 (2007), 547—565.

[14En effet, si
$x_{n}=0$, alors $x_{2n}x_{2n+1}=01$, et si $x_{n}=1$, alors $x_{2n}x_{2n+1}=10.$

[15Comme les images des lettres $0$ et $1$ par cette substitution sont de même longueur, elle est aussi dite engendrée par une substitution de longueur constante.

[16On montre qu’une suite est automatique si et seulement si elle est engendrée par une substitution de longueur constante (quitte à travailler sur un alphabet
plus grand puis à projeter sur l’alphabet de départ).

[17A. Cobham, On the Hartmanis-Stearns problem for a class of tag
machines, IEEE Conference Record of 1968 Ninth Annual Symposium on
Switching and Automata Theory (1968), 51—60.

[18J. H. Loxton, A. J. van der Poorten,
Arithmetic properties of automata : regular sequences. J. Reine Angew. Math.
392 (1988), 57—69.

[19qui n’est pas forcément de longueur constante

[20rappelons que $p(n,x)$ compte le nombre des mots de longueur $n$ qui apparaissent dans le développement décimal de $x$

[21Bien sûr, si l’on oublie l’hypothèse d’irrationalité, l’exemple de $1/11$ nous montre
que l’on peut avoir un développement décimal dans lequel on a des chiffres qui manquent
(seuls les chiffres $0$ et $9$ apparaissent).

Partager cet article

Pour citer cet article :

Valérie Berthé — «Nombres et représentations » — Images des Mathématiques, CNRS, 2011

Commentaire sur l'article

  • Nombres et représentations

    le 8 août 2011 à 18:37, par a.leblanc

    Merci pour ce panorama sur les développements en
    fractions continues et les représentations des nombres.
    Je me permets de signaler
    qu’un nombre rationnel n’est rien d’autre qu’une fraction. Une approximation rationnelle est donc une approximation
    d’un nombre réel par une fraction. A propos de racine de
    2, on peut ajouter que ce nombre n’est pas rationnel. L’exposition de démonstrations de ce fait (qui à ma connaissance n’utilise
    pas les fractions continues) fait l’objet d’un petit opus, intitulé Rationnel mon Q, dont il a déjà été question ici. C’est l’été et une bonne lecture de vacances.

    Répondre à ce message
  • Comment obtenir les chiffres ?

    le 22 novembre 2011 à 13:26, par Marc JAMBON

    Je lis

    « L’une des premières questions qui se pose concernant ces systèmes de représentation est de savoir comment l’on obtient les chiffres. Il existe pour chacun de ces deux types de développement des procédés algorithmiques simples de production des chiffres. Ces procédés reposent sur l’usage des parties entières et fractionnaires, ainsi que des opérations arithmétiques élémentaires. »

    Tel que vous l’énoncez, c’est acceptable dans un certain sens, mais le seul ennui, c’est que je ne connais aucun procédé algorithmique donnant, pour tout nombre réel, sa partie entière.
    Je peux préciser le problème.
    Soit un nombre réel donné par une suite de Cauchy de nombres rationnels
    n ----> q(n)
    et une autre suite de nombres entiers définie pour p > 0
    p ----> N(p)
    qui garantit que la première suite est bien de Cauchy

    n ≥ N(p) & m ≥ N(p) ==> l q(n) - q(m) l ≤ 1/p

    On suppose que le calcul des deux suites données ne pose aucun problème, par exemple, elles sont primitives récursives.Trouver un algorithme qui, à tout couple de deux telles suites, fasse correspondre la partie entière du nombre réel engendré par la suite de Cauchy (q(n)).
    L’algorithme peut, par exemple, être défini par un programme dans un langage algorithmique de votre choix accepté par un ordinateur, avec deux appels de sous-programme (pour appeler les deux suites données).

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM