View source for Thue-Morse sequence

A sequence appearing in numerous fields and discovered and rediscovered in different contexts.

The Thue–Morse sequence may be defined as the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200901.png" /> which counts the sum modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200902.png" /> of the digits of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200903.png" /> in base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200904.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200905.png" /> gives the parity of the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200906.png" />s in the binary expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200907.png" />). This sequence can also be generated by an iterative process called substitution. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200908.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t1200909.png" /> denote the set of words defined on the [[Alphabet|alphabet]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009010.png" /> (cf. also [[Word|Word]]). Consider the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009011.png" /> defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009013.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009014.png" /> extends to a morphism of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009015.png" /> by concatenation. One can iterate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009016.png" />, and the nested words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009017.png" /> converge in the product topology to the infinite sequence which begins with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009018.png" />, for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009019.png" />. This sequence is precisely the Thue–Morse sequence.

This sequence was first discovered by E. Prouhet in 1851 as a solution of the so-called Prouhet–Tarry–Escott problem (G. Tarry and E.B. Escott re-introduced this problem after Prouhet in the years 1910–1920): Consider a finite set of integers that can be partitioned into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009020.png" /> classes with the same cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009021.png" /> such that the sums of the elements, the sums of squares, etc., the sums of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009022.png" />th powers in each class, are independent of the class. If the sums of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009023.png" />th powers are not equal, then the solution is said to be an exact solution of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009025.png" />. The Thue–Morse sequence provides a solution of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009026.png" /> exactly (when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009027.png" />) by considering the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009029.png" />. Note that this partition is conjectured to be the unique partition of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009030.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009031.png" /> classes providing an exact solution of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009032.png" />. For more results on this subject, see [[#References|[a1]]].

The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009033.png" /> was next rediscovered by A. Thue in 1912 [[#References|[a7]]]. Thue tried to construct arbitrarily long words on a two-letter alphabet without cubes, i.e., without factors of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009034.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009035.png" /> is a non-empty word. It is easily seen that there are no infinite [[Square-free word|square-free sequences]] on two letters. It is then natural to ask whether there are infinite sequences free of powers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009036.png" />, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009037.png" />. Such a sequence is called overlap-free; in other words, none of its factors is of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009038.png" />. In fact, the Thue–Morse sequence is an infinite overlap-free word on two letters. Moreover, all overlap-free words are derived from this sequence. Furthermore, if one defines the Thue–Morse sequence on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009039.png" /> (by mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009040.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009042.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009043.png" />), then the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009044.png" /> defined on the three-letter alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009045.png" /> is square-free. By applying the morphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009048.png" />, one also gets an infinite cube-free word on two letters. These results have been extended within the theory of avoidable and [[unavoidable pattern]]s in strings. Note that such combinatorial properties were used to solve various algebraic problems, and to provide a negative answer to the [[Burnside problem]]. For more information on the subject, see [[#References|[a4]]].

The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009049.png" /> was next introduced by M. Morse [[#References|[a5]]] in 1921 in order to show the existence of non-periodic recurrent geodesics over simply-connected surfaces with constant negative curvature (cf. also [[Simply-connected domain|Simply-connected domain]]; [[Surface|Surface]]; [[Geodesic line|Geodesic line]]), by coding a geodesic by an infinite sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009050.png" />s and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009051.png" />s, according to which boundary of the surface it meets. Indeed, the Thue–Morse sequence is a [[uniformly recurrent word]], i.e., every factor appears in an infinite number of places with bounded gaps. In other words, the symbolic dynamical system generated by the Thue–Morse sequence is minimal (see, for instance, [[#References|[a6]]] or [[Dynamical system|Dynamical system]]).

The Thue–Morse sequence is a typical example of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009053.png" />-automatic sequence. Actually, like every fixed point of a substitution of constant length, it can be generated by a finite machine, called a finite automaton (cf. [[Automaton, finite|Automaton, finite]]), as follows. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009055.png" />-automaton is given by a finite set of states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009056.png" />, one state being called the initial state, by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009057.png" /> mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009058.png" /> into itself (denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009059.png" />) and by an output mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009060.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009061.png" /> into a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009062.png" />. Such an automaton generates a sequence with values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009063.png" /> as follows: Feed the automaton with the digits of the base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009064.png" /> expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009065.png" />, starting with the initial state; then define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009066.png" /> as the image under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009067.png" /> of the reached state. In the Thue–Morse case, the automaton has two states, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009068.png" />, the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009069.png" /> maps each state to itself whereas the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009070.png" /> exchanges both states, the output mapping is the identity mapping and the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009071.png" /> is the initial state.

Automatic sequences have many nice characterizations (see, for instance, [[#References|[a8]]]). Automatic sequences are exactly the letter-to-letter images of fixed points of constant-length substitutions. Furthermore, this is equivalent to the fact that the following subset of subsequences (called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009073.png" />-kernel)

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009074.png" /></td> </tr></table>

is finite or to the fact that the series <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009075.png" /> is algebraic over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009076.png" />, in the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009077.png" /> is a prime power. Note that, on the other hand, the real number that has, as dyadic expansion, the Thue–Morse sequence is transcendental. For more references and connections with physics, see [[#References|[a3]]].

Consider the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009078.png" /> that counts modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009079.png" /> the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009080.png" />s (possibly with overlap) in the base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009081.png" /> expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009082.png" />. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009083.png" /> is easily seen to have a finite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009084.png" />-kernel and hence to be be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009085.png" />-automatic. This sequence was introduced independently by W. Rudin and H.S. Shapiro (see the references in [[#References|[a6]]]) in order to minimize uniformly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009086.png" />, for a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009087.png" /> defined over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009088.png" />. The Rudin–Shapiro sequence hence provides

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009089.png" /></td> </tr></table>

The dynamical system generated by each of the two sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009091.png" /> is strictly ergodic (cf. also [[Ergodic theory|Ergodic theory]]), since both underlying substitutions are primitive (see, for instance, [[#References|[a6]]]). But, although very similar in their definition, these two sequences have very distinct spectral properties. The Morse system has a singular simple spectrum, whereas the dynamical system generated by the Rudin–Shapiro sequence provides an example of a system with finite spectral multiplicity and a Lebesgue component in the spectrum. For more references on the ergodic, spectral and harmonic properties of substitutive sequences, see [[#References|[a6]]].

If (almost) everything is known concerning the Thue–Morse and the Rudin–Shapiro sequences, then the situation is completely different for the fascinating Kolakoski sequence. The Kolakoski sequence is the self-determined sequence defined over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009092.png" /> as follows. The sequence begins with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009093.png" />, and the sequence of lengths of the consecutive strings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009094.png" />s and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009095.png" />s is the sequence itself. Hence this sequence is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t120/t120090/t12009096.png" /> For a survey of related properties and conjectures, see [[#References|[a2]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Borwein,   C. Ingalls,   "The Prouhet–Tarry–Escott problem revisited"  ''Enseign. Math.'' , '''40'''  (1994)  pp. 3–27</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  F.M. Dekking,   "What is the long range order in the Kolakoski sequence" , ''The Mathematics Of Long-Range Aperiodic Order (Waterloo, ON, 1995)'' , ''NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.'' , '''489''' , Kluwer Acad. Publ.  (1997)  pp. 115–125</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  "Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches"  F. Axel (ed.)  et al. (ed.) , Springer  (1995)</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Lothaire,   "Combinatorics on words" , Cambridge Univ. Press  (1997)</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Morse,   "Recurrent geodesics on a surface of negative curvature"  ''Trans. Amer. Math. Soc.'' , '''22'''  (1921)  pp. 84–100</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  M. Queffélec,   "Substitution dynamical systems. Spectral analysis" , ''Lecture Notes Math.'' , '''1294''' , Springer  (1987)</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Thue,   "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , ''Selected Math. Papers of Axel Thue'' , Universiteitsforlaget  (1977)  (Published in 1912)</TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  J.-P. Allouche,   "Automates finis en théorie des nombres"  ''Experim. Math.'' , '''5'''  (1987)  pp. 239–266</TD></TR>
</table>

====Comments====
The invariance of the Thue-Morse sequence under the mapping $a \mapsto ab$, $b \mapsto ba$ may be expressed by saying that it defines a ''[[morphic word]]'' over the alphabet $\{a,b\}$.

The subsets of the natural numbers for which the sequence $u_n = 0$ and $1$ respectively have been termed the "evil" and "odious" numbers by Richard Guy.  They appears in the analysis of certain combinatorial games.

====References====
* Allouche, Jean-Paul; Shallit, Jeffrey ''Automatic Sequences: Theory, Applications, Generalizations'' Cambridge University Press (2003) ISBN 978-0-521-82332-6 {{ZBL|1086.11015}}
* Lothaire, M. ''Combinatorics on Words'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17''''  Cambridge University Press (1997) ISBN 0-521-59924-5 {{ZBL|0874.20040}}
* Lothaire, M. ''Algebraic Combinatorics on Words'' Encyclopedia of Mathematics and Its Applications '''90''' Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 {{ZBL|1221.68183}}
* Pytheas Fogg, N. (ed.) ''Substitutions in dynamics, arithmetics and combinatorics'' Lecture Notes in Mathematics '''1794''' Springer (2002) ISBN 978-3-540-44141-0 {{ZBL|1014.11015}}
* Berlekamp, E., Conway, J.H., Guy R.K. ''Winning Ways, for Your Mathematical Plays'' Academic Press (1982) {{ZBL|0485.00025}}