Nombre normal

En mathématiques, un nombre normal en base 10 est un nombre réel tel que dans la suite de ses décimales, toute suite finie de décimales consécutives (ou séquence) apparaît avec la même fréquence limite que n'importe laquelle des séquences de même longueur. Par exemple, la séquence 1789 y apparaît avec une fréquence limite 1/10 000. Émile Borel les a ainsi nommés lors de sa démonstration que presque tout réel possède cette propriété.

Définitions

Notons $A=\{0,\dots ,b-1\}$ l'ensemble des chiffres en base $b$, et soit $x$ un nombre réel. Si $s$ est une suite finie d'éléments de $A$, notons $N(s,n)$ le nombre d'apparitions de la suite $s$ parmi les $n$ premiers chiffres après la virgule du développement propre de $x$ en base $b$. Le nombre $x$ est dit :

• simplement normal (ou parfois équiréparti) en base $b$ si$\forall a\in A\quad \lim _{n\to \infty }{\frac {N((a),n)}{n}}={\frac {1}{b}}$ ;
• normal en base $b$ s'il est simplement normal en base $b^{k}$ pour tout entier $k>0$, ce qui équivaut à :$\forall k\geqslant 1\quad \forall s\in A^{k}$$\quad \lim _{n\to \infty }{\frac {N(s,n)}{n}}={\frac {1}{b^{k}}}$ ;
• normal (ou quelquefois absolument normal) s'il est normal dans toute base, ce qui équivaut à : simplement normal dans toute base.

Théorème des nombres normaux

Le concept de nombre normal a été introduit par Émile Borel en 1909. En utilisant le lemme de Borel-Cantelli, il démontre le « théorème des nombres normaux » : presque tous les nombres réels sont absolument normaux, dans le sens où l'ensemble des nombres non absolument normaux est de mesure nulle (pour la mesure de Lebesgue).

Théorème — Dans $\mathbb {R}$, presque tout nombre (au sens de la mesure de Lebesgue) est absolument normal.

Démonstration

En utilisant que toute réunion dénombrable d'ensembles négligeables est négligeable, on se ramène facilement à démontrer que dans une base b fixée, presque tout élément de $\Omega =\left[0,1\right[$ est simplement normal.

Notons alors $A=\{0,\dots ,b-1\}$. Tout élément ω de $\Omega$ possède un unique développement propre en base b : il existe une unique écriture de ω sous la forme :

$\omega =\sum _{n=1}^{\infty }{\frac {\varepsilon _{n}(\omega )}{b^{n}}}$

telle que, pour tout n, $\varepsilon _{n}(\omega )\in A,$ et tel que la suite $\left(\varepsilon _{n}(\omega )\right)_{n\geq 1}$ ne se termine pas par une suite infinie de chiffres b – 1.

On se donne un chiffre a ∈ A et l'on s'intéresse à la fréquence d'apparition de ce chiffre dans la suite des n premiers chiffres du développement de ω en base b.

On se place sur l'espace probabilisé $\left(\Omega ,{\mathcal {A}},\mathbb {P} \right),$ où ${\mathcal {A}}$ désigne la tribu borélienne de $\Omega$ et où $\mathbb {P}$ est la mesure de Lebesgue restreinte à ${\mathcal {A}}$. Alors, sous $\mathbb {P}$, la famille $\left(\varepsilon _{n}\right)_{n\geqslant 1}$ est une famille de variables aléatoires uniformes sur A et indépendantes, c'est-à-dire que, pour toute partie finie B de ℕ

$\mathbb {P} \left(\forall i\in B\quad \varepsilon _{i}=m_{i}\right)=b^{-{\text{card}}B}.$

Les variables aléatoires

$X_{j}=1_{\varepsilon _{j}=a}$

sont des variables de Bernoulli indépendantes de paramètre 1/b et, en vertu de la loi forte des grands nombres, la fréquence d'apparition de a dans la suite des n premiers chiffres du développement de ω :

$F_{a}(n,\omega )={\frac {X_{1}(\omega )+...+X_{n}(\omega )}{n}}$

vérifie :

$F_{a}(n){\underset {p.s.}{\longrightarrow }}E[X_{1}]={\frac {1}{b}}.$

On conclut en utilisant qu'une réunion de b ensembles négligeables — correspondant chacun à un chiffre a — est négligeable.

Propriétés et exemples

• Un nombre rationnel (donc de développement périodique en toute base) est simplement normal en base $b$ si et seulement si la longueur $p$ de sa période dans cette base est un multiple de $b$ et chaque chiffre de 0 à $b-1$ apparaît $p/b$ fois dans cette période. Il n'est donc jamais normal en base $b$. Par exemple, le rationnel ${\frac {137174210}{1111111111}}$, dont le développement décimal s'écrit $0,12345678901234567890...$ , est simplement normal en base dix mais pas en base cent.

• Un nombre $x$ est normal en base $b$ si et seulement si la suite $\left(b^{k}x\right)_{k}$ est équidistribuée modulo 1, ce qui, d'après le critère de Weyl, équivaut à :

$\lim {\frac {1}{n}}\sum _{k=0}^{n-1}\mathrm {e} ^{2\pi \mathrm {i} mb^{k}x}=0$ pour tout entier $m\geqslant 1$.

• Le produit d'un nombre normal en base $b$ par un rationnel non nul est normal en base $b$ .

• L'ensemble des nombres simplement normaux en base $b$ est maigre. A fortiori, l'ensemble des nombres normaux en base $b$ est maigre (alors que le sur-ensemble des nombres univers en base $b$ est comaigre).

• Le nombre de Champernowne $0{,}123\,456\,789\,10\,11\,12\,13\,14\,15\,16\,17\cdots$, dont le développement décimal est formé par la concaténation de tous les nombres naturels, est normal en base dix, de même que celui de Copeland-Erdős $0{,}2357\,11\,13\,17\,19\,23\,29\,31\,37\,41\cdots$, obtenu en concaténant les nombres premiers, mais il n'est pas démontré qu'ils le soient dans d'autres bases.

• Un nombre peut en effet être normal dans une base mais pas dans une autre ; par exemple

$\alpha =\sum _{m=1}^{\infty }{\frac {1}{3^{m}2^{3^{m}}}}$

est normal en base 2 mais pas en base 6. Plus généralement, pour deux bases $b$ et $c$ dans $\{2,3,4,...\}$, les nombres normaux sont les mêmes si et seulement si les entiers $b$ et $c$ sont « équivalents » au sens « puissance rationnelle l'un de l'autre », tandis que si deux parties complémentaires $R$ et $S$ de $\{2,3,4,...\}$ sont fermées pour cette relation d'équivalence, alors l'ensemble des nombres qui sont normaux dans toute base de $R$ et anormaux dans toute base de $S$ a la puissance du continu.

En particulier (cas $S=\varnothing$) l'ensemble des nombres normaux a la puissance du continu (ce qui se déduisait déjà du théorème de Borel), de même que (cas $R=\varnothing$) l'ensemble des réels qui ne sont normaux dans aucune base (ce qui se déduisait déjà du fait qu'il est comaigre).

• Le théorème des nombres normaux établit l'existence des nombres normaux, mais n'en construit explicitement aucun. Cependant, Henri Lebesgue et Wacław Sierpiński ont, indépendamment, repris la preuve de Borel et l'ont exprimée sous une « forme constructive » qui permet de définir explicitement un nombre normal, mais peut-être non calculable. Il existe beaucoup de nombres normaux non calculables (par exemple tous les réels au développement numérique aléatoire, comme la constante de Chaitin Ω), mais il existe aussi des nombres normaux calculables.

• Il est extrêmement difficile de démontrer la normalité de nombres pourtant simples. Par exemple, on ne sait pas si √2, π, ln(2) ou e sont normaux (mais des expériences numériques font conjecturer qu'ils le sont). On ne sait même pas démontrer qu'un chiffre donné apparaît une infinité de fois dans le développement décimal de ces constantes (une propriété analogue, mais bien plus faible, que celle d’être un nombre univers). Émile Borel a conjecturé en 1950 que tout irrationnel algébrique est normal ; on ne connaît pas de contre-exemple, mais on ne connaît même pas non plus de nombre algébrique qui soit normal dans une base.
• Un algorithme presque linéaire qui génère le développement binaire d'un nombre absolument normal x est donné par Jack H. Lutz et Elvira Mayordomo, le n-ième bit de x étant calculé après n polylog(n) étapes de calcul. Cette vitesse est obtenue en calculant et en diagonalisant simultanément contre une martingale qui incorpore les algorithmes d'analyse de Lempel-Ziv dans toutes les bases.

Nombres normaux et automates finis

Des liens existent entre nombres normaux et automates finis. Ainsi, on a

Théorème — Un nombre réel est normal dans une certaine base entière si et seulement si son développement dans cette base est incompressible par un automate de compression sans perte.

Dans ce contexte, un automate de compression sans perte est un automate déterministe avec sorties (donc un transducteur fonctionnel) injectif.

Un corollaire du théorème est un théorème dû à V. N. Agafonov et datant de 1968 sur la préservation de la normalité de sous-suites sélectionnées par un automate fini :

Théorème d'Agafonov — Soit l'alphabet binaire. Une suite infinie sur $A$ est normale sur $A$ si et seulement si tout sous-suite sélectionnée par un automate fini est elle-même normale sur $A$.

Ce théorème, dont la démonstration originale est en russe, a été redémontré par Mary G. O’Connor, puis généralisé à des alphabets arbitraires par Broglio et Liardet.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Normal number » (voir la liste des auteurs).

Bibliographie

• (en) L. Kuipers et H. Niederreiter, Uniform Distribution of Sequences, Dover, 2012 (1^re éd. 1974) (lire en ligne),  Chapitre 1, § 8: « Normal numbers », p. 69-77
• (en) Ivan Niven, Irrational Numbers, MAA, coll. « The Carus Mathematical Monographs » (n^o 11), 1956 (lire en ligne),  Chapitre 8: « Normal numbers », p. 94-116
• (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers (1^re éd. 1938) [détail des éditions], § 9.12 et 9.13