Danger

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

Prouhet-Thue-Morse Research 4: Binary Equivalence

2026-05-04

1. Foundations & Binary Numeric Definitions

2. Binary Definitions - Textual & Sequential

3. Binary Definitions - Others

4. Binary Equivalence (you are here)

5. Extending the Alphabet

6. Extended Equivalence

7. Property Preservation

8. Complexity and Honorable Mentions

Introduction

Proofs. Dotted means conjectured, solid means proven here, thick means proven elsewhere

Proving Equivalence Between Standard Definitions

Correlating Definition 1 and Definition 2

\begin{proof}
\par\noindent\par
    \textbf{Observation 1}: For all integers $n$, $(-1)^n \in \{1, -1\}$

    \textbf{Observation 2}: For $n = \{1, -1\}$, $\dfrac{1 - n}{2} = \{0, 1\}$

    \textbf{Observation 3}: For all $n = 2k$, $(-1)^n = 1$

    \textbf{Observation 4}: For all $n = 2k + 1$, $(-1)^n = -1$

    \textbf{Inference 1}: $\dfrac{1 - (-1)^n}{2} = n \;\; \mod{2}$

    \textbf{Conclusion}:
    \vspace{-1.5em}
    \begin{equation}\begin{aligned}
        T_{2,2}(n) &= \dfrac{1 - (-1)^{p(n)}}{2}\\
                &= p(n) \mod{2}\\
                &= T_{2,1}(n)
    \end{aligned}
    \end{equation}\vspace{-1.5em}
\end{proof}

Correlating Definition 1 and Definition 4

Note that in Equation \ref{eq:p2_d4} where we define $T_{2,4}$, we are working in mod 2, where $+1$ and $-1$ are logically equivalent. We can therefore simplify its definition to be:

\begin{equation}
    \label{eq:p2d04s}
    \begin{aligned}
T_{2,4}(0) &= 0 \\
T_{2,4}(n) &= n + T_{2,4}\left(\floor{\dfrac{n}{2}}\right) \pmod{2}
    \end{aligned}
\end{equation}

This is identical to Equation \ref{eq:p2_d1}, where we define $T_{2,1}$.

Correlating Definition 1 and Definition 8

\begin{proof}
\par\noindent\par
    \textbf{Observation 1}: $0 \le n < 2^k \implies t(k+1)_{2^k + n} \equiv t(k)_n + 1$
    This is because at each step in the process, you are inverting and extending. Inversion is equivalent to $x + 1 \; \mod{2}$, and each entry keeps a relative position by adding a power of 2.

    \textbf{Inference 1}: \begin{equation}
        \begin{aligned}
            T_{2,8}(0) &= 0 \\
            T_{2,8}(n) &= T_{2,3}(n - 2^{\floor{\log_2(n)}}) + 1 \mod{2}
        \end{aligned}
    \end{equation}

    \textbf{Observation 2}: By subtracting a power of 2, you reduce the Hamming Weight by 1

    \textbf{Inference 2}: Since you are adding 1 for each time you reduce the Hamming Weight by 1, this means $T_{2,8}$ is recursively computing the parity of the Hamming Weight.

    \textbf{Observation 3}: $T_{2,1} = p(n)$, and $p(n)$ computes the parity of the Hamming Weight of $n$.

    \textbf{Conclusion}: $T_{2,1}(n) = T_{2,8}(n)$
\end{proof}

Correlating Definition 2 and Definition 5

\begin{proof}
\par\noindent\par
    \textbf{Observation 1}: If $n$ is even:\begin{equation}\begin{aligned}
    b(n = 2k) &= b(\ceil{\tfrac{2k}{2}}) - b(\floor{\tfrac{2k}{2}}) \\
    &= b(k) - b(k) \\&= 0
    \end{aligned}
    \end{equation}

    \textbf{Inference 1}: Therefore, \begin{equation}
\begin{aligned}
    b(n=2k+1) &= b\left(\ceil{\dfrac{2k+1}{2}}\right) - b\left(\floor{\dfrac{2k+1}{2}}\right) \\
            &= b(k + 1) - b(k) \\
            &= \begin{cases}
                b(k+1) & \text{if } k \text{ is even} \\
                -b(k)  & \text{if } k \text{ is odd}
            \end{cases}
\end{aligned}
    \end{equation}

    \textbf{Hypothesis 1}: $b(2k+1) = (-1)^{p(k)}$

    \textbf{Assumption 1}: Assume $b(2k+1) \ne (-1)^{p(k)}$

    \textbf{Assumption 2}: \begin{equation}\begin{aligned}
    T_{2,2}(n) = \tfrac{1 - (-1)^{p(n)}}{2} &= \tfrac{1 - b(2n+1)}{2} = T_{2,5}(n) \\
    1 - (-1)^{p(n)} &= 1 - b(2n+1) \\
    (-1)^{p(n)} &= b(2n+1)
    \end{aligned}
    \end{equation}

    \textbf{Contradiction!} The only way for these definitions to be equal is for $b(2n+1) = (-1)^{p(n)}$

    \note{I don't think this proof is 100\% solid}
\end{proof}

Correlating Definition 9 and Definition 10

\begin{proof}
\par\noindent\par
    \textbf{Observation 1}: $r(\textbf{x}, i) = r(\textbf{x}, i + k \cdot |\textbf{x}|)$

    \textbf{Inference 1}: $r(\textbf{x}, i) = r(\textbf{x}, i \;\; \mod{|\textbf{x}|})$

    \textbf{Observation 2}: $s(0) = \tuple{0, 1} = r(s(0), 0)$

    \textbf{Observation 3}: $s(1) = \tuple{1, 0} = r(s(0), 1)$

    \textbf{Inference 2}: $s(n) = r(s(0), n)$

    \note{This is where I run into trouble. I know I can keep going from here, but I'm not quite sure how.}

    \textbf{Conclusion}: $T_{2,9}(n) = T_{2,10}(n)$
\end{proof}

Citations

Cite As

Click here to expand the bibtex entry.

@online{appleton_blog_0017,
  title    = { Prouhet-Thue-Morse Research 4: Binary Equivalence },
  author   = { Olivia Appleton-Crocker },
  editor   = { Ultralee0 and Ruby },
  language = { English },
  version  = { 1 },
  date     = { 2026-05-04 },
  url      = { https://blog.oliviaappleton.com/posts/0017-thue-morse-04 }
}

Tags: math, hobby-horse

Comments ,