Nombre normal

Modèle:Voir homonyme

En mathématiques, un nombre normal en base dix 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, ou encore plage) apparaît avec la même fréquence limite que n'importe laquelle des séquences de même longueur^[1]. 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 $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^[2]) en base $b$ si $\forall a \in A \lim_{n \to \infty} \frac{N ((a), n)}{n} = \frac{1}{b}$ ^[1]Modèle:,^[3] ;
normal en base $b$ s'il est simplement normal en base $b^{k}$ pour tout entier $k > 0$ ^[4], ce qui équivaut à : $\forall k ⩾ 1 \forall s \in A^{k}$ ^[5] $\lim_{n \to \infty} \frac{N (s, n)}{n} = \frac{1}{b^{k}}$ ^[6] ;
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^[7]. 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:Théorème

Modèle:Démonstration

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^[2]. 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^[2] mais pas en base cent.

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

\lim \frac{1}{n} \sum_{k = 0}^{n - 1} e^{2 π i m b^{k} x} = 0

pour tout entier

m ⩾ 1

.

Le produit d'un nombre normal en base $b$ par un rationnel non nul est normal en base $b$ ^[9].

L'ensemble des nombres simplement normaux en base $b$ est maigre^[10]. 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 \dots$ , dont le développement décimal est formé par la concaténation de tous les nombres naturels, est normal en base dix^[11], de même que celui de Copeland-Erdős $0, 2357 11 13 17 19 23 29 31 37 41 \dots$ , obtenu en concaténant les nombres premiers^[12], 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

α = \sum_{m = 1}^{\infty} \frac{1}{3^{m} 2^{3^{m}}}

est normal en base 2^[13] mais pas en base 6^[14]. 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 »^[15], 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^[16].

En particulier (cas

S = \emptyset

) 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 = \emptyset

) 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^[17] 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^[1]. 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^[18].

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^[19]Modèle:,^[20]). 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^[21] 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^[22], 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

Modèle:Théorème

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^[23], puis généralisé en 1992 à des alphabets arbitraires^[24]Modèle:,^[25].

Voir aussi

Nombre univers (possédant la propriété plus faible que toute séquence apparait dans la suite des décimales, sans imposer l'équipartition).

Notes et références

Modèle:Traduction/Référence Modèle:Références

Bibliographie

Modèle:Palette

Modèle:Portail

↑ ^1,0 ^1,1 et ^1,2 Modèle:Article.
↑ ^2,0 ^2,1 et ^2,2 Modèle:Ouvrage (présenté seulement pour la base dix).
↑ Modèle:Article (Modèle:P.).
↑ Modèle:Harvsp (repris dans Modèle:Harvsp) exigeait de plus que bx, bModèle:2x, bModèle:3xModèle:Etc. soient simplement normaux en base bModèle:Exp (on peut évidemment arrêter le « etc. » à bModèle:Expx), 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).
↑ [[Produit cartésien#n-uplets|AModèle:Exp]] est l'ensemble des suites de longueur k d'éléments de A.
↑ 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).
↑ Modèle:Harvsp.
↑ Modèle:Harvsp, th. 8.15.
↑ Modèle:Ouvrage.
↑ Le résultat de Modèle:Lien (1966), plus précis, est énoncé Modèle:P. de Modèle:Chapitre.
↑ 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.
↑ Modèle:Article ; cet article démontre que ce résultat est vrai pour toute suite d'entiers suffisamment dense.
↑ Modèle:Article.
↑ Modèle:Lien web.
↑ Modèle:Article.
↑ Modèle:Article.
↑ 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.
↑ Modèle:En 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..
↑ Modèle:Article.
↑ Modèle:Ouvrage
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Article.
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BecherHeiber2013

[Delahaye-1] 1,0 ^1,1 et ^1,2 Modèle:Article.

[L1-2] 2,0 ^2,1 et ^2,2 Modèle:Ouvrage (présenté seulement pour la base dix).

[3] Modèle:Article (Modèle:P.).

[4] Modèle:Harvsp (repris dans Modèle:Harvsp) exigeait de plus que bx, bModèle:2x, bModèle:3xModèle:Etc. soient simplement normaux en base bModèle:Exp (on peut évidemment arrêter le « etc. » à bModèle:Expx), 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).

[5] [[Produit cartésien#n-uplets|AModèle:Exp]] est l'ensemble des suites de longueur k d'éléments de A.

[6] 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).

[7] Modèle:Harvsp.

[8] Modèle:Harvsp, th. 8.15.

[9] Modèle:Ouvrage.

[10] Le résultat de Modèle:Lien (1966), plus précis, est énoncé Modèle:P. de Modèle:Chapitre.

[11] 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.

[12] Modèle:Article ; cet article démontre que ce résultat est vrai pour toute suite d'entiers suffisamment dense.

[13] Modèle:Article.

[14] Modèle:Lien web.

[15] Modèle:Article.

[16] Modèle:Article.

[17] 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.

[18] Modèle:En 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..

[19] Modèle:Article.

[:2-20] Modèle:Ouvrage

[21] Modèle:Article.

[22] Modèle:Article.

[23] Modèle:Article.

[24] Modèle:Article.

[BecherHeiber2013-25] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BecherHeiber2013

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Nombre normal

Sommaire

Définitions

Théorème des nombres normaux

Propriétés et exemples

Nombres normaux et automates finis

Voir aussi

Notes et références

Bibliographie

Menu de navigation

Nombre normal

Définitions

Théorème des nombres normaux

Propriétés et exemples

Nombres normaux et automates finis

Voir aussi

Notes et références

Bibliographie

Menu de navigation

Rechercher