Thue–Morse sequence

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. The full sequence begins:

01101001100101101001011001101001.... (sequence A010060 in the OEIS)

Any other ordered pair of symbols may be used instead of 0 and 1; the logical structure of the Thue–Morse sequence does not depend on the symbols that are used to represent it.

Definition

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

Direct definition

To compute the n^th element t_n, write the number n in binary. If the number of ones in this binary expansion is odd then t_n = 1, if even then t_n = 0.^[1] For this reason John H. Conway et al. call numbers n satisfying t_n = 1 odious (for odd) numbers and numbers for which t_n = 0 evil (for even) numbers. In other words, t_n = 0 if n is an evil number and t_n = 1 if n is an odious number.

This method leads to a fast method for computing the Thue–Morse sequence: start with t₀ = 0, and then, for each n, find the highest-order bit in the binary representation of n that is different from the same bit in the representation of n − 1. (This bit can be isolated by letting x be the bitwise exclusive or of n and n − 1, shifting x right by one bit, and computing the exclusive or of this shifted value with x.) If this bit is at an even index, t_n differs from t_n − 1, and otherwise it is the same as t_n − 1. The resulting algorithm takes constant time to generate each sequence element, using only a logarithmic number of bits (constant number of words) of memory.^[2]

Recurrence relation

The Thue–Morse sequence is the sequence t_n satisfying the recurrence relation

t₀	= 0,
t_2n	= t_n, and
t_2n+1	= 1 − t_2n.

for all positive integers n.^[1]

L-system

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

Variables	0, 1
Constants	None
Start	0
Rules	(0 → 01), (1 → 10)

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.

T₀ = 0.
T₁ = 01.
T₂ = 0110.
T₃ = 01101001.
T₄ = 0110100110010110.
T₅ = 01101001100101101001011001101001.
T₆ = 0110100110010110100101100110100110010110011010010110100110010110.
And so on.

Infinite product

The sequence can also be defined by:

\prod _{i=0}^{\infty }(1-x^{2^{i}})=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j}{\mbox{,}}\!

where t_j is the j^th 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. Indeed, $X$ is such a string if and only if $X=A,\,{\overline {A}},\,A{\overline {A}}A,$ or ${\overline {A}}A{\overline {A}}$ where $A=T_{k}$ for some $k\geq 0$ and ${\overline {A}}$ denotes the bitwise negation of $A$ (interchange 0s and 1s).^[4] For instance, with $k=0$ , we have $\ A=T_{0}=0$ , and the square $A{\overline {A}}AA{\overline {A}}A=010010$ appears in $T$ starting at the 16th bit. (Thus, squares in $T$ have length either a power of 2 or 3 times a power of 2.) However, there are no cubes: instances of XXX. There are also no overlapping squares: instances of 0X0X0 or 1X1X1.^[5]^[6] The critical exponent is 2.^[7]

Notice that T_2n is palindrome for any n > 1. Further, let q_n be a word obtain from T_2n by counting ones between consecutive zeros. For instance, q₁ = 2 and q₂ = 2102012 and so on. The words T_n do not contain overlapping squares in consequence, the words q_n are palindrome squarefree words.

The statement above that the Thue–Morse sequence is "filled with squares" can be made precise: It is a uniformly recurrent word, 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_X.^[8]^[9] 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 uniformly recurrent without being periodic, not even eventually periodic (meaning periodic after some nonperiodic initial segment).^[10]

We define the Thue–Morse morphism to be the function f from the set of binary sequences to itself by replacing every 0 in a sequence with 01 and every 1 with 10.^[11] Then if T is the Thue–Morse sequence, then f(T) is T again; that is, T is a fixed point of f. The function f is a prolongable morphism on the free monoid {0,1}^∗ with T as fixed point: indeed, 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 generalized to the concept of an automatic sequence.

The generating series of T over the binary field is the formal power series

t(Z)=\sum _{n=0}^{\infty }T(n)Z^{n}\ .

This power series is algebraic over the field of formal power series, satisfying the equation^[12]

Z+(1+Z)^{2}t+(1+Z)^{3}t^{2}=0

In combinatorial game theory

The set of evil numbers (numbers $n$ with $t_{n}=0$ ) 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.

The Prouhet–Tarry–Escott problem

The Prouhet–Tarry–Escott problem can be defined as: given a positive integer N and a non-negative integer k, partition the set S = { 0, 1, ..., N-1 } into two disjoint subsets S₀ and S₁ that have equal sums of powers up to k, that is:

\sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}

for all integers i from 1 to k.

This has a solution if N is a multiple of 2^k+1, given by:

S₀ consists of the integers n in S for which t_n = 0,
S₁ consists of the integers n in S for which t_n = 1.

For example, for N = 8 and k = 2,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

The condition requiring that N be a multiple of 2^k+1 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 k^th powers of any set of N 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 n^th element of an arithmetic progression.

Fractals and Turtle graphics

A Turtle Graphics is the curve that is generated if an automaton is programmed with a sequence. If the Thue–Morse Sequence members are used in order to select program states:

If t(n) = 0, move ahead by one unit,
If t(n) = 1, rotate counterclockwise by an angle of π/3,

the resulting curve converges to the Koch snowflake, a fractal curve of infinite length containing a finite area. This illustrates the fractal nature of the Thue–Morse Sequence.^[13]

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.^[14]

Lionel Levine and Katherine 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.”^[15]

Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication.^[16] He presented the sequences T_n as step functions on the interval [0,1] and described their relationship to the Walsh and Rademacher functions. He showed that the n^th derivative can be expressed in terms of T_n. As a consequence, the step function arising from T_n is orthogonal to polynomials of order n − 1. 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.^[17]

Joshua Cooper and Aaron Dutle showed why the Thue-Morse order provides a fair outcome for discrete events.^[18] 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 T_n of length 2ⁿ, 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^[16] or discretely.^[18]

Sports competitions form an important class of equitable sequencing problems, because strict alternation often gives an unfair advantage to one team. Richman suggested that the fairest way for “captain A” and “captain B” to choose sides for a pick-up game of basketball mirrors T₃: captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.^[16] 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, the rotation of color of pieces in a chess match, and the serving order in a tennis tie-break.^[19]

History

The Thue–Morse sequence was first studied by Eugène 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. 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, who held the world championship title from 1935 to 1937, 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 a rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.

Notes

References

Abrahams, Marc (12 July 2010). "How to pour the perfect cup of coffee". The Guardian.
Arndt, Jörg (2011). "1.16.4 The Thue–Morse sequence". Matters Computational: Ideas, Algorithms, Source Code (PDF). Springer. p. 44.
Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. p. 7. ISBN 978-0-521-51597-9. Zbl 1197.68006.
Brams, Steven J.; Taylor, Alan D. (1999). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. W. W. Norton & Co., Inc. pp. 36–44. ISBN 0-393-04729-6.
Brlek, Srećko (1989). "Enumeration of Factors in the Thue-Morse Word". Discrete Applied Mathematics. 24: 83–96. doi:10.1016/0166-218x(92)90274-e.
Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl pre06066616.
Cooper, Joshua; Dutle, Aaron (2013). "Greedy Galois Games" (PDF). American Mathematical Monthly. 120 (5): 441–451. doi:10.4169/amer.math.monthly.120.05.441.
Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe. Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006. Lecture Notes in Computer Science. 4036. Springer-Verlag. pp. 280–291. ISBN 3-540-35428-X. Zbl 1227.68074.
Levine, Lionel; Stange, Katherine E. (2012). "How to Make the Most of a Shared Meal: Plan the Last Bite First" (PDF). American Mathematical Monthly. 119 (7): 550–565. doi:10.4169/amer.math.monthly.119.07.550.
Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
Ma, Jun; Holdener, Judy (2005). "When Thue-Morse meets Koch" (PDF). Fractals. 13 (3): 191–206. doi:10.1142/S0218348X05002908. MR 2166279.
Palacios-Huerta, Ignacio (2012). "Tournaments, fairness and the Prouhet–Thue–Morse sequence" (PDF). Economic inquiry. 50 (3): 848–849. doi:10.1111/j.1465-7295.2011.00435.x.
Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
Richman, Robert (2001). "Recursive Binary Sequences of Differences" (PDF). Complex Systems. 13 (4): 381–392.

External links

Wikimedia Commons has media related to Thue–Morse sequence.

Hazewinkel, Michiel, ed. (2001), "Thue-Morse sequence", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Weisstein, Eric W. "Thue-Morse Sequence". 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) (sequence A001285 in the OEIS)
Odious numbers (sequence A000069 in the OEIS)
Evil numbers (sequence A001969 in the OEIS)
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.
Parker, Matt. "The Fairest Sharing Sequence Ever" (video). standupmaths. Retrieved 20 January 2016.

This article is issued from Wikipedia - version of the 12/1/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.