Sucesión de Thue-Morse

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.

Definición

Esta secuencia se obtiene mediante una sucesión de dígitos binarios s = {d₀,d₁,...d_n} tal que:

d₀ = 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 π.

Una definición alternativa podría ser el siguiente 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

Y 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; sin embargo no hay cubos: ocurrencias de la cadena XXX. Tampoco hay cuadrados solapados: ocurrencias de 0X0X0 o 1X1X1.

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.

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.

Enlaces externos

(Inglés)

• Thue-Morse Sequence Propiedades de la sucesión en Mathworld.
• The Ubiquitous Prouhet-Thue-Morse Sequence. Allouche, J.-P. & Shallit, J. O. Aplicaciones e Historia de la secuencia.
• MathWorld: Thue-Morse Sequence. Más aplicaciones
• (sucesión A010060 en OEIS)
• (sucesión A001285 en OEIS),para un estudio sobre la secuencia de (1,2)