Thue - Morse sekvens - Thue–Morse sequence

Denne grafikken viser gjentagende og komplementær sminke av Thue - Morse -sekvensen.

I matematikk er Thue - Morse -sekvensen , eller Prouhet - Thue - Morse -sekvensen , den binære sekvensen (en uendelig sekvens av 0s og 1s) oppnådd ved å starte med 0 og etterfølgende legge til det boolske komplementet til sekvensen som er oppnådd så langt. De første trinnene i denne prosedyren gir strengene 0 deretter 01, 0110, 01101001, 0110100110010110, og så videre, som er prefikser for Thue - Morse -sekvensen. Hele sekvensen begynner:

01101001100101101001011001101001 .... (sekvens A010060 i OEIS )

Sekvensen er oppkalt etter Axel Thue og Marston Morse .

Definisjon

Det er flere likeverdige måter å definere Thue - Morse -sekvensen på.

Direkte definisjon

Når man teller i binær, er tallsummen modulo 2 Thue - Morse -sekvensen

For å beregne det n. Elementet t _n , skriv tallet n i binært . Hvis antallet en i denne binære ekspansjonen er oddetall, er t _n  = 1, selv om t _n  = 0. Av denne grunn er John H. Conway et al . anropsnummer n tilfredsstillende t _n  = 1 odious (for odd ) tall og tall som t _n  = 0 onde (for partall ) tall for. Med andre ord, t _n  = 0 hvis n er et ondt tall og t _n  = 1 hvis n er et ekkelt tall .

Rask sekvensgenerering

Denne metoden fører til en rask metode for å beregne den Thue-Morse sekvens: starte med t ₀  = 0 , og deretter, for hver n , finner den høyeste ordens bit i den binære representasjon av n som er forskjellig fra den samme bit i representasjon av n  - 1 . (Denne biten kan isoleres ved å la x være den bitvis eksklusive eller av n og n  - 1 , forskyve x rett med en bit, og beregne den eksklusive eller av denne skiftede verdien med x .) Hvis denne biten er på en jevn indeks, t _n skiller seg fra t _{n  - 1} , og ellers er det det samme som t _{n  - 1} .

I pseudokodeform:

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

Den resulterende algoritmen tar konstant tid å generere hvert sekvenselement, og bruker bare et logaritmisk antall biter (konstant antall ord) minne.

Gjentagelsesforhold

Thue - Morse -sekvensen er sekvensen t _{n som} tilfredsstiller gjentakelsesforholdet

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

for alle ikke-negative heltall n .

L-system

Thue-Morse-sekvens generert av et L-system

Thue - Morse -sekvensen er et morfisk ord : det er resultatet av følgende Lindenmayer -system :

Karakterisering ved hjelp av bitvis negasjon

Thue - Morse -sekvensen i formen gitt ovenfor, som en sekvens av biter , kan defineres rekursivt ved bruk av bitvis negasjon . Så, det første elementet er 0. Så når de første 2 ⁿ elementene er spesifisert, som danner en streng s , må de neste 2 ⁿ elementene danne den bitvise negasjonen av s . Nå har vi definert de første 2 ^{n +1} elementene, og vi gjentar.

Skriv de første trinnene i detalj:

• Vi starter med 0.
• Den bitvise negasjonen av 0 er 1.
• Ved å kombinere disse er de to første elementene 01.
• Den bitvise negasjonen av 01 er 10.
• Ved å kombinere disse er de fire første elementene 0110.
• Den bitvise negasjonen av 0110 er 1001.
• Ved å kombinere disse er de første 8 elementene 01101001.
• Og så videre.

Så

• T ₀ = 0.
• T ₁ = 01.
• T ₂ = 0110.
• T ₃ = 01101001.
• T ₄ = 0110100110010110.
• T ₅ = 01101001100101101001011001101001.
• T ₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• Og så videre.

Uendelig produkt

Sekvensen kan også defineres ved:

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

hvor t _j er det j th elementet hvis vi starter på j = 0.

Noen eiendommer

Fordi hver ny blokk i Thue - Morse -sekvensen er definert ved å danne bitvis negasjon av begynnelsen, og denne gjentas i begynnelsen av neste blokk, er Thue - Morse -sekvensen fylt med firkanter : påfølgende strenger som gjentas. Det vil si at det er mange forekomster av XX , der X er en streng. Faktisk er en slik streng hvis og bare hvis eller hvor for noen og angir den bitvise negasjonen av (veksling 0s og 1s). For eksempel, med , vi har , og firkanten vises ved å begynne med den 16. biten. (Dermed har firkanter i lengde enten en effekt på 2 eller 3 ganger en kraft på 2.) Imidlertid er det ingen terninger : forekomster av XXX . Det er heller ingen overlappende firkanter : forekomster av 0 X 0 X 0 eller 1 X 1 X 1. Den kritiske eksponenten er 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}$

Sekvensen T _{2 n} er palindrom for alle n . La q _n være et ord hentet fra T _{2 n} ved å telle dem mellom påfølgende nuller. For eksempel, q ₁ = 2 og q ₂ = 2102012 og så videre. Ordene T _n inneholder ikke overlappende firkanter som konsekvens, ordene q _n er palindrome kvadratfrie ord .

Uttalelsen ovenfor om at Thue - Morse -sekvensen er "fylt med firkanter" kan gjøres presis: Det er et jevnt tilbakevendende ord , noe som betyr at gitt en endelig streng X i sekvensen, er det en viss lengde n _X (ofte mye lengre enn lengden av X ) slik at X vises i hver blokk med lengde n _X . Den enkleste måten å lage en tilbakevendende sekvens er å danne en periodisk sekvens , en der sekvensen gjentas helt etter et gitt antall m trinn. Deretter n _X kan innstilles til en hvilken som helst multippel av m som er større enn to ganger lengden av X . Men morsesekvensen er jevnt tilbakevendende uten å være periodisk, ikke engang periodisk (betyr periodisk etter et ikke -periodisk innledende segment).

Vi definerer Thue - Morse morfismen til å være funksjonen f fra settet med binære sekvenser til seg selv ved å erstatte hver 0 i en sekvens med 01 og hver 1 med 10. Så hvis T er Thue - Morse sekvensen, så f ( T ) er T igjen; det vil si at T er et fast punkt på f . Funksjonen f er en forlengelig morfisme på den frie monoiden {0,1} ^∗ med T som fastpunkt: faktisk er T det eneste faste punktet for f ; det eneste andre faste punktet er den bitvise negasjonen av T , som ganske enkelt er Thue - Morse -sekvensen på (1,0) i stedet for på (0,1). Denne egenskapen kan generaliseres til begrepet en automatisk sekvens .

Den genererende rekke av T over binære felt er den formelle potensrekken

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

Denne kraftserien er algebraisk over feltet for rasjonelle funksjoner, og tilfredsstiller ligningen

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

I kombinatorisk spillteori

Settet med onde tall (tall med ) danner et underrom av de ikke-negative heltallene under nim-addisjon ( bitvis eksklusiv eller ). For spillet Kayles forekommer onde nim-verdier for få (endelig mange) posisjoner i spillet, med alle gjenværende posisjoner som har stygge nim-verdier. ${\ displaystyle n}$${\ displaystyle t_ {n} = 0}$

Problemet Prouhet – Tarry – Escott

Den Prouhet-Tarry-Escott problem kan defineres som: gitt et positivt heltall N og et ikke-negativt heltall k , skillevegg settet S = {0, 1, ..., N -1} i to atskilte undergrupper S ₀ og S ₁ som har like store summer opp til k, det vil si:

${\ displaystyle \ sum _ {x \ i S_ {0}} x^{i} = \ sum _ {x \ i S_ {1}} x^{i}}$for alle heltall i fra 1 til k .

Dette har en løsning hvis N er et multiplum av 2 ^{k +1} , gitt av:

• S ₀ består av heltallene n i S som t _n = 0,
• S ₁ består av heltallene n i S som t _n = 1.

For eksempel, for N = 8 og k = 2,

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

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

Betingelsen som krever at N er et multiplum på 2 ^{k +1} er ikke strengt nødvendig: det er noen flere tilfeller der det finnes en løsning. Imidlertid garanterer den en sterkere egenskap: hvis betingelsen er oppfylt, kan settet med k th -potens for et sett med N -tall i aritmetisk progresjon deles i to sett med like store summer. Dette følger direkte av utvidelsen gitt av binomialsetningen som brukes på binomien som representerer det n. Elementet i en aritmetisk progresjon.

For generaliseringer av Thue - Morse -sekvensen og Prouhet - Tarry - Escott -problemet til partisjoner i mer enn to deler, se Bolker, Offner, Richman og Zara, "The Prouhet - Tarry - Escott -problemet og generaliserte Thue - Morse -sekvenser".

Fraktaler og skilpaddegrafikk

Ved bruk av skilpaddegrafikk kan en kurve genereres hvis en automat er programmert med en sekvens. Når Thue - Morse -sekvensmedlemmer brukes for å velge programtilstander:

• Hvis t ( n ) = 0, gå videre med en enhet,
• Hvis t ( n ) = 1, roter du med en vinkel på π/3 radianer (60 °)

Den resulterende kurven konvergerer til Koch -kurven , en fraktalkurve med uendelig lengde som inneholder et begrenset område. Dette illustrerer den fraktale naturen til Thue - Morse -sekvensen.

Det er også mulig å tegne kurven nøyaktig ved å bruke følgende instruksjoner:

• Hvis t ( n ) = 0, roter du med en vinkel på π radianer (180 °),
• Hvis t ( n ) = 1, gå fremover med en enhet, roter deretter med en vinkel på π/3 radianer.

Rettferdig sekvensering

I sin bok om problemet med rettferdig fordeling , Steven Brams og Alan Taylor påberopt seg Thue-Morse sekvens, men ikke identifisere den som sådan. Når de tildelte en omtvistet haug med varer mellom to parter som er enige om elementenes relative verdier, foreslo Brams og Taylor en metode de kalte balansert veksling , eller å bytte på å bytte tur. . . , som en måte å omgå favoritten iboende når den ene parten velger foran den andre. Et eksempel viste hvordan et skilsmissepar kan oppnå et rettferdig oppgjør i fordelingen av felleseide gjenstander. Partene skulle bytte på å være den første som velger på forskjellige punkter i utvelgelsesprosessen: Ann velger ett element, så gjør Ben, deretter velger Ben ett element, så gjør Ann.

Lionel Levine og Katherine E. Stange , i sin diskusjon om hvordan man rettferdig fordeler et delt måltid som en etiopisk middag , foreslo Thue - Morse -sekvensen som en måte å redusere fordelen ved å flytte først. De foreslo at "det ville være interessant å tallfeste intuisjonen om at Thue - Morse -ordenen har en tendens til å gi et rettferdig resultat."

Robert Richman tok opp dette problemet, men også han identifiserte ikke Thue - Morse -sekvensen som sådan på tidspunktet for publisering. Han presenterte sekvensene T _n som trinnfunksjoner på intervallet [0,1] og beskrev deres forhold til Walsh- og Rademacher -funksjonene. Han viste at n th derivatet kan uttrykkes i form av T _n . Som en følge av dette trinnet funksjon som oppstår fra T _n er ortogonal til polynomer av orden n  - 1. En konsekvens av dette resultatet er at en ressurs som har en verdi blir uttrykt som en monotont avtagende kontinuerlig funksjon er mest ganske fordeles ved hjelp av en sekvens som konvergerer til Thue – Morse ettersom funksjonen blir flatere . Et eksempel viste hvordan å helle kopper kaffe av samme styrke fra en karaffel med en ikke-lineær konsentrasjon -gradient , spørre en lunefull artikkel erte i pressen.

Joshua Cooper og Aaron Dutle viste hvorfor Thue - Morse -ordenen gir et rimelig utfall for diskrete hendelser. De anså den mest rettferdige måten å arrangere en Galois -duell, der hver av skytterne har like dårlige skyteferdigheter. Cooper og Dutle postulerte at hver dueller ville kreve en sjanse til å skyte så snart den andres a priori sannsynlighet for å vinne oversteg sin egen. De beviste at etter hvert som duellernes treffsannsynlighet nærmer seg null, konverreres avfyringssekvensen til Thue - Morse -sekvensen. På den måten demonstrerte de at Thue - Morse -ordenen gir et rettferdig resultat ikke bare for sekvenser T _n med lengde 2 ⁿ , men for sekvenser av hvilken som helst lengde.

Dermed støtter matematikken å bruke Thue - Morse -sekvensen i stedet for vekslende svinger når målet er rettferdighet, men tidligere svinger skiller seg monotont fra senere svinger i en meningsfull kvalitet, enten den kvaliteten varierer kontinuerlig eller diskret.

Sportskonkurranser utgjør en viktig klasse med likeverdige sekvenseringsproblemer, fordi streng veksling ofte gir en urettferdig fordel for ett lag. Ignacio Palacios-Huerta foreslo å endre rekkefølgen til Thue-Morse for å forbedre rettferdigheten i etterkant av forskjellige turneringskonkurranser, for eksempel sparkesekvensen for en straffesparkkonkurranse i fotball. Han gjorde et sett med felteksperimenter med proffspillere og fant ut at laget som sparket først vant 60% av kampene ved bruk av ABAB (eller T ₁ ), 54% ved bruk av ABBA (eller T ₂ ) og 51% ved å bruke full Thue – Morse (eller T _n ). Som et resultat gjennomgår ABBA omfattende prøver i FIFA (European and World Championships) og English Federation professional football ( EFL Cup ). Det er også funnet et ABBA-serveringsmønster for å forbedre rettferdigheten til tennis-tie-break . I konkurransedyktig roing er T ₂ det eneste arrangementet av mannskaper fra babord- og styrbord-roing som eliminerer tverrgående krefter (og dermed svingninger sidelengs) på en fire-ledd coxless racerbåt, mens T ₃ er en av bare fire rigger for å unngå vridning på en åtteleddet båt.

Rettferdighet er spesielt viktig i spillerutkast . Mange profesjonelle idrettsligaer prøver å oppnå konkurransedyktig likhet ved å gi svakere lag tidligere valg i hver runde. Derimot har fantasifotballligaer ingen eksisterende ubalanse å korrigere, så de bruker ofte et "slange" -utkast (fremover, bakover osv. Eller T ₁ ). Ian Allan hevdet at en "reversering i tredje runde" (fremover, bakover, bakover, fremover osv. Eller T ₂ ) ville være enda mer rettferdig. Richman antydet at den mest rettferdige måten for “kaptein A” og “kaptein B” for å velge side for en pick-up spill av basketball speil T ₃ : kaptein A har den første, fjerde, sjette og syvende valg, mens kaptein B har andre, tredje, femte og åttende valg.

Historie

Thue - Morse -sekvensen ble først studert av Eugène Prouhet i 1851, som brukte den på tallteori . Imidlertid nevnte Prouhet ikke sekvensen eksplisitt; dette ble overlatt til Axel Thue i 1906, som brukte det til å finne studiet av kombinatorikk på ord . Sekvensen ble bare gjort oppmerksom på verdensomspennende med arbeidet til Marston Morse i 1921, da han brukte den på differensialgeometri . Sekvensen har blitt oppdaget uavhengig mange ganger, ikke alltid av profesjonelle matematikere; for eksempel Max Euwe , et sjakkmesteren , som holdt VM-tittelen 1935-1937, og matematikk lærer , oppdaget det i 1929 i en søknad til sjakk : ved hjelp av sin kube eiendom (se ovenfor), viste han hvordan å omgå den tredobbelte repetisjonsregelen som tar sikte på å forhindre uendelig langvarige spill ved å erklære gjentakelse av trekk uavgjort. På den tiden var påfølgende identiske styrestater pålagt å utløse regelen; regelen ble senere endret til at samme styreposisjon ble gjentatt tre ganger på rad når som helst, da sekvensen viser at det påfølgende kriteriet kan unngås for alltid.

Se også

• Dejeans teorem
• Fabius -funksjon
• Grå kode
• Komornik - Loreti konstant
• Prouhet – Thue – Morse konstant

Merknader

Referanser

Videre lesning

• Bugeaud, Yann (2012). Fordeling modulo one og Diophantine tilnærming . Cambridge Tracts in Mathematics. 193 . Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0. Zbl  1260.11001 .
• Lothaire, M. (2005). Brukte kombinatorikk på ord . Encyclopedia of Mathematics and its Applications. 105 . Et kollektivt verk av 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 og Valérie Berthé. Cambridge: Cambridge University Press . ISBN 978-0-521-84802-2. Zbl  1133.68067 .

Eksterne linker

• "Thue-Morse-sekvens" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Thue-Morse Sequence" . MathWorld .
• Allouche, J.-P .; Shallit, JO Den allestedsnærværende Prouhet-Thue-Morse-sekvensen . (inneholder mange applikasjoner og litt historie)
• Thue - Morse -sekvens over (1,2) (sekvens A001285 i OEIS )
• OEIS -sekvens A000069 (Odious tall: tall med et oddetall på 1 -tallet i sin binære ekspansjon)
• OEIS -sekvens A001969 (onde tall: tall med et partall 1 i sin binære ekspansjon)
• Redusere påvirkningen av DC offset drift i analoge IP-er ved hjelp av Thue-Morse-sekvensen . En teknisk applikasjon av Thue - Morse -sekvensen
• MusiNum - Musikken i tallene . Freeware for å generere selvlignende musikk basert på Thue-Morse-sekvensen og relaterte nummersekvenser.
• Parker, Matt . "The Fairest Sharing Sequence Ever" (video) . standupmaths . Hentet 20. januar 2016 .