Danger

This article is not yet released. If you’re seeing it, please note that it is not complete.

Prouhet-Thue-Morse Research 7: Property Preservation

2026-05-25

1. Foundations & Binary Numeric Definitions

2. Binary Definitions - Textual & Sequential

3. Binary Definitions - Others

4. Binary Equivalence

5. Extending the Alphabet

6. Extended Equivalence

7. Property Preservation (you are here)

8. Complexity and Honorable Mentions

Introduction

Proving Persistence (Or Lack Thereof) of Original Properties

Use as a Fair-Share Sequence

Note

Goal: show that for a variety of value functions, greedy algorithms given this turn order will always minimize inequality. They should at least do so more than the standard turn order. This is going to look like setting up an equation to show

\[\begin{split}\begin{equation} \begin{aligned} eq(x, y) &= \begin{cases} 1& \text{if } x = y \\ 0& \text{if } x \ne y \end{cases} \\ f(v, p, s) &= \lim_{n \to \infty} \sum_{i=0}^n v(i) \cdot eq(T_n(i, s), p) \\ \forall p : p &\in \{1, \dots, s-1\}\\ f(v, 0, s) + \epsilon &< f(v, p, s) < f(v, 0, s) - \epsilon \end{aligned} \end{equation}\end{split}\]

Note

This is for \(v(i)\) being a value function and \(\epsilon\) being an arbitrarily small number. \(f()\) is therefore the sum of total value that they will be receiving. For example, one could model a board game as \(v(i) = \tfrac{1}{2^i}\), where \(v()\) models the amount each turn contributes to your probability of victory. Note that this may be very hard to show for versions of \(v()\) which shrink too quickly, such as \(v(i) = \tfrac{1}{i!}\), so for those cases we must show that it’s better than the standard turn order

Note

\(v(0)\) should always return the highest value, and \(v(n)\) the lowest value, where \(n+1\) is the number of items

On the value function of 1

It is well known [CK] for the Standard Prouhet-Thue-Morse Sequence that

\[\begin{equation} \lim_{n\to\infty} \sum_{i=0}^n \dfrac{T_{2}(i)}{n+1} = \dfrac{1}{2} \end{equation}\]

Note

Does this generalize to: ?

\[\begin{equation} \lim_{n\to\infty} \sum_{i=0}^n\dfrac{T_{n}(i, s)}{n+1} = \sum_{i=0}^{s-1}\dfrac{i}{s} = \dfrac{n-1}{2} \end{equation}\]

Note

and

\[\begin{split}\begin{equation} \begin{aligned} &\forall{x} \;|\; 0 \le x < s \text{ and } x \in \mathbf{Z} \\ &\lim_{n\to\infty} \sum_{i=0}^n\dfrac{eq\left(T_{n}(i, s), x\right)}{n+1} = \dfrac{1}{s} \end{aligned} \end{equation}\end{split}\]

Galois Duels & Related Decreasing Functions

The OEIS Sequence A287150 [CD, Inc] gives an extension of \(T_{2,21}\) for 3 players. It should be noted that it is different from the extensions in this paper, meaning that this property is not preserved.

\[\begin{split}\begin{equation} \begin{aligned} T_3 &= \tuple{0, 1, 2, 1, 2, 0, 2, 0, 1, \dots} \\ A287150 &= \tuple{0, 1, 2, 2, 1, 0, 2, 1, 0, \dots} \end{aligned} \end{equation}\end{split}\]

Uniform Distributions

Let us have a value function that goes over a uniform distribution:

\[\begin{equation} v_u(x) = a+(b-a)(1-\dfrac{x}{n}) \end{equation} Where \begin{itemize} \item $a$ is the lower bound of the distribution \item $b$ is the upper bound of the distribution, and \item $n$ is the total number of items \end{itemize}\]

\begin{conjecture}
\label{conj:equit_dist_uniform}
For $n \ge 2$ players and $n^k$ items, greedily distributing items in the order $T_n$ will minimize the difference between players' received values, when values are distributed according to $v_u(x)$.
\end{conjecture}

Normal Distributions

Let us have a value function that goes over a normal distribution:

\[\begin{equation} v_n(x) =\mu-\sigma \cdot \Phi^{-1}\left(\dfrac{x}{n}\right) \end{equation} Where \begin{itemize} \item $\mu$ is the mean of the distribution \item $\sigma$ is the standard deviation, and \item $\Phi^{-1}$ is inverse CDF of the normal distribution \end{itemize}\]

\begin{conjecture}
\label{conj:equit_dist_normal}
For $n \ge 2$ players and $n^k$ items, greedily distributing items in the order $T_n$ will minimize the difference between players' received values, when values are distributed according to $v_n(x)$.
\end{conjecture}

Exponential Distributions

Let us have a value function that goes over an exponential distribution:

\[\begin{equation} v_e(x) = -\dfrac{1}{\lambda} \cdot \ln\left(1 - \dfrac{x}{n}\right) \end{equation}\]

Where \(\lambda\) is the rate parameter of the exponential distribution

\begin{conjecture}
\label{conj:equit_dist_exponential}
For $n \ge 2$ players and $n^k$ items, greedily distributing items in the order $T_n$ will minimize the difference between players' received values, when values are distributed according to $v_e(x)$.
\end{conjecture}

Discrete Value Distributions

It is trivial to show that for non-continuous value functions, neither the Standard nor Extended Prouhet-Thue-Morse Sequence distributed fairly. For example, consider a set of items with the value \(\{2^5, 2^3, 2^3, 1, 1, 1\}\). When split among two players, they will end up with a total value of \(\langle34, 17\rangle\). A more equitable distribution is achieved by giving player \(0\) the first item, and the remainder to player \(1\), resulting in \(\langle32, 19\rangle\). Similar observations can be made for larger numbers of players. This is left to the reader.

Palindrome

In base 2: \begin{equation}
    \forall x, y : (x > 1) \land (0 \le y < 2^x), \;\; t_2(x)_y = t_2(x)_{2^x - y - 1}
\end{equation}
\note{(Find a citation for this)}

\begin{proof}
\par\noindent\par
    \textbf{Assumption 1}: $n > 2$

    \textbf{Assumption 2}: $t_n(x)$ is palindromic, for $x > 1$

    \textbf{Observation 1}: $$t_n(x)_{n^x - 1} = p_n(n^x - 1) \equiv (n - 1)x \pmod{n}$$

    \textbf{Inference 1}: By Assumption 2, $t_n(x)_0 = 0 = t_n(x)_{n^x - 1}$

    \textbf{Observation 2}: $$t_n(x)_{n^x - 2} = p_n(n^x - 2) \equiv (n - 1)(x - 1) - 2 \pmod{n}$$

    \textbf{Inference 2}: By Assumption 2, $t_n(x)_1 = 1 = t_n(x)_{n^x - 2}$

    \textbf{Inference 3}: By Inferences 1 \& 2, \begin{equation}\begin{aligned}
        t_n(x)_{n^x-1} &\equiv t_n(x)_{n^x-2} - 1  \\
        (n - 1)x &\equiv (n - 1)(x - 1) - 2 - 1 \\
                &\equiv (n - 1)(x - 1) + (n - 1) - 2 \\
                &\equiv (n - 1)x - 2 \\
            0 &\equiv - 2 \\
    \end{aligned}
    \end{equation}

    \textbf{Contradiction!} While $n > 2$, these terms cannot be equal. This means that if the first and last terms match, the second and penultimate will not, and vice versa.
\end{proof}

Uniform Recurrence

Note

The Prouhet-Thue-Morse Sequence is a uniformly recurrent word: 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 nX. Tackle this by using \(T_{n,6}\)

Deriving Square Free Sequences

\note{Given a word $X : |X| > 1, X \in T_n$, $(X \concat X) \not\in T_n$. Square Free implies Overlap Free. The original \TMS is \textit{not} square-free, as it is not possible to construct a square-free sequence with an alphabet smaller than 3 (cite to Thue himself). However it can produce a square-free sequence easily by taking the difference of subsequent terms (A029883).}

Let $T_{dn}$ be the sequence generated by taking the difference of terms in the sequence $T_n$, such that $T_{d2} = \tuple{-1, 0, 1, -1, \ldots}$. The resulting sequence is square-free.

\begin{theorem}
\label{theo:square_free_dn}
This method does not generalize to $n \in \Integers_{\ge2}$
\begin{proof}
\par\noindent\par Proof by counterexample: \begin{itemize}
    \item $T_{d3}(19\dots25) = \tuple{-1, 1, -1, -1, 1, -1}$
    \item $T_{d4}(37\dots45) = \tuple{-1, -1, 2, -1, -1, -1, 2, -1}$
    \item $\forall n : n > 4,\; T_{dn}(0\dots3) = \tuple{-1,-1,-1,-1}$
\end{itemize}
\end{proof}
\end{theorem}

Another method to make a square-free sequence from $T_2$ is to construct a different alphabet \cite{offner_repetitions} using pairs of terms. This generates a new sequence $T_{p2} = \tuple{01, 11, 10, 01, 10, 00, \dots}$

\begin{conjecture}
\label{conj:square_free_pn}
This method generalizes to $T_n$ by iterating pairwise, making $T_{pn}$, where $T_{pn}(x) = \tuple{T_n(x), T_n(x+1)}$.
\end{conjecture}

\begin{proof}
    \note{Not sure how to do this rigorously, but computer testing hasn't found a counterexample}
\end{proof}

\begin{conjecture}
\label{conj:square_free_nxn}
This method generalizes to $T_n$ by iterating over a sliding window of size $n$, making $T_{n\times n}$, where $T_{n\times n}(x) = \tuple{T_n(x), T_n(x+1), \dots, T_n(x+n-1)}$.
\end{conjecture}

\begin{proof}
    \note{Not sure how to do this rigorously, but computer testing hasn't found a counterexample}
\end{proof}

Overlap Free

Extensions of the Prouhet-Thue-Morse Sequence that comply with \(T_{n,8}\) are overlap-free [Tom].

Note

Is that true? I thought they used invertible matrices in this paper, and I don’t think the general solution in \(T_{n,8}\) are invertible. Needs followup.

Note

Given a word \(X : |X| > 1, X \in T_n\), \((X \concat X \concat X_0) \not\in T_n\). For \(T_2\), this is shown in [Pan]. Note additionally that this apparently is equivalent to 7/3-power-free [Ram]. Overlap Free implies Cube Free

Cube Free

Because extensions of the Prouhet-Thue-Morse Sequence that comply with \(T_{n,8}\) are overlap-free [Tom], they are also cube-free.

Note

Given a word \(X : |X| > 1, X \in T_n\), \((X \concat X \concat X) \not\in T_n\).

Aperiodicity

Note

Not totally sure how this should go, but I think a good approximation would be to show that the distance between the nearest two appearances of a substring grows to infinity much faster than the length of those substrings grows. For words of size greater than $n$, this seems feasible. For words in size 2 thru n, I think I need to show that the distance between repetitions is aperiodic. That should be equivalent to distance between repetitions of integers, since one of the definitions expands digits to words

Generalization of Prouhet-Terry-Escott Problem

The standard Prouhet-Terry-Escott problem [AL77, Pro51] is

\begin{quote}
    Given $m > 1$ find $r > m$ and disjoint sets of distinct integers $\{a_1 \dots a_r\}$ and $\{b_1 \dots b_r\}$ such that:
    \begin{equation}
        \sum_{i=1}^r a_i^k = \sum_{i=1}^r b_i^k
    \end{equation}
    holds for every $k = 1 \dots m$
\end{quote}

Does this extension allow us to generalize to

\begin{quote}
    Given $m > 1$ find $r > m$ and $n$ disjoint sets of distinct integers $\{s_{1,1} \dots s_{1,r}\}$, $\{s_{2,1} \dots s_{2,r}\}$, $\dots$, $\{s_{n,1} \dots s_{n,r}\}$ such that:
    \begin{equation}
        \forall x : 2 \le x \le n \left(\sum_{i=1}^r s_{1,i}^k = \sum_{i=1}^r s_{x,i}^k \right)
    \end{equation}
    holds for every $k = 1 \dots m$
\end{quote}

Note

I think [BORZ16] says yes, but I’m not certain I understand it yet

Maresh Multifractions

It is a well known result [AS99] that the infinite nested fraction defined by:

\[\begin{equation} \dfrac{1}{2} \to \dfrac{\left(\dfrac{1}{2}\right)}{\left(\dfrac{3}{4}\right)} \to \dfrac{\left(\dfrac{\left(\tfrac{1}{2}\right)}{\left(\tfrac{3}{4}\right)}\right)}{\left(\dfrac{\left(\tfrac{5}{6}\right)}{\left(\tfrac{7}{8}\right)}\right)} \to \dots \to \prod_{k=1}^\infty k^{(-1)^{T_2(k-1)}} \end{equation}\]

and that this converges to \(\tfrac{1}{\sqrt{2}}\). Can we generalize fractions in a way that this result holds for \(T_n\)?

Let a Maresh multifraction [McI] be

\[\begin{equation} M_n(a_0, \dots, a_{n-1}) = \prod_{k=0}^{n-1} a_{k}^{e^{2ki \pi/n}} \end{equation}\]

Note that in the case of \(n=2\), this reduces to a standard fraction: \(M_2(a, b) = \tfrac{a}{b}\). For all other cases, it rotates the input values such that they are equidistant around the unit circle, then takes their product.

\begin{conjecture}
\label{conj:maresh_multifraction}
Suppose for some multifraction of size $n$, we begin chunking the counting numbers into groups of $n$. Each of these groups then gets put into a multifraction, and these multifractions subsequently get put into a multifraction, and so on. We will call this sequence $F_n$
\begin{equation}
\begin{aligned}
F_n &= \lim_{x\to\infty} F_n(x) \\
F_n(1) &= M_n(1, \ldots, n-1) \\
F_n(2) &= M_n\left(\begin{aligned}
        &M_n(1, \ldots, n), \\
        &M_n(n+1, \ldots, 2n),\\
        &\ldots, \\
        &M_n((n-1)n+1, \ldots, n^2)
\end{aligned}\right)\\
\forall n: n &\ge 2, |F_n| = \left| \sum_{k=0}^\infty (k+1)(\omega_n^{T_n(k)}) \right| = \dfrac{1}{\sqrt{n}}
\end{aligned}
\end{equation}
\end{conjecture}

Fractal Turtle Geometry

Note

\(T_2\) generates the von Koch snowflake. Do other integer bases also generate fractals in a way that can be generalized? [McI, Sch]

Citations

[AL77]

Allan Adler and Shuo-Yen Robert Li. Magic cubes and prouhet sequences. The American Mathematical Monthly, 84(8):618–627, 1977. URL: https://doi.org/10.1080/00029890.1977.11994435, arXiv:https://doi.org/10.1080/00029890.1977.11994435, doi:10.1080/00029890.1977.11994435.

[AS99]

Jean-Paul Allouche and Jeffrey Shallit. The ubiquitous prouhet-thue-morse sequence. In C. Ding, T. Helleseth, and H. Niederreiter, editors, Sequences and their Applications, 1–16. London, 1999. Springer London.

[BORZ16]

Ethan D. Bolker, Carl Offner, Robert Richman, and Catalin Zara. The prouhet–tarry–escott problem and generalized thue–morse sequences. Journal of Combinatorics, 7(1):117–133, 2016. URL: http://dx.doi.org/10.4310/JOC.2016.v7.n1.a5, doi:10.4310/joc.2016.v7.n1.a5.

[CK]

Yi Cai and Vilmos Komornik. Difference of cantor sets and frequencies in thue–morse type sequences. URL: https://arxiv.org/abs/2006.16119, arXiv:2006.16119.

[CD]

Joshua N. Cooper and Aaron M. Dutle. Greedy galois games. URL: https://arxiv.org/abs/1110.1137, arXiv:1110.1137.

[Inc]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences (oeis). OEIS Sequence ID: A287150. Fairest turn sequence for 3 players where the probability of a win for a player on his turn approaches 0. URL: https://oeis.org/A287150 (visited on 2024-10-24).

[McI] (1,2)

Matt McIrvin. Fractions, fractals and thue-morse sequences. A 3 part series of blog posts: 1) https://mmcirvin.dreamwidth.org/499645.html, 2) https://mmcirvin.dreamwidth.org/499830.html, 3) https://mmcirvin.dreamwidth.org/500104.html.

[Pan]

Diyath Pannipitiya. To symbolic dynamics through the thue-morse sequence. URL: https://arxiv.org/abs/2402.07015, arXiv:2402.07015.

[Pro51]

Eugene Prouhet. Mémoire sur quelques relations entre les puissances des nombres. CR Acad. Sci. Paris, 33(225):1851, 1851.

[Ram]

Narad Rampersad. Words avoiding 7/3-powers and the thue-morse morphism. URL: https://arxiv.org/abs/math/0307401, arXiv:math/0307401.

[Sch]

Leif Schaumann. Generalized results on the convergence of thue-morse turtle curves. URL: https://arxiv.org/abs/2412.06183, arXiv:2412.06183.

[Tom] (1,2)

C. Robinson Tompkins. Latin square thue-morse sequences are overlap-free. URL: https://arxiv.org/abs/0706.0907, arXiv:0706.0907.

Cite As

Click here to expand the bibtex entry.

@online{appleton_blog_0020,
  title    = { Prouhet-Thue-Morse Research 7: Extended Equivalence },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-05-25 },
  url      = { https://blog.oliviaappleton.com/posts/0020-thue-morse-07 }
}

Tags: math, hobby-horse

Comments ,