The Thue-Morse Transform

This paper introduces the Thue-Morse transform on binary sequences, demonstrating that its iterates generate new families of solutions to the Prouhet-Tarry-Escott problem, establish functional equations for generalized evil and odious numbers, and reveal a complete hierarchical factor complexity for Mersenne levels, while also extending these concepts to $d$-ary and Fibonacci-based numeration systems.

The Gist

Imagine you have a giant, infinite row of light switches, each either ON (1) or OFF (0). This row represents a sequence of numbers. The most famous row of switches in mathematics is the Thue-Morse sequence. It's a pattern that looks random but is actually generated by a very strict rule: it never repeats the same block of switches three times in a row, and it has a perfect balance of ONs and OFFs.

This paper introduces a new "machine" called the Thue-Morse Transform. Think of this machine as a magical loom that takes a row of switches and weaves a new row of switches based on the positions of the old ones.

Here is the simple breakdown of what the paper does, using everyday analogies:

1. The Machine: Sorting the Switches

Imagine you have a row of switches.

• The "Evil" Switches: These are the switches that are OFF (0).
• The "Odious" Switches: These are the switches that are ON (1).

The machine looks at the positions (the address numbers) of all the OFF switches and all the ON switches. It then uses these two lists of addresses to build a brand new row of switches.

• If a position was an "OFF" address in the old row, the new switch at that spot copies the value of the index of that switch.
• If a position was an "ON" address, the new switch does the opposite (flips the bit).

The author takes the classic Thue-Morse row, runs it through this machine, gets a new row, runs that new row through the machine, and keeps going. This creates a Tower of Sequences.

2. The Secret Code: The "Bitmask"

The paper's biggest discovery is that this complicated, repetitive machine process isn't actually random or messy. It follows a simple, hidden code.

Imagine you have a stencil (a mask) with holes in it.

• If you hold this stencil over a number written in binary (like a computer sees it: 0s and 1s), you only look at the digits where the stencil has holes.
• The paper proves that every single row in this infinite tower is just the result of looking at a number through a specific stencil and counting whether the visible holes have an odd or even number of 1s.

The "stencil" changes depending on which level of the tower you are on. Level 0 is the original Thue-Morse. Level 1 uses a slightly different stencil, Level 2 uses another, and so on. This "stencil formula" allows mathematicians to predict the entire infinite row instantly without having to build it step-by-step.

3. The Magic Trick: The Prouhet-Tarry-Escott Problem

Why do we care about these rows of switches? They solve a very old, difficult math puzzle called the Prouhet-Tarry-Escott problem.

The Analogy: Imagine you have a bag of numbered balls (0, 1, 2, 3...). You want to split them into two piles (Pile A and Pile B) such that:

1. The sum of the numbers in Pile A equals the sum in Pile B.
2. The sum of the squares of the numbers in Pile A equals the sum of the squares in Pile B.
3. The sum of the cubes... and so on, up to a very high power.

Usually, this is incredibly hard to do. But the Thue-Morse sequence (and the new rows generated by the machine) acts like a perfect sorting hat. If you put the first $2^L$ numbers into Pile A or B based on whether their switch is ON or OFF, the sums of powers will match perfectly up to a certain degree.

The paper shows that by using the new "stencil" levels, we can create new families of these perfect splits, allowing us to match sums of powers to much higher degrees than before.

4. The "Correction" Ghost

In the original Thue-Morse sequence, the relationship between the positions of the ONs and OFFs was very simple and constant (like a straight line).

However, as the author runs the machine again and again (creating Level 1, Level 2, etc.), this relationship gets complicated. It's no longer a straight line; it starts to wiggle. The paper proves that these "wiggles" (called corrections) aren't random noise. They follow their own strict, predictable patterns (called automatic sequences). It's like the machine adds a tiny, rhythmic "glitch" to the pattern every time it runs, but that glitch is actually a secret message that can be decoded.

5. Beyond the Binary World

The paper doesn't stop at just ON/OFF switches.

• The Multi-Color Version: The author shows how to do this with 3, 4, or more colors of switches (not just black and white), expanding the magic trick to different number systems.
• The Fibonacci Version: The author tries the machine on a different famous pattern based on the Fibonacci numbers (1, 1, 2, 3, 5...). While it doesn't work exactly the same way as the binary version, it creates a beautiful, slightly different kind of mathematical shadow that still solves parts of the puzzle.

Summary

In short, this paper takes a famous mathematical pattern, builds a machine to generate new versions of it, and discovers that:

1. There is a simple secret code (a stencil) that describes every single new pattern.
2. These patterns are super-sorts that perfectly balance complex mathematical sums.
3. The "glitches" in the patterns are actually structured messages that reveal deep connections between numbers.

It turns a complex, iterative process into a clear, predictable, and beautiful mathematical structure.

Technical Summary

1. Problem Statement and Motivation

The paper addresses the structural properties of binary sequences generated by iterating a specific operator, the Thue–Morse Transform (TM-transform), starting from the classical Thue–Morse sequence.

• The Operator: Given a binary sequence $\sigma$ (starting with 01 and containing infinitely many 0s and 1s), the TM-transform $T(\sigma)$ creates a new sequence $\tau$ by mapping the positions of 0s (called "evil numbers") and 1s ("odious numbers") of $\sigma$ to the values of $\tau$. Specifically, if $v_\sigma(n)$ and $u_\sigma(n)$ are the $n$-th positions of 0 and 1 in $\sigma$, then $\tau(v_\sigma(n)) = \tau(n)$ and $\tau(u_\sigma(n)) = 1 - \tau(n)$.
• The Goal: The author investigates the orbit of the classical Thue–Morse sequence $t(n) = s_2(n) \pmod 2$ under repeated application of this transform ($a_0 = t, a_{m+1} = T(a_m)$). The objectives are to:
  1. Find an explicit closed-form description of these iterates.
  2. Determine their solutions to the Prouhet–Tarry–Escott (PTE) problem (partitioning integers into sets with equal sums of powers).
  3. Analyze the composition laws of the generalized evil and odious numbers associated with these sequences.
  4. Calculate the factor complexity (subword complexity) of the resulting infinite words.
  5. Explore extensions to non-dyadic settings (base $d$ and Fibonacci numeration).

2. Methodology

The paper employs a combination of combinatorial number theory, generating functions, and automata theory.

• Bit-Mask Representation: The core methodology involves translating the recursive definition of the transform into a bitwise operation. The author defines a "mask" $m$ that selects specific bit positions in the binary expansion of an integer $n$.
• Generating Functions: To prove PTE identities, the author utilizes generating functions of the form $F_S(x) = \sum (-1)^{f_S(n)} x^n$. By analyzing the order of vanishing of these functions at $x=1$, the author establishes equal sums of powers.
• Desubstitution and Derived Sequences: For factor complexity, the paper introduces a "derived sequence" $\Delta(n) = a_m(n) \oplus a_m(n+1)$. By showing that $\Delta$ satisfies a uniform substitution rule, the complexity of the original sequence is reduced to that of the derived sequence.
• Recursive Composition Analysis: The paper analyzes the functional equations governing the $n$-th generalized evil ($v_m$) and odious ($u_m$) numbers, identifying "correction terms" that arise from the interaction of bit positions.

3. Key Contributions and Results

A. Explicit Closed Form (The Iterated Tower)

The primary structural result is the identification of the $m$-th iterate $a_m(n)$ with an explicit bit-mask formula:
$$a_m(n) = \bigoplus_{p \ge 0, \, p \,\&\, m = 0} b_p(n)$$
where $b_p(n)$ is the $p$-th binary digit of $n$, $\oplus$ is XOR, and $\&$ is bitwise AND.

• Interpretation: The sequence $a_m$ is the parity of the sum of binary digits of $n$ at positions $p$ that are disjoint from the binary support of $m$.
• Significance: This transforms the recursive definition into a direct arithmetic formula, revealing that the "tower" of sequences is governed by the selection of bit positions based on the mask $m$.

B. Generalized Prouhet–Tarry–Escott (PTE) Solutions

The paper proves that each level $m$ of the tower generates new families of PTE solutions.

• Theorem: For a mask $m$, let $S(m)$ be the set of selected bit positions per period. Let $s_m = |S(m)|$. On an interval of length $N = B(m)^L$ (where $B(m)$ is a power of 2 related to the period), the partition induced by $a_m$ yields equal sums of powers up to degree $s_m L - 1$.
• Novelty: Unlike classical Prouhet constructions where the degree depends on the interval size, here the degree is controlled by the mask parameter $m$ (specifically the number of selected bits $s_m$). This allows for constructing PTE solutions of arbitrary high degree by choosing appropriate masks.

C. Functional Equations for Generalized Evil/Odious Numbers

The paper extends the classical composition formulas for evil ($v$) and odious ($u$) numbers (e.g., $u(u(n)) = 2u(n)$).

• Result: For the iterated sequences, the composition laws hold but include non-constant correction terms that are themselves automatic sequences.
  • Example (Odd $m$): $u_m(u_m(n)) = 2u_m(n) + 1 - c_m(n)$, where $c_m(n)$ is a specific automatic sequence derived from the mask.
• Cross-Level Interaction: The paper derives functional equations for compositions across different levels ($u_m \circ u_{m'}$), showing that the correction terms depend on the parity of the outer mask $m$.

D. Factor Complexity

The paper provides a complete analysis of the factor complexity $p_{a_m}(n)$ (the number of distinct subwords of length $n$) for Mersenne levels ($m = 2^k - 1$).

• Initial Linear Regime: For $n \le B(m) + 1$, the complexity is exactly $2n$.
• Piecewise Formula: For larger $n$, the complexity follows a hierarchical piecewise formula involving growth phases and plateaus. The proof relies on a desubstitution argument on the derived sequence $\Delta$, which is shown to be a fixed point of a uniform substitution.
• Non-Mersenne Levels: The paper notes that for non-Mersenne masks, the structure is more complex, and a complete closed formula remains an open problem.

E. Extensions Beyond the Dyadic Setting

1. Base-$d$ Generalization: The PTE mechanism is extended to arbitrary bases $d$. The mask $m$ selects digit positions in base $d$, and the resulting partitions satisfy equal power sums up to degree $s_m L - 1$.
2. Meta-Thue–Morse Sequence: The author shows that the transform works on the "meta-Thue–Morse" sequence $M_2$ (a 4-automatic sequence), generating a distinct family of PTE solutions, suggesting the mechanism is robust across different automatic templates.
3. Fibonacci Analogue: The paper explores applying the transform to the Fibonacci–Thue–Morse sequence (based on Zeckendorf numeration). While it yields a "PTE shadow" (balanced partitions at degree 0), the lack of independent digits prevents the clean product factorization seen in the dyadic case, resulting in non-vanishing defects for higher degrees.

4. Significance

• Unification: The paper unifies the study of the Thue–Morse sequence, PTE problems, and automatic sequences under a single operator (the TM-transform).
• Explicit Construction: It provides the first explicit closed-form description for the iterates of the Thue–Morse transform, moving beyond recursive definitions.
• New PTE Families: It introduces a new parameterized family of PTE solutions where the degree is tunable via the bit-mask, extending Prouhet's classical work.
• Structural Insight: The discovery that the "correction terms" in composition laws are automatic sequences (rather than constants) reveals a richer arithmetic structure in the iterated tower than previously known.
• Complexity Analysis: The exact determination of factor complexity for Mersenne levels provides a benchmark for understanding the combinatorial complexity of iterated automatic sequences.

5. Open Problems

The paper concludes by highlighting several open directions:

1. Base-$d$ Composition Theory: Developing the full composition theory (correction sets and functional equations) for bases $d \ge 3$.
2. General Seeds: Characterizing which binary sequences (beyond Thue–Morse and $M_2$) yield structured TM-transform orbits.
3. Complexity of Non-Mersenne Levels: Finding a closed formula for the factor complexity of $a_m$ when $m$ is not a Mersenne number.
4. Fibonacci Tower: Understanding the structure of the orbit if the Fibonacci–Thue–Morse sequence is used as the seed.

In summary, Benoît Cloitre's paper establishes a rigorous arithmetic framework for the "Thue–Morse Transform," revealing a deep hierarchy of binary sequences with explicit formulas, rich PTE properties, and complex combinatorial structures.