Thue-Morse sequence

In mathematics and its applications, the Thue-Morse sequence, or Prouhet-Thue-Morse sequence, is a certain binary sequence whose initial segments alternate (in a certain sense).

The Thue-Morse sequence begins:

01101001100101101001011001101001...

However, sometimes other symbols are used besides 0 & 1, such as 1 & 2, or 1 & 0 (in the opposite order), or left & right, up & down, etc. Thus one may speak of the Thue-Morse sequence on a given ordered pair.

Contents

1 Definition 1.1 Recurrence relation 1.2 Characterization using bitwise negation 1.3 Infinite product 2 Some properties 3 History 4 See also 5 External links

Definition

There are several equivalent ways of defining the Thue-Morse sequence.

Recurrence relation

The Thue-Morse sequence is the sequence <math>t_n<math> satisfying <math>t_0 = 0<math> and

<math>t_{2n} = t_n<math>

<math>t_{2n+1} = 1-t_n<math>

for all positive integers n.

Characterization using bitwise negation

The Thue-Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation. So, the first element is 0. Then once the first 2ⁿ elements have been specified, forming a string s, then the next 2ⁿ elements must form the bitwise negation of s. Now we have defined the first 2ⁿ⁺¹ elements, and we recurse.

Spelling out the first few steps in detail:

• We start with 0.
• The bitwise negation of 0 is 1.
• Combining these, the first 2 elements are 01.
• The bitwise negation of 01 is 10.
• Combining these, the first 4 elements are 0110.
• The bitwise negation of 0110 is 1001.
• Combining these, the first 8 elements are 01101001.
• And so on.

Infinite product

The sequence can also be defined by:

<math> \prod_{i=0}^{\infty} (1 - x^{2^{i}}) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \! <math>

where t_j is the jth element if we start at j = 0.

Some properties

Because each new block in the Thue-Morse sequence is defined by forming the bitwise negation of the beginning, and this is repeated at the beginning of the next block, the Thue-Morse sequence is filled with squares: consecutive strings that are repeated. That is, there are many instances of XX, where X is some string. However, there are no cubes: instances of XXX. There are also no overlapping squares: instances of 0X0X0 or 1X1X1.

The statement above that the Thue-Morse sequence is "filled with squares" can be made precise: It is a recurrent sequence, meaning that given any finite string X in the sequence, there is some length n_X (often much longer than the length of X) such that X appears in every block of length n. The easiest way to make a recurrent sequence is to form a periodic sequence, one where the sequence repeats entirely after a given number m of steps. Then n_X can be set to any multiple of m that is larger than twice the length of X. But the Morse sequence is recurrent without being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).

One can define a function f from the set of binary sequences to itself by replacing every 0 in a sequence with 01 and every 1 with 10. Then if T is the Thue-Morse sequence, then f(T) is T again; that is, T is a fixed point of f. In fact, T is essentially the only fixed point of f; the only other fixed point is the bitwise negation of T, which is simply the Thue-Morse sequence on (1,0) instead of on (0,1). This property may be generated to the concept of an automatic sequence.

History

The Thue-Morse sequence was first studied by P. Prouhet in 1851, who applied it to number theory. However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906, who used it to found the study of combinatorics on words. Since Thue published in Norwegian, his work was ignored at first; the sequence was only brought to worldwide attention with the work of Marston Morse in 1921, when he applied it to differential geometry. The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster and mathematics teacher, discovered it in 1929 in an application to chess.

See also

• Prouhet-Thue-Morse constant
• Sturmian word, of which the Thue-Morse sequence is a standard example

External links

• The Ubiquitous Prouhet-Thue-Morse Sequence. (http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps) Allouche, J.-P.; Shallit, J. O. Many applications and some history
• MathWorld: Thue-Morse Sequence (http://mathworld.wolfram.com/Thue-MorseSequence.html). Some other applications
• Sequence A010060 (http://www.research.att.com/projects/OEIS?Anum=A010060) from Sloane's On-Line Encyclopedia of Integer Sequences
• Sequence A001285 (http://www.research.att.com/projects/OEIS?Anum=A001285) from Sloane's OEIS for the sequence over (1,2)sl:Thue-Morsejevo zaporedje

fr:Suite de Prouhet-Thue-Morse