Sucesión de Thue-Morse
# 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. 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..._2$ = $0.41245403364..._{10}$

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 (+).

De esta forma, el primer elemento es 0. Luego, una vez que se han especificado los primeros $2^n$ elementos, formando una cadena s, entonces los siguientes $2^n$ elementos deben formar la negación a nivel de bit de s. Ahora se han definido los primeros $2^{n+1}$ 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$ = 0.
* $T_1$ = 01.
* $T_2$ = 0110.
* $T_3$ = 01101001.
* $T_4$ = 0110100110010110.
* $T_5$ = 01101001100101101001011001101001.
* $T_6$ = 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). 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. El exponente crítico es 2.

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_1$ = 2 y $q_2$ = 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 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

    $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. 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.

