Thue–Morse sequence

This graphic demonstrates the repeating and complementary makeup of the Thue–Morse sequence.

In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of Template:Maths and Template:Maths) that can be obtained by starting with Template:Math and successively appending the Boolean complement of the sequence obtained thus far. It is sometimes called the fair share sequence because of its applications to fair division or parity sequence. The first few steps of this procedure yield the strings Template:Math, Template:Math, Template:Math, Template:Math, Template:Math, and so on, which are the prefixes of the Thue–Morse sequence. The full sequence begins:

Template:Math

The sequence is named after Axel Thue, Marston Morse and (in its extended form) Template:Ill.

Definition

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

Direct definition

When counting in binary, the digit sum modulo 2 is the Thue–Morse sequence

To compute the Template:Mvarth element Template:Math, write the number Template:Mvar in binary. If the number of ones in this binary expansion is odd then Template:Math, if even then Template:Math. That is, Template:Math is the even parity bit for Template:Mvar. John Conway et al. deemed numbers Template:Mvar satisfying Template:Math to be odious (intended to be similar to odd) numbers, and numbers for which Template:Math to be evil (similar to even) numbers.

Fast sequence generation

This method leads to a fast method for computing the Thue–Morse sequence: start with Template:Math, and then, for each Template:Mvar, find the highest-order bit in the binary representation of Template:Mvar that is different from the same bit in the representation of Template:Math. If this bit is at an even index, Template:Math differs from Template:Math, and otherwise it is the same as Template:Math.

In Python:

from typing import Iterator

def generate_sequence(seq_length: int) -> Iterator[int]:
    """Thue–Morse sequence."""
    value: int = 1
    for n in range(seq_length):
        # Note: assumes that (-1).bit_length() gives 1
        x: int = (n ^ (n - 1)).bit_length() + 1
        if x & 1 == 0:
            # Bit index is even, so toggle value
            value = 1 - value
        yield value

The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.Template:Sfnp

Recurrence relation

The Thue–Morse sequence is the sequence Template:Math satisfying the recurrence relation

$\begin{array}{cc}{t}_0& =0,\\ t_{2n}& =t_n,\\ t_{2n+1}& =1-t_n,\end{array}$

for all non-negative integers Template:Mvar.

L-system

Thue–Morse sequence generated by an L-System

The Thue–Morse sequence is a morphic word: it is the output of the following Lindenmayer system:

Variables	Template:Math, Template:Math
Constants	none
Start	Template:Math
Rules	Template:Math, Template:Math

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. The first element is Template:Math. Once the first Template:Math elements have been specified, forming a string Template:Mvar, then the next Template:Math elements must form the bitwise negation of Template:Mvar. Now we have defined the first Template:Math elements, and we recurse.

Spelling out the first few steps in detail:

• We start with Template:Math.
• The bitwise negation of Template:Math is Template:Math.
• Combining these, the first 2 elements are Template:Math.
• The bitwise negation of Template:Math is Template:Math.
• Combining these, the first 4 elements are Template:Math.
• The bitwise negation of Template:Math is Template:Math.
• Combining these, the first 8 elements are Template:Math.
• And so on.

So

• Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• Template:Math.
• And so on.

In Python:

def thue_morse_bits(n: int) -> int:
	"""Return an int containing the first 2**n bits of the Thue–Morse sequence, low-order bit 1st."""
	bits = 0
    for i in range(n):
        bits |= ((1 << (1 << i)) - 1 - bits) << (1 << i)
    return bits

Which can then be converted to a (reversed) string as follows:

n = 7
print(f"{thue_morse_bits(n):0{1<<n}b}")

Generating function

A generating function for the sequence can be defined by:

$\prod _{i=0}^{\mathrm{\infty }}(1-x^{2^i})=\sum _{j=0}^{\mathrm{\infty }}(-1{)}^{t_j}{x}^j,$

where Template:Math is the Template:Mvarth element if we start at Template:Math.

Properties

The Thue–Morse sequence contains many squares: instances of the string Template:Math, where Template:Math denotes the string Template:Math, Template:Math, Template:Math, or Template:Math, where Template:Math for some Template:Math and Template:Math is the bitwise negation of Template:Math.Template:Sfnp For instance, if Template:Math, then Template:Math. The square Template:Math appears in Template:Math starting at the 16th bit. Since all squares in Template:Math are obtained by repeating one of these 4 strings, they all have length Template:Math or Template:Math for some Template:Math. Template:Math contains no cubes: instances of Template:Math for any Template:Math. There are also no overlapping squares: instances of Template:Math or Template:Math. The critical exponent of Template:Math is Template:Math.Template:Sfnp

The Thue–Morse sequence is a uniformly recurrent word: given any finite string Template:Mvar in the sequence, there is some length Template:Math (often much longer than the length of Template:Mvar) such that Template:Mvar appears in every block of length Template:Math.Template:Sfnp Notably, the Thue–Morse sequence is uniformly recurrent without being either periodic or eventually periodic (i.e., periodic after some initial nonperiodic segment).

The sequence Template:Math is a palindrome for any Template:Mvar. Furthermore, let Template:Math be a word obtained by counting the ones between consecutive zeros in Template:Math . For instance, Template:Math and Template:Math. Since Template:Math does not contain overlapping squares, the words Template:Math are palindromic squarefree words.

The Thue–Morse morphism Template:Mvar is defined on alphabet Template:Math by the substitution map Template:Math, Template:Math: every Template:Math in a sequence is replaced with Template:Math and every Template:Math with Template:Math. If Template:Mvar is the Thue–Morse sequence, then Template:Math is also Template:Mvar. Thus, Template:Mvar is a fixed point of Template:Mvar. The morphism Template:Mvar is a prolongable morphism on the free monoid Template:Math with Template:Mvar as fixed point: Template:Mvar is essentially the only fixed point of Template:Mvar; the only other fixed point is the bitwise negation of Template:Mvar, which is simply the Thue–Morse sequence on Template:Math instead of on Template:Math. This property may be generalized to the concept of an automatic sequence.

In the Thue–Morse sequence, the symbols Template:Math and Template:Math can be replaced with the variables Template:Mvar and Template:Mvar to obtain a generalized Thue–Morse sequence. If Template:Mvar and Template:Mvar are distinct positive integers, then the resulting sequence can be taken to be the terms of a simple continued fraction. The resulting Thue–Morse continued fraction,

$[a;b,b,a,b,a,a,b,\dots ]=a+\frac{1}{b+\frac{1}{b+\frac{1}{a+\frac{1}{b+\frac{1}{a+\frac{1}{a+\frac{1}{b+\ddots }}}}}}},$

is transcendental.

In combinatorial game theory

The set of evil numbers (numbers Template:Math with Template:Math) forms a subspace of the nonnegative integers under nim-addition (bitwise exclusive or). For the game of Kayles, evil nim-values occur for few (finitely many) positions in the game, with all remaining positions having odious nim-values.

Prouhet–Tarry–Escott problem

The Prouhet–Tarry–Escott problem can be defined as: given a positive integer Template:Mvar and a non-negative integer Template:Mvar, partition the set Template:Math into two disjoint subsets Template:Math and Template:Math that have equal sums of powers up to Template:Mvar, that is:

$\sum _{x\in S_0}{x}^i=\sum _{x\in S_1}{x}^i$ for all integers Template:Mvar from Template:Math to Template:Mvar.

This has a solution if Template:Mvar is a multiple of Template:Math, given by:

• Template:Math consists of the integers Template:Mvar in Template:Mvar for which Template:Math,
• Template:Math consists of the integers Template:Mvar in Template:Mvar for which Template:Math.

For example, for Template:Math and Template:Math,

Template:Math

Template:Math

The condition requiring that Template:Mvar be a multiple of Template:Math is not strictly necessary: there are some further cases for which a solution exists. However, it guarantees a stronger property: if the condition is satisfied, then the set of Template:Mvarth powers of any set of Template:Mvar numbers in arithmetic progression can be partitioned into two sets with equal sums. This follows directly from the expansion given by the binomial theorem applied to the binomial representing the Template:Mvarth element of an arithmetic progression.

For generalizations of the Thue–Morse sequence and the Prouhet–Tarry–Escott problem to partitions into more than two parts, see Bolker, Offner, Richman and Zara, "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences".Template:Sfnp

Fractals and turtle graphics

Using turtle graphics, a curve can be generated if an automaton is programmed with a sequence. Using the Thue–Morse sequence, the rules

• If Template:Math, move ahead by one unit,
• If Template:Math, rotate by an angle of Template:Math radians (60°)

generate a curve that converges to the Koch curve, a fractal curve of infinite length containing a finite area. This illustrates the fractal nature of the Thue–Morse Sequence.Template:Sfnp

It is also possible to draw the curve precisely using the following instructions:

• If Template:Math, rotate by an angle of Template:Mvar radians (180°),
• If Template:Math, move ahead by one unit, then rotate by an angle of Template:Math radians.

Equitable sequencing

In their book on the problem of fair division, Steven Brams and Alan Taylor invoked the Thue–Morse sequence but did not identify it as such. When allocating a contested pile of items between two parties who agree on the items' relative values, Brams and Taylor suggested a method they called balanced alternation, or taking turns taking turns taking turns ... , as a way to circumvent the favoritism inherent when one party chooses before the other. An example showed how a divorcing couple might reach a fair settlement in the distribution of jointly owned items. The parties would take turns to be the first chooser at different points in the selection process: Ann chooses one item, then Ben does, then Ben chooses one item, then Ann does.Template:Sfnp

Lionel Levine and Katherine E. Stange, in their discussion of how to fairly apportion a shared meal such as an Ethiopian dinner, proposed the Thue–Morse sequence as a way to reduce the advantage of moving first. They suggested that "it would be interesting to quantify the intuition that the Thue–Morse order tends to produce a fair outcome".Template:Sfnp

Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication. He presented the sequences [[#Characterization using bitwise negation|Template:Math]] as step functions on the interval Template:Math and described their relationship to the Walsh and Rademacher functions. He showed that the Template:Mvarth derivative can be expressed in terms of Template:Math. As a consequence, the step function arising from Template:Math is orthogonal to polynomials of order Template:Math. A consequence of this result is that a resource whose value is expressed as a monotonically decreasing continuous function is most fairly allocated using a sequence that converges to Thue–Morse as the function becomes flatter. An example showed how to pour cups of coffee of equal strength from a carafe with a nonlinear concentration gradient, prompting a whimsical article in the popular press.Template:Sfnp

Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events. They considered the fairest way to stage a Galois duel, in which each of the shooters has equally poor shooting skills. Cooper and Dutle postulated that each dueler would demand a chance to fire as soon as the other's a priori probability of winning exceeded their own. They proved that, as the duelers' hitting probability approaches zero, the firing sequence converges to the Thue–Morse sequence. In so doing, they demonstrated that the Thue–Morse order produces a fair outcome not only for sequences [[#Characterization using bitwise negation|Template:Math]] of length Template:Math, but for sequences of any length.

Thus the mathematics supports using the Thue–Morse sequence instead of alternating turns when the goal is fairness but earlier turns differ monotonically from later turns in some meaningful quality, whether that quality varies continuously or discretely.

Sports competitions form an important class of equitable sequencing problems, because strict alternation often gives an unfair advantage to one team. Ignacio Palacios-Huerta proposed changing the sequential order to Thue–Morse to improve the ex post fairness of various tournament competitions, such as the kicking sequence of a penalty shoot-out in soccer.Template:Sfnp He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or Template:Math), 54% using ABBA (or Template:Math), and 51% using full Thue–Morse (or Template:Math).  As a result, ABBA is undergoing extensive trials in FIFA (European and World Championships) and English Federation professional soccer (EFL Cup).Template:Sfnp An ABBA serving pattern has also been found to improve the fairness of tennis tie-breaks.Template:Sfnp In competitive rowing, Template:Math is the only arrangement of port- and starboard-rowing crew members that eliminates transverse forces (and hence sideways wiggle) on a four-membered coxless racing boat, while Template:Math is one of only four rigs to avoid wiggle on an eight-membered boat.Template:Sfnp

Fairness is especially important in player drafts. Many professional sports leagues attempt to achieve competitive parity by giving earlier selections in each round to weaker teams. By contrast, fantasy football leagues have no pre-existing imbalance to correct, so they often use a "snake" draft (forward, backward, etc.; or Template:Math). Ian Allan argued that a "third-round reversal" (forward, backward, backward, forward, etc.; or Template:Math) would be even more fair. Richman suggested that the fairest way for "captain A" and "captain B" to choose sides for a pick-up game of basketball mirrors Template:Math: captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.

Hash collisions

The initial Template:Math bits of the Thue–Morse sequence are mapped to Template:Math by a wide class of polynomial hash functions modulo a power of two, which can lead to hash collisions.

Riemann zeta function

Certain linear combinations of Dirichlet series whose coefficients are terms of the Thue–Morse sequence give rise to identities involving the Riemann Zeta function (Tóth, 2022). For instance:

$\begin{array}{cc}\sum _{n\ge 1}\frac{5t_{n-1}+3t_n}{n^2}& =4\zeta (2)=\frac{2{\pi }^2}{3},\\ \sum _{n\ge 1}\frac{9t_{n-1}+7t_n}{n^3}& =8\zeta (3),\end{array}$

where Template:Math is the Template:Mathth term of the Thue–Morse sequence. In fact, for all Template:Math with real part greater than Template:Math, we have

$(2^s+1)\sum _{n\ge 1}\frac{t_{n-1}}{n^s}+(2^s-1)\sum _{n\ge 1}\frac{t_n}{n^s}=2^s\zeta (s).$

History

The Thue–Morse sequence was first studied by Template:Ill 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. 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: by using its cube-free property (see above), he showed how to circumvent the threefold repetition rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw. At the time, consecutive identical board states were required to trigger the rule; the rule was later amended to the same board position reoccurring three times at any point, as the sequence shows that the consecutive criterion can be evaded forever.

See also

• Dejean's theorem
• Fabius function
• First difference of the Thue–Morse sequence
• Gray code
• Komornik–Loreti constant
• Prouhet–Thue–Morse constant

References

• Template:Cite news
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite journal

Further reading

• Template:Cite book
• Template:Cite book

External links

• Template:Springer
• Template:MathWorld
• Allouche, J.-P.; Shallit, J. O. The Ubiquitous Prouhet–Thue–Morse Sequence. (contains many applications and some history)
• Thue–Morse Sequence over (1,2) Template:OEIS
• Template:OEIS el
• Template:OEIS el
• Reducing the influence of DC offset drift in analog IPs using the Thue–Morse Sequence. A technical application of the Thue–Morse Sequence
• MusiNum – The Music in the Numbers. Freeware to generate self-similar music based on the Thue–Morse Sequence and related number sequences.
• Template:Cite web