Secuencia Baum-Sweet

Secuencia matemática de 1 y 0

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 0 consecutivos de longitud impar;

b _n = 0 en caso contrario;

para n ≥ 0. ^[1]

Por ejemplo, b ₄ = 1 porque la representación binaria de 4 es 100, que solo contiene un bloque de 0 consecutivos de longitud 2; mientras que b ₅ = 0 porque la representación binaria de 5 es 101, que contiene un bloque de 0 consecutivos de longitud 1.

A partir de n = 0, los primeros términos de la secuencia Baum-Sweet son:

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (secuencia A086747 en la OEIS )

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. Todavía no se conoce un contraejemplo a esta conjetura. ^{[3] [4]} El artículo de Baum y Sweet mostró que la misma expectativa no se cumple para las series de potencias algebraicas . Dieron un ejemplo de serie de potencias cúbicas en cuyos 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 la extensión del campo asociado con el real algebraico en la conjetura de Khinchin). ${\displaystyle \mathbb {F} _{2}((X^{-1}))}$

Una de las series consideradas en el artículo de Baum y Sweet es una raíz de

${\displaystyle f^{3}+x^{-1}f+1=0.}$^{[2] [5]}

Los autores muestran que, mediante el lema de Hensel , existe una raíz única en porque al reducir la ecuación definitoria de módulo se obtiene , que se factoriza como ${\displaystyle \mathbb {F} _{2}((X^{-1}))}$ ${\displaystyle f}$ ${\displaystyle X^{-1}}$ ${\displaystyle f^{3}+1}$

${\displaystyle f^{3}+1=(f+1)(f^{2}+f+1).}$

Luego prueban que esta raíz única tiene cocientes parciales de grado . Antes de hacerlo, afirman (en la observación que sigue al Teorema 2, pág. 598) ^[2] que la raíz se puede escribir en la forma ${\displaystyle \leq 2}$

${\displaystyle f=\sum _{k\geq 0}f_{i}X^{-k}}$

donde y para si y solo si la expansión binaria de contiene solo bloques de longitud par de 's. Este es el origen de la secuencia de Baum-Sweet. ${\displaystyle f_{0}=1}$ ${\displaystyle f_{k}=1}$ ${\displaystyle k\geq 1}$ ${\displaystyle n}$ ${\displaystyle 0}$

Mkaouar ^[6] y Yao ^[7] demostraron que los cocientes parciales de la fracción continua anterior no forman una secuencia automática. ^[8] Sin embargo, la secuencia de cocientes parciales puede generarse mediante un morfismo no uniforme. ^[9] ${\displaystyle f}$

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 sucesión de Baum–Sweet se puede hallar recursivamente de la siguiente manera. Si n = m ·4 ^k , donde m no es divisible por 4 (o es 0), entonces

${\displaystyle b_{n}={\begin{cases}1&{\text{if }}n=0\\0&{\text{if }}m{\text{ is even}}\\b_{(m-1)/2}&{\text{if }}m{\text{ is odd}}.\end{cases}}}$

Por lo tanto, b ₇₆ = b ₉ = b ₄ = b ₀ = 1, lo que se puede verificar 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 de morfismo se puede ver que la palabra Baum–Sweet contiene bloques de 0 consecutivos de cualquier longitud ( b _n  = 0 para todos 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, mediante el pequeño teorema de Cobham, la palabra Baum-Sweet puede expresarse como una codificación aplicada al punto fijo de un morfismo uniforme . De hecho, el morfismo ${\displaystyle \tau }$ ${\displaystyle \varphi }$

${\displaystyle \varphi (A)=AB,\varphi (B)=CB,\varphi (C)=BD,\varphi (D)=DD}$

y codificación

${\displaystyle \tau (A)=1,\tau (B)=1,\tau (C)=0,\tau (D)=0}$

generar la palabra de esa manera. ^[10]

Notas

1. Weisstein, Eric W. "Baum: dulce secuencia". MundoMatemático .
2. Baum, Leonard E.; Sweet, Melvin M. (1976). "Fracciones continuas de series de potencias algebraicas en característica 2". Anales de matemáticas . 103 (3): 593–610. doi :10.2307/1970953. JSTOR  1970953.
3. 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) . Cambridge University Press. Sección 31, pág. 449–470.
4. Khinchin, AI (1964). Fracciones continuas . Prensa de la Universidad de Chicago.
5. Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward Recurrence Sequences AMS 2003, p 236.
6. Mkaouar, M. (1995). "Sur le desarrollo en fracción continúa de la serie de Baum et Sweet". Toro. Soc. Matemáticas. Francia . 123 (3): 361–374. doi : 10.24033/bsmf.2264 .
7. Yao, J.-Y. (1997). "Critères de non-automaticité et leurs apps". Acta Arith . 80 (3): 237–248. doi : 10.4064/aa-80-3-237-248 .
8. Allouche y Shallit (2003) pág. 210.
9. Allouche, J.-.P. (1993). "Autómatas finitos y aritmética". Seminario Lotharingien de Combinatoire : 23.
10. Allouche y Shallit (2003) pág. 176.

Referencias

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge University Press . ISBN 978-0-521-82332-6.Zbl 1086.11015  .