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<ref name="Delahaye">Modèle:Article.</ref>. 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 du fait que presque tout réel possède cette propriété.

Définitions

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

• simplement normal (ou parfois équiréparti<ref name="L1">Modèle:Ouvrage (présenté seulement pour la base dix).</ref>) en base <math>b</math> si<math>\forall a\in A\quad\lim_{n\to\infty}\frac{N((a),n)}n=\frac1b</math><ref name=Delahaye/><ref>Modèle:Article (Modèle:P.).</ref> ;
• normal en base <math>b</math> s'il est simplement normal en base <math>b^k</math> pour tout entier <math>k > 0</math><ref>Modèle:Harvsp (repris dans Modèle:Harvsp) exigeait de plus que bx, b²x, bModèle:3xModèle:Etc. soient simplement normaux en base b^k (on peut évidemment arrêter le « etc. » à b^k–1x), mais cette condition était redondante, comme l'a démontré Modèle:Article, pour répondre à une objection d'un reviewer sur sa preuve simple du théorème de Champernowne. Cette preuve venait démentir le commentaire de Hardy et Wright sur ce théorème : Modèle:Citation étrangère (dernière phrase du chap. 9).</ref>, ce qui équivaut à :<math>\forall k\geqslant 1\quad\forall s\in A^k</math><ref>A^k est l'ensemble des suites de longueur k d'éléments de A.</ref><math>\quad\lim_{n\to\infty}\frac{N(s,n)}n=\frac1{b^k}</math><ref>C'est cette définition, désormais classique, qui est choisie par Modèle:Harvsp et reprise par Modèle:Ouvrage. Modèle:Harvsp, démontre en effet qu'elle s'intercale dans l'implication démontrée par Pillai entre sa définition allégée et celle de Borel (cf. note précédente).</ref> ;
• 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<ref>Modèle:Harvsp.</ref>. 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).

Modèle:Démonstration</math>

telle que, pour tout n, <math>\varepsilon_n(\omega)\in A,</math> et tel que la suite <math>\left(\varepsilon_n(\omega)\right)_{n\ge 1}</math> 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é <math>\left(\Omega,\mathcal A,\mathbb P\right),</math> où <math>\mathcal A</math> désigne la tribu borélienne de <math>\Omega</math> et où <math>\mathbb P</math> est la mesure de Lebesgue restreinte à <math>\mathcal A</math>. Alors, sous <math>\mathbb P</math>, la famille <math>\left(\varepsilon_n\right)_{n\geqslant 1}</math> est une famille de variables aléatoires uniformes sur A et indépendantes, c'est-à-dire que, pour toute partie finie B de ℕ

<math>\mathbb P\left(\forall i\in B\quad\varepsilon_i=m_i\right)=b^{-\text{card}B}.</math>

Les variables aléatoires

<math>X_j=1_{\varepsilon_j=a}</math>

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 ω :

<math>F_a(n,\omega)=\frac{X_1(\omega)+...+X_n(\omega)}n</math>

vérifie :

<math>F_a(n)\underset{p.s.}{\longrightarrow}E[X_1]=\frac1b.</math>

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 <math>b</math> si et seulement si la longueur <math>p</math> de sa période dans cette base est un multiple de <math>b</math> et chaque chiffre de 0 à <math>b-1</math> apparaît <math>p/b</math> fois dans cette période<ref name="L1" />. Il n'est donc jamais normal en base <math>b</math>. Par exemple, le rationnel <math>\frac{137174210}{1111111111}</math>, dont le développement décimal s'écrit <math>0,12345678901234567890...</math>, est simplement normal en base dix<ref name="L1" /> mais pas en base cent.

• Un nombre <math>x</math> est normal en base <math>b</math> si et seulement si la suite <math>\left(b^kx\right)_k</math> est équidistribuée modulo 1<ref>Modèle:Harvsp, th. 8.15.</ref>, ce qui, d'après le critère de Weyl, équivaut à :

<math>\lim\frac1n\sum_{k=0}^{n-1}\mathrm e^{2\pi\mathrm imb^kx}=0</math> pour tout entier <math>m\geqslant 1</math>.

• Le produit d'un nombre normal en base <math>b</math> par un rationnel non nul est normal en base <math>b</math> <ref>Modèle:Ouvrage.</ref>.

• L'ensemble des nombres simplement normaux en base <math>b</math> est maigre<ref>Le résultat de Modèle:Lien (1966), plus précis, est énoncé Modèle:P. de Modèle:Chapitre.</ref>. A fortiori, l'ensemble des nombres normaux en base <math>b</math> est maigre (alors que le sur-ensemble des nombres univers en base <math>b</math> est comaigre).

• Le nombre de Champernowne <math>0{,}123\, 456\, 789\, 10\,11\,12\,13\,14\,15\,16\,17\cdots</math>, dont le développement décimal est formé par la concaténation de tous les nombres naturels, est normal en base dix<ref>Modèle:Harvsp ; Modèle:Harvsp ; plus généralement, si f est un polynôme qui envoie tout entier > 0 sur un entier > 0, alors le réel formé (en base dix par exemple) en concaténant les entiers f(1), f(2), … est normal dans cette base : Modèle:Article.</ref>, de même que celui de Copeland-Erdős <math>0{,}2357\, 11\, 13\, 17\, 19\, 23\, 29\, 31\, 37\, 41\cdots</math>, obtenu en concaténant les nombres premiers<ref>Modèle:Article ; cet article démontre que ce résultat est vrai pour toute suite d'entiers suffisamment dense.</ref>, 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

<math>\alpha=\sum_{m=1}^{\infty}{\frac1{3^m2^{3^m}}}</math>

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

En particulier (cas <math>S=\varnothing</math>) 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 <math>R=\varnothing</math>) 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<ref>W. Sierpiński, « Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective d'un tel nombre », Bull. Soc. Math. France, Modèle:Abrd 45, 1917, Modèle:P. Modèle:Lire en ligne ;
  H. Lebesgue, « Sur certaines démonstrations d'existence », même vol. (mais écrit en 1909), Modèle:P. Modèle:Lire en ligne.</ref> ont, indépendamment, repris la démonstration de Borel et l'ont exprimée sous une Modèle:Citation qui permet de définir explicitement un nombre normal, mais peut-être non calculable<ref name="Delahaye" />. 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<ref>{{#invoke:Langue|indicationDeLangue}} Verónica Becher et Santiago Figueira, « An example of a computable absolutely normal number », Theoret. Comput. Sci., Modèle:Abrd 270, 2002, Modèle:P..</ref>.

• Il est extrêmement difficile de démontrer la normalité de nombres pourtant simples. Par exemple, on ne sait pas si [[Racine carrée de deux|Modèle:Racine]], [[Pi|Modèle:Math]], Modèle:Math ou [[e (nombre)|Modèle:Math]] sont normaux (mais des expériences numériques font conjecturer qu'ils le sont<ref>Modèle:Article.</ref>). 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<ref>Modèle:Article.</ref> 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<ref>Modèle:Article.</ref>, 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

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

Un corollaire est le théorème suivant, dû à V. N. Agafonov et datant de 1968 : Modèle:Théorème

Ce théorème a été redémontré indépendamment vingt ans plus tard<ref>Modèle:Article.</ref>, puis généralisé en 1992 à des alphabets arbitraires<ref>Modèle:Article.</ref><ref name="BecherHeiber2013"/>.

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:HardyWright, § 9.12 et 9.13