Editing Thue–Morse sequence (section)

== Properties ==
The Thue–Morse sequence contains many ''squares'': instances of the string <math>XX</math>, where <math>X</math> denotes the string <math>A</math>, <math>\overline{A}</math>, <math>A \overline{A}A</math>, or <math>\overline{A}A \overline{A}</math>, where <math>A=T_{k}</math> for some <math>k\ge 0</math> and <math>\overline{A}</math> is the bitwise negation of <math>A</math>.{{sfnp|Brlek|1989}} For instance, if <math>k=0</math>, then <math>A=T_{0}=0 </math>. The square <math>A \overline{A}AA \overline{A}A = 010010</math> appears in <math>T</math> starting at the 16th bit. Since all squares in <math>T</math> are obtained by repeating one of these 4 strings, they all have length <math>2^n</math> or <math>3\cdot2^n</math> for some <math>n\ge 0</math>. <math>T</math> contains no ''cubes'': instances of <math>XXX</math>. There are also no ''overlapping squares'': instances of <math>0X0X0</math> or <math>1X1X1</math>.<ref name=ACOW113>{{harvtxt|Lothaire|2011|p=113}}</ref><ref name=PF103>{{harvtxt|Pytheas Fogg|2002|p=103}}</ref> The [[Critical exponent of a word|critical exponent]] of <math>T</math> is 2.{{sfnp|Krieger|2006}}

The Thue–Morse sequence is a [[uniformly recurrent word]]: given any finite string ''X'' in the sequence, there is some length ''n<sub>X</sub>'' (often much longer than the length of ''X'') such that ''X'' appears in ''every'' block of length ''n<sub>X</sub>''.<ref name=ACOW30>{{harvtxt|Lothaire|2011|p=30}}</ref>{{sfnp|Berthé|Rigo|2010}} Notably, the Thue–Morse sequence is uniformly recurrent ''without'' being either [[periodic sequence|periodic]] or eventually periodic (i.e., periodic after some initial nonperiodic segment).<ref name=ACOW31>{{harvtxt|Lothaire|2011|p=31}}</ref>

The sequence ''T''<sub>2''n''</sub> is a [[Palindromic number|palindrome]] for any ''n''. Furthermore, let ''q''<sub>''n''</sub> be a word obtained by counting the ones between consecutive zeros in ''T''<sub>2''n''</sub> . For instance, ''q''<sub>1</sub> = 2 and ''q''<sub>2</sub> = 2102012. Since ''T<sub>n</sub>'' does not contain ''overlapping squares'', the words ''q<sub>n</sub>'' are palindromic [[squarefree word]]s.

The '''Thue–Morse [[monoid morphism|morphism]]''' ''μ'' is defined on alphabet {0,1} by the substitution map ''μ''(0) = 01, ''μ''(1) = 10: every 0 in a sequence is replaced with 01 and every 1 with 10.<ref name=BLRS70>{{harvtxt|Berstel|Lauve|Reutenauer|Saliola|2009|p=70}}</ref> If ''T'' is the Thue–Morse sequence, then ''μ''(''T'') is also ''T''. Thus, ''T'' is a [[fixed point (mathematics)|fixed point]] of ''μ''. The morphism ''μ'' is a [[prolongable morphism]] on the [[free monoid]] {0,1}<sup>&lowast;</sup> with ''T'' as fixed point: ''T'' is essentially the ''only'' fixed point of ''μ''; 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]]

:<math>t(Z) = \sum_{n=0}^\infty T(n) Z^n \ . </math>

This [[power series]] is algebraic over the field of rational functions, satisfying the equation<ref name=BLRS80>{{harvtxt|Berstel|Lauve|Reutenauer|Saliola|2009|p=80}}</ref>

:<math>Z + (1+Z)^2 t + (1+Z)^3 t^2 = 0 </math>

=== In combinatorial game theory ===
The set of ''evil numbers'' (numbers <math>n</math> with <math>t_n=0</math>) forms a subspace of the nonnegative integers under [[nim-addition]] ([[bitwise operation|bitwise]] [[exclusive or]]).  For the game of [[Kayles]], evil [[nim-value]]s occur for few (finitely many) positions in the game, with all remaining positions having odious nim-values.

=== The Prouhet–Tarry–Escott problem === <!-- This section is linked to from [[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 of a set|partition]] the set ''S'' = { 0, 1, ..., ''N''-1 } into two [[Disjoint sets|disjoint]] subsets ''S''<sub>0</sub> and ''S''<sub>1</sub> that have equal sums of powers up to k, that is:
:<math> \sum_{x \in S_0} x^i = \sum_{x \in S_1} x^i</math> for all integers ''i'' from 1 to ''k''.

This has a solution if ''N'' is a multiple of 2<sup>''k''+1</sup>, given by:
* ''S''<sub>0</sub> consists of the integers ''n'' in ''S'' for which ''t<sub>n</sub>'' = 0,
* ''S''<sub>1</sub> consists of the integers ''n'' in ''S'' for which ''t<sub>n</sub>'' = 1.

For example, for ''N'' = 8 and ''k'' = 2,
:{{nowrap|1= 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,}}
:{{nowrap|1= 0<sup>2</sup> + 3<sup>2</sup> + 5<sup>2</sup> + 6<sup>2</sup> = 1<sup>2</sup> + 2<sup>2</sup> + 4<sup>2</sup> + 7<sup>2</sup>.}}

The condition requiring that ''N'' be a multiple of 2<sup>''k''+1</sup> 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.

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".{{sfnp|Bolker|Offner|Richman|Zara|2016}}

=== Fractals and turtle graphics ===
Using [[turtle graphics]], a curve can be generated if an automaton is programmed with a sequence.
When 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 by an angle of π/3 [[radian]]s (60°)

The resulting curve converges to the [[Koch snowflake|Koch curve]], a [[fractal curve]] of
infinite length containing a finite area. This illustrates the fractal nature of the Thue–Morse Sequence.{{sfnp|Ma|Holdener|2005}}

It is also possible to draw the curve precisely using the following instructions:<ref>{{Cite web|url=http://blog.zacharyabel.com/2012/01/thue-morse-navigating-turtles/|title=Thue-Morse Navigating Turtles|last=Abel|first=Zachary|date=January 23, 2012|website=Three-Cornered Things}}</ref>

*If ''t''(''n'') = 0, rotate by an angle of π radians (180°),
* If ''t''(''n'') = 1, move ahead by one unit, then rotate by an angle of π/3 radians.

===Equitable sequencing===
In their book on the problem of [[fair division]], [[Steven Brams]] and [[Alan D. Taylor|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.{{sfnp|Brams|Taylor|1999}}

[[Lionel Levine]] and [[Katherine E. Stange]], in their discussion of how to fairly apportion a shared meal such as an [[Ethiopian cuisine|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.”{{sfnp|Levine|Stange|2012}}

Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication.<ref name="richman">{{harvtxt|Richman|2001}}</ref>   He presented the sequences [[#Characterization using bitwise negation|''T<sub>n</sub>'']] as [[step function]]s on the interval [0,1] and described their relationship to the [[Walsh function|Walsh]] and [[Hans Rademacher|Rademacher]] functions.  He showed that the ''n''th [[derivative]] can be expressed in terms of  ''T<sub>n</sub>''.  As a consequence, the step function arising from  ''T<sub>n</sub>'' is [[Orthogonality|orthogonal]] to [[polynomial]]s of [[Degree of a polynomial|order]] ''n''&nbsp;&minus;&nbsp;1.  A consequence of this result is that a resource whose value is expressed as a [[Monotonic function|monotonically]] decreasing [[continuous function]] is most fairly allocated using a sequence that converges to Thue–Morse as the function becomes [[Flat function|flatter]].  An example showed how to pour cups of [[Drip brew|coffee]] of equal strength from a carafe with a [[Nonlinear system|nonlinear]] [[concentration]] [[gradient]], prompting a whimsical article in the popular press.{{sfnp|Abrahams|2010}}

Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events.<ref name="cooper">{{harvtxt|Cooper|Dutle|2013}}</ref>  They considered the fairest way to stage a [[Évariste Galois|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|''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|''T<sub>n</sub>'']] of length ''2<sup>n</sup>'', 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<ref name="richman" /> or discretely.<ref name="cooper" />

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 (association football)#Procedure|penalty shoot-out]] in soccer.{{sfnp|Palacios-Huerta|2012}} He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or ''T''<sub>1</sub>), 54% using ABBA (or ''T''<sub>2</sub>), and 51% using full Thue–Morse (or ''T''<sub>n</sub>).  As a result, ABBA is undergoing [[Penalty shoot-out (association football)#Advantage to team kicking first?|extensive trials]] in [[FIFA#FIFA competitions|FIFA (European and World Championships)]] and English Federation professional soccer ([[EFL Cup]]).{{sfnp|Palacios-Huerta|2014}} An ABBA serving pattern has also been found to improve the fairness of [[Tennis scoring system#Scoring a tiebreak game|tennis tie-breaks]].{{sfnp|Cohen-Zada|Krumer|Shapir|2018}} In [[Rowing (sport)|competitive rowing]], ''T''<sub>2</sub> is the only arrangement of [[Port and starboard|port- and starboard-rowing]] crew members that eliminates transverse forces (and hence sideways wiggle) on a four-membered coxless racing boat, while ''T''<sub>3</sub> is one of only four [[Boat rigging|rigs]]  to avoid wiggle on an eight-membered boat.{{sfnp|Barrow|2010}}

Fairness is especially important in [[Draft (sports)|player drafts]]. Many professional sports leagues attempt to achieve [[Parity (sports)|competitive parity]] by giving earlier selections in each round to weaker teams. By contrast, [[Fantasy football (American)|fantasy football leagues]] have no pre-existing imbalance to correct, so they often use a “snake” draft (forward, backward, etc.; or ''T''<sub>1</sub>).<ref>{{cite web |url=http://www.nfl.com/fantasyfootball/help/drafttypes |archive-url=https://web.archive.org/web/20181012053900/http://www.nfl.com/fantasyfootball/help/drafttypes |archive-date=October 12, 2018 |title=Fantasy Draft Types |work=[[National Football League|NFL.com]]}}</ref> Ian Allan argued that a “third-round reversal” (forward, backward, backward, forward, etc.; or ''T''<sub>2</sub>) would be even more fair.<ref>{{cite web |first=Ian |last=Allan |url=https://www.fantasyindex.com/2014/07/16/fantasy-news/third-round-reversal-drafts |title=Third-Round Reversal Drafts |date=July 16, 2014 |work=Fantasy Index |access-date=September 1, 2020}}</ref> Richman suggested that the fairest way for “captain A” and “captain B” to choose sides for a [[Streetball|pick-up game of basketball]] mirrors  ''T''<sub>3</sub>:  captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.<ref name="richman" />

=== Hash collisions ===
The initial {{math|2<sup>''k''</sup>}} bits of the Thue–Morse sequence are mapped to 0 by a wide class of polynomial [[hash function]]s modulo a [[power of two]], which can lead to [[hash collision]]s.<ref>{{cite journal |last1=Pachocki |first1=Jakub |last2=Radoszewski |first2=Jakub |title=Where to Use and How not to Use Polynomial String Hashing |journal=Olympiads in Informatics |date=2013 |volume=7 |pages=90–100 |url=https://ioinformatics.org/journal/INFOL119.pdf}}</ref>

===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 <ref>
{{cite journal|author1-link=Tóth|last1=Tóth|first1=László|title=Linear Combinations of Dirichlet Series Associated with the Thue-Morse Sequence|journal=Integers|volume=22|year=2022|issue=article 98|arxiv=2211.13570 }}
</ref>). For instance:
:<math>  \begin{align}
    \sum_{n\geq1} \frac{5 t_{n-1} + 3 t_n}{n^2} &= 4 \zeta(2) = \frac{2 \pi^2}{3}, \\
	\sum_{n\geq1} \frac{9 t_{n-1} + 7 t_n}{n^3} &= 8 \zeta(3),\end{align}</math>
where <math>(t_n)_{n\geq0}</math> is the <math>n^{\rm th}</math> term of the Thue–Morse sequence. In fact, for all <math>s</math> with real part greater than <math>1</math>, we have
:<math>  (2^s+1) \sum_{n\geq1} \frac{t_{n-1}}{n^s} + (2^s-1) \sum_{n\geq1} \frac{t_{n}}{n^s} = 2^s \zeta(s).</math>