Namespaces
Variants
Actions

Difference between revisions of "Thue-Morse sequence"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (typo)
(→‎References: zbl link)
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 +
$\newcommand{\calA}{\mathcal{A}}$
 +
 
A sequence appearing in numerous fields and discovered and rediscovered in different contexts.
 
A sequence appearing in numerous fields and discovered and rediscovered in different contexts.
  
==Arithmetical definition.==
+
The Thue–Morse sequence may be defined as the sequence $u = (u_n)_n$ which counts the sum modulo $2$ of the digits of $n$ in base $2$ ($u_n$ gives the parity of the number of $1$s in the binary expansion of $n$). This sequence can also be generated by an iterative process called substitution. Let $\calA = \{a, b\}$ and let $\calA^*$ denote the set of words defined on the
The Thue–Morse sequence is 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.
+
[[Alphabet|alphabet]] $\calA$ (cf. also
 +
[[Word|Word]]). Consider the mapping $\sigma : \calA \to \calA^*$ defined by $\sigma(a) = ab$ and $\sigma(b) = ba$. The mapping $\sigma$ extends to a morphism of $\calA^*$ by concatenation. One can iterate $\sigma$, and the nested words $\sigma^n(a)$ converge in the product topology to the infinite sequence which begins with $\sigma^n(a)$, for every $n$. 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]]].
+
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 $c$ classes with the same cardinality $s$ such that the sums of the elements, the sums of squares, etc., the sums of the $k$th powers in each class, are independent of the class. If the sums of the $(k+1)$th powers are not equal, then the solution is said to be an exact solution of order $k$. The Thue–Morse sequence provides a solution of degree $k$ exactly (when $c=2$) by considering the classes $\left\{ 0 \le n \le 2^{k+1} - 1 : u_n = a \right\}$ and $\left\{0 \le n \le 2^{k+1} - 1 : u_n = b \right\}$. Note that this partition is conjectured to be the unique partition of the set $\{0, 1, \ldots, 2^{k+1} - 1\}$ into $2$ classes providing an exact solution of degree $k$. 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 patterns]] 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 $u$ 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 $www$, where $w$ 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 $2+\epsilon$, for any $\epsilon > 0$. Such a sequence is called overlap-free; in other words, none of its factors is of the form $xuxux$. 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 $\{0, 1\}$ (by mapping $a$ to $1$ and $b$ to $0$), then the sequence $(u_{n+1} - u_n)_n$ defined on the three-letter alphabet $\{-1, 0, 1\}$ is square-free. By applying the morphism $\mu(-1) = a$, $\mu(0) = ab$, $\mu(1) = abb$, 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 sequence $u$ 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 $0$s and $1$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.
+
The Thue–Morse sequence is a typical example of a $k$-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 $k$-automaton is given by a finite set of states $S$, one state being called the initial state, by $k$ mappings from $S$ into itself (denoted by $0,\dots,k-1$) and by an output mapping $\phi$ from $S$ into a given set $Y$. Such an automaton generates a sequence with values in $Y$ as follows: Feed the automaton with the digits of the base-$k$ expansion of $n$, starting with the initial state; then define $u_n$ as the image under $\phi$ of the reached state. In the Thue–Morse case, the automaton has two states, say $\{A,B\}$, the mapping $0$ maps each state to itself whereas the mapping $1$ exchanges both states $A \leftrightarrow B$, the output mapping is the identity mapping and the state $A$ 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)
+
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 $k$-kernel)
 +
$$
 +
\left\lbrace{ \left({ u_{k^ t n+r} }\right)_n : t \ge 0\,,\ 0 \le r \le t^k-1 }\right\rbrace
 +
$$
 +
is finite or, in the case $k$ is a prime power, to the fact that the series $\sum u_n Z^n$ is algebraic over $\mathbf{F}_k(Z)$. 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]]].
  
<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>
+
Define the '''Rudin–Shapiro sequence''' $v = (v_n)$ that counts modulo $2$ the number of $11$s (possibly with overlap) in the base-$2$ expansion of $n$. The sequence $v$ is easily seen to have a finite $2$-kernel and hence to be $2$-automatic. This sequence was introduced independently by W. Rudin and H.S. Shapiro (see the references in
 +
[[#References|[a6]]]) in order to minimize uniformly $\left|{ \sum_{n=0}^{N-1} a_n e^{int} }\right|$, for a sequence $a_n$ defined over $\{ \pm 1 \}$. The Rudin–Shapiro sequence achieves
 +
$$
 +
\sup_{t} \left|{ \sum_{n=0}^{N-1} v_n e^{int} }\right| \le (2+\sqrt 2)\sqrt{N} \ .
 +
$$
  
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]]].
+
The dynamical system generated by each of the two sequences $u$ and $v$ 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]]].
  
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
+
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 $\{1, 2\}$ as follows. The sequence begins with $2$, and the sequence of lengths of the consecutive strings of $2$s and $1$s is the sequence itself. Hence this sequence is equal to $22112122122112\ldots$ For a survey of related properties and conjectures, see
 +
[[#References|[a2]]].
  
<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>
+
====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'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17''''  Cambridge University Press (1997) {{ISBN|0-521-59924-5}} {{ZBL|0874.20040}}</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 {{ZBL|0641.10041}}</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]]].
+
====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\}$.
  
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]]].
+
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====
 
====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>
+
* 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. ''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}}

Latest revision as of 15:03, 18 May 2024

$\newcommand{\calA}{\mathcal{A}}$

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

The Thue–Morse sequence may be defined as the sequence $u = (u_n)_n$ which counts the sum modulo $2$ of the digits of $n$ in base $2$ ($u_n$ gives the parity of the number of $1$s in the binary expansion of $n$). This sequence can also be generated by an iterative process called substitution. Let $\calA = \{a, b\}$ and let $\calA^*$ denote the set of words defined on the alphabet $\calA$ (cf. also Word). Consider the mapping $\sigma : \calA \to \calA^*$ defined by $\sigma(a) = ab$ and $\sigma(b) = ba$. The mapping $\sigma$ extends to a morphism of $\calA^*$ by concatenation. One can iterate $\sigma$, and the nested words $\sigma^n(a)$ converge in the product topology to the infinite sequence which begins with $\sigma^n(a)$, for every $n$. 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 $c$ classes with the same cardinality $s$ such that the sums of the elements, the sums of squares, etc., the sums of the $k$th powers in each class, are independent of the class. If the sums of the $(k+1)$th powers are not equal, then the solution is said to be an exact solution of order $k$. The Thue–Morse sequence provides a solution of degree $k$ exactly (when $c=2$) by considering the classes $\left\{ 0 \le n \le 2^{k+1} - 1 : u_n = a \right\}$ and $\left\{0 \le n \le 2^{k+1} - 1 : u_n = b \right\}$. Note that this partition is conjectured to be the unique partition of the set $\{0, 1, \ldots, 2^{k+1} - 1\}$ into $2$ classes providing an exact solution of degree $k$. For more results on this subject, see [a1].

The sequence $u$ was next rediscovered by A. Thue in 1912 [a7]. Thue tried to construct arbitrarily long words on a two-letter alphabet without cubes, i.e., without factors of the form $www$, where $w$ is a non-empty word. It is easily seen that there are no infinite square-free sequences on two letters. It is then natural to ask whether there are infinite sequences free of powers $2+\epsilon$, for any $\epsilon > 0$. Such a sequence is called overlap-free; in other words, none of its factors is of the form $xuxux$. 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 $\{0, 1\}$ (by mapping $a$ to $1$ and $b$ to $0$), then the sequence $(u_{n+1} - u_n)_n$ defined on the three-letter alphabet $\{-1, 0, 1\}$ is square-free. By applying the morphism $\mu(-1) = a$, $\mu(0) = ab$, $\mu(1) = abb$, one also gets an infinite cube-free word on two letters. These results have been extended within the theory of avoidable and unavoidable patterns 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 [a4].

The sequence $u$ was next introduced by M. Morse [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; Surface; Geodesic line), by coding a geodesic by an infinite sequence of $0$s and $1$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, [a6] or Dynamical system).

The Thue–Morse sequence is a typical example of a $k$-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), as follows. A $k$-automaton is given by a finite set of states $S$, one state being called the initial state, by $k$ mappings from $S$ into itself (denoted by $0,\dots,k-1$) and by an output mapping $\phi$ from $S$ into a given set $Y$. Such an automaton generates a sequence with values in $Y$ as follows: Feed the automaton with the digits of the base-$k$ expansion of $n$, starting with the initial state; then define $u_n$ as the image under $\phi$ of the reached state. In the Thue–Morse case, the automaton has two states, say $\{A,B\}$, the mapping $0$ maps each state to itself whereas the mapping $1$ exchanges both states $A \leftrightarrow B$, the output mapping is the identity mapping and the state $A$ is the initial state.

Automatic sequences have many nice characterizations (see, for instance, [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 $k$-kernel) $$ \left\lbrace{ \left({ u_{k^ t n+r} }\right)_n : t \ge 0\,,\ 0 \le r \le t^k-1 }\right\rbrace $$ is finite or, in the case $k$ is a prime power, to the fact that the series $\sum u_n Z^n$ is algebraic over $\mathbf{F}_k(Z)$. 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 [a3].

Define the Rudin–Shapiro sequence $v = (v_n)$ that counts modulo $2$ the number of $11$s (possibly with overlap) in the base-$2$ expansion of $n$. The sequence $v$ is easily seen to have a finite $2$-kernel and hence to be $2$-automatic. This sequence was introduced independently by W. Rudin and H.S. Shapiro (see the references in [a6]) in order to minimize uniformly $\left|{ \sum_{n=0}^{N-1} a_n e^{int} }\right|$, for a sequence $a_n$ defined over $\{ \pm 1 \}$. The Rudin–Shapiro sequence achieves $$ \sup_{t} \left|{ \sum_{n=0}^{N-1} v_n e^{int} }\right| \le (2+\sqrt 2)\sqrt{N} \ . $$

The dynamical system generated by each of the two sequences $u$ and $v$ is strictly ergodic (cf. also Ergodic theory), since both underlying substitutions are primitive (see, for instance, [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 [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 $\{1, 2\}$ as follows. The sequence begins with $2$, and the sequence of lengths of the consecutive strings of $2$s and $1$s is the sequence itself. Hence this sequence is equal to $22112122122112\ldots$ For a survey of related properties and conjectures, see [a2].

References

[a1] P. Borwein, C. Ingalls, "The Prouhet–Tarry–Escott problem revisited" Enseign. Math. , 40 (1994) pp. 3–27
[a2] 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
[a3] "Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches" F. Axel (ed.) et al. (ed.) , Springer (1995)
[a4] M. Lothaire, Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17' Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
[a5] M. Morse, "Recurrent geodesics on a surface of negative curvature" Trans. Amer. Math. Soc. , 22 (1921) pp. 84–100
[a6] M. Queffélec, "Substitution dynamical systems. Spectral analysis" , Lecture Notes Math. , 1294 , Springer (1987)
[a7] A. Thue, "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , Selected Math. Papers of Axel Thue , Universiteitsforlaget (1977) (Published in 1912)
[a8] J.-P. Allouche, "Automates finis en théorie des nombres" Experim. Math. , 5 (1987) pp. 239–266 Zbl 0641.10041

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. 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
How to Cite This Entry:
Thue-Morse sequence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Thue-Morse_sequence&oldid=39630
This article was adapted from an original article by V. Berthé (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article