\documentclass[11pt]{article}
\usepackage[a4paper,margin=24mm]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage[hidelinks]{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{problem}{Problem}
\renewcommand{\theproblem}{\Alph{problem}}

\newcommand{\xor}{\oplus}
\newcommand{\NN}{\mathbb{N}}

\title{Periodic Forcing, Echo Constraints and the Non-Periodicity of the Rule~30 Centre Column:
Structural Lemmas, Certified Computations and Barriers}
\author{Isaac Kaimfa}
\date{October 2026}

\begin{document}
\maketitle

\begin{abstract}
Wolfram's Rule~30 Prize Problem~1 asks whether the centre column of Rule~30, started from a single
lit cell, is ever eventually periodic. We study the problem through a half-line system driven by a
periodic boundary signal. Combining a known local identity with the standard reduction to finite
seeds, Problem~1 follows from a single statement, the \emph{Echo Lemma}: no finite half-line
configuration driven by a non-constant periodic boundary can satisfy, at every lit boundary minute,
the identity that Rule~30 forces on the neighbour of the centre. Around this formulation we prove a
collection of exact structural results: a dependence-window lemma and a merging criterion for
reconstructed columns, triangularity and monotonicity of the finite-support constraints, a
forced-creation identity at boundary bounces, a description of the infinite survivors as a full
shift for period two, and, for the two-sided period-two problem, exact forced identities near the
centre, including a half-column that must vanish identically. For the linear relative Rule~150 we
prove the analogue of the Echo Lemma for every odd period by a Frobenius self-similarity argument,
and identify exactly the two steps that fail for Rule~30. We report exhaustive and SAT-certified
computations excluding counterexamples of bounded width, and document barriers: every exact
mechanism found is confined to a bounded neighbourhood of the centre, no additive conserved quantity
of small range exists, and the sideways reconstruction has a growing number of distinguishable
states. The Echo Lemma, and with it Problem~1, remains open. Every statement is labelled as proved,
certified computation or open.
\end{abstract}

\section{Introduction}
Rule~30 updates a bi-infinite row by $x_i(t+1)=x_{i-1}(t)\xor(x_i(t)\lor x_{i+1}(t))$. Started from a
single lit cell, its centre column $c(t)=x_0(t)$ passes standard tests of randomness
\cite{NKS,MS}. Problem~1 of the 2019 prizes \cite{Prizes} asks whether $c$ is ever eventually periodic.
Jen proved that a finite Rule~30 orbit has at most one eventually periodic column \cite{Jen}; Condrey
proved that no column of a nonzero finite orbit is eventually constant, settling period one, and
named eventual period two as the next open case \cite{Condrey}.

The formulation in Section~\ref{sec:echo} uses known ingredients: the local identity of
Lemma~\ref{lem:echo} appears in \cite{Crypto}, and the reduction to finite seeds, together with
uniqueness of the left half given the right half, appears in \cite{Condrey} and in a Lean
development \cite{Adler}. Our contributions are:
\begin{itemize}
\item exact structural lemmas for the driven half-line: a dependence-window lemma, a merging criterion
certifying exact equivalence of reconstructions, triangularity and monotonicity of the finite-support
constraints, and a forced-creation identity (Section~\ref{sec:struct});
\item for the two-sided period-two problem, a golden-mean restriction on boundary inputs and exact
forced identities near the centre, including $x_{-4}(2n)\equiv 0$ (Section~\ref{sec:two});
\item a proof of the Echo Lemma's analogue for Rule~150 at every odd period, with an account of the
two steps that fail for Rule~30 (Section~\ref{sec:150});
\item certified computations (Section~\ref{sec:cert}) and a catalogue of barriers (Section~\ref{sec:bar}).
\end{itemize}
We do not claim a solution of Problem~1.

\section{Setting and notation}
Fix $d:\NN\to\{0,1\}$, periodic with period $p$ and not constant. A half-line configuration
$a_k(t)$, $k\ge1$, evolves by
\begin{equation}\label{eq:rule}
a_k(t+1)=a_{k+1}(t)\xor\bigl(a_k(t)\lor a_{k-1}(t)\bigr),\qquad a_0(t)=d(t).
\end{equation}
A minute $t$ is \emph{lit} if $d(t)=1$. A start is \emph{finite} of width $w$ if $a_w(0)=1$ and
$a_k(0)=0$ for $k>w$. Solving \eqref{eq:rule} for the far cell gives the inverse rule
\begin{equation}\label{eq:inv}
a_{k+1}(t)=a_k(t+1)\xor\bigl(a_k(t)\lor a_{k-1}(t)\bigr).
\end{equation}
Over $\mathrm{GF}(2)$, $u\lor v=u\xor v\xor uv$, so \eqref{eq:rule} is Rule~150 plus the product
$a_ka_{k-1}$. We write $\Delta_k(t)=a_k(t)\xor a_k(t+p)$; since $d(t)=d(t+p)$, $\Delta_0\equiv0$.

\section{The Echo Lemma formulation}\label{sec:echo}
\begin{lemma}[echo law; known \cite{Crypto}]\label{lem:echo}
In Rule~30, if $c(t)=1$ then $x_{-1}(t)=1\xor c(t+1)$.
\end{lemma}
\begin{proof}$c(t+1)=x_{-1}(t)\xor(c(t)\lor x_1(t))$ and the OR equals $1$.\end{proof}

\noindent\textbf{Echo Lemma (open).} For every non-constant periodic $d$ and every finite start there
is a lit minute $t$ with $a_1(t)\ne 1\xor d(t+1)$.

\begin{observation}[combines \cite{Condrey,Crypto,Adler}]\label{obs:red}
The Echo Lemma implies Problem~1.
\end{observation}
\begin{proof}
If $c$ is eventually constant, \cite{Condrey} gives a contradiction. Otherwise $c$ is eventually
periodic with a non-constant pattern of period $p$ from some time $T$. The cells $a_k=x_{-k}$ obey
\eqref{eq:rule} with $a_0=c$, and at time $T$ only finitely many are lit. Lemma~\ref{lem:echo}
gives the echo identity at every lit minute, contradicting the Echo Lemma. The finite-seed step is
the standard same-orbit reduction \cite{Condrey,Adler}.
\end{proof}

\section{Structural results}\label{sec:struct}
\begin{lemma}[front advance]\label{lem:front}
If the outermost lit cell at time $t$ is at depth $R$, then $a_R(t+1)=a_{R+1}(t+1)=1$ and
$a_k(t+1)=0$ for $k>R+1$.
\end{lemma}
\begin{lemma}[arrival]\label{lem:arrival}
If two half-lines agree at depths $1,\dots,m-1$ and differ at depth $m\ge2$ at time $t$, then at
time $t+1$ they agree at depths $1,\dots,m-2$ and differ at depth $m-1$.
\end{lemma}
\begin{lemma}[dependence window]\label{lem:window}
$a_k(t)$ depends only on $a_1(t),\dots,a_1(t+k-1)$ and $d$, and
$a_k(0)=a_1(k-1)\xor F_k\bigl(a_1(0),\dots,a_1(k-2)\bigr)$.
\end{lemma}
\begin{proof}Induction on $k$ using \eqref{eq:inv}; the newest value enters only through $a_k(t+1)$,
by XOR.\end{proof}

Under the echo, $a_1$ is prescribed at lit minutes and free at dark minutes; write $b_k=a_k(0)$.
\begin{proposition}[triangularity]\label{prop:tri}
If minute $k-1$ is dark, $b_k=0$ determines the free bit $a_1(k-1)$ uniquely from earlier bits
(forcing); if it is lit, $b_k=0$ constrains earlier bits only (filter).
\end{proposition}
\begin{corollary}[monotonicity]\label{cor:mono}
The sets $S_n$ of surviving prefixes, each extended uniquely through forcing constraints, satisfy
$S_{n+1}\subseteq S_n$.
\end{corollary}
\begin{lemma}[merging]\label{lem:merge}
If two traces agree at every minute after $N$ and their reconstructions agree on minutes
$0,\dots,N$ at two consecutive depths, they agree at every greater depth and every minute.
\end{lemma}
\begin{proof}By Lemma~\ref{lem:window}, values after minute $N$ agree at every depth; the window
$0,\dots,N$ propagates by \eqref{eq:inv}, whose boundary term lies after $N$.\end{proof}
For song $011111$ and support bound $M=76$, four surviving assignments stall through nine filters;
Lemma~\ref{lem:merge} certifies (independently verified) that they coincide from depth $48$ on.

\begin{lemma}[forced creation]\label{lem:fc}
If $t$ is dark, $t+1$ is lit and the echo holds at $t+1$, then $[a_1(t)=a_2(t)]=d(t+2)$; at a bounce,
$\Delta_2(t+1)=\Delta_3(t)\xor d(t+2)$.
\end{lemma}
\begin{proof}On a dark minute $a_1(t+1)=a_1(t)\xor a_2(t)$, and the echo fixes $a_1(t+1)=1\xor d(t+2)$.\end{proof}

With $R_k=a_{k-1}\Delta_k\xor a_k\Delta_{k-1}\xor\Delta_k\Delta_{k-1}$ one has
$\Delta_k(t+1)=\Delta_{k+1}\xor\Delta_k\xor\Delta_{k-1}\xor R_k$, and the echo gives
$R_1=d\,\Delta_1\equiv0$.

\begin{proposition}[front stripes]\label{prop:stripes}
Let $F_j(t)$ be the cell $j$ behind the outermost lit cell. Then
$F_j(t+1)=F_{j-2}(t)\xor(F_{j-1}(t)\lor F_j(t))$; each fixed lag is eventually periodic with period a
power of two, doubling exactly when lag $j-1$ is eventually dark and lag $j-2$ has odd parity over a
period. This matches \cite{NKSnotes}.
\end{proposition}

\begin{proposition}[fiber, period two]\label{prop:fiber}
For $d=1,0,1,0,\dots$ the echo-compatible half-lines correspond bijectively to arbitrary dark-minute
sequences, and two steps of \eqref{eq:rule} act as the shift.
\end{proposition}
\begin{lemma}[finite wallpapers]
For period $p$, configurations fixed by $p$ steps are determined by their first $p$ cells; there are
at most $2^p$, each eventually periodic in space.
\end{lemma}

\section{The two-sided period-two problem}\label{sec:two}
Let $c(2n)=0$, $c(2n+1)=1$. The right half evolves autonomously given $c$.
\begin{proposition}[uniqueness; also \cite{Adler}]
Given a finite right half, $x_{-1}(t)=c(t+1)\xor(c(t)\lor x_1(t))$ for all $t$, and \eqref{eq:inv}
determines the left half.
\end{proposition}
\begin{lemma}[golden-mean restriction]\label{lem:golden}
With $y_j(n)=x_j(2n)$: $y_1(n+1)=\neg\bigl(y_1(n)\lor y_2(n)\lor y_3(n)\bigr)$; in particular
$x_1(2n)\,x_1(2n+2)=0$.
\end{lemma}
\begin{proposition}[forced identities]\label{prop:ids}
With $A_k(n)=x_{-k}(2n)$:
$A_2=\neg A_1$, $A_3(n)=A_1(n+1)$, $A_4\equiv0$, $A_5(n)=[A_1(n+1)=A_1(n+2)]$,
$A_6=\neg A_5\land(A_3\lor A_2)$, $A_7(n)=[A_1(n+2)=A_1(n+3)]$.
\end{proposition}
The continuation $A_{2m+1}(n)=[A_1(n+m-1)=A_1(n+m)]$ fails from depth $9$. Up to depth $41$ the only
constant half-columns are $x_{-1}$ at odd minutes and $x_{-4}$ at even minutes; cells $-6$ to $-10$
contain no adjacent dark pair at odd minutes in all samples (not proved).

\section{A linear comparison: Rule 150}\label{sec:150}
\begin{theorem}\label{thm:150}
For $a_k(t+1)=a_{k+1}(t)\xor a_k(t)\xor a_{k-1}(t)$ with $a_0=d$ of odd period $p$ and a lit phase, no
finite nonzero start has $a_1(t)=a_1(t+p)$ at every lit minute.
\end{theorem}
\begin{proof}
$\Delta$ evolves by the same rule with dark boundary and $\Delta(0)\ne0$. Mirror by
$\Delta_{-k}=\Delta_k$; with $\varphi=x^{-1}+1+x$ and $P(x)=\sum_k\Delta_k(0)(x^k+x^{-k})$,
$\Delta_1(t)=[x^1]\varphi^tP \bmod 2$. Since $\varphi^{2^m}=x^{-2^m}+1+x^{2^m}$ mod $2$, for $N$ a sum
of distinct widely spaced large powers of two, $\Delta_1(r+N)=\Delta_1(r)$. With $o$ the order of $2$
mod $p$, sums of $k$ powers $2^{M+2io}$ are $\equiv k2^M$, covering every residue, so $r+N$ can be made
lit. Hence $\Delta_1\equiv0$, and \eqref{eq:inv} gives $\Delta\equiv0$, a contradiction.
\end{proof}
The ingredients are classical \cite{AS,LD,RY,MOW}. For Rule~90 the central term is absent. For Rule~30
the identity $\Delta_1(r+2^m)=\Delta_1(r)$ holds in $50.2\%$ of tests (all $268{,}968$ for Rule~150).

\section{Certified computations}\label{sec:cert}
\begin{center}\small
\begin{tabular}{lll}\toprule
Statement & Range & Method\\\midrule
Echo Lemma, song $01$ & widths $\le34$ & exhaustive trees; Z3\\
Echo Lemma, songs $001$, $0001$ & widths $\le20$ & SAT, two encodings\\
Echo Lemma, song $011111$ & widths $\le80$ & exact tables, $2^{19}$ assignments$^{*}$\\
Two-sided, alternating & radius $\le10$ & exhaustive, $2^{21}$ seeds\\
Two-sided, alternating & right $\le14$, left $\le125$ & all $2^{14}$ right halves\\\bottomrule
\end{tabular}
\end{center}
$^{*}$An independent run, not included here, reports widths $\le97$. Scripts for every other row are in \texttt{anc/}.\\[2pt]
Maximum steps beyond actual radius $R$: $6,1,3,3,4,4,3,7,8,7$ for $R=1,\dots,10$.

\section{Barriers}\label{sec:bar}
\begin{itemize}
\item Single-path XOR identities telescope to their endpoints.
\item No bounded quantity can decrease along every finite start; no additive conserved quantity on
patterns of length $\le5$; closed global parities are memoryless.
\item Exact local forcing terminates within about $9$--$11$ cells of the centre.
\item Distinguishable sideways histories grow exponentially (lower bounds $27\to30{,}301$ and $4\to437$).
\item Stall lengths of the surviving set grow with the support bound.
\item Rule~30 versus Rule~150 from the same start: neither consistently earlier.
\end{itemize}

\section{Open problems}
\begin{problem}Prove the Echo Lemma (at least as strong as needed for Problem~1).\end{problem}
\begin{problem}For every finite right half, the left half forced by an alternating centre has
infinitely many lit cells (period-two case of Problem~1; open in \cite{Condrey}).\end{problem}
\begin{problem}Find an exact OR-based constraint reaching arbitrarily far from the centre.\end{problem}
\begin{problem}Decide whether stalls of single residual behaviours are uniformly bounded.\end{problem}

\section*{Acknowledgement}
Computational experiments and verification scripts were developed with the assistance of AI systems;
certificates in Section~\ref{sec:struct} were checked by an independent implementation.

\begin{thebibliography}{99}
\bibitem{NKS} S. Wolfram, \emph{A New Kind of Science}, Wolfram Media, 2002.
\bibitem{Condrey} D. L. Condrey, Finite configurations cannot generate a constant trace in Rule 30, arXiv:2609.09431, 2026.
\bibitem{AS} J.-P. Allouche and J. Shallit, \emph{Automatic Sequences}, Cambridge University Press, 2003.
\bibitem{Jen} E. Jen, Global properties of cellular automata, \emph{J. Stat. Phys.} 43 (1986).
\bibitem{LD} B. Litow and P. Dumas, Additive cellular automata and algebraic series, \emph{Theoret. Comput. Sci.} 119 (1993).
\bibitem{MS} W. Meier and O. Staffelbach, Analysis of pseudo random sequences generated by cellular automata, EUROCRYPT 1991.
\bibitem{RY} E. Rowland and R. Yassawi, A characterization of $p$-automatic sequences as columns of linear cellular automata, \emph{Adv. Appl. Math.} 63 (2015) 68--89.
\bibitem{MOW} O. Martin, A. M. Odlyzko and S. Wolfram, Algebraic properties of cellular automata, \emph{Comm. Math. Phys.} 93 (1984).
\bibitem{Prizes} S. Wolfram, Announcing the Rule 30 Prizes, 2019.
\bibitem{NKSnotes} S. Wolfram, notes to \emph{A New Kind of Science}, Rule 30 left-edge periodicities.
\bibitem{Crypto} Cellular automata in cryptographic random generators, arXiv:1306.3546, 2013, Proposition 3.4.
\bibitem{Adler} keithadler (GitHub), rule30-seed-gap: Lean reduction of Problem 1 to finite seeds, 2026.
\end{thebibliography}
\end{document}