Número normal

En matemáticas , se dice que un número real es simplemente normal en una base entera b ^[1] si su secuencia infinita de dígitos se distribuye uniformemente en el sentido de que cada uno de los b valores de dígitos tiene la misma densidad natural  1/ b . Se dice que un número es normal en base b si, para cada entero positivo n , todas las posibles cadenas de n dígitos de longitud tienen densidad  b ^{− n} .

Intuitivamente, que un número sea simplemente normal significa que ningún dígito aparece con más frecuencia que otro. Si un número es normal, ninguna combinación finita de dígitos de una longitud dada aparece con más frecuencia que cualquier otra combinación de la misma longitud. Un número normal puede considerarse como una secuencia infinita de lanzamientos de moneda ( binario ) o tiradas de un dado ( base 6 ). Aunque habrá secuencias como 10, 100 o más cruces consecutivas (binario) o cincos (base 6) o incluso 10, 100 o más repeticiones de una secuencia como cruz-cara (dos lanzamientos consecutivos de moneda) o 6-1 (dos tiradas consecutivas de un dado), también habrá la misma cantidad de cualquier otra secuencia de igual longitud. Ningún dígito o secuencia es "favorecido".

Se dice que un número es normal (a veces llamado absolutamente normal ) si es normal en todas las bases enteras mayores o iguales a 2.

Aunque se puede dar una prueba general de que casi todos los números reales son normales (lo que significa que el conjunto de números no normales tiene medida de Lebesgue cero), ^[2] esta prueba no es constructiva , y solo se ha demostrado que unos pocos números específicos son normales. Por ejemplo, cualquier constante de Chaitin es normal (e incomputable ). Se cree ampliamente que los números (computables) √ 2 , π y e son normales, pero una prueba sigue siendo difícil de alcanzar. ^[3]

Sea Σ un alfabeto finito de b dígitos, Σ ^ω el conjunto de todas las secuencias infinitas que pueden extraerse de ese alfabeto, y Σ ^∗ el conjunto de secuencias finitas, o cadenas . ^[4] Sea S ∈ Σ ^ω una de esas secuencias. Para cada a en Σ sea N _S ( a , n ) el número de veces que el dígito a aparece en los primeros n dígitos de la secuencia S . Decimos que S es simplemente normal si el límite

$${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(a,n)}{n}}={\frac {1}{b}}}$$

para cada a . Ahora sea w cualquier cadena finita en Σ ^∗ y sea N _S ( w , n ) el número de veces que la cadena w aparece como subcadena en los primeros n dígitos de la secuencia S . (Por ejemplo, si S = 01010101 ... , entonces N _S ( 010 , 8) = 3 .) S es normal si, para todas las cadenas finitas w ∈ Σ ^∗ ,

$${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{b^{|w|}}}}$$

donde | w | denota la longitud de la cadena w . En otras palabras, S es normal si todas las cadenas de igual longitud ocurren con igual frecuencia asintótica . Por ejemplo, en una secuencia binaria normal (una secuencia sobre el alfabeto { 0 , 1 } ), 0 y 1 ocurren cada uno con frecuencia 1 ⁄ 2 ; 00 , 01 , 10 y 11 ocurren cada uno con frecuencia 1 ⁄ 4 ; 000 , 001 , 010 , 011 , 100 , 101 , 110 y 111 ocurren cada uno con frecuencia 1 ⁄ 8 ; etc. En términos generales, la probabilidad de encontrar la cadena w en cualquier posición dada en S es precisamente la esperada si la secuencia se hubiera producido al azar .

Supongamos ahora que b es un entero mayor que 1 y x es un número real . Consideremos la expansión de la secuencia de dígitos infinitos S _{x , b} de x en el sistema de numeración posicional de base b (ignoramos el punto decimal). Decimos que x es simplemente normal en base b si la secuencia S _{x , b} es simplemente normal ^[5] y que x es normal en base b si la secuencia S _{x , b} es normal. ^[6] El número x se llama un número normal (o a veces un número absolutamente normal ) si es normal en base b para cada entero b mayor que 1. ^{[7] [8]}

Una secuencia infinita dada es normal o no normal, mientras que un número real, que tiene una expansión en base b diferente para cada entero b ≥ 2 , puede ser normal en una base pero no en otra ^{[9] [10]} (en cuyo caso no es un número normal). Para bases r y s con log r / log s racional (de modo que r = b ^m y s = b ⁿ ) todo número normal en base r es normal en base s . Para bases r y s con log r / log s irracional, hay incontables números normales en cada base pero no en la otra. ^[10]

Una sucesión disyuntiva es una sucesión en la que aparece cada cadena finita. Una sucesión normal es disyuntiva, pero una sucesión disyuntiva no necesita ser normal. Un número rico en base b es aquel cuya expansión en base b es disyuntiva: ^[11] aquel que es disyuntivo respecto de toda base se llama absolutamente disyuntivo o se dice que es un léxico . Un número normal en base b es rico en base b , pero no necesariamente a la inversa. El número real x es rico en base b si y solo si el conjunto { x b ⁿ mod 1 : n ∈ N } es denso en el intervalo unitario . ^{[11] [12]}

Definimos un número como simplemente normal en base b si cada dígito individual aparece con una frecuencia de 1 ⁄ b . Para una base b dada , un número puede ser simplemente normal (pero no normal o rico), rico (pero no simplemente normal o normal), normal (y por lo tanto simplemente normal y rico), o ninguna de estas. Un número es absolutamente no normal o absolutamente anormal si no es simplemente normal en ninguna base. ^{[7] [13]}

El concepto de número normal fue introducido por Émile Borel  (1909). Utilizando el lema de Borel-Cantelli , demostró que casi todos los números reales son normales, estableciendo la existencia de números normales. Wacław Sierpiński  (1917) demostró que es posible especificar un número particular de ese tipo. Becher y Figueira (2002) demostraron que existe un número absolutamente normal computable . Aunque esta construcción no da directamente los dígitos de los números construidos, muestra que es posible en principio enumerar cada dígito de un número normal particular.

El conjunto de los números no normales, a pesar de ser "grande" en el sentido de ser incontable , es también un conjunto nulo (ya que su medida de Lebesgue como subconjunto de los números reales es cero, por lo que esencialmente no ocupa espacio dentro de los números reales). Además, los números no normales (así como los números normales) son densos en los reales: el conjunto de números no normales entre dos números reales distintos no está vacío ya que contiene todos los números racionales (de hecho, es incontablemente infinito ^[14] e incluso comeagre ). Por ejemplo, hay incontables números cuyas expansiones decimales (en base 3 o superior) no contienen el dígito 1, y ninguno de esos números es normal.

La constante de Champernowne

obtenida concatenando en orden las representaciones decimales de los números naturales , es normal en base 10. Asimismo, las diferentes variantes de la constante de Champernowne (realizadas realizando la misma concatenación en otras bases) son normales en sus respectivas bases (por ejemplo, la constante de Champernowne en base 2 es normal en base 2), pero no se ha demostrado que sean normales en otras bases.

La constante de Copeland-Erdős

obtenido por concatenación de los números primos en base 10, es normal en base 10, como demostraron AH Copeland y Paul Erdős  (1946). De manera más general, estos últimos autores demostraron que el número real representado en base b por la concatenación

donde f ( n ) es el n ^º primo expresado en base b , es normal en base b . Besicovitch  (1935) demostró que el número representado por la misma expresión, con f ( n ) = n ² ,

obtenido al concatenar los números cuadrados en base 10, es normal en base 10. Harold Davenport y Erdős (1952) demostraron que el número representado por la misma expresión, siendo f cualquier polinomio no constante cuyos valores en los números enteros positivos son números enteros positivos, expresados ​​en base 10, es normal en base 10.

Nakai y Shiokawa (1992) demostraron que si f ( x ) es cualquier polinomio no constante con coeficientes reales tales que f ( x ) > 0 para todo x > 0, entonces el número real representado por la concatenación

donde [ f ( n )] es la parte entera de f ( n ) expresada en base b , es normal en base b . (Este resultado incluye como casos especiales todos los resultados mencionados anteriormente de Champernowne, Besicovitch y Davenport & Erdős.) Los autores también muestran que el mismo resultado se cumple de manera más general cuando f es cualquier función de la forma

donde αs y βs son números reales con β > β ₁ > β ₂ > ... > β _d ≥ 0, y f ( x ) > 0 para todo x > 0.

Bailey y Crandall (2002) muestran una clase explícitamente infinita e incontable de números b -normales perturbando los números de Stoneham .

Ha sido un objetivo difícil de alcanzar demostrar la normalidad de números que no están construidos artificialmente. Si bien se conjetura firmemente que √ 2 , π , ln(2) y e son normales, aún no se sabe si lo son o no. Ni siquiera se ha demostrado que todos los dígitos ocurran en realidad infinitas veces en las expansiones decimales de esas constantes (por ejemplo, en el caso de π, no se sabe si es cierta la afirmación popular de que "toda cadena de números ocurre eventualmente en π"). ^[15] También se ha conjeturado que todo número algebraico irracional es absolutamente normal (lo que implicaría que √ 2 es normal), y no se conocen contraejemplos en ninguna base. Sin embargo, no se ha demostrado que ningún número algebraico irracional sea normal en ninguna base.

Ningún número racional es normal en ninguna base, ya que las secuencias de dígitos de los números racionales son eventualmente periódicas .

Martin (2001) da un ejemplo de un número irracional que es absolutamente anormal. ^[16] Sea

$${\displaystyle f\left(n\right)={\begin{cases}n^{\frac {f\left(n-1\right)}{n-1}},&n\in \mathbb {Z} \cap \left[3,\infty \right)\\4,&n=2\end{cases}}}$$

$${\displaystyle {\begin{aligned}&\alpha =\prod _{m=2}^{\infty }\left({1-{\frac {1}{f\left(m\right)}}}\right)=\left(1-{\frac {1}{4}}\right)\left(1-{\frac {1}{9}}\right)\left(1-{\frac {1}{64}}\right)\left(1-{\frac {1}{152587890625}}\right)\left(1-{\frac {1}{6^{\left(5^{15}\right)}}}\right)\ldots =\\&=0.6562499999956991\underbrace {99999\ldots 99999} _{23,747,291,559}8528404201690728\ldots \end{aligned}}}$$

Entonces α es un número de Liouville y es absolutamente anormal.

Las propiedades adicionales de los números normales incluyen:

• Todo número real distinto de cero es el producto de dos números normales. Esto se deduce del hecho general de que todo número es el producto de dos números de un conjunto si el complemento de X tiene medida 0.${\displaystyle X\subseteq \mathbb {R} ^{+}}$
• Si x es normal en base b y a ≠ 0 es un número racional, entonces también es normal en base b . ^[17]${\displaystyle x\cdot a}$
• Si es denso (para cada y para todos los n suficientemente grandes , ) y son las expansiones en base b de los elementos de A , entonces el número , formado al concatenar los elementos de A , es normal en base b (Copeland y Erdős 1946). De esto se sigue que el número de Champernowne es normal en base 10 (ya que el conjunto de todos los enteros positivos es obviamente denso) y que la constante de Copeland–Erdős es normal en base 10 (ya que el teorema de los números primos implica que el conjunto de los primos es denso).${\displaystyle A\subseteq \mathbb {N} }$${\displaystyle \alpha <1}$${\displaystyle |A\cap \{1,\ldots ,n\}|\geq n^{\alpha }}$${\displaystyle a_{1},a_{2},a_{3},\ldots }$${\displaystyle 0.a_{1}a_{2}a_{3}\ldots }$
• Una secuencia es normal si y sólo si cada bloque de igual longitud aparece con igual frecuencia. (Un bloque de longitud k es una subcadena de longitud k que aparece en una posición en la secuencia que es un múltiplo de k : por ejemplo, el primer bloque de longitud k en S es S [1.. k ], el segundo bloque de longitud k es S [ k +1..2 k ], etc.) Esto estaba implícito en el trabajo de Ziv y Lempel (1978) y se hizo explícito en el trabajo de Bourke, Hitchcock y Vinodchandran (2005).
• Un número es normal en base b si y solo si es simplemente normal en base b ^k para todo . Esto se desprende de la caracterización de bloques anterior de la normalidad: dado que el n ^-ésimo bloque de longitud k en su expansión en base b corresponde al n- ^ésimo dígito en su expansión en base b ^k , un número es simplemente normal en base b ^k si y solo si aparecen bloques de longitud k en su expansión en base b con igual frecuencia.${\displaystyle k\in \mathbb {Z} ^{+}}$
• Un número es normal si y sólo si es simplemente normal en todas sus bases. Esto se desprende de la caracterización anterior de la normalidad en base b .
• Un número es b -normal si y sólo si existe un conjunto de enteros positivos donde el número es simplemente normal en bases b ^m para todo ^[18]. Ningún conjunto finito es suficiente para demostrar que el número es b -normal.${\displaystyle m_{1}<m_{2}<m_{3}<\cdots }$${\displaystyle m\in \{m_{1},m_{2},\ldots \}.}$
• Todas las sucesiones normales están cerradas bajo variaciones finitas : agregar, quitar o cambiar un número finito de dígitos en cualquier sucesión normal la deja normal. De manera similar, si se agrega, quita o cambia un número finito de dígitos en cualquier sucesión simplemente normal, la nueva sucesión sigue siendo simplemente normal.

Agafonov demostró una conexión temprana entre las máquinas de estados finitos y las secuencias normales: cada subsecuencia infinita seleccionada de una secuencia normal por un lenguaje regular también es normal. En otras palabras, si se ejecuta una máquina de estados finitos en una secuencia normal, donde cada uno de los estados de la máquina de estados finitos se etiqueta como "salida" o "sin salida", y la máquina genera el dígito que lee a continuación después de ingresar en un estado de "salida", pero no genera el dígito siguiente después de ingresar en un estado de "sin salida", entonces la secuencia que genera será normal. ^[19]

Existe una conexión más profunda con los jugadores de estados finitos (FSG) y los compresores de estados finitos sin pérdida de información (ILFSC).

• Un jugador de estados finitos (también conocido como martingala de estados finitos ) es una máquina de estados finitos sobre un alfabeto finito , cada uno de cuyos estados está etiquetado con porcentajes de dinero para apostar en cada dígito en . Por ejemplo, para un FSG sobre el alfabeto binario , el estado actual q apuesta un porcentaje del dinero del jugador en el bit 0 y la fracción restante del dinero del jugador en el bit 1. El dinero apostado en el dígito que viene a continuación en la entrada (dinero total multiplicado por el porcentaje apostado) se multiplica por , y el resto del dinero se pierde. Después de leer el bit, el FSG pasa al siguiente estado de acuerdo con la entrada que recibió. Un FSG d tiene éxito en una secuencia infinita S si, a partir de $1, gana dinero ilimitado apostando en la secuencia; es decir, si donde es la cantidad de dinero que tiene el jugador d después de leer los primeros n dígitos de S (ver límite superior ).${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle \Sigma =\{0,1\}}$${\displaystyle q_{0}\in [0,1]}$${\displaystyle q_{1}=1-q_{0}}$${\displaystyle |\Sigma |}$ $${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$$${\displaystyle d(S\upharpoonright n)}$
• Un compresor de estados finitos es una máquina de estados finitos con cadenas de salida que etiquetan sus transiciones de estado , incluyendo posiblemente la cadena vacía. (Dado que se lee un dígito de la secuencia de entrada para cada transición de estado, es necesario poder emitir la cadena vacía para lograr cualquier compresión). Un compresor de estados finitos sin pérdida de información es un compresor de estados finitos cuya entrada se puede recuperar de forma única de su salida y estado final. En otras palabras, para un compresor de estados finitos C con un conjunto de estados Q , C no tiene pérdida de información si la función , que asigna la cadena de entrada de C a la cadena de salida y al estado final de C , es 1–1 . Las técnicas de compresión como la codificación de Huffman o la codificación de Shannon-Fano se pueden implementar con ILFSC. Un ILFSC C comprime una secuencia infinita S si donde es el número de dígitos de salida de C después de leer los primeros n dígitos de S. La relación de compresión (el límite inferior indicado anteriormente) siempre se puede hacer igual a 1 mediante el ILFSC de 1 estado que simplemente copia su entrada a la salida.${\displaystyle f:\Sigma ^{*}\to \Sigma ^{*}\times Q}$ $${\displaystyle \liminf _{n\to \infty }{\frac {|C(S\upharpoonright n)|}{n}}<1,}$$${\displaystyle |C(S\upharpoonright n)|}$

Schnorr y Stimm demostraron que ningún FSG puede tener éxito en ninguna secuencia normal, y Bourke, Hitchcock y Vinodchandran demostraron lo contrario . Por lo tanto:

Ziv y Lempel demostraron:

(De hecho, demostraron que la relación de compresión óptima de la secuencia sobre todos los ILFSC es exactamente su tasa de entropía , una medida cuantitativa de su desviación de la normalidad, que es 1 exactamente cuando la secuencia es normal). Dado que el algoritmo de compresión LZ comprime asintóticamente tan bien como cualquier ILFSC, esto significa que el algoritmo de compresión LZ puede comprimir cualquier secuencia no normal. ^[20]

Estas caracterizaciones de las secuencias normales pueden interpretarse en el sentido de que "normal" = "aleatoria de estado finito"; es decir, las secuencias normales son precisamente aquellas que parecen aleatorias para cualquier máquina de estado finito. Compárese esto con las secuencias aleatorias algorítmicas , que son aquellas secuencias infinitas que parecen aleatorias para cualquier algoritmo (y de hecho tienen caracterizaciones de juego y compresión similares con las máquinas de Turing que reemplazan a las máquinas de estado finito).

Un número x es normal en base b si y solo si la secuencia está equidistribuida módulo 1, ^{[21] [22]} o equivalentemente, utilizando el criterio de Weyl , si y solo si${\displaystyle {\left(b^{k}x\right)}_{k=0}^{\infty }}$

$${\displaystyle \lim _{n\rightarrow \infty }{\frac {1}{n}}\sum _{k=0}^{n-1}e^{2\pi imb^{k}x}=0\quad {\text{ for all integers }}m\geq 1.}$$

Esta conexión conduce a la terminología de que x es normal en base β para cualquier número real β si y sólo si la secuencia está equidistribuida módulo 1. ^[22]${\displaystyle \left({x\beta ^{k}}\right)_{k=0}^{\infty }}$

• Constante de Champernowne
• Secuencia de De Bruijn
• Teorema del mono infinito
• La biblioteca de Babel

• Weisstein, Eric W. "Número normal". MathWorld .