Secuencia Thue-Morse

En matemáticas, la secuencia Thue-Morse o la secuencia Prouhet-Thue-Morse o la secuencia de paridad es la secuencia binaria (una secuencia infinita de 0 y 1) obtenido comenzando con 0 y añadiendo sucesivamente el complemento booleano de la secuencia obtenida hasta el momento. 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....

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

Definición

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

Definición directa

Para calcular el nésimo elemento t_n, escribe 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. Es decir, t_n es el bit de paridad par para n. John H. Conway et al. números llamados n que satisfacen 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 malvado y t_n = 1 si n es Un número odioso.

Generación rápida de secuencias

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 la representación de n − 1. 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:

def generate_sequence()seq_length: int): ""Thue-Morse sequence."" valor = 0 para n = 0 a seq_length-1 por 1: # Nota: asume un número uniforme de bits en el tamaño de la palabra, y el complemento aritmético de dos para que cuando n == 0, x es extraño (por ejemplo 31 o 63) x = index_of_highest_one_bit()n ^ ()n - 1) si ()x " 1) == 0): # Bit index is even, so toggle value valor = 1 - valor rendimiento valor

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

Relación de recurrencia

La secuencia Thue-Morse es la secuencia t_n que satisface la relación de recurrencia

${displaystyle {begin{aligned}t_{0} limit=0,\t_{2n}duc=t_{n},t_{2n+1} âTMa=1-t_{n},end{aligned}}$

para todos los números enteros no negativos n.

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 hayan especificado los primeros 2ⁿ elementos, formando una cadena s, luego los siguientes 2ⁿ deben formar la negación bit a bit de s. Ahora hemos definido los primeros 2ⁿ⁺¹ elementos y recurrimos.

Detallando los primeros pasos:

• Empezamos con 0.
• La negación del bitwise de 0 es 1.
• Combinando estos, los primeros 2 elementos son 01.
• La negación del 01 es 10.
• Combinando estos, los primeros 4 elementos son 0110.
• La negación del bitwise de 0110 es 1001.
• Combinando estos, los primeros 8 elementos son 01101001.
• Y así.

Así que

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

Producto infinito

La secuencia también se puede definir mediante:

${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 elemento jésimo si comenzamos en j = 0.

Propiedades

La secuencia Thue-Morse contiene muchos cuadrados: instancias de la cadena ${displaystyle XX}$, donde ${displaystyle X}$ denota la cuerda ${displaystyle A}$, ${displaystyle {fnK}}$, ${displaystyle A{overline {A}A}$, o ${displaystyle {fnK}A {fnMicrosoft}A {fnMicrosoft} {A}}$, donde ${displaystyle A=T_{k}$ para algunos ${displaystyle kgeq 0}$ y ${displaystyle {fnK}}$ es la negación del bitwise ${displaystyle A}$. Por ejemplo, si ${displaystyle k=0}$, entonces ${displaystyle A=T_{0}=0}$. El cuadrado ${displaystyle A{overline {A}AA{overline {A}A=010010}$ aparece ${displaystyle T}$ empezando en el 16. Desde todos los cuadrados en ${displaystyle T}$ se obtienen repitiendo una de estas 4 cuerdas, todas tienen longitud ${displaystyle 2^{n}$ o ${displaystyle 3cdot 2^{n}$ para algunos ${displaystyle ngeq 0}$. ${displaystyle T}$ no cubos: instancias de ${displaystyle XXX}$. No hay cuadrados superpuestos: instancias de ${displaystyle 0X0X0}$ o ${displaystyle 1X1X1}$. El exponente crítico de ${displaystyle T}$ 2.

La secuencia Thue-Morse es una palabra uniformemente recurrente: dada cualquier cadena finita X en la secuencia, hay cierta longitud n_X (a menudo mucho más largo que la longitud de X) de modo que X aparezca en cada bloque de longitud n_X. En particular, la secuencia Thue-Morse es uniformemente recurrente sin ser periódica o eventualmente periódica (es decir, periódica después de algún segmento inicial no periódico).

La secuencia T_2n es un palíndromo para cualquier n. Además, sea q_n una palabra obtenida contando los unos entre ceros consecutivos en T_{2. n}. Por ejemplo, q₁ = 2 y q₂ = 2102012. Dado que T_n no contiene cuadrados superpuestos, las palabras q_n son palabras palindrómicas sin cuadrados.

El morfismo Thue-Morse μ se define en el alfabeto {0,1} mediante el mapa de sustitución μ(0) = 01, μ(1) = 10: cada 0 en una secuencia se reemplaza por 01 y cada 1 por 10. Si T es la secuencia de Thue-Morse, entonces μ (T) también es T. Por tanto, T es un punto fijo de μ. El morfismo μ es un morfismo prolongable sobre el monoide libre {0,1}^∗ con T como punto fijo: T es esencialmente el único punto fijo de μ; el único otro punto fijo es la negación bit a bit de T, que es simplemente la secuencia de 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 potencias formal

${displaystyle t(Z)=sum _{n=0}infty$

Esta serie de potencias es algebraica sobre el campo de funciones racionales y satisface la ecuación

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

En teoría de juegos combinatorios

El conjunto de números malvados (números ${displaystyle n}$ con ${displaystyle T_{n}=0}$) forma un subespacial de los enteros no negativos bajo nim-addición (sujeto bits o exclusivos). Para el juego de Kayles, los valores de nim malvados ocurren por pocas posiciones (finitamente muchas) en el juego, con todas las posiciones restantes que tienen valores de nim odiosos.

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 _{xin S_{0}x^{i}=sum _{xin S_{1}x^{i}$ para todos los enteros i de 1 a 1 k.

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

• S₀ consiste en los enteros n dentro S para la cual t_n = 0,
• S₁ consiste en los enteros n dentro S para la cual 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 múltiplo de 2^k+1 no es estrictamente necesaria: hay algunos casos adicionales para los cuales existe solución. Sin embargo, garantiza una propiedad más sólida: si se cumple la condición, entonces el conjunto de késimas potencias de cualquier conjunto de N números en progresión aritmética se puede dividir en dos conjuntos. con sumas iguales. Esto se deriva 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 de Thue-Morse y el problema de Prouhet-Tarry-Escott a particiones en más de dos partes, consulte Bolker, Offner, Richman y Zara, "The Prouhet-Tarry-Escott problem and generalized Thue –Secuencias Morse".

Fractales y gráficos de 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 estados del programa:

• Si t()n) = 0, adelante por una unidad,
• Si t()n) = 1, girar por un ángulo de π/3 radians (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 siguiendo las siguientes instrucciones:

• Si t()n) = 0, girar por un ángulo de π radians (180°),
• Si t()n) = 1, avanzar por una unidad, luego girar por un ángulo de π/3 radians.

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 artículos en disputa entre dos partes que están de acuerdo sobre los artículos' valores relativos, Brams y Taylor sugirieron un método que llamaron alternancia equilibrada, o turnarse, turnarse, turnarse..., como una manera de eludir el favoritismo inherente cuando una parte elige antes que el otro. Un ejemplo mostró cómo una pareja que se divorcia podría llegar a un acuerdo justo en la distribución de bienes de propiedad conjunta. Las partes se turnarían para ser las primeras en elegir en diferentes puntos del proceso de selección: Ann elige un elemento, luego Ben, luego Ben elige un elemento y luego Ann.

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 manera 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 Tn como funciones escalonadas en el intervalo [0,1] y describió su relación con las funciones de Walsh y Rademacher. Demostró que la nésima derivada se puede expresar en términos de T_n. Como consecuencia, la función escalonada que surge de T_n es ortogonal a polinomios de orden n − 1. Una consecuencia de este resultado es que a El recurso cuyo valor se expresa como una función continua monótonamente decreciente se asigna de manera más justa utilizando una secuencia que converge a Thue-Morse a medida que la función se vuelve más plana. Un ejemplo mostró cómo servir tazas de café de igual concentración desde una jarra con un gradiente de concentración no lineal, lo que dio lugar a un artículo caprichoso en la prensa popular.

Joshua Cooper y Aaron Dutle demostraron por qué el orden Thue-Morse proporciona un resultado justo para eventos discretos. Consideraron que 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 duelista exigiría una oportunidad de disparar tan pronto como la probabilidad a priori de ganar del otro excediera la suya. Demostraron que, cuando la probabilidad de acertar de los duelistas se acerca a cero, la secuencia de disparo converge a la secuencia Thue-Morse. Al hacerlo, demostraron que el orden Thue-Morse produce un resultado justo no sólo para secuencias Tn de longitud 2ⁿ, sino también para 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 secuenciación equitativa, porque la alternancia estricta a menudo da una ventaja injusta a un equipo. Ignacio Palacios-Huerta propuso cambiar el orden secuencial a Thue-Morse para mejorar la equidad ex post de varias competiciones de torneos, como la secuencia de patadas en la tanda de penales en el fútbol. Hizo una serie de experimentos de campo con jugadores profesionales y descubrió que el equipo que pateaba primero ganaba el 60% de los juegos usando ABAB (o T₁), el 54% usando ABBA (o T₂), y el 51 % utiliza Thue–Morse completo (o T_n). Como resultado, ABBA está pasando por extensas pruebas en la FIFA (Campeonatos de Europa y del Mundo) y en la Federación Inglesa de fútbol profesional (Copa EFL). También se ha descubierto que un patrón de servicio ABBA mejora la imparcialidad de los desempates en el tenis. En el remo competitivo, T₂ es la única disposición de los miembros de la tripulación de remo a babor y estribor que elimina las fuerzas transversales (y, por lo tanto, el movimiento lateral) en una regata de cuatro miembros sin timonel. barco, mientras que T₃ es uno de los cuatro únicos aparejos que evitan el movimiento en un barco de ocho miembros.

La equidad es especialmente importante en los drafts de jugadores. Muchas ligas deportivas profesionales intentan lograr la paridad competitiva dando selecciones más tempranas en cada ronda a los equipos más débiles. Por el contrario, las ligas de fútbol de fantasía no tienen ningún desequilibrio preexistente que corregir, por lo que a menudo utilizan un draft de “serpiente” (hacia adelante, hacia atrás, etc.; o T₁). Ian Allan argumentó que una “reversión de 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 partido de baloncesto es 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.

Colisiones de hash

Los 2^k bits iniciales de la secuencia Thue-Morse se asignan a 0 mediante una amplia clase de polinomio. funciones hash módulo una potencia de dos, lo que puede provocar colisiones hash.

Historia

La secuencia Thue-Morse fue estudiada por primera vez por Eugène Prouhet [fr] en 1851, quien lo aplicó a la teoría de números. Sin embargo, Prouhet no mencionó explícitamente la secuencia; esto quedó en manos de Axel Thue en 1906, quien lo utilizó para fundar el estudio de la combinatoria de las palabras. La secuencia sólo llamó 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 y profesor de matemáticas, lo descubrió en 1929 en una aplicación al ajedrez: utilizando su propiedad libre de cubos (ver arriba), mostró cómo eludir la regla de la triple repetición destinada a evitar partidas infinitamente prolongadas. declarando empate la repetición de movimientos. En ese momento, se requería que los estados consecutivos de la junta directiva fueran idénticos para activar la regla; Posteriormente, la regla se modificó para que la misma posición del tablero se repitiera tres veces en cualquier punto, ya que la secuencia muestra que el criterio consecutivo se puede evadir para siempre.