info prev up next book cdrom email home

Thue-Morse Sequence

The Integer Sequence (also called the Morse-Thue Sequence)

\end{displaymath} (1)

(Sloane's A010060) which arises in the Thue-Morse Constant. It can be generated from the Substitution Map
$\displaystyle 0$ $\textstyle \to$ $\displaystyle 01$ (2)
$\displaystyle 1$ $\textstyle \to$ $\displaystyle 10$ (3)

starting with 0 as follows:
0 \to 01 \to 0110 \to 01101001 \to \ldots.
\end{displaymath} (4)

Writing the sequence as a Power Series over the Galois Field GF(2),
F(x) = 0 + 1x + 1x^2 + 0x^3 + 1x^4 +\ldots,
\end{displaymath} (5)

then $F$ satisfies the quadratic equation
(1+x)F^2 + F = {x\over 1+x^2} \ ({\rm mod\ } 2).
\end{displaymath} (6)

This equation has two solutions, $F$ and $F'$, where $F'$ is the complement of $F$, i.e.,
F + F' = 1 + x + x^2 + x^3 +\ldots = {1\over 1+x},
\end{displaymath} (7)

which is consistent with the formula for the sum of the roots of a quadratic. The equality (6) can be demonstrated as follows. Let ($abcdef$...) be a shorthand for the Power series
a + bx + cx^2 + dx^3 +\ldots,
\end{displaymath} (8)

so $F(x)$ is (0110100110010110...). To get $F^2$, simply use the rule for squaring Power Series over GF(2)
(A + B)^2 = A^2 + B^2\ ({\rm mod\ }2),
\end{displaymath} (9)

which extends to the simple rule for squaring a Power Series
(a_0 + a_1x + a_2x^2 +\ldots)^2 = a_0 + a_1x^2 + a_2x^4 +\ldots\ ({\rm mod\ } 2),
\end{displaymath} (10)

i.e., space the series out by a factor of 2, (0 1 1 0 1 0 0 1 ...), and insert zeros in the Odd places to get
F^2 = (0010100010000010\ldots).
\end{displaymath} (11)

Then multiply by $x$ (which just adds a zero at the front) to get
xF^2 = (00010100010000010\ldots).
\end{displaymath} (12)

Adding to $F^2$ gives
(1+x)F^2 = (0011110011000011\ldots).
\end{displaymath} (13)

This is the first term of the quadratic equation, which is the Thue-Morse sequence with each term doubled up. The next term is $F$, so we have
$\displaystyle (1+x)F^2$ $\textstyle =$ $\displaystyle (0011110011000011\ldots)$ (14)
$\displaystyle F$ $\textstyle =$ $\displaystyle (0110100110010110\ldots).$ (15)

The sum is the above two sequences XORed together (there are no Carries because we're working over GF(2)), giving
(1+x)F^2 + F = (0101010101010101\ldots).
\end{displaymath} (16)

We therefore have

(1+x)F^2 + F = {x\over 1+x^2} = x + x^3 + x^5 + x^7 + x^9 + x^{11} + \ldots\ ({\rm mod\ }2).
\end{displaymath} (17)

The Thue-Morse sequence is an example of a cube-free sequence on two symbols (Morse and Hedlund 1944), i.e., it contains no substrings of the form $WWW$, where $W$ is any Word. For example, it does not contain the Words 000, 010101 or 010010010. In fact, the following stronger statement is true: the Thue-Morse sequence does not contain any substrings of the form $WWa$, where $a$ is the first symbol of $W$. We can obtain a Squarefree sequence on three symbols by doing the following: take the Thue-Morse sequence 0110100110010110... and look at the sequence of Words of length 2 that appear: 01 11 10 01 10 00 01 11 10 .... Replace 01 by 0, 10 by 1, 00 by 2 and 11 by 2 to get the following: 021012021.... Then this Sequence is Squarefree (Morse and Hedlund 1944).

The Thue-Morse sequence has important connections with the Gray Code. Kindermann generates fractal music using the Self-Similarity of the Thue-Morse sequence.

See also Gray Code, Parity Constant, Rabbit Sequence, Thue Sequence


Kindermann, L. ``MusiNum--The Music in the Numbers.''

Morse, M. and Hedlund, G. A. ``Unending Chess, Symbolic Dynamics, and a Problem in Semigroups.'' Duke Math. J. 11, 1-7, 1944.

Schroeder, M. R. Fractals, Chaos, and Power Laws: Minutes from an Infinite Paradise. New York: W. H. Freeman, 1991.

Sloane, N. J. A. Sequence A010060 in ``The On-Line Version of the Encyclopedia of Integer Sequences.''

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein