Sucesión de Thue-Morse

En matemáticas, la sucesión de Thue-Morse (también conocida como sucesión de Prouhet-Thue-Morse) es una sucesión de dígitos binarios que si se concatenan produce una secuencia con segmentos iniciales alternos. La secuencia se obtiene comenzando con un cero y añadiendo sucesivamente el complemento Booleano de la secuencia que existe al momento. De esta forma, la secuencia comienza con 0, 01, 0110, 01101001, 0110100110010110...(sucesión A010060 en OEIS)

Definición

Existen varias definiciones equivalentes de la sucesión de Thue-Morse:

Definición directa

Para calcular el n^ésimo elemento t_n, se escribe el número n en binario. Si el total de números 1 en esta expansión binaria es impar, entonces t_n = 1; si es par, entonces t_n = 0.^[1] Es por esta razón que John H. Conway et al. le llamó a los números n que satisfacen t_n = 1 números odiosos (basándose en la palabra inglesa odd, "impar") y a los números que satisfacen t_n = 0 como números malignos (basándose en la palabra inglesa even, "par").

Relación de recurrencia

Esta secuencia se obtiene mediante una sucesión de dígitos binarios $s=\{d_{0},d_{1},...d_{n}\}$ que satisface la siguiente relación de recurrencia:

d_{0}=0

d_{2n}=d_{n}

d_{2n+1}=1-d_{n}

Para todo valor entero positivo de n.

Es decir, si representamos los dígitos binarios como 0 y 1 la secuencia de Thue-Morse tiene la siguiente forma:

01101001100101101001011001101001...

Esta secuencia, tomada como la parte decimal de un número en base 2 es conocida como constante de Thue-Morse:

0,01101001100101101001011001101001...₂ = 0.41245403364...₁₀

que es un número trascendental como $e$ o como $\pi$ .

Caracterización a través de negación a nivel de bits

Una definición alternativa es a través de un algoritmo que utiliza el negador binario a nivel de bit (~) y la concatenación de cadenas de dígitos (+).

 1. X:= 0.
 2. REPETIR MIENTRAS LONGITUD(X) < LONGITUD_TERMINAL
 3.    Y:= ~X
 4.    X:= X+Y
 5. DEVOLVER X

De esta forma, el primer elemento es 0. Luego, una vez que se han especificado los primeros 2ⁿ elementos, formando una cadena s, entonces los siguientes 2ⁿ elementos deben formar la negación a nivel de bit de s. Ahora se han definido los primeros 2ⁿ⁺¹ elementos y se repite la operación.

En particular, estos primeros pasos son los siguientes:

Se empieza con un 0.
La negación a nivel de bit de 0 es 1.
Al combinar (o concatenar) éstos, los primeros elementos son 01.
La negación a nivel de bit de 01 es 10.
Al combinar éstos, los primeros 4 elementos son 0110.
La negación a nivel de bit de 0110 es 1001.
Al combinar éstos, los primeros 8 elementos son 01101001.
Y así sucesivamente.

De esta forma,

T₀ = 0.
T₁ = 01.
T₂ = 0110.
T₃ = 01101001.
T₄ = 0110100110010110.
T₅ = 01101001100101101001011001101001.
T₆ = 0110100110010110100101100110100110010110011010010110100110010110.
Y así sucesivamente.

Producto infinito

La sucesión también se puede definir mediante el siguiente producto:

\prod _{i=0}^{\infty }(1-x^{2^{i}})=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j}{\mbox{,}}\!

donde t_j es el j-simo elemento si comenzamos en j = 0.

Algunas propiedades

Dado que cada bloque en la secuencia de Thue-Morse se define formando una negación binaria del comienzo de la secuencia, y que esta operación se repite al comienzo del siguiente bloque, la secuencia está llena de cuadrados: ocurrencias de la cadena XX, donde X es una cadena de dígitos determinada. En efecto, $X$ es una cadena así descrita si y sólo si $X=A,\,{\overline {A}},\,A{\overline {A}}A,$ o ${\overline {A}}A{\overline {A}}$ donde $A=T_{k}$ para algún $k\geq 0$ y ${\overline {A}}$ denota la negación a nivel de bit de $A$ (intercambiar los ceros y los unos).^[2] Por ejemplo, con $k=0$ , tenemos que $\ A=T_{0}=0$ , y el cuadrado $A{\overline {A}}AA{\overline {A}}A=010010$ aparece en $T$ comenzando en el bit número 16. (De esta forma, los cuadrados en $T$ tienen una longitud que es una potencia de 2 o el triple de una potencia de 2.) Sin embargo no hay cubos: ocurrencias de la cadena XXX. Tampoco hay cuadrados solapados: ocurrencias de 0X0X0 o 1X1X1.^[3]^[4] El exponente crítico es 2.^[5]

Nótese que T_2n es un número capicúa para cualquier n > 1. Más allá, sea q_n una palabra obtenida de T_2n al contar los unos entre ceros consecutivos. Por ejemplo, q₁ = 2 y q₂ = 2102012 y así sucesivamente. Las palabras T_n no contienen cuadrados que se traslapan y en consecuencia las "palabras" q_nson capicúas libres de cuadrados

En realidad, la afirmación de que la secuencia de Thue-Morse está llena de cuadrados puede ser más precisa: se trata de una secuencia recursiva, lo que quiere decir que para toda cadena de dígitos finita X en la secuencia, existe una longitud n_X determinada (normalmente mucho más larga que la de X) tal que X aparece en cada bloque de longitud n. La forma más sencilla de crear una secuencia recursiva es formar una sucesión periódica donde la secuencia se repite completamente de nuevo después de un número m dado de pasos. Esto implica que n_X se puede asignar a cualquier múltiplo de m que sea mayor que dos veces la longitud de X. Pero la secuencia de Thue-Morse es recursiva sin ser periódica, ni siquiera parcialmente periódica (una secuencia parcialmente periódica se repite completamente después de una fase inicial aperiódica).

El morfismo Thue Morse se define como la función f del conjunto de secuencias binarias a sí misma reemplazando cada 0 en una secuencia con 01 y cada 1 con 10^[6] Entonces, si T es la sucesión de Thue-Morse, entoncesf(T) es T otra vez; esto es; T es un punto fijo de f. La función f es un morfismo prolongable en el monoide libre {0,1}^∗ con T como punto fijo: de hecho T es esencialmente el único punto fijo de f; el único otro punto fijo es la negación por pares de bits de T, la cual essimplemente la sucesión de Thue-Morse sobre (1, 0) en lugar de (0, 1). Esta propiedad puede ser generalizada al concepto de una secuencia automática.

La secuencia generadora de T sobre el campo binario es la serie formal de potencias:

t(Z)=\sum _{n=0}^{\infty }T(n)Z^{n}\ .

Esta serie de potencias es algebraica sobre el campo de las series formales de potencias, satisfaciendo la ecuación^[7]

Z+(1+Z)^{2}t+(1+Z)^{3}t^{2}=0

División equitativa

En su libro acerca del problema de la división justa, Steven Brams y Alan Taylor mencionan la secuencia Thue-Morse pero sin identificarla por su nombre. Cuando hay que distribuir entre 2 personas una cantidad de objetos cuyo valor ya se había acordado, sugirieron un método al que llamaron "alternación balanceada" o sea cambiar el orden de selección cada vez que se termina una secuencia de selección, como una manera de evitar la ventaja que tiene el que escoge primero. El ejemplo que pusieron fue el de una pareja que se divorcia, para repartirse los bienes, el primero que escoja debe escoger segundo a la siguiente ronda.^[8] La secuencia de Thue-Morse tiene muchas aplicaciones para la distribución o partición binaria, por ejemplo para escoger los miembros de dos equipos de trabajo, de deporte. Para servir 2 tazas de café desde una jarra, herencias binarias (base 2), etc.

Historia

La sucesión de Thue-Morse fue estudiada por primera vez por P. Prouhet en 1851, que la aplicó a la teoría de números. Sin embargo, Prouhet no la mencionó de forma explícita. Quien sí lo hizo fue Axel Thue en 1906, en un estudio de la combinatoria lingüística. Dado que Thue publicó su trabajo originalmente en noruego, el análisis de la misma permaneció en la ignorancia general del público internacional, al que sólo llegaría cuando otro matemático (Marston Morse) la aplicó en 1921 a sus trabajos sobre geometría diferencial.

En realidad, dada la aparente simplicidad de su formulación, la secuencia ha sido redescubiera, redefinida y estudiada de forma independiente en muchas ocasiones; y no siempre en el contexto de la investigación matemática. Por ejemplo el Gran Maestro del ajedrez Max Euwe la descubrió de forma independiente en 1929 aplicándola a desarrollos teóricos del ajedrez.

Referencias

↑ Allouche & Shallit (2003) p.15
↑ Brlek, Srećko (1989). «Enumeration of Factors in the Thue-Morse Word». Discrete Applied Mathematics 24: 83-96. doi:10.1016/0166-218x(92)90274-e.
↑ Lothaire (2011) p.113
↑ Pytheas Fogg (2002) p.103
↑ Krieger, Dalia (2006). «On critical exponents in fixed points of non-erasing morphisms». En Ibarra, Oscar H.; Dang, Zhe, eds. Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, EUA, Junio 26-29, 2006. Lecture Notes in Computer Science 4036. Springer-Verlag. pp. 280-291. ISBN 3-540-35428-X. Zbl 1227.68074.
↑ Berstel (2009) p.70
↑ Berstel (2009) p.80
↑ Brams; Taylor (1999). sfnp.

Enlaces externos

Weisstein, Eric W. «Thue-Morse Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
The Ubiquitous Prouhet-Thue-Morse Sequence. Allouche, J.-P. & Shallit, J. O. Aplicaciones e Historia de la secuencia.
(sucesión A010060 en OEIS)
(sucesión A001285 en OEIS),para un estudio sobre la secuencia de (1,2)

Datos: Q1477120
Multimedia: Thue-Morse sequence / Q1477120

[AS15-1] Allouche & Shallit (2003) p.15

[2] Brlek, Srećko (1989). «Enumeration of Factors in the Thue-Morse Word». Discrete Applied Mathematics 24: 83-96. doi:10.1016/0166-218x(92)90274-e.

[ACOW113-3] Lothaire (2011) p.113

[PF103-4] Pytheas Fogg (2002) p.103

[5] Krieger, Dalia (2006). «On critical exponents in fixed points of non-erasing morphisms». En Ibarra, Oscar H.; Dang, Zhe, eds. Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, EUA, Junio 26-29, 2006. Lecture Notes in Computer Science 4036. Springer-Verlag. pp. 280-291. ISBN 3-540-35428-X. Zbl 1227.68074.

[BLRS70-6] Berstel (2009) p.70

[BLRS80-7] Berstel (2009) p.80

[8] Brams; Taylor (1999). sfnp.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]