En matemáticas, la secuencia Baum-Sweet es una secuencia automática infinita de 0 y 1 definida por la regla:
- b n = 1 si la representación binaria de n no contiene ningún bloque de ceros consecutivos de longitud impar;
- b n = 0 en caso contrario;
para n ≥ 0. [1]
Por ejemplo, b 4 = 1 porque la representación binaria de 4 es 100, que solo contiene un bloque de ceros consecutivos de longitud 2; mientras que b 5 = 0 porque la representación binaria de 5 es 101, que contiene un bloque de ceros consecutivos de longitud 1.
A partir de n = 0, los primeros términos de la secuencia de Baum-Sweet son:
Motivación histórica
Las propiedades de la secuencia fueron estudiadas por primera vez por Leonard E. Baum y Melvin M. Sweet en 1976. [2] En 1949, Khinchin conjeturó que no existe un número real algebraico no cuadrático que tenga cocientes parciales acotados en su expansión fraccionaria continua. . Aún no se conoce un contraejemplo de esta conjetura. [3] [4] El artículo de Baum y Sweet mostró que no se cumple la misma expectativa para las series de potencias algebraicas. Dieron un ejemplo de series de potencia cúbica encuyos cocientes parciales están acotados. (El grado de la serie de potencias en el resultado de Baum y Sweet es análogo al grado de extensión del campo asociado con el real algebraico en la conjetura de Khinchin).
Una de las series consideradas en el artículo de Baum y Sweet es una raíz de
Los autores muestran que según el lema de Hensel , existe una raíz única en porque reducir la ecuación definitoria de modulo da , que factores como
Continúan demostrando que esta raíz única tiene cocientes parciales de grado . Antes de hacerlo, afirman (en la observación que sigue al teorema 2, p. 598) [2] que la raíz se puede escribir en la forma
dónde y por si y solo si la expansión binaria de contiene solo bloques de longitud uniforme de 's. Este es el origen de la secuencia Baum-Sweet.
Mkaouar [6] y Yao [7] demostraron que los cocientes parciales de la fracción continua paraanteriores no forman una secuencia automática. [8] Sin embargo, la secuencia de cocientes parciales puede generarse mediante un morfismo no uniforme. [9]
Propiedades
La secuencia Baum-Sweet puede ser generada por un autómata de 3 estados . [9]
El valor del término b n en la secuencia Baum-Sweet se puede encontrar de forma recursiva de la siguiente manera. Si n = m · 4 k , donde m no es divisible por 4 (o es 0), entonces
Por lo tanto, b 76 = b 9 = b 4 = b 0 = 1, lo que puede verificarse observando que la representación binaria de 76, que es 1001100, no contiene bloques consecutivos de 0 con longitud impar.
La palabra Baum-Sweet 1101100101001001 ..., que se crea concatenando los términos de la secuencia Baum-Sweet, es un punto fijo de las reglas de morfismo o sustitución de cadenas
- 00 → 0000
- 01 → 1001
- 10 → 0100
- 11 → 1101
como sigue:
- 11 → 1101 → 11011001 → 1101100101001001 → 11011001010010011001000001001001 ...
De las reglas del morfismo se puede ver que la palabra Baum-Sweet contiene bloques de ceros consecutivos de cualquier longitud ( b n = 0 para los 2 k enteros en el rango 5.2 k ≤ n <6.2 k ), pero no contiene ningún bloque de tres 1 consecutivos.
Más sucintamente, según el pequeño teorema de Cobham, la palabra Baum-Sweet puede expresarse como una codificación aplicado al punto fijo de un morfismo uniforme . De hecho, el morfismo
y codificación
generar la palabra de esa manera. [10]
Notas
- ^ Weisstein, Eric W. "Baum-Sweet Sequence" . MathWorld .
- ^ a b c Baum, Leonard E .; Dulce, Melvin M. (1976). "Continuación de las fracciones de la serie de potencias algebraicas en la característica 2". Annals of Mathematics . 103 (3): 593–610. doi : 10.2307 / 1970953 . JSTOR 1970953 .
- ^ Waldschmidt, M. (2009). "Palabras y trascendencia". En WWL Chen; WT Gowers; H. Halbertstam; WM Schmidt; RC Vaughan (eds.). Teoría analítica de números: ensayos en honor a Klaus Roth (PDF) . Prensa de la Universidad de Cambridge. Sección 31, pág. 449–470.
- ^ Khinchin, AI (1964). Fracciones continuas . Prensa de la Universidad de Chicago.
- ^ Graham Everest, Alf van der Poorten, Igor Shparlinski, Secuencias de recurrencia de Thomas WardAMS 2003, p 236.
- ^ Mkaouar, M. (1995). "Sur le développement en fracción continue de la série de Baum et Sweet" . Toro. Soc. Matemáticas. Francia . 123 (3): 361–374. doi : 10.24033 / bsmf.2264 .
- ^ Yao, J.-Y. (1997). "Critères de non-automaticité et leurs aplicaciones" . Acta Arith . 80 (3): 237–248. doi : 10.4064 / aa-80-3-237-248 .
- ^ Allouche y Shallit (2003) p 210.
- ^ a b Allouche, J .-. P. (1993). "Autómatas finitos y aritmética". Séminaire Lotharingien de Combinatoire : 23.
- ^ Allouche y Shallit (2003) p 176.
Referencias
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . ISBN 978-0-521-82332-6. Zbl 1086.11015 .