You are currently browsing julesjulesjulesjules’s articles.

\displaystyle 1,2,4,8,16,32,64,128,256,512,1024,2056,...

Dans l’enfance, il est une période où l’on a tendance à abuser des questions existentielles sur le monde qui nous entoure; et si cette période rencontre celle où vous avez appris à multiplier par {2}, peut-être en gardez vous des questions aussi tordues que non triviales comme celles que nous allons nous poser dans ce billet.

Autrement, pas de panique, les puissances de {2} constituent une dynamique qui ne manque pas d’applications. La première qui vous vient en tête se trouve dans le monde informatique, car même si vous n’avez aucune idée de ce qui se cache dessous, vous aurez au moins reconnu les nombres qui désignent la capacité de vos diverses clés USB. Et ce n’est que le début, un jour peut être, les ordinateurs quantiques auront une efficacité telle que {N} bits quantiques pourront renvoyer autant d’informations que {2^N} bits classiques ({2^{300}} c’est déja plus que le nombre de particules de l’univers…).

Bref, tout cela pour vous rassurer quant à l’utilité des questions d’apparence bizarres que peut poser la suite des {2^N}, que cela soit dans le but de soulager une question de votre enfance ou pour servir un besoin scientifique.

Je peux ainsi m’empresser de poser l’une d’entre elle qui constitue un bon alibi pour observer les résultats que peut fournir la dynamique ergodique:

A quelle fréquence apparaît le chiffre 7 en première position du nombre {2^N}?

Plus précisément, on regarde les premiers termes de la suite des premiers chiffres de {(2^n)_{n\in \mathbb{N}}}:

\displaystyle 1,2,4,8,1,3,6,1,2,5,1,2...

Pas l’ombre d’un {7}… Mais il finira bien par arriver, on me souffle que {2^{46}} commence par un {7}. Sa fréquence d’apparition semble bien inférieure à celle de {1} déjà présent à répétition dans les premiers termes écrits plus haut. Traduisons mathématiquement la question qu’on se pose…

{7} a été choisi pour la commodité de la lecture, mais on pourra obtenir une comparaison, en fonction du chiffre choisi pour l’expérience, qui sera intéressante. Ainsi, choisissons {a\in \{1,2,3,4,5,6,7,8,9 \}}, et cherchons à quelle fréquence il apparaît comme premier chiffre de {2^N}.

Soit {n\in \mathbb{N}} tel que {2^n} commence par {a}. Autrement dit, il existe un entier {k} et un nombre {b} tels que:

\displaystyle 2^n = a... = a10^k+b

avec la particularité que {b<10^k}. Ou encore:

\displaystyle a10^k \le 2^n < (a+1)10^k.

En passant cette encadrement au logarithme décimal, il devient:

\displaystyle k+ \log_{10}(a) \le n\log_{10}(2) < k+\log_{10}(a+1).

En remarquant que {\log_{10}(a)\in [0,1]} et qu’ainsi {k} est la partie entière de {n\log_{10}(2)}, il nous reste à étudier la partie fractionnaire de {n\log_{10}(2)} que l’on note {\{ n\log_{10}(2) \}} ({\{ x \} = x-E(x)}{E(x)} désigne la partie entière de {x}).
En passant l’encadrement aux parties fractionnaires, on obtient: {\{ n\log_{10}(2) \} \in [\log_{10}(a),\log_{10}(a+1)]} qui traduit exactement la condition « {a} est le premier chiffre de {2^n}« .

Il ne nous reste qu’à compter. Notons « {Prem(x)} » la fonction qui renvoie le premier chiffre de l’entier {x}. On s’interesse à la fréquence {F_a} d’apparition de {a} en première position des puissances successives de {2}. Autrement dit:

\displaystyle F_a = \lim_{n\rightarrow \infty} \frac{1}{n} \# \{ k\in [1,n], Prem(2^k) = a \}

ce que l’on peut réécrire, grâce à la traduction de la condition vue ci-dessus:

\displaystyle F_a = \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{k=1}^{n} \mathbf{1}_{[\log_{10}(a),\log_{10}(a+1)]}(\{ k\log_{10}(2) \}).

{\mathbf{1}} désigne la fonction indicatrice.
Il nous faut ainsi réussir à calculer la moyenne de l’évaluation de cette indicatrice après chaque itération de {\log_{10}(2)}. C’est ce que nous allons reconnaître comme une somme de Birkhoff, l’objet phare de la théorie ergodique, statut qui se manifeste ici.

Énonçons alors les résultats de théorie ergodique qui vont nous servir à calculer la limite de cette somme.

Pour arriver aux systèmes dynamiques uniquement ergodiques.

Un système dynamique mesuré consiste en la donnée de {(X,\mathcal{B},\mu,T)}{X} est un ensemble, {\mathcal{B}} est une tribu sur {X}, {\mu} une mesure borelienne, et {T:X\rightarrow X} est une fonction mesurable qui est telle que {T_{*}\mu=\mu}. Autrement dit, pour tout borélien {B\in \mathcal{B}}, {\mu(T^{-1}B)=\mu(B)}.
Dans la suite on supposera que {X} est un espace topologique compact et que {\mu} est finie, ce qui constitue le cadre adéquat à notre problème.
{T} est ainsi la transformation qu’il nous intéresse d’itérer, c’est notre dynamique à temps discret. Soit {f\in L_1(X,\mu)} une fonction. En théorie ergodique, on s’intéresse aux sommes de Birkhoff:

\displaystyle S_N f = \frac{1}{N}\sum_{n=0}^{N-1}f\circ T^n

et plus particulièrement à leur comportement limite. Il s’agit de la moyenne des valeurs prises par {f} après chaque itération. Évidemment en prenant {\mathbf{1}_{[\log_{10}(a),\log_{10}(a+1)]}} comme fonction à évaluer, on retrouve la somme de Birkhoff qui est notre fil conducteur.
Le théorème de Birkhoff stipule que pour un système dynamique mesuré, ces moyennes convergent pour {\mu}-presque tout {x\in X} vers une fonction notée {f_{*}} qui vérifie entre autre:

\displaystyle f_{*}\circ T = f_{*}.

Certains systèmes sont particulièrement intéressants, il s’agit des systèmes dynamiques ergodiques. Ils vérifient la propriété suivante qui peut être prise comme définition: Pour toute fonction mesurable {f:X\rightarrow \mathbb{R}}, si {f\circ T = f} alors {f} est constante {\mu}-presque partout.
Dans le cadre de ces systèmes, le théorème de Birkhoff se manifeste de façon plus pratique…

Théorème (Ergodique). Si {(X,\mathcal{B},\mu,T)} est ergodique, alors {f_{*}(x) = \lim_{N\rightarrow \infty} S_N f} est constante presque partout, et vaut {\frac{1}{\mu(X)}\int f d\mu}. (Si {\mu} n’était pas finie, {f_{*}} serait nulle).

Lorsque {X} est compact, il existe toujours une mesure invariante et ergodique pour {T}.
Si de plus il n’y a qu’une seule mesure invariante pour {T}, elle est a fortiori ergodique et on dit alors que le système est uniquement ergodique. La convergence des sommes de Birkhoff n’en est que plus gentille:

Proposition (Unique ergodicité). {(X,\mathcal{B},\mu,T)} est uniquement ergodique si, et seulement si, pour toute fonction {f\in C(X,\mathbb{R})}, les sommes de Birkhoff {S_N f} convergent uniformément vers une constante.

Les rotations irrationnelles sur le cercle sont des systèmes dynamiques uniquement ergodiques.

On va s’intéresser aux fameuses rotations irrationnelles déjà beaucoup traitées sur ce blog… Ceci car notre problème fait intervenir l’itération de {\log_{10}(2)}, ce que l’on peut voir comme des rotations successives d’un angle {\log_{10}(2)}, irrationnel.
{\mathbb{T}} désigne le cercle, qu’on verra ici comme le quotient: {\mathbb{R}/\mathbb{Z}}. Soit {\alpha \in [0,1]} un irrationnel. On note {T_{\alpha}} la rotation correspondante:

\displaystyle T_{\alpha}: \left \{ \begin{array}{ccc} \mathbb{T} & \rightarrow & \mathbb{T}\\ x & \mapsto & x+\alpha \ mod \ 1 \end{array} \right.

Comme vous n’avez sûrement pas pu le rater en parcourant les articles de ce blog, la propriété primordiale de ce système (et qui change du cas rationnel) est que ses orbites sont denses dans le cercle. Autrement dit, pour tout {x\in \mathbb{T}}, {\{ T_{\alpha}^n (x), n\in \mathbb{N}\}} est dense dans {\mathbb{T}}, donc s’approche aussi près qu’on le souhaite de chaque point du cercle..
La mesure de Lebesgue, stable par translation, est donc invariante pour {T_{\alpha}} et ce quelque soit {\alpha}.
Supposons qu’il existe une mesure {\nu} invariante pour {T}. Alors, pour tout {n\in \mathbb{N}}:

\displaystyle T_{\alpha *}^n \nu = T_{n\alpha *} \nu = \nu

Ceci en utilisant qu’itérer {n} fois revient a translater de {n\alpha}, et la conservation de la mesure par {T}.
Ainsi, par densité de {\{ n\alpha = T_{\alpha}^n (0), n\in \mathbb{Z} \}} dans {\mathbb{T}}, on a pour tout {\beta \in [0,1]}:

\displaystyle T_{\beta*} \nu = \nu

Ceci en prenant la limite de {T_{n_i \alpha *}} pour une suite extraite de {n_i \alpha} qui tend vers {\beta}, et obtenue par densité de l’orbite.

On reconnaît alors que {\nu} est la mesure de Lebesgue, seule mesure invariante par toute translation.

On a obtenu qu’une rotation irrationnelle du cercle constitue un système uniquement ergodique.

Quant à l’occurrence de {7} comme premier chiffre dans les puissances successives de {2}.

L’apport de la théorie ergodique repose sur le fait que {\{ k\log_{10}(2) \}} peut-être vue comme le {k}-ième itéré de la rotation d’angle { \log_{10}(2) }, soit:

\displaystyle F_a = \lim_{n\rightarrow \infty} \frac{1}{n} \sum_{k=1}^{n} \mathbf{1}_{[\log_{10}(a),\log_{10}(a+1)]}(T_{\log_{10}(2)}^k(0)).

Et (ici se trouve un point clé) on reconnaît une somme de Birkhoff pour la fonction {\mathbf{1}_{[\log_{10}(a),\log_{10}(a+1)]}}.
De plus, comme un cadeau, il nous vient que { \log_{10}(2) } est irrationnel (la question n’était, il est vrai, pas choisie au hasard…), on a une rotation irrationnelle qui est uniquement ergodique, d’après les deux paragraphes précédents. Ainsi cette somme de Birkhoff converge uniformément vers l’intégrale donnée par le Théorème ergodique vu plus haut:

\displaystyle F_a = \int_{\mathbb{T}} \mathbf{1}_{[\log_{10}(a),\log_{10}(a+1)]} d\mu = \log_{10}(1+\frac{1}{a})

La fréquence d’apparition de {a} comme premier chiffre dans les puissances successives de {2} est {\log_{10}(1+\frac{1}{a})}.

Comme promis, la conclusion peut paraître loufoque, car en regardant de loin, aucune raison apparente nous indique qu’un chiffre apparaîtra en première position plus souvent qu’un autre. Malgré aucun indicateur sur la définition de cette suite d’une brisure de cette symétrie, elle n’est pas du tout vérifiée.
Ce n’est qu’un exemple des propriétés purement numériques que l’on observe, à moindre coût, grâce à la théorie ergodique.

Dans la même veine, et en traduisant le problème exactement comme on vient de le faire, on trouve la même absence de symétrie, en comparant les nombres {2^n} qui commencent par {123456789} et ceux qui commencent par {987654321}. En effet, le début {123456789} apparaît plus fréquemment que {987654321}. Je vous laisse le soin de multiplier par {2} jusqu’à vous en convaincre (ou jusqu’à ne plus en pouvoir et décider de faire aveuglément confiance à la théorie ergodique).
Ainsi, avec comme seule hypothèse importante que {\log_{10}(2)} est irrationnel, on peut appliquer des théorèmes aussi puissant que ceux de la théorie ergodique à des questions sur les puissances de {2}, et obtenir des résultats pas évidents avant un grand nombre d’itérations… nombre inatteignable pour quelqu’un d’autre qu’un ordinateur quantique, à cause de la vitesse de croissance d’une telle suite.

Publicités