Secuencia disyuntiva

Una secuencia disyuntiva es una secuencia infinita de caracteres extraídos de un alfabeto finito , en la que cada cadena finita aparece como una subcadena . Por ejemplo, la constante de Champernowne definida al concatenar las representaciones en base 10 de los enteros positivos:

C ₁₀ = 0.1234567891011121314151617181920...

claramente contiene todas las cadenas y por lo tanto es disyuntiva.

Cualquier secuencia normal (una secuencia en la que cada cadena de igual longitud aparece con igual frecuencia) es disyuntiva, pero lo contrario no es cierto. Por ejemplo, sea 0 ⁿ la cadena de longitud n que consta de todos 0s, consideremos la secuencia

${\displaystyle 0\ 0^{1}\ 1\ 0^{2}\ 00\ 0^{4}\ 01\ 0^{8}\ 10\ 0^{16}\ 11\ 0^{32}\ 000\ 0^{64}\ldots }$

Se obtiene insertando secuencias exponencialmente largas de ceros en el ordenamiento shortlex de todas las cadenas binarias. La mayor parte de esta secuencia consiste en largas rachas de ceros, por lo que no es normal, pero sigue siendo disyuntiva.

La función de complejidad de una secuencia disyuntiva S sobre un alfabeto de tamaño k es p _S ( n ) = k ⁿ . ^{[ 1 ]}

Una secuencia disyuntiva es recurrente , pero nunca uniformemente recurrente/casi periódica.

El siguiente resultado ^{[ 2 ] [ 3 ]} puede utilizarse para generar una variedad de secuencias disyuntivas:

Si a ₁ , a ₂ , a ₃ , ..., es una secuencia infinita estrictamente creciente de enteros positivos tal que lim _{n → ∞} ( a _{n +1} / a _n ) = 1,

Entonces, para cualquier entero positivo m y cualquier entero en base b ≥ 2, existe un a _n cuya expresión en base b comienza con la expresión de m en base b .

(Por consiguiente, la secuencia infinita obtenida al concatenar las expresiones en base b para a ₁ , a ₂ , a ₃ , ..., es disyuntiva sobre el alfabeto {0, 1, ..., b -1}.)

Dos casos sencillos ilustran este resultado:

• a _n = n ^k , donde k es un entero positivo fijo . (En este caso, lim _{n → ∞} ( a _{n +1} / a _n ) = lim _{n → ∞} ( ( n +1) ^k / n ^k ) = lim _{n → ∞} (1 + 1/ n ) ^k = 1.)

Por ejemplo, utilizando expresiones en base diez, las secuencias

123456789101112... ( k = 1, números naturales positivos ),

1491625364964... ( k = 2, cuadrados ),

182764125216343... ( k = 3, cubos ),

etc.,

son disyuntivas en {0,1,2,3,4,5,6,7,8,9}.

• a _n = p _n , donde p _n es el n- ^ésimo número primo . (En este caso, lim _{n → ∞} ( a _{n +1} / a _n ) = 1 es una consecuencia de p _n ~ n ln n .)

Por ejemplo, las secuencias

23571113171923... (usando base diez),

10111011111011110110001 ... (usando base dos),

etc.,

son disyuntivas en los conjuntos de dígitos respectivos.

Otro resultado ^{[ 4 ]} que proporciona una variedad de secuencias disyuntivas es el siguiente:

Si a _n = piso ( f ( n )), donde f es cualquier polinomio no constante con coeficientes reales tal que f ( x ) > 0 para todo x > 0,

entonces la concatenación a ₁ a ₂ a ₃ ... (con a n _expresado en base b ) es una secuencia normal en base b , y por lo tanto es disyuntiva en {0, 1, ..., b -1}.

Por ejemplo, utilizando expresiones en base diez, las secuencias

818429218031851879211521610... (con f ( x ) = 2 x ³ - 5 x ² + 11 x )

591215182124273034... (con f ( x ) = π x + e )

son disyuntivas en {0,1,2,3,4,5,6,7,8,9}.

Un número rico o disyuntivo es un número real cuya expansión con respecto a alguna base b es una sucesión disyuntiva sobre el alfabeto {0,..., b −1}. Todo número normal en base b es disyuntivo, pero no a la inversa. El número real x es rico en base b si y solo si el conjunto { xb ⁿ mod 1} es denso en el intervalo unitario . ^{[ 5 ]}

Un número que es disyuntivo a cualquier base se denomina absolutamente disyuntivo o léxico . Cada cadena de cualquier alfabeto se encuentra dentro de un léxico. Un conjunto se denomina " comeager " o "residual" si contiene la intersección de una familia numerable de conjuntos abiertos y densos. El conjunto de los números reales absolutamente disyuntivos es residual. ^{[ 6 ]} Se conjetura que todo número algebraico irracional real es absolutamente disyuntivo. ^{[ 7 ]}