Danger

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

Prouhet-Thue-Morse Research 3: Binary Definitions - Others

2026-04-27

  1. Foundations & Binary Numeric Definitions

  2. Binary Definitions - Textual & Sequential (you are here)

  3. Binary Definitions - Others

  4. Binary Equivalence

  5. Extending the Alphabet

  6. Extended Equivalence

  7. Property Preservation

  8. Complexity and Honorable Mentions

Introduction

Binary Definitions - Others

17 / 21 - Generating Function 1

This generating function\footnote{
A generating function is a polynomial such that the coefficient of each term is equal to the value in a sequence. $[x^n]G(f)$ indicates ``the coefficient of $x^n$ in the function $G(x)$.'' So $[x^2]\left(1 + 2x + 3x^2\right) = 3$
} definition appears in \cite{Allouche-Shallit_1999, OEIS-TMS}.

\begin{equation}
\begin{aligned}
G(x) &= \mathcal{G.F.} \;\; \begin{aligned}[c]
    \dfrac{\displaystyle\dfrac{1}{1 - x} - \prod_{k \ge 0}^\infty (1 - x^{2^k})}{2}
    \end{aligned} \\
    &= \mathcal{G.F.} \;\; \begin{aligned}[c]
    \dfrac{\displaystyle\sum_{k\ge0}^\infty x^k - \prod_{k \ge 0}^\infty (1 - x^{2^k})}{2}
    \end{aligned} \\
T_{2,\arabic{stddefctr}}(n) &= [x^n]G(x)
\end{aligned}
\end{equation}

The logic of this construction is fairly clear. The component that is $\tfrac{1}{1-x}$ will generate coefficients of all $1$s. This is then subtracted by a sequence that counts the high bits of a given index, evaluating to $-1$ if the number of bits is even, and $1$ if it is odd. This means that the only possible outputs of the top part are $0$ or $2$, so the divisor corrects for that.

This means that it is equivalent to $T_{2,1}$ \note{(prove it)}.

In practice, to get the coefficients up to the $n$th term, one needs to only expand the product to $k_\text{max} = \floor{\log_2(n + 1)} - 1$.

Note that this and the next definition are by far the least computationally efficient definitions in this paper (see Figure \ref{fig:benchmark_in_s} and Tables \ref{tab:time_p2_d17}, \ref{tab:space_p2_d17}, \ref{tab:time_p2_d18}, \ref{tab:space_p2_d18}).\footnote{Our implementation \cite{repo} heavily utilizes \cite{symengine, sympy} for these calculations}

18 / 21 - Generating Function 2

This definition appears in \cite{weisstein_thue_morse_2024, OEIS-TMS-pos-neg}. The coefficients of this generating function are given in OEIS Sequence A309303 \cite{OEIS-A309303}.

\begin{equation}
\begin{aligned}
G(x) &= \mathcal{G.F.} \dfrac{\sqrt{x+1} - \sqrt
{1-3x}}{2 \cdot (x+1)^{\tfrac{3}{2}}} \\
    T_{2,\arabic{stddefctr}}(n) &= \dfrac{1 - (-1)^{[x^n]G(x)}}{2}
\end{aligned}
\end{equation}

19 / 21 - Hypergeometry

\note{I'm a little unclear why this works, but it certainly seems to}

This definition appears in \cite{weisstein_thue_morse_2024, OEIS-TMS-pos-neg}.

\begin{equation}
T_{2,\arabic{stddefctr}}(n) = \left(\begin{aligned}&1 + \frac{(-1)^n}{2} + \\ &\sqrt\pi\cdot(-3)^n \cdot \frac{_2F_1(\frac{3}{2}, -n; \frac{3}{2} - n; \frac{-1}{3})}{4 \cdot n!}\end{aligned}\right) \mod{2}
\end{equation}
where \(\ _2F_1(a_1, a_2; b_1; z) \) is the generalized, regularized hypergeometric function given by:
\begin{equation}
\ _2F_1(a_1, a_2; b_1; z) = \sum_{k=0}^\infty \begin{aligned}\dfrac{\frac{(a_1)_k (a_2)_k}{(b_1)_k} \cdot \frac{z^k}{k!}}{\Gamma(b_1)}\end{aligned},
\end{equation}
and \((a)_k\) is the Pochhammer symbol defined as:

\begin{equation}
(a)_k = \left(\prod_{i=0}^{k-1} (a+i), \;\; (a)_0 = 1\right) \approx \dfrac{(a + k - 1)!}{(a - 1)!}
\end{equation}

20 / 21 - Cellular Automaton

This definition appears in \cite{weisstein_thue_morse_2024, OEIS-TMS-pos-neg}.

Using Mathematica-like notation,
\begin{equation}
\begin{aligned}
T_{2,\arabic{stddefctr}} = \lim_{k\to\infty} 1 - \text{Flatten}[&\text{CellularAutomaton}[ \\
&\{69540422, 2, 2\}, \\
&\{\{1\}, 0\}, \\
&2^k - 1, \\
&\{\text{All}, 0\}]]
\end{aligned}
\end{equation}

Here, the \textbf{CellularAutomaton} function is used to generate the sequence. The first argument, $\{69540422,2,2\}$, represents the rule for the automaton. Rule $69540422 = 1000011100001011101111010_2$ is a specific binary rule for generating the sequence, while the numbers 2 and 2 correspond to the number of states and the neighborhood range, respectively. This means that each cell will have the following transformation table, when including the state of its left and right 2 neighbors:

\begin{table}[h]
\centering
\begin{tabular}{|c|c|}
\hline
\textbf{Neighborhood} & \textbf{Output} \\
\hline
$\tuple{0,0,0,0,0}$ & $0$ \\ \hline
$\tuple{0,0,0,0,1}$ & $1$ \\ \hline
$\tuple{0,0,0,1,0}$ & $0$ \\ \hline
$\tuple{0,0,0,1,1}$ & $1$ \\ \hline
$\tuple{0,0,1,0,0}$ & $1$ \\ \hline
$\tuple{0,0,1,0,1}$ & $1$ \\ \hline
$\tuple{0,0,1,1,0}$ & $1$ \\ \hline
$\tuple{0,0,1,1,1}$ & $0$ \\ \hline
$\tuple{0,1,0,0,0}$ & $1$ \\ \hline
$\tuple{0,1,0,0,1}$ & $1$ \\ \hline
$\tuple{0,1,0,1,0}$ & $1$ \\ \hline
$\tuple{0,1,0,1,1}$ & $0$ \\ \hline
$\tuple{0,1,1,0,0}$ & $1$ \\ \hline
$\tuple{0,1,1,0,1}$ & $0$ \\ \hline
$\tuple{0,1,1,1,0}$ & $0$ \\ \hline
$\tuple{0,1,1,1,1}$ & $0$ \\ \hline
$\tuple{1,0,0,0,0}$ & $0$ \\ \hline
$\tuple{1,0,0,0,1}$ & $1$ \\ \hline
$\tuple{1,0,0,1,0}$ & $1$ \\ \hline
$\tuple{1,0,0,1,1}$ & $1$ \\ \hline
$\tuple{1,0,1,0,0}$ & $0$ \\ \hline
$\tuple{1,0,1,0,1}$ & $0$ \\ \hline
$\tuple{1,0,1,1,0}$ & $0$ \\ \hline
$\tuple{1,0,1,1,1}$ & $0$ \\ \hline
$\tuple{1,1,0,0,0}$ & $1$ \\ \hline
$\tuple{1,1,0,0,1}$ & $0$ \\ \hline
$\tuple{1,1,0,1,0}$ & $0$ \\ \hline
$\tuple{1,1,0,1,1}$ & $0$ \\ \hline
$\tuple{1,1,1,0,0}$ & $0$ \\ \hline
$\tuple{1,1,1,0,1}$ & $0$ \\ \hline
$\tuple{1,1,1,1,0}$ & $0$ \\ \hline
$\tuple{1,1,1,1,1}$ & $0$ \\ \hline
\end{tabular}
\caption{Enumerated 5-cell neighborhood configurations and their corresponding rule bits.}
\end{table}

The initial configuration is specified by $\{\{1\},0\}$, meaning the sequence starts with a single $1$ surrounded on either side by a field of $0$s. The value $2^{k-1}$ specifies the number of iterations to take. The function will output the initial state of the center cell, followed by its state at each iteration. Finally, the Flatten function ensures that the sequence is flattened into a one-dimensional list. Each element $x$ in the list is then passed through $1 - x$. As $k\to\infty$, this process generates an increasingly large sequence approaching the \TMS.

21 / 21 - Equitable Galois Duels

Consider a Galois Duel, where two players fire upon each other with equally improbable odds of success. At limit, the Thue-Morse Sequence is the turn order that minimizes advantage between players, breaking any ties using lexographic order \cite{cooper_2011}.

Consider the following system of equations, where $q$ is an arbitrarily low probability:

\begin{equation}
\begin{aligned}
    a_{n+1} &= \begin{cases}
            -a_n &\text{if } f_n(q) \ge 0 \\
            a_n  &\text{otherwise}
    \end{cases} \\
    f_n(q) &= a_n \cdot \left( \sum_{j=0}^n T_{2,21}(j) \cdot q^j \right) \\
T_{2,21}(n) &= \dfrac{1 - (-1)^{a_n}}{2}
\end{aligned}
\end{equation}

Citations

Cite As

Click here to expand the bibtex entry.
@online{appleton_blog_0016,
  title    = { Prouhet-Thue-Morse Research 2: Binary Definitions - Textual },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-04-27 },
  url      = { https://blog.oliviaappleton.com/posts/0016-thue-morse-03 }
}

Tags: math, hobby-horse

Comments Boosts , Likes