Thue-Morse Sequence

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

$$01101001100101101001011001101001\ldots$$ (1)

(Sloane's A010060) which arises in the Thue-Morse Constant. It can be generated from the Substitution Map

$$0 \to 01$$ (2)

$$1 \to 10$$ (3)

starting with 0 as follows:

$$0 \to 01 \to 0110 \to 01101001 \to \ldots.$$ (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,$$ (5)

then $F$ satisfies the quadratic equation

$$(1+x)F^2 + F = {x\over 1+x^2} \ ({\rm mod\ } 2).$$ (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},$$ (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,$$ (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),$$ (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),$$ (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).$$ (11)

Then multiply by $x$ (which just adds a zero at the front) to get

$$xF^2 = (00010100010000010\ldots).$$ (12)

Adding to $F^2$ gives

$$(1+x)F^2 = (0011110011000011\ldots).$$ (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

$$(1+x)F^2 = (0011110011000011\ldots)$$ (14)

$$F = (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).$$ (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).$$ (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

References

Kindermann, L. ``MusiNum--The Music in the Numbers.'' http://www.forwiss.uni-erlangen.de/~kinderma/musinum/.

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.'' http://www.research.att.com/~njas/sequences/eisonline.html.