Sequência Thue-Morse - Thue–Morse sequence

Este gráfico demonstra a composição repetitiva e complementar da sequência Thue-Morse.

Em matemática , a sequência Thue-Morse , ou sequência Prouhet-Thue-Morse , é a sequência binária (uma sequência infinita de 0s e 1s) obtida começando com 0 e anexando sucessivamente o complemento booleano da sequência obtida até agora. As primeiras etapas deste procedimento geram as strings 0 e 01, 0110, 01101001, 0110100110010110 e assim por diante, que são prefixos da sequência Thue-Morse. A sequência completa começa:

01101001100101101001011001101001 .... (sequência A010060 no OEIS )

A sequência foi nomeada em homenagem a Axel Thue e Marston Morse .

Definição

Existem várias maneiras equivalentes de definir a sequência Thue-Morse.

Definição direta

Ao contar em binário, o módulo de soma de dígitos 2 é a sequência Thue-Morse

Para calcular o n- ésimo elemento t _n , escreva o número n em binário . Se o número de unidades nesta expansão binária for ímpar, então t _n  = 1, se par, então, t _n  = 0. Por esta razão, John H. Conway et al . números de telefone n satisfazendo t _n  = 1 números odiosos (para ímpar ) e números para os quais t _n  = 0 números ruins (para pares ). Em outras palavras, t _n  = 0 se n for um número mau e t _n  = 1 se n for um número odioso .

Geração de sequência rápida

Este método leva a um método rápido para calcular a sequência Thue-Morse: comece com t ₀  = 0 e, em seguida, para cada n , encontre o bit de ordem mais alta na representação binária de n que é diferente do mesmo bit no representação de n  - 1 . (Este bit pode ser isolado deixando x ser o bit a bit exclusivo ou de n e n  - 1 , deslocando x à direita em um bit e calculando o exclusivo ou desse valor deslocado com x .) Se este bit estiver em um índice par, t _n difere de t _{n  - 1} , caso contrário, é igual a t _{n  - 1} .

Na 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

O algoritmo resultante leva um tempo constante para gerar cada elemento da sequência, usando apenas um número logarítmico de bits (número constante de palavras) de memória.

Relação de recorrência

A sequência Thue-Morse é a sequência t _{n que} satisfaz a relação de recorrência

${\ displaystyle {\ begin {alinhados} t_ {0} & = 0, \\ t_ {2n} & = t_ {n}, \\ t_ {2n + 1} & = 1-t_ {n}, \ end { alinhado}}}$

para todos os inteiros não negativos n .

Sistema L

Sequência Thue-Morse gerada por um L-System

A sequência Thue-Morse é uma palavra mórfica : é a saída do seguinte sistema de Lindenmayer :

Caracterização usando negação bit a bit

A sequência Thue-Morse na forma dada acima, como uma sequência de bits , pode ser definida recursivamente usando a operação de negação bit a bit . Portanto, o primeiro elemento é 0. Então, uma vez que os primeiros 2 ⁿ elementos tenham sido especificados, formando uma string s , os próximos 2 ⁿ elementos devem formar a negação bit a bit de s . Agora definimos os primeiros 2 ^{n +1} elementos e recursamos.

Descrevendo as primeiras etapas em detalhes:

• Começamos com 0.
• A negação bit a bit de 0 é 1.
• Combinando estes, os primeiros 2 elementos são 01.
• A negação bit a bit de 01 é 10.
• Combinando estes, os primeiros 4 elementos são 0110.
• A negação bit a bit de 0110 é 1001.
• Combinando estes, os primeiros 8 elementos são 01101001.
• E assim por diante.

Então

• T ₀ = 0.
• T ₁ = 01.
• T ₂ = 0,110.
• T ₃ = 01101001.
• T ₄ = 0110100110010110.
• T ₅ = 01101001100101101001011001101001.
• T ₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• E assim por diante.

Produto infinito

A sequência também pode ser definida por:

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

onde t _j é o j ésimo elemento se começarmos em j = 0.

Algumas propriedades

Como cada novo bloco na sequência Thue-Morse é definido pela formação da negação bit a bit do início, e isso é repetido no início do próximo bloco, a sequência Thue-Morse é preenchida com quadrados : strings consecutivas que são repetidas. Ou seja, existem muitas ocorrências de XX , onde X é alguma string. Na verdade, essa string é se e somente se ou onde para alguns e denota a negação bit a bit de (intercâmbio 0s e 1s). Por exemplo, com , temos , e o quadrado aparece começando no 16º bit. (Assim, os quadrados têm comprimento ou uma potência de 2 ou 3 vezes uma potência de 2.) No entanto, não há cubos : instâncias de XXX . Também não há quadrados sobrepostos : instâncias de 0 X 0 X 0 ou 1 X 1 X 1. O expoente crítico é 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}$

A sequência de T _{2 n} é palindrome para qualquer n . Além disso, deixar que q _n ser uma palavra obtido a partir de T _{2 n} contando os entre zeros consecutivos. Por exemplo, q ₁ = 2 e q ₂ = 2102012 e assim por diante. Consequentemente, as palavras T _n não contêm quadrados sobrepostos , as palavras q _n são palíndromos sem quadrados .

A afirmação acima de que a sequência Thue-Morse é "preenchida com quadrados" pode ser mais precisa: é uma palavra uniformemente recorrente , o que significa que dada qualquer string finita X na sequência, há algum comprimento n _X (muitas vezes muito mais longo do que o comprimento de X ) de tal modo que X aparece em cada bloco de comprimento n _X . A maneira mais fácil de fazer uma sequência recorrente é formar uma sequência periódica , em que a sequência se repete inteiramente após um determinado número m de etapas. Então n _X pode ser definido como qualquer múltiplo de m , que é maior do que duas vezes o comprimento de X . Mas a sequência de Morse é uniformemente recorrente sem ser periódica, nem mesmo eventualmente periódica (significando periódica após algum segmento inicial não periódico).

Definimos o morfismo de Thue-Morse como a função f do conjunto de sequências binárias para si mesma, substituindo cada 0 em uma sequência por 01 e cada 1 por 10. Então, se T for a sequência Thue-Morse, então f ( T ) é T novamente; isto é, T é um ponto fixo de f . A função f é um morfismo prolongável no monóide livre {0,1} ^∗ com T como ponto fixo: de fato, T é essencialmente o único ponto fixo de f ; o único outro ponto fixo é a negação bit a bit de T , que é simplesmente a sequência Thue-Morse em (1,0) em vez de em (0,1). Essa propriedade pode ser generalizada para o conceito de uma seqüência automática .

A série geradora de T sobre o campo binário é a série de potências formal

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

Esta série de potências é algébrica sobre o campo das funções racionais, satisfazendo a equação

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

Na teoria dos jogos combinatórios

O conjunto de números malignos (números com ) forma um subespaço dos inteiros não negativos sob a adição de nim ( exclusivo ou bit a bit ). Para o jogo de Kayles , valores nim malignos ocorrem para poucas (finitamente muitas) posições no jogo, com todas as posições restantes tendo valores nim odiosos. ${\ displaystyle n}$${\ displaystyle t_ {n} = 0}$

O problema Prouhet – Tarry – Escott

O problema de Prouhet – Tarry – Escott pode ser definido como: dado um inteiro positivo N e um inteiro não negativo k , particionar o conjunto S = {0, 1, ..., N -1} em dois subconjuntos disjuntos S ₀ e S ₁ que têm somas iguais de potências até k, ou seja:

${\ displaystyle \ sum _ {x \ in S_ {0}} x ^ {i} = \ sum _ {x \ in S_ {1}} x ^ {i}}$para todos os inteiros i de 1 a k .

Isso tem uma solução se N for um múltiplo de 2 ^{k +1} , dado por:

• S ₀ consiste nos inteiros n em S para os quais t _n = 0,
• S ₁ consiste nos inteiros n em S para os quais t _n = 1.

Por exemplo, para N = 8 e k = 2,

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

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

A condição que exige que N seja um múltiplo de 2 ^{k +1} não é estritamente necessária: existem outros casos para os quais existe uma solução. No entanto, garante uma propriedade mais forte: se a condição for satisfeita, o conjunto de k- ésimas potências de qualquer conjunto de N números em progressão aritmética pode ser dividido em dois conjuntos com somas iguais. Isto resulta directamente da expansão dado pelo teorema binário aplicado ao binomial representando o n ésimo elemento de uma progressão aritmética.

Para generalizações da sequência Thue-Morse e do problema Prouhet-Tarry-Escott para partições em mais de duas partes, consulte Bolker, Offner, Richman e Zara, "The Prouhet-Tarry-Escott problem and generalized Thue-Morse sequence".

Fractais e gráficos de tartaruga

Usando gráficos de tartaruga , uma curva pode ser gerada se um autômato for programado com uma sequência. Quando os membros da sequência Thue-Morse são usados ​​para selecionar os estados do programa:

• Se t ( n ) = 0, avance uma unidade,
• Se t ( n ) = 1, gire por um ângulo de π / 3 radianos (60 °)

A curva resultante converge para a curva de Koch , uma curva fractal de comprimento infinito contendo uma área finita. Isso ilustra a natureza fractal da Sequência Thue-Morse.

Também é possível desenhar a curva com precisão usando as seguintes instruções:

• Se t ( n ) = 0, gire por um ângulo de π radianos (180 °),
• Se t ( n ) = 1, avance uma unidade e gire em um ângulo de π / 3 radianos.

Sequenciamento equitativo

Em seu livro sobre o problema da divisão justa , Steven Brams e Alan Taylor invocaram a sequência Thue-Morse, mas não a identificaram como tal. Ao alocar uma pilha contestada de itens entre duas partes que concordam com os valores relativos dos itens, Brams e Taylor sugeriram um método que chamaram de alternância equilibrada , ou revezamento, revezando-se. . . , como forma de contornar o favoritismo inerente à escolha de uma das partes antes da outra. Um exemplo mostrou como um casal divorciado pode chegar a um acordo justo na distribuição de itens de propriedade conjunta. As partes se revezariam para serem as primeiras a escolher em diferentes pontos do processo de seleção: Ana escolhe um item, então Ben escolhe, então Ben escolhe um item, então Ann escolhe.

Lionel Levine e Katherine E. Stange , em sua discussão sobre como distribuir de maneira justa uma refeição compartilhada, como um jantar etíope , propuseram a sequência Thue-Morse como uma forma de reduzir a vantagem de se mover primeiro. Eles sugeriram que “seria interessante quantificar a intuição de que a ordem Thue-Morse tende a produzir um resultado justo”.

Robert Richman abordou esse problema, mas ele também não identificou a sequência Thue-Morse como tal no momento da publicação. Ele apresentou as sequências T _n como funções degrau no intervalo [0,1] e descreveu sua relação com as funções de Walsh e Rademacher . Ele mostrou que a n- ésima derivada pode ser expressa em termos de T _n . Como consequência, a função degrau decorrente de T _n é ortogonal a polinômios de ordem n  - 1. Uma conseqüência desse resultado é que um recurso cujo valor é expresso como uma função contínua monotonicamente decrescente é mais justamente alocado usando uma sequência que converge para Thue – Morse conforme a função se torna mais plana . Um exemplo mostrou como servir xícaras de café de igual intensidade de uma garrafa com gradiente de concentração não linear , gerando um artigo caprichoso na imprensa popular.

Joshua Cooper e Aaron Dutle mostraram por que a ordem Thue-Morse fornece um resultado justo para eventos discretos. Eles consideraram a maneira mais justa de encenar um duelo de Galois , no qual cada um dos atiradores tem habilidades de tiro igualmente ruins. Cooper e Dutle postularam que cada duelista exigiria uma chance de atirar assim que a probabilidade de vitória a priori do outro ultrapassasse a sua. Eles provaram que, à medida que a probabilidade de acerto dos dueladores se aproxima de zero, a sequência de tiro converge para a sequência de Thue-Morse. Ao fazer isso, eles demonstraram que a ordem Thue-Morse produz um resultado justo não apenas para sequências T _n de comprimento 2 ⁿ , mas para sequências de qualquer comprimento.

Assim, a matemática apóia o uso da sequência Thue-Morse em vez de curvas alternadas quando o objetivo é a justiça, mas as curvas anteriores diferem monotonicamente das curvas posteriores em alguma qualidade significativa, independentemente de essa qualidade variar continuamente ou discretamente.

As competições esportivas constituem uma classe importante de problemas de sequenciamento eqüitativo, porque a alternância estrita geralmente dá uma vantagem injusta a uma equipe. Ignacio Palacios-Huerta propôs alterar a ordem sequencial para Thue-Morse para melhorar a justiça ex post de várias competições de torneios, como a sequência de chutes em uma disputa de pênaltis no futebol. Ele fez um conjunto de experiências de campo com jogadores profissionais e descobriu que a equipe que chutou primeiro ganhou 60% dos jogos usando ABAB (ou T ₁ ), 54% usando ABBA (ou T ₂ ) e 51% usando Thue-Morse completo (ou T _n ). Como resultado, o ABBA está passando por testes extensivos na FIFA (Campeonatos Europeus e Mundiais) e no futebol profissional da Federação Inglesa ( Copa EFL ). Um padrão de serviço do ABBA também foi encontrado para melhorar a imparcialidade dos desempates no tênis . No remo competitivo , o T ₂ é o único arranjo de membros da tripulação de remo a bombordo e estibordo que elimina as forças transversais (e, portanto, a oscilação lateral) em um barco de corrida sem manivela de quatro membros, enquanto o T ₃ é um dos apenas quatro equipamentos para evitar a oscilação em um barco de oito membros.

A justiça é especialmente importante nas escolhas dos jogadores . Muitas ligas esportivas profissionais tentam alcançar a paridade competitiva dando seleções anteriores em cada rodada para times mais fracos. Por outro lado, as ligas de futebol fantasia não têm desequilíbrio pré-existente para corrigir, então muitas vezes usam um draft de “cobra” (para frente, para trás etc .; ou T ₁ ). Ian Allan argumentou que uma “terceira rodada reversão” (frente, para trás, para trás, para a frente, etc .; ou T ₂ ) seria ainda mais justo. Richman sugeriu que a maneira mais justa para o "capitão A" e o "capitão B" escolherem os lados para um jogo de espelhos de basquete T ₃ : o capitão A tem a primeira, quarta, sexta e sétima escolhas, enquanto o capitão B tem a segunda, terceira, quinta e oitava opções.

História

A sequência Thue-Morse foi estudada pela primeira vez por Eugène Prouhet em 1851, que a aplicou à teoria dos números . No entanto, Prouhet não mencionou a sequência explicitamente; isso foi deixado para Axel Thue em 1906, que o usou para fundar o estudo da combinatória das palavras . A sequência só ganhou destaque mundial com o trabalho de Marston Morse em 1921, quando a aplicou à geometria diferencial . A sequência foi descoberta de forma independente muitas vezes, nem sempre por pesquisadores matemáticos profissionais; por exemplo, Max Euwe , um grande mestre de xadrez , que detém o título do Campeonato Mundial de 1935 a 1937, e professor de matemática , o descobriu em 1929 em uma aplicação ao xadrez : usando sua propriedade livre de cubos (veja acima), ele mostrou como contornar a regra de repetição tripla destinada a prevenir jogos infinitamente prolongados, declarando empate a repetição de movimentos. Na época, estados de placa idênticos consecutivos eram necessários para acionar a regra; a regra foi posteriormente alterada para a mesma posição do tabuleiro, sendo repetida três vezes consecutivas em qualquer ponto, pois a sequência mostra que o critério consecutivo pode ser evitado para sempre.

Veja também

• Teorema de Dejean
• Função Fabius
• Código cinza
• Constante de Komornik – Loreti
• Constante de Prouhet-Thue-Morse

Notas

Referências

Leitura adicional

• Bugeaud, Yann (2012). Distribuição módulo um e aproximação diofantina . Cambridge Tracts in Mathematics. 193 . Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0. Zbl  1260.11001 .
• Lothaire, M. (2005). Combinação aplicada às palavras . Enciclopédia de matemática e suas aplicações. 105 . Uma obra coletiva 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 e Valérie Berthé. Cambridge: Cambridge University Press . ISBN 978-0-521-84802-2. Zbl  1133.68067 .

links externos

• "Sequência de Thue-Morse" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Thue-Morse Sequence" . MathWorld .
• Allouche, J.-P .; Shallit, JO The Ubiquitous Prouhet-Thue-Morse Sequence . (contém muitos aplicativos e algum histórico)
• Sequência Thue-Morse sobre (1,2) (sequência A001285 no OEIS )
• Sequência OEIS A000069 (números odiosos: números com um número ímpar de 1 em sua expansão binária)
• Sequência OEIS A001969 (números malignos: números com um número par de 1 em sua expansão binária)
• Reduzindo a influência do desvio DC offset em IPs analógicos usando a Sequência de Thue-Morse . Uma aplicação técnica da Sequência Thue-Morse
• MusiNum - a música nos números . Freeware para gerar música semelhante com base na sequência Thue-Morse e sequências numéricas relacionadas.
• Parker, Matt . "The Fairest Sharing Sequence Ever" (vídeo) . standupmaths . Retirado em 20 de janeiro de 2016 .