\documentclass{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{bbold}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[
backend=biber,
style=alphabetic,
sorting=ynt
]{biblatex}
\addbibresource{phoenix.bib}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\title{Phoenix agars of all even periods}
\author{Alex Greason}
\date{May 2026}

\begin{document}

\maketitle

\begin{theorem}\label{thm:phoenix-even-periods}
Conway's Game of Life phoenix agars exist for every even period.
\end{theorem}

Proved below after proving several lemmas.

\begin{lemma}\label{lem:odd-rule90}
For every odd integer $m \geq 3$, there exists a finite spatial period Wolfram rule 90 pattern of exact temporal period $m$.
\end{lemma}

\begin{proof}
Let $m$ be odd, $m\geq 3$

Let $r = ord_m(2)$, the multiplicative order of 2 modulo m.

Because $m$ is odd, $gcd(m,2)=1$, so this is well-defined.

So $2^r \equiv_m 1 \implies 2^r - 1 \equiv_m 0 \implies m |2^r-1$

Now move to $\mathbb{F}_{2^r}$. 

The multiplicative group $\mathbb{F}_{2^r}^*$ is cyclic with order $2^r - 1$

And from above, $m |2^r-1$, therefore $\exists y \in \mathbb{F}_{2^r}^*:ord(y)=m$

Take the quadratic equation $Z^2+yZ+1=0$. As a quadratic equation over $\mathbb{F}_{2^r}$, it has a root in $\mathbb{F}_{2^{2r}}$, let $z \in \mathbb{F}_{2^{2r}}$ be such a root. $0^2+0y+1 \neq 0$, so $z \neq 0$.

$\mathbb{F}_{2^{2r}}$ is a field, so $z$ has a multiplicative inverse $z^{-1}$. Divide $z^2+yz+1=0$ by $z$, giving $z+y+z^{-1}=0$.

Rearrange to $-y = z+z^{-1}$, and since this field has characteristic 2, $-y = y$, so $y = z+z^{-1}$.

Let $L=ord(z)$. Since $z \in \mathbb{F}_{2^{2r}}$, $L|2^{2r} -1$, so $L$ is odd.

We use the formalism from \textit{Algebraic Properties of Cellular Automata} \cite{martin}, where a rule 90 pattern with periodic boundary conditions and a width of L is represented as an element of $R_L=\mathbb{F}_{2}[x]/(x^L-1)$, and one step of rule 90 evolution is represented by multiplication by $x+x^{-1}$.

Let $g(x)$ be the minimal polynomial of $z$ over $\mathbb{F}_2$. $L=ord(z)$, so $z^L-1=0$, so $g(x)|x^L-1$.

Let $f(x)=x^L-1$ over $\mathbb{F}_2$. $L$ is odd, so $L \equiv_2 1$, so the formal derivative $f'(x)=Lx^{L-1}=x^{L-1}$. $gcd(f, f')=gcd(x^L-1, x^{L-1})=1$, so $f$ has no repeated roots and is squarefree.

We have that $g(x)|x^L-1$. Take $Q(x)$ such that $x^L-1=g(x)Q(x)$. Since $x^L-1$ is squarefree, $gcd(g, Q)=1$, so by the Chinese Remainder Theorem $\mathbb{F}_2[x]/(x^L-1) \cong \mathbb{F}_2[x]/g(x) \times \mathbb{F}_2[x]/Q(x)$. So $R_L$ has a direct factor isomorphic to $\mathbb{F}_2[x]/g(x)$, and in that factor $x$ acts as $z$.

We have that $y=z+z^{-1}$ and $ord(y)=m$, so within this factor $ord(x+x^{-1})=m$.

We have that $gcd(g(x), Q(x))=1$, so by Bezout's lemma there exists $B(x)$ such that $B(x)Q(x) \equiv_{g(x)} 1$. Let $E(x)=B(x)Q(x)$ in $R_L$. By construction, $E(x) \equiv_{g(x)} 1$ and $E(x) \equiv_{Q(x)} 0$.

Consider $E(x)$ in $\mathbb{F}_{2}[x]/(x^L-1)$ as a rule 90 pattern, and its temporal period. $E$ has period $t$ if $t$ is the least value $>0$ such that $(x+x^{-1})^tE(x) \equiv_{x^L-1} E(x)$. $x^L-1=g(x)Q(x)$ and $gcd(g, Q)=1$, so this splits into two congruences $(x+x^{-1})^tE(x) \equiv_{g(x)} E(x)$ and $(x+x^{-1})^tE(x) \equiv_{Q(x)} E(x)$.

The second congruence $(x+x^{-1})^tE(x) \equiv_{Q(x)} E(x)$ is automatic, since $E(x) \equiv_{Q(x)} 0$. 

Since $E(x) \equiv_{g(x)} 1$, the first congruence  $(x+x^{-1})^tE(x) \equiv_{g(x)} E(x)$ simplifies to  $(x+x^{-1})^t \equiv_{g(x)} 1$. In $\mathbb{F}_2[x]/g(x)$, $y=x+x^{-1}$ has order $m$, so this is true iff $t$ is a multiple of $m$, and the least such nonzero $t$ is $m$ itself.

So the width-L spatially periodic pattern $E(x)$ has exact temporal period $m$ under rule 90 evolution.
\end{proof}

\begin{lemma}\label{lem:rule90-doubling}
Let $P$ be a nonzero rule 90 pattern of spatial period $L$ and exact temporal period $m$.
Form a new pattern of spatial period $2L$ by inserting a blank cell between each pair
of neighboring cells of $P$. Then the new pattern has exact temporal period $2m$.
\end{lemma}

\begin{proof}
This is closely related to lemma 3.6 from \cite{martin}. Consider a segment $[0, x_0, 0, x_1, 0, x_2, 0]$ of an expanded pattern. After one step this evolves to $[?, 0, x_0+x_1, 0, x_1+x_2, 0, ?]$ (The outer cells value depends on the value of cells outside of this segment whose values are not specified). After a second step, $[?, ?, 0, x_0+x_1+x_1+x_2, 0, ?, ?]$. $x_1+x_1=0$, so the central cell value is equivalent to $x_0+x_2$. Now consider the unexpanded version of this segment, $[x_0, x_1, x_2]$. After one step, this evolves to $[?, x_0+x_2, ?]$ - the central cell has the same value after one step in the base pattern as it does after two steps in the expanded pattern. The rule is translationally invariant, so this applies to all locations. Two steps of evolution on the expanded pattern produces the same pattern as evolving the original pattern by one step and then expanding it. And on odd-parity timesteps, the opposite parity of spatial locations are populated as are populated at time zero, so (if the original pattern is temporally periodic and not all zeros) the pattern after any odd number of timesteps cannot equal the pattern at time zero. So if the base pattern has temporal period $m$ the expanded pattern has period $2m$.
\end{proof}

\begin{lemma}\label{lem:rule90-omniperiodic}
Wolfram rule 90 is omniperiodic.
\end{lemma}

\begin{proof}
Let $t$ be a positive integer. Either $t=1$, or $t=2$, or $t$ is odd and $\geq 3$, or $t$ is even and $\geq 4$.

Case: $t=1$

The width-3 configuration $[1, 1, 0]\rightarrow[1, 1, 0]$ has exact period 1.

Case: $t=2$

The width-6 configuration $[1,0,1,0,0,0]\rightarrow[0,0,0,1,0,1]\rightarrow[1,0,1,0,0,0]$ has exact period 2.

Case: $t$ odd, $t\geq 3$

There is a configuration with exact period $t$ by lemma \ref{lem:odd-rule90}.

Case: $t$ even, $t\geq4$

$t$ can be written as $2^km$ for some $k > 0$ and some odd $m$ (possibly $1$). If $m \geq 3$ there is a pattern of exact period $m$ by lemma \ref{lem:odd-rule90}, otherwise $m=1$ and the pattern $[1, 1, 0]$ can be used. Applying lemma \ref{lem:rule90-doubling} $k$ times produces a pattern of exact period $t$.
\end{proof}

\begin{lemma}\label{lem:rule18-rule90}
If all cells of one spatial parity of a rule 18 pattern are blank, then advancing for two steps is equivalent to one step of Wolfram rule 90 on the state produced by removing the cells of the parity that is all zero at time 0.
\end{lemma}

\begin{proof}
Given three sequential cells $[x_0, x_1, x_2]$ with values over $\mathbb{F_2}$, under one step of wolfram rule 18 the new center cell value is $(x_1+1)*(x_0+x_2)=x_1*x_0+x_1*x_2+x_0+x_2$. Take the segment $[x_0, 0, x_1, 0, x_2]$. Under one step of rule 18, this goes to $[?, 0*x_0+0*x_1+x_0+x_1, x_1*0+x_1*0+0+0, 0*x_1+0*x_2+x_1+x_2, ?]$, which reduces to $[?, x_0+x_1, 0, x_1+x_2, ?]$. Applying another step and reducing this goes to $[?, ?, x_0+x_2, ?, ?]$. Now take the contracted version $[x_0, x_1, x_2]$ and apply one step of rule 90, this goes to $[?, x_0+x_2, ?]$. The center cell value is the same in both cases, and this applies everywhere by translational invariance.
\end{proof}

\begin{lemma}\label{lem:rule18-even-periods}
Rule 18, on initial patterns where all odd-parity cells are blank, has oscillators of all even periods.
\end{lemma}

\begin{proof}
Follows directly from lemmas \ref{lem:rule18-rule90} and \ref{lem:rule90-omniperiodic}
\end{proof}

\begin{lemma}\label{lem:barberpole-rule18}
Against a barberpole agar background, perturbations in the form of complemented horizontal stripes (at y-coordinates that are populated in the backing agar, which are all in one parity class or all in the other in alternating generations), evolve according to wolfram rule 18, with the pattern remaining a phoenix.
\end{lemma}

\begin{proof}
Determined by observation, examples below. These examples include all relevant local neighborhoods.
\end{proof}

Unmodified phoenix agar unit cell (period 2, corresponds to period-1 rule 90 state $[0, 0, 0, 0, 0]$): 
\begin{verbatim}
x = 5, y = 10, rule = B3/S23:T5,10
obo2b$5b$o2bob$5b$bobob$5b$bo2bo$5b$2bobo$5b!
\end{verbatim}
Note that at even time all live cells have even y-coordinates, and at odd times all live cells have odd y-coordinates, so the pattern is a phoenix. This property is preserved when modifying the time-zero pattern by complementing any subset of the rows with even y-coordinate.\\

Period 4 phoenix agar, corresponds to width-6 period-2 rule 90 oscillator $[0, 0, 0, 1, 0, 1] \rightarrow [1, 0, 1, 0, 0, 0]$. Note that because the unit cell of the backing agar has vertical spatial period 10, the pattern of complemented stripes needs to be repeated to reach a vertical spatial period of $lcm(2*6, 10) = 60$ to allow the backing cgol agar's vertical spatial period and the imposed rule 18 agar's spatial period to sync up. $2*6$ rather than just $6$ because the rule 18 pattern is twice the size of the emulated rule 90 pattern. This does not impact the temporal period.
\begin{verbatim}
x = 5, y = 60, rule = B3/S23:T5,60
obo2b$5b$o2bob$5b$obobo$5b$bo2bo$5b$2obob$5b$obo2b$5b$o2bob$5b$bobob$5
b$ob2ob$5b$2bobo$5b$bob2o$5b$o2bob$5b$bobob$5b$bo2bo$5b$2obob$5b$obo2b
$5b$b2obo$5b$bobob$5b$bo2bo$5b$2bobo$5b$bob2o$5b$o2bob$5b$obobo$5b$bo2
bo$5b$2bobo$5b$obo2b$5b$b2obo$5b$bobob$5b$ob2ob$5b$2bobo$5b!
\end{verbatim}

Period-6 phoenix agar, corresponds to width-5 period-3 rule 90 oscillator $[0, 1, 1, 1, 1] \rightarrow [0, 1, 0, 0, 1] \rightarrow [0, 0, 1, 1, 0]$.
\begin{verbatim}
x = 5, y = 10, rule = B3/S23:T5,10
obo2b$5b$b2obo$5b$obobo$5b$ob2ob$5b$2obob$5b!
\end{verbatim}


Period-8 phoenix agar, corresponds to width-12 period-4 rule 90 oscillator $[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]$ - note that this is the width-6 period-2 oscillator above, expanded as in lemma \ref{lem:rule90-doubling}. Repeated to height $lcm(2*12, 10)=120$ for spatial period syncing.
\begin{verbatim}
x = 5, y = 120, rule = B3/S23:T5,120
obo2b$5b$o2bob$5b$bobob$5b$bo2bo$5b$2obob$5b$obo2b$5b$o2bob$5b$bobob$5
b$ob2ob$5b$2bobo$5b$obo2b$5b$o2bob$5b$bobob$5b$bo2bo$5b$2bobo$5b$obo2b
$5b$b2obo$5b$bobob$5b$bo2bo$5b$2bobo$5b$bob2o$5b$o2bob$5b$bobob$5b$bo2
bo$5b$2bobo$5b$obo2b$5b$o2bob$5b$bobob$5b$ob2ob$5b$2bobo$5b$obo2b$5b$o
2bob$5b$obobo$5b$bo2bo$5b$2bobo$5b$obo2b$5b$o2bob$5b$bobob$5b$bo2bo$5b
$2bobo$5b$bob2o$5b$o2bob$5b$bobob$5b$bo2bo$5b$2obob$5b$obo2b$5b$o2bob$
5b$bobob$5b$bo2bo$5b$2bobo$5b$obo2b$5b$o2bob$5b$obobo$5b$bo2bo$5b$2bob
o$5b$obo2b$5b$b2obo$5b$bobob$5b$bo2bo$5b$2bobo$5b!
\end{verbatim}


Period-12 phoenix agar, corresponds to width-10 period-6 rule 90 oscillator $[0, 0, 1, 0, 1, 0, 1, 0, 1, 0]$. Note that this is the above width-5 period-3 oscillator expanded as in lemma \ref{lem:rule90-doubling}. The corresponding rule 18 oscillator width of $2*10$ was already a multiple of the unit cell height, so no repetition is needed.
\begin{verbatim}
x = 5, y = 20, rule = B3/S23:T5,20
obo2b$5b$o2bob$5b$obobo$5b$bo2bo$5b$2obob$5b$obo2b$5b$b2obo$5b$bobob$5
b$ob2ob$5b$2bobo$5b!
\end{verbatim}

\begin{proof}[Proof of Theorem~\ref{thm:phoenix-even-periods}]
By lemma \ref{lem:barberpole-rule18}, any rule 18 pattern where only one spatial parity is populated can be translated into a Conway's game of life phoenix agar with equivalent evolution. By lemma \ref{lem:rule18-even-periods}, this includes oscillators of all even periods.
\end{proof}

\medskip

\printbibliography

\end{document}