Secuencia de Thue-Morse - Thue–Morse sequence

Este gráfico demuestra la composición repetitiva y complementaria de la secuencia Thue-Morse.

En matemáticas , la secuencia Thue-Morse , o secuencia Prouhet-Thue-Morse , es la secuencia binaria (una secuencia infinita de 0 y 1) que se obtiene comenzando con 0 y agregando sucesivamente el complemento booleano de la secuencia obtenida hasta ahora. Los primeros pasos de este procedimiento producen las cadenas 0, luego 01, 0110, 01101001, 0110100110010110, etc., que son prefijos de la secuencia Thue-Morse. Comienza la secuencia completa:

01101001100101101001011001101001 .... (secuencia A010060 en la OEIS )

La secuencia lleva el nombre de Axel Thue y Marston Morse .

Definición

Hay varias formas equivalentes de definir la secuencia Thue-Morse.

Definición directa

Al contar en binario, la suma de dígitos módulo 2 es la secuencia Thue-Morse

Para calcular el n- ésimo elemento t _n , escriba el número n en binario . Si el número de unos en esta expansión binaria es impar, entonces t _n  = 1, si es par, entonces t _n  = 0. Por esta razón, John H. Conway et al . números de clasificación n satisfactorios t _n  = 1 números odiosos (para impares ) y números para los cuales t _n  = 0 números malos (para pares ). En otras palabras, t _n  = 0 si n es un número maligno y t _n  = 1 si n es un número odioso .

Generación de secuencia rápida

Este método conduce a un método rápido para calcular la secuencia Thue-Morse: comience con t ₀  = 0 , y luego, para cada n , encuentre el bit de mayor orden en la representación binaria de n que sea diferente del mismo bit en el representación de n  - 1 . (Este bit se puede aislar dejando que x sea ​​el bit a bit exclusivo o de n y n  - 1 , desplazando x a la derecha un bit y calculando el valor exclusivo o de este desplazado con x .) Si este bit está en un índice par, t _n difiere de t _{n  - 1} y, por lo demás, es lo mismo que t _{n  - 1} .

En forma de pseudocódigo:

generateSequence(seqLength):
    value = 0
    for n = 0 to seqLength-1 by 1:     
        x = n ^ (n-1)                         
        if ((x ^ (x>>1)) & 0x55555555):
            value = 1 - value
        return value

El algoritmo resultante necesita un tiempo constante para generar cada elemento de secuencia, utilizando solo un número logarítmico de bits (número constante de palabras) de memoria.

Relación de recurrencia

La secuencia de Thue-Morse es la secuencia t _{n que} satisface la relación de recurrencia

${\ Displaystyle {\ begin {alineado} t_ {0} & = 0, \\ t_ {2n} & = t_ {n}, \\ t_ {2n + 1} & = 1-t_ {n}, \ end { alineado}}}$

para todos los enteros no negativos n .

Sistema L

Secuencia Thue-Morse generada por un sistema L

La secuencia Thue-Morse es una palabra mórfica : es el resultado del siguiente sistema Lindenmayer :

Caracterización mediante negación bit a bit

La secuencia Thue-Morse en la forma dada anteriormente, como una secuencia de bits , se puede definir de forma recursiva utilizando la operación de negación bit a bit . Entonces, el primer elemento es 0. Luego, una vez que se han especificado los primeros 2 ⁿ elementos, formando una cadena s , los siguientes 2 ⁿ elementos deben formar la negación bit a bit de s . Ahora hemos definido los primeros 2 ^{n +1} elementos, y recurrimos.

Detallando los primeros pasos en detalle:

• Empezamos con 0.
• La negación bit a bit de 0 es 1.
• Combinando estos, los primeros 2 elementos son 01.
• La negación bit a bit de 01 es 10.
• Combinando estos, los primeros 4 elementos son 0110.
• La negación bit a bit de 0110 es 1001.
• Combinando estos, los primeros 8 elementos son 01101001.
• Etcétera.

Entonces

• T ₀ = 0.
• T ₁ = 01.
• T ₂ = 0110.
• T ₃ = 01101001.
• T ₄ = 0110100110010110.
• T ₅ = 01101001100101101001011001101001.
• T ₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• Etcétera.

Producto infinito

La secuencia también se puede definir por:

${\ Displaystyle \ prod _ {i = 0} ^ {\ infty} \ left (1-x ^ {2 ^ {i}} \ right) = \ sum _ {j = 0} ^ {\ infty} (- 1 ) ^ {t_ {j}} x ^ {j},}$

donde t _j es el j- ésimo elemento si comenzamos en j = 0.

Algunas propiedades

Debido a que cada nuevo bloque en la secuencia Thue-Morse se define formando la negación bit a bit del principio, y esto se repite al comienzo del siguiente bloque, la secuencia Thue-Morse se llena de cuadrados : cadenas consecutivas que se repiten. Es decir, hay muchas instancias de XX , donde X es una cadena. De hecho, es una cadena de este tipo si y solo si o dónde para algunos y denota la negación bit a bit de (intercambio de 0 y 1). Por ejemplo, con , tenemos , y el cuadrado aparece comenzando en el bit 16. (Por lo tanto, los cuadrados en tienen una longitud de una potencia de 2 o 3 veces una potencia de 2.) Sin embargo, no hay cubos : instancias de XXX . Tampoco hay cuadrados superpuestos : instancias de 0 X 0 X 0 o 1 X 1 X 1. El exponente crítico es 2. ${\ Displaystyle X}$${\ Displaystyle X = A, \, {\ overline {A}}, \, A {\ overline {A}} A,}$${\ Displaystyle {\ overline {A}} A {\ overline {A}}}$${\ Displaystyle A = T_ {k}}$${\ Displaystyle k \ geq 0}$${\ Displaystyle {\ overline {A}}}$${\ Displaystyle A}$${\ Displaystyle k = 0}$${\ Displaystyle \ A = T_ {0} = 0}$${\ Displaystyle A {\ overline {A}} AA {\ overline {A}} A = 010010}$${\ Displaystyle T}$${\ Displaystyle T}$

La secuencia T _{2 n} es palíndromo para cualquier n . Además, sea q _n una palabra obtenida de T _{2 n} contando unos entre ceros consecutivos. Por ejemplo, q ₁ = 2 y q ₂ = 2102012 y así sucesivamente. En consecuencia, las palabras T _n no contienen cuadrados superpuestos , las palabras q _n son palabras libres de cuadrados palíndromos .

La afirmación anterior de que la secuencia Thue-Morse está "llena de cuadrados" puede ser precisa: es una palabra uniformemente recurrente , lo que significa que dada cualquier cadena finita X en la secuencia, hay una longitud n _X (a menudo mucho más larga que la longitud de X ) tal que X aparece en cada bloque de longitud N _X . La manera más fácil de hacer una secuencia recurrente es para formar una secuencia periódica , uno donde la secuencia se repite por completo después de un número dado m de pasos. Entonces n _X se puede ajustar a cualquier múltiplo de m que es mayor que dos veces la longitud de X . Pero la secuencia de Morse es uniformemente recurrente sin ser periódica, ni siquiera eventualmente periódica (es decir, periódica después de algún segmento inicial no periódico).

Definimos el morfismo Thue-Morse como la función f del conjunto de secuencias binarias a sí mismo reemplazando cada 0 en una secuencia con 01 y cada 1 con 10. Entonces, si T es la secuencia Thue-Morse, entonces f ( T ) es T de nuevo; es decir, 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 bit a bit de T , que es simplemente la secuencia Thue-Morse en (1,0) en lugar de en (0,1). Esta propiedad puede generalizarse al concepto de secuencia automática .

La serie generadora de T sobre el campo binario es la serie de potencia formal

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

Esta serie de potencias es algebraica sobre el campo de las funciones racionales, satisfaciendo la ecuación

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

En teoría combinatoria de juegos

El conjunto de números malvados (números con ) forma un subespacio de los enteros no negativos bajo nim-suma ( bit a bit o exclusivo ). Para el juego de Kayles , los valores nim malignos ocurren para pocas (finitas) posiciones en el juego, y todas las posiciones restantes tienen valores nim odiosos. ${\ Displaystyle n}$${\ Displaystyle t_ {n} = 0}$

El problema Prouhet-Tarry-Escott

El problema de Prouhet-Tarry-Escott se puede definir como: dado un entero positivo N y un entero no negativo k , dividir el conjunto S = {0, 1, ..., N -1} en dos subconjuntos disjuntos S ₀ y S ₁ que tienen sumas iguales de potencias hasta k, es decir:

${\ Displaystyle \ sum _ {x \ in S_ {0}} x ^ {i} = \ sum _ {x \ in S_ {1}} x ^ {i}}$para todos los enteros i de 1 a k .

Esto tiene una solución si N es un múltiplo de 2 ^{k +1} , dado por:

• S ₀ consiste en los enteros n en S para los cuales t _n = 0,
• S ₁ consiste en los números enteros n en S para los cuales t _n = 1.

Por ejemplo, para N = 8 y k = 2,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0 ² + 3 ² + 5 ² + 6 ² = 1 ² + 2 ² + 4 ² + 7 ² .

La condición que requiere que N sea ​​un múltiplo de 2 ^{k +1} no es estrictamente necesaria: hay algunos casos adicionales para los que existe una solución. Sin embargo, garantiza una propiedad más fuerte: si se cumple la condición, entonces el conjunto de k- ésimo potencias de cualquier conjunto de N números en progresión aritmética se puede dividir en dos conjuntos con sumas iguales. Esto se sigue directamente de la expansión dada por el teorema del binomio aplicado al binomio que representa el n- ésimo elemento de una progresión aritmética.

Para generalizaciones de la secuencia Thue-Morse y el problema Prouhet-Tarry-Escott a particiones en más de dos partes, véase Bolker, Offner, Richman y Zara, "El problema Prouhet-Tarry-Escott y secuencias Thue-Morse generalizadas".

Gráficos de fractales y tortugas

Usando gráficos de tortugas , se puede generar una curva si se programa un autómata con una secuencia. Cuando se utilizan miembros de la secuencia Thue-Morse para seleccionar los estados del programa:

• Si t ( n ) = 0, avanza una unidad,
• Si t ( n ) = 1, rotar en un ángulo de π / 3 radianes (60 °)

La curva resultante converge a la curva de Koch , una curva fractal de longitud infinita que contiene un área finita. Esto ilustra la naturaleza fractal de la secuencia Thue-Morse.

También es posible dibujar la curva con precisión usando las siguientes instrucciones:

• Si t ( n ) = 0, rotar en un ángulo de π radianes (180 °),
• Si t ( n ) = 1, avance una unidad, luego gire un ángulo de π / 3 radianes.

Secuenciación equitativa

En su libro sobre el problema de la división justa , Steven Brams y Alan Taylor invocaron la secuencia Thue-Morse pero no la identificaron como tal. Al asignar una pila de elementos en disputa entre dos partes que están de acuerdo en los valores relativos de los elementos, Brams y Taylor sugirieron un método que llamaron alternancia equilibrada , o turnarse para turnarse. . . , como una forma de eludir el favoritismo inherente cuando una parte elige antes que la otra. Un ejemplo mostró cómo una pareja divorciada podría llegar a un acuerdo justo en la distribución de artículos de propiedad conjunta. Las partes se turnarían para ser los primeros en elegir en diferentes puntos del proceso de selección: Ann elige un artículo, luego Ben lo hace, luego Ben elige un artículo y luego Ann lo hace.

Lionel Levine y Katherine E. Stange , en su discusión sobre cómo repartir equitativamente una comida compartida, como una cena etíope , propusieron la secuencia Thue-Morse como una forma de reducir la ventaja de moverse primero. Sugirieron que "sería interesante cuantificar la intuición de que el orden Thue-Morse tiende a producir un resultado justo".

Robert Richman abordó este problema, pero tampoco identificó la secuencia Thue-Morse como tal en el momento de la publicación. Presentó las secuencias T _n como funciones escalonadas en el intervalo [0,1] y describió su relación con las funciones de Walsh y Rademacher . Mostró que el n º derivada puede expresarse en términos de T _n . Como consecuencia, la función escalón que surge de T _n es ortogonal a los polinomios de orden n  - 1. Una consecuencia de este resultado es que un recurso cuyo valor se expresa como una función continua decreciente monótonamente se asigna de manera más justa usando una secuencia que converge a Thue – Morse a medida que la función se vuelve más plana . Un ejemplo mostró cómo verter tazas de café de igual intensidad desde una jarra con un gradiente de concentración no lineal , lo que provocó un artículo caprichoso en la prensa popular.

Joshua Cooper y Aaron Dutle demostraron por qué la orden Thue-Morse proporciona un resultado justo para eventos discretos. Consideraron la forma más justa de organizar un duelo de Galois , en el que cada uno de los tiradores tiene habilidades de tiro igualmente pobres. Cooper y Dutle postularon que cada duelo exigiría una oportunidad de disparar tan pronto como la probabilidad a priori de ganar del otro excediera la suya. Demostraron que, a medida que la probabilidad de golpe de los duenos se acerca a cero, la secuencia de disparo converge a la secuencia de Thue-Morse. Al hacerlo, demostraron que el orden Thue-Morse produce un resultado justo no solo para las secuencias T _n de longitud 2 ⁿ , sino también para las secuencias de cualquier longitud.

Por lo tanto, las matemáticas apoyan el uso de la secuencia Thue-Morse en lugar de alternar turnos cuando el objetivo es la equidad, pero los turnos anteriores difieren monótonamente de los posteriores en alguna cualidad significativa, ya sea que esa cualidad varíe de forma continua o discreta.

Las competiciones deportivas forman una clase importante de problemas de secuencia equitativa, porque la alternancia estricta a menudo otorga una ventaja injusta a un equipo. Ignacio Palacios-Huerta propuso cambiar el orden secuencial a Thue-Morse para mejorar la equidad ex post de varios torneos, como la secuencia de patadas de una tanda de penaltis en el fútbol. Hizo una serie de experimentos de campo con jugadores profesionales y descubrió que el equipo que pateó primero ganó el 60% de los juegos usando ABAB (o T ₁ ), el 54% usando ABBA (o T ₂ ) y el 51% usando Thue-Morse completo (o T _n ). Como resultado, ABBA se está sometiendo a extensas pruebas en la FIFA (campeonatos europeos y mundiales) y en el fútbol profesional de la Federación Inglesa ( Copa EFL ). También se ha descubierto que un patrón de servicio ABBA mejora la imparcialidad de los desempates de tenis . En el remo competitivo , T ₂ es la única disposición de miembros de la tripulación de remos de babor y estribor que elimina las fuerzas transversales (y por lo tanto el movimiento lateral) en un bote de carreras sin timonel de cuatro miembros, mientras que el T ₃ es uno de los únicos cuatro aparejos para evitar el movimiento en un barco de ocho miembros.

La equidad es especialmente importante en el draft de los jugadores . Muchas ligas deportivas profesionales intentan lograr la paridad competitiva dando selecciones anteriores en cada ronda a los equipos más débiles. Por el contrario, las ligas de fútbol de fantasía no tienen un desequilibrio preexistente que corregir, por lo que a menudo usan un draft de "serpiente" (hacia adelante, hacia atrás, etc .; o T ₁ ). Ian Allan argumentó que una “reversión de la tercera ronda” (hacia adelante, hacia atrás, hacia atrás, hacia adelante, etc. O T ₂ ) sería aún más justa. Richman sugirió que la forma más justa para que el "capitán A" y el "capitán B" elijan bandos para un juego de baloncesto es el T ₃ : el capitán A tiene la primera, cuarta, sexta y séptima opciones, mientras que el capitán B tiene la segunda, tercera, quinta y octava opciones.

Historia

La secuencia Thue-Morse fue estudiada por primera vez por Eugène Prouhet en 1851, quien la aplicó a la teoría de números . Sin embargo, Prouhet no mencionó la secuencia explícitamente; esto se dejó a Axel Thue en 1906, quien lo utilizó para fundar el estudio de la combinatoria en palabras . La secuencia solo atrajo la atención mundial con el trabajo de Marston Morse en 1921, cuando la aplicó a la geometría diferencial . La secuencia ha sido descubierta de forma independiente muchas veces, no siempre por investigadores matemáticos profesionales; por ejemplo, Max Euwe , un gran maestro de ajedrez , que ostentaba el título del Campeonato del Mundo de 1935 a 1937, y profesor de matemáticas , lo descubrió en 1929 en una aplicación al ajedrez : al usar su propiedad libre de cubos (ver arriba), mostró cómo para eludir la regla de repetición triple destinada a prevenir juegos infinitamente prolongados declarando que la repetición de movimientos es un empate. En ese momento, se requerían estados idénticos consecutivos de la placa para activar la regla; la regla se modificó posteriormente para que la misma posición del tablero se repitiera tres veces seguidas en cualquier punto, ya que la secuencia muestra que el criterio consecutivo se puede eludir para siempre.

Ver también

• Teorema de Dejean
• Función Fabius
• Código gris
• Constante de Komornik – Loreti
• Constante de Prouhet-Thue-Morse

Notas

Referencias

Otras lecturas

• Bugeaud, Yann (2012). Distribución módulo uno y aproximación diofántica . Cambridge Tracts in Mathematics. 193 . Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0. Zbl  1260.11001 .
• Lothaire, M. (2005). Combinatoria aplicada sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 105 . Una obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov , Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé. Cambridge: Cambridge University Press . ISBN 978-0-521-84802-2. Zbl  1133.68067 .

enlaces externos

• "Secuencia de Thue-Morse" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Secuencia de Thue-Morse" . MathWorld .
• Allouche, J.-P .; Shallit, JO La ubicua secuencia Prouhet-Thue-Morse . (contiene muchas aplicaciones y algo de historia)
• Secuencia Thue-Morse sobre (1,2) (secuencia A001285 en la OEIS )
• Secuencia OEIS A000069 (números extraños: números con un número impar de unos en su expansión binaria)
• Secuencia OEIS A001969 (Números malvados: números con un número par de unos en su expansión binaria)
• Reducir la influencia de la deriva de compensación de CC en IP analógicas mediante la secuencia Thue-Morse . Una aplicación técnica de la secuencia Thue-Morse
• MusiNum - La música en números . Freeware para generar música auto-similar basada en la secuencia Thue-Morse y secuencias numéricas relacionadas.
• Parker, Matt . "La secuencia de intercambio más justa de todos los tiempos" (video) . standupmaths . Consultado el 20 de enero de 2016 .