Secuencia disyuntiva

Secuencia en la que cada cadena finita aparece como una subsecuencia

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 secuencia binaria de Champernowne

${\displaystyle 0\ 1\ 00\ 01\ 10\ 11\ 000\ 001\ldots }$

formada por la concatenación de todas las cadenas binarias en orden shortlex , contiene claramente todas las cadenas binarias y por lo tanto es disyuntiva. (Los espacios anteriores no son significativos y están presentes únicamente para aclarar los límites entre cadenas). La función de complejidad de una secuencia disyuntiva S sobre un alfabeto de tamaño k es p _S ( n ) = k ⁿ . ^[1]

Cualquier secuencia normal (una secuencia en la que cada cadena de igual longitud aparece con la misma frecuencia) es disyuntiva, pero la inversa no es cierta. Por ejemplo, si 0 ⁿ denota la cadena de longitud n que consta de todos los 0, considere 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 uniendo cadenas de 0 exponencialmente largas en el ordenamiento shortlex de todas las cadenas binarias. La mayor parte de esta secuencia consta de largas series de 0, por lo que no es normal, pero sigue siendo disyuntiva.

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

Ejemplos

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

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

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

(En consecuencia, 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 simples 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 de 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 ^º 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 disyuntivos en los respectivos conjuntos de dígitos.

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

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

entonces la concatenación a ₁ a ₂ a ₃ ... (con la a _n expresada 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 de 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}.

Números ricos

Un número rico o número disyuntivo es un número real cuya expansión respecto de 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 sólo si el conjunto { xb ⁿ mod 1} es denso en el intervalo unitario . ^[5]

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

Notas

1. Bugeaud (2012) pág. 91
2. Calude, C .; Priese, L.; Staiger, L. (1997), Secuencias disyuntivas: una descripción general , Universidad de Auckland, Nueva Zelanda, págs. 1–35, CiteSeerX 10.1.1.34.1370 
3. Istrate, G.; Păun, Gh. (1994), "Algunas propiedades combinatorias de secuencias de autolectura", Discrete Applied Mathematics , 55 : 83–86, doi :10.1016/0166-218X(94)90037-X, Zbl  0941.68656
4. Nakai, Yoshinobu; Shiokawa, Iekata (1992), "Estimaciones de discrepancia para una clase de números normales" (PDF) , Acta Arithmetica , LXII.3 (3): 271–284, doi : 10.4064/aa-62-3-271-284
5. Bugeaud (2012) pág. 92
6. Calude y Zamfirescu (1999)
7. Adamczewski y Bugeaud (2010) p.414

Referencias

• Adamczewski, Boris; Bugeaud, Yann (2010). "8. Trascendencia y aproximación diofántica". En Berthé, Valérie ; Rigo, Michael (eds.). Combinatoria, autómatas y teoría de números . Enciclopedia de matemáticas y sus aplicaciones. Vol. 135. Cambridge: Cambridge University Press . págs. 410–451. ISBN 978-0-521-51597-9.Zbl 1271.11073  .
• Bugeaud, Yann (2012). Distribución módulo uno y aproximación diofántica . Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press . ISBN. 978-0-521-11169-0.Zbl 1260.11001  .
• Calude, CS ; Zamfirescu, T. (1999). "La mayoría de los números no obedecen a leyes de probabilidad". Publicaciones Mathematicae Debrecen . 54 (Suplemento): 619–623.