Worldlex Wiki En mathématiques , un nombre réel est dit simplement normal en base b si sa suite infinie de chiffres est uniformément distribuée , au sens où chacune des b valeurs de chiffres a la même densité naturelle 1/ b . Un nombre est dit normal en base b si, pour tout entier positif n , toutes les suites possibles de n chiffres ont une densité b − n .
Intuitivement, un nombre simplement normal signifie qu'aucun chiffre n'apparaît plus fréquemment qu'un autre. Si un nombre est normal, aucune combinaison finie de chiffres d'une longueur donnée n'apparaît plus fréquemment qu'une autre combinaison de même longueur. On peut se représenter un nombre normal comme une suite infinie de lancers de pièce ( binaire ) ou de jets de dé ( base 6 ). Bien qu'il existe des suites telles que 10, 100 ou plus de faces consécutives (binaire) ou de 5 (base 6), ou encore 10, 100 ou plus de répétitions d'une suite comme face-pile (deux lancers de pièce consécutifs) ou 6-1 (deux jets de dé consécutifs), il existera également un nombre égal de toute autre suite de même longueur. Aucun chiffre ni aucune suite n'est « favorisé ».
Un nombre est dit normal (parfois appelé absolument normal ) s'il est normal dans toutes les bases entières supérieures ou égales à 2.
Bien qu'il soit possible de démontrer de manière générale que presque tous les nombres réels sont normaux (c'est-à-dire que l' ensemble des nombres non normaux a une mesure de Lebesgue nulle) , cette démonstration n'est pas constructive et seuls quelques nombres spécifiques ont été montrés comme étant normaux. Par exemple, toute constante de Chaitin est normale (et non calculable ). Il est largement admis que les nombres (calculables) ,
Définitions
Soit chiffres, l'ensemble de toutes les séquences infinies que on peut tirer de cet alphabet, et l'ensemble des séquences finies, ou chaînes . Soit une telle séquence. Pour chaque <sub> apparaît dans les On dit que
pour chaque une chaîne finie quelconque dans et soit le nombre de fois où la chaîne premiers chiffres de la séquence ... , alors , 8) = 3 .) ,
où w | désigne la longueur de la chaîne est normale si toutes les chaînes de même longueur apparaissent avec la même fréquence asymptotique . Par exemple, dans une séquence binaire normale (une séquence sur l'alphabet , 1 } ), 0 et 1 apparaissent chacun avec une fréquence de 1/2 ; 00 , 01 , 10 et 11 apparaissent chacun avec une fréquence de 1/4 ; 000 , 001 , 010 , 011 , 100 , 101 , 110 et 111 apparaissent chacun avec une fréquence de 1/8 ; etc. En résumé, la probabilité de trouver la chaîne est exactement la même que celle attendue si la séquence avait été générée aléatoirement .
Supposons maintenant que un nombre réel . Considérons le développement en séquences infinies de chiffres de (on ignore la virgule décimale). On dit que si la séquence est simplement normale et que si la séquence est normale Le nombre pour tout entier différent pour chaque entier , peut être normal dans une base mais pas dans une autre (auquel cas il n'est pas normal). Pour des bases telles que rationnel (donc et ), tout nombre normal en base . Pour des bases telles que irrationnel, il existe une infinité non dénombrable de nombres normaux dans chaque base mais pas dans l'autre.
Une suite disjonctive est une suite dans laquelle apparaît toute chaîne finie. Une suite normale est disjonctive, mais une suite disjonctive n'est pas nécessairement normale. Un nombre riche en base est disjonctif : un nombre disjonctif à toute base est dit absolument disjonctif ou est appelé lexique . Un nombre normal en base , mais la réciproque n'est pas nécessairement vraie. Le nombre réel si et seulement si l'ensemble : n ∈ N } est dense dans l' intervalle unité .
Nous avons défini un nombre comme étant simplement normal en base / b . Pour une base Borel ( 1909 ) . À l'aide du lemme de Borel-Cantelli , il a démontré que presque tous les nombres réels sont normaux, établissant ainsi l'existence des nombres normaux. ( 1917 ) a montré qu'il est possible de spécifier un tel nombre. Figueira ( 2002 ) ont prouvé l'existence d'un nombre absolument normal calculable . Bien que cette construction ne donne pas directement les chiffres des nombres construits, elle montre qu'il est possible, en principe, d'énumérer chaque chiffre d'un nombre normal particulier.
L'ensemble des nombres non normaux, bien que « grand » au sens d' indénombrable , est également un ensemble vide (sa mesure de Lebesgue en tant que sous-ensemble des nombres réels étant nulle, il n'occupe donc aucun espace dans l'ensemble des nombres réels). De plus, les nombres non normaux (ainsi que les nombres normaux) sont denses dans les réels : l'ensemble des nombres non normaux compris entre deux nombres réels distincts est non vide puisqu'il contient tous les nombres rationnels (en fait, il est infini non dénombrable et même composé ). Par exemple, il existe une infinité non dénombrable de nombres dont le développement décimal (en base 3 ou supérieure) ne contient pas le chiffre 1, et aucun de ces nombres n'est normal.
L'ensemble obtenu en concaténant les nombres premiers en base 10 est normal en base 10, comme l'ont démontré Copeland et Paul Erdős ( 1946 ) . Plus généralement, ces derniers auteurs ont prouvé que le nombre réel représenté en base b par la concaténation
1935 ) a prouvé que le nombre représenté par la même expression, avec f ( n ) = n² ,Davenport et Erdős ( 1952 ) ont prouvé que le nombre représenté par la même expression, avec f étant un polynôme non constant quelconque dont les valeurs sur les entiers positifs sont des entiers positifs, exprimé en base 10, est normal en base 10.Shiokawa ( 1992 ) ont démontré que si f ( x ) est un polynôme non constant à coefficients réels tel que f ( x ) > 0 pour tout x > 0, alors le nombre réel représenté par la concaténation
où les αs et les βs sont des nombres réels avec β > β 1 > β 2 > ... > β d ≥ 0, et f ( x ) > 0 pour tout x > 0.
Crandall ( 2002 ) montrent une classe infinie non dénombrable explicite de nombres b -normaux en perturbant les nombres de Stoneham .
, π , ln(2) et e soient normaux, leur normalité reste incertaine. Il n'a même pas été prouvé que tous les chiffres apparaissent une infinité de fois dans le développement décimal de ces constantes (par exemple, dans le cas de π, l'affirmation courante selon laquelle « toute suite de nombres finit par apparaître dans π » n'est pas avérée). a également conjecturé que tout nombre algébrique irrationnel est absolument normal (ce qui impliquerait que est normal), et aucun contre-exemple n'est connu dans aucune base. Cependant, aucun nombre algébrique irrationnel n'a été démontré normal dans aucune base.
Nombres non normaux
Aucun nombre rationnel n'est normal dans aucune base, car la séquence de chiffres d'un nombre rationnel est finalement périodique , et donc la plupart des chaînes plus longues que la période n'apparaissent pas dans la séquence de chiffres.
2001 ) donne un exemple de nombre irrationnel absolument anormal. Soit
Alors le nombre α n'est normal dans aucune base. α est également un nombre de Liouville .
Propriétés
Les propriétés supplémentaires des nombres normaux incluent :
- Tout nombre réel non nul est le produit de deux nombres normaux. Ceci découle du fait général que tout nombre est le produit de deux nombres appartenant à un ensemble.
- Si x suit une loi normale de base b et si a ≠ 0 est un nombre rationnel, alors
- Si
- Une séquence est normale si et seulement si chaque bloc de même longueur apparaît avec la même fréquence. (Un bloc de longueur k est une sous-chaîne de longueur k apparaissant à une position dans la séquence qui est un multiple de k : par exemple, le premier bloc de longueur k dans S est S [1.. k ], le deuxième bloc de longueur k est S [ k +1..2 k ], etc.) Ceci était implicite dans le travail de Lempel ( 1978 ) et explicité dans le travail de et Vinodchandran ( 2005 ) .
- Un nombre est normal en base b si et seulement s'il est simplement normal en base b k pour tout
- Un nombre est dit normal si et seulement si il est simplement normal dans toute base. Ceci découle de la caractérisation précédente de la normalité en base b .
- Un nombre est b -normal si et seulement s'il existe un ensemble d'entiers positifs.
- Toute suite normale est stable par variations finies : ajouter, supprimer ou modifier un nombre fini de chiffres dans une suite normale la laisse normale. De même, si l’on ajoute, supprime ou modifie un nombre fini de chiffres dans une suite simplement normale, la nouvelle suite reste simplement normale.
Connexion aux machines à états finis
Agafonov a établi un lien précoce entre les automates finis et les suites normales : toute sous-suite infinie sélectionnée dans une suite normale par un langage régulier est également normale. Autrement dit, si l’on exécute un automate fini sur une suite normale, où chaque état de l’automate est étiqueté « sortie » ou « pas de sortie », et que l’automate produit le chiffre suivant après être entré dans un état « sortie », mais ne produit pas le chiffre suivant après être entré dans un état « pas de sortie », alors la suite produite sera normale.
Il existe un lien plus profond avec les joueurs à états finis (FSG) et les compresseurs à états finis sans perte d'information (ILFSC).
- Un joueur à états finis (ou martingale à états finis ) est une machine à états finis sur un alphabet fini
- Un compresseur à états finis est une machine à états finis dont les sorties sont des chaînes de caractères étiquetant ses transitions d'état , y compris éventuellement la chaîne vide. (Puisqu'un chiffre est lu dans la séquence d'entrée pour chaque transition d'état, il est nécessaire de pouvoir produire la chaîne vide pour obtenir une compression quelconque). Un compresseur à états finis sans perte d'information est un compresseur dont l'entrée peut être retrouvée de manière unique à partir de sa sortie et de son état final. Autrement dit, pour un compresseur à états finis C d'ensemble d'états Q , C est sans perte d'information si la fonction
Schnorr et Stimm ont démontré qu'aucun FSG ne peut réussir sur une séquence normale, et Bourke, Hitchcock et Vinodchandran ont démontré le contraire . Par conséquent :
(Ils ont en effet démontré que le taux de compression optimal de la séquence parmi tous les ILFSC correspond exactement à son taux d'entropie , une mesure quantitative de son écart à la normalité, qui vaut 1 précisément lorsque la séquence est normale). Puisque l' algorithme de compression LZ compresse asymptotiquement aussi bien que n'importe quel ILFSC, cela signifie qu'il peut compresser toute séquence non normale.
Ces caractérisations des suites normales peuvent s'interpréter comme signifiant que « normal » = « aléatoire pour un automate fini » ; autrement dit, les suites normales sont précisément celles qui apparaissent aléatoires pour tout automate fini. Comparons cela aux suites algorithmiquement aléatoires , qui sont ces suites infinies qui apparaissent aléatoires pour tout algorithme (et qui, de fait, présentent des caractérisations similaires en termes de jeu et de compression, les machines de Turing remplaçant les automates finis).
Lien avec les séquences équidistribuées
Un nombre x est normal en base b si et seulement si la séquence
Ce lien conduit à la terminologie selon laquelle x est normal en base β pour tout nombre réel β si et seulement si la suite