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).

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 nX (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 nX 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.

Related Topics:
Function - Set

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~