\documentclass[11pt,letterpaper]{amsart}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern,microtype,amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs}
\usepackage[hidelinks]{hyperref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\rev}{rev}
\DeclareMathOperator{\per}{per}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\title[Palindromic sections in phase actions]{Palindromic sections in two Kolakoski phase actions}
\author{Will Howe}
\email{howew@purdue.edu}
\author{Grant Huffman}
\email{huffma97@purdue.edu}
\author{Jensen Kohlmeyer}
\email{jenwin@purdue.edu}
\author{Liam Kruer}
\email{kruerl@purdue.edu}
\thanks{Prepared with AI assistance from OpenAI Codex in mathematical exploration,
  checking, and manuscript preparation.}
\date{November 7, 2026}

\begin{document}
\begin{abstract}
We prove the two specified-phase orbit statements in Shen's Conjectures 3.4
and 3.7. The all-ones phase for the alphabet $\{1,n\}$, with $n$ positive
and even, and both alternating phases for $\{-1,n\}$, with $n$ any even
integer, have orbit length $2^{\lceil d/2\rceil}$ at depth $d$.
The proof uses unreduced signed words and a palindrome class preserved by
taking the section of the square at two phase coordinates. It also gives
the all-ones statement for nonpositive even $n$ under Shen's displayed
signed recursion. These are finite phase-orbit results; they do not imply
the density conjecture for the classical Kolakoski sequence.
\end{abstract}
\maketitle

\section{Statements and conventions}

Shen's phase maps record the starting symbols left after successive
run-length expansions. We use their signed extension from
\cite[Definition 3.6]{Shen}, which can be specified without referring to
run lengths of nonpositive size.

Let $A=\{a,b\}$ be an alphabet of two distinct symbols and write
$\overline a=b$, $\overline b=a$. Fix integers $m,n$ and put
$v(a)=m$, $v(b)=n$. For each $d\geq 0$ define permutations
$G_{a,d},G_{b,d}$ of $A^d$ recursively. Both are the identity on the
single empty word at depth zero. For $x,s\in A$ and $u\in A^d$, set
\begin{equation}\label{eq:recursion}
 G_{x,d+1}(su)=\overline s\,G_{s,d}^{\,v(x)}(u).
\end{equation}
Here an integer power denotes a power of a permutation, including inverse
powers. This is well-defined by induction: the two subsets with first
symbol $a$ and $b$ are interchanged, and the map on each suffix is a
permutation. More explicitly,
\begin{equation}\label{eq:inverse}
 G_{x,d+1}^{-1}(su)=\overline s\,G_{\overline s,d}^{-v(x)}(u).
\end{equation}
These formulas commute with deleting the final coordinate. We therefore
write $G_x$ when the depth is understood. When $m\ne n$, relabeling
$a,b$ as $m,n$ identifies $G_x$ with Shen's map $C_{m,n}(v(x),-)$.

For a permutation $g$ and a point $t$, let $\per_g(t)$ denote the least
positive integer $r$ with $g^r(t)=t$. For $d\geq0$, let $\alpha_d$ and
$\beta_d$ be the length-$d$ prefixes of $abab\cdots$ and $baba\cdots$,
respectively.

\begin{theorem}\label{thm:main}
Let $n$ be an even integer and use the recursion
\eqref{eq:recursion}. For every $d\geq0$ the following hold.
\begin{enumerate}[label=\textup{(\roman*)}]
\item If $m=1$, then $\per_{G_a}(a^d)=2^{\lceil d/2\rceil}$.
\item If $m=-1$, then
\[
 \per_{G_a}(\alpha_d)=\per_{G_a}(\beta_d)
 =2^{\lceil d/2\rceil}.
\]
\end{enumerate}
\end{theorem}

At depth $2j-1$, part (i) for positive even $n$ is
\cite[Conjecture 3.4]{Shen}; part (ii) for every even integer $n$ is
\cite[Conjecture 3.7]{Shen}. The positivity in the first statement comes
from the standing convention before Shen introduces the signed
extension. Part (i) also records the extension to all even integers
using \eqref{eq:recursion}.

Shen's upper bound is $2^{\lceil d/2\rceil}$ for any phase orbit
\cite[Proposition 3.3]{Shen}. We include a proof of this bound below.
MacAulay studies the transformation groups of these automata and counts
their maximal orbits; the existence result in
\cite[Section 4]{MacAulay} does not specify the all-ones phase. Our
argument identifies the particular phases in Theorem~\ref{thm:main}.
The original observation for $n=2$ is attributed by Shen to Yongyi Chen
\cite[Section 4]{Shen}.

\begin{remark}\label{rem:zero}
When $n=0$, formula \eqref{eq:recursion} makes $G_b$ interchange the
first symbol and leave the suffix fixed. In particular, $G_b$ is not the
identity at positive depth. This follows from the displayed formula in
\cite[Definition 3.6]{Shen}; the sentence at the beginning of its
Section~4 that describes the zero-input map as the identity is
inconsistent with that formula. Throughout this paper, including the
case $n=0$, the convention is \eqref{eq:recursion}.
\end{remark}

\section{Signed words and their sections}

A signed letter is $x^{\eps}$ with $x\in A$ and $\eps\in\{1,-1\}$.
A signed word is a finite list of signed letters. We keep these words
unreduced: their lengths refer to the number of letters as written,
even if neighboring inverse letters occur. For a word $W$, write
$|W|$ for its length and $\rev(W)$ for its reversal, which retains the
sign of every letter. Its complement $\overline W$ exchanges $a$ and
$b$ and also retains all signs. A signed palindrome satisfies
$W=\rev(W)$.

The action $G_W$ means that the letters of $W$ act successively from
left to right. Thus $G_{UV}=G_V\circ G_U$. Empty words act as the
identity. For a phase symbol $s$ and an integer $k$, the word $s^{[k]}$
means $k$ copies of $s$ if $k\geq0$, and $-k$ copies of $s^{-1}$ if
$k<0$. Brackets distinguish this formal word from a phase word or
a permutation power. In particular, $s^{[0]}$ is empty.

\begin{definition}\label{def:section}
For $s\in A$, define the signed word $D_s(W)$ by scanning $W$ from
left to right with current phase initially $s$. A letter $x$ emits
$s^{[v(x)]}$, whereas $x^{-1}$ emits
$\overline s^{[-v(x)]}$. After either letter, interchange the current
phase. Concatenate the emitted words in their scanning order.
\end{definition}

The use of the opposite phase for an inverse letter is necessary:
it is exactly the inverse formula \eqref{eq:inverse}. Define
$\sigma_s(W)=s$ if $|W|$ is even and
$\sigma_s(W)=\overline s$ if $|W|$ is odd.

\begin{lemma}\label{lem:section}
For all signed words $U,V,W$, all $s,t\in A$, and every suffix $u$,
\begin{align}
 D_s(UV)&=D_s(U)D_{\sigma_s(U)}(V),\label{eq:concat}\\
 G_W(su)&=\sigma_s(W)\,G_{D_s(W)}(u).
 \label{eq:section}
\end{align}
The section of $G_W$ at the two-symbol phase $st$ is consequently
$G_{D_t(D_s(W))}$.
Moreover,
\begin{equation}\label{eq:length}
 |D_s(W)|=\sum_{x^{\eps}\text{ in }W}|v(x)|,
 \qquad D_{\overline s}(W)=\overline{D_s(W)}.
\end{equation}
\end{lemma}
\begin{proof}
After scanning $U$ the current phase is $\sigma_s(U)$; this gives
\eqref{eq:concat}. For a single signed letter, \eqref{eq:section}
is \eqref{eq:recursion} or \eqref{eq:inverse}. Applying these formulas
successively proves \eqref{eq:section} for any word. Applying it once
more to the suffix proves the two-symbol assertion. Each input letter
emits $|v(x)|$ letters, independently of its sign and the incoming
phase. Complementing the incoming phase complements every emitted
letter while preserving its sign. These observations prove
\eqref{eq:length}.
\end{proof}

\begin{lemma}[Reversal]\label{lem:reversal}
Let $P$ be a signed palindrome.
\begin{enumerate}[label=\textup{(\roman*)}]
\item If $|P|$ is even, then $|D_s(P)|$ is even and
\[
 D_{\overline s}(P)=\rev(D_s(P)).
\]
\item If $|P|$ is odd, then $D_s(P)$ is a signed palindrome. Its
length has the parity of $|v(x)|$, where $x^{\eps}$ is the central
letter of $P$.
\end{enumerate}
\end{lemma}
\begin{proof}
Number the input positions from $1$ to $\ell=|P|$. The phase at
position $i$ is obtained from $s$ by $i-1$ interchanges. The reflected
position is $\ell+1-i$, whose phase is obtained by $\ell-i$
interchanges. The two positions carry exactly the same signed letter.
If $\ell$ is even, their phases are opposite; if $\ell$ is odd, their
phases agree. Each emitted block is a constant signed word and is
therefore equal to its reversal. Reversing the order of all these
blocks proves the asserted word identities. Their lengths occur in
equal reflected pairs. In the even case this makes the total even;
in the odd case only the central block contributes to its parity.
The empty palindrome is covered by the same conclusions.
\end{proof}

\section{Two levels at a time}

\begin{lemma}\label{lem:square}
For any signed word $W$, its squared action $G_W^2=G_{WW}$ fixes
every phase prefix of length two.
\end{lemma}
\begin{proof}
The first phase is interchanged $2|W|$ times. By
\eqref{eq:length}, the first section of $WW$ has length
$2\sum_{x^{\eps}\text{ in }W}|v(x)|$, an even integer. Its action
therefore fixes the second phase as well.
\end{proof}

\begin{proposition}\label{prop:upper}
Every orbit of every signed word action on $A^d$ has length dividing
$2^{\lceil d/2\rceil}$.
\end{proposition}
\begin{proof}
At depths zero and one every such action has order dividing $1$ and
$2$, respectively. For $d\geq2$, Lemma~\ref{lem:square} allows us
to restrict $G_W^2$ to each fixed two-symbol prefix. By
Lemma~\ref{lem:section}, its action on the remaining $d-2$ symbols
is another signed word action. Induction shows that raising this
section to $2^{\lceil(d-2)/2\rceil}$ gives the identity. Hence
$G_W^{2^{\lceil d/2\rceil}}$ is the identity on $A^d$, proving the
divisibility assertion.
\end{proof}

\begin{lemma}[Exact doubling]\label{lem:doubling}
Suppose that $|W|$ is odd and put
$W'=D_t(D_s(WW))$. For every finite suffix $u$,
\[
 \per_{G_W}(stu)=2\per_{G_{W'}}(u).
\]
At depth zero the period is one; at depth one it is two.
\end{lemma}
\begin{proof}
An odd number of applications of $G_W$ interchanges the first phase,
so every return requires an even number, say $2r$, of applications.
By Lemma~\ref{lem:square} the square fixes $st$, and by
Lemma~\ref{lem:section} its restriction over that prefix is $G_{W'}$.
Thus $G_W^{2r}(stu)=stu$ if and only if $G_{W'}^r(u)=u$.
Taking least positive return times proves the formula. The two base
cases follow directly from the action on the empty word and from the
first-phase interchange.
\end{proof}

\section{Palindromes preserved at the specified phases}

\begin{proposition}\label{prop:ones}
Suppose $m=1$ and $n$ is even. If $W=aP$ with $P$ an even-length
signed palindrome, then
\[
 D_a(D_a(WW))=aP'
\]
for an even-length signed palindrome $P'$.
\end{proposition}
\begin{proof}
Set $U=D_b(P)$. Since $|P|$ is even, Lemma~\ref{lem:reversal}
gives $D_a(P)=\rev(U)$ and $|U|$ even. Scanning the four pieces
$a,P,a,P$ and using $v(a)=1$ gives the exact word identity
\begin{equation}\label{eq:ones}
 D_a(WW)=a\,U\,b\,\rev(U).
\end{equation}
Indeed, the phases at their starts are $a,b,b,a$, respectively.
The word $V=Ub\rev(U)$ is an odd-length signed palindrome with
central letter $b$. Applying $D_a$ to the first letter $a$ in
\eqref{eq:ones} emits $a$ and leaves incoming phase $b$ for $V$.
Consequently
\[
 D_a(D_a(WW))=aD_b(V).
\]
By Lemma~\ref{lem:reversal}, $D_b(V)$ is a signed palindrome of
even length, since $|v(b)|=|n|$ is even. This proves the claim,
including negative $n$ and $n=0$.
\end{proof}

\begin{proposition}\label{prop:alternating}
Suppose $m=-1$ and $n$ is even. The following classes are preserved:
\begin{align*}
 W=aP&\quad\Longrightarrow\quad D_b(D_a(WW))=aP',\\
 W=Pa&\quad\Longrightarrow\quad D_a(D_b(WW))=P'a,
\end{align*}
where $P$ and $P'$ are even-length signed palindromes.
\end{proposition}
\begin{proof}
In both cases put $U=D_b(P)$, so that $D_a(P)=\rev(U)$ and
$|U|$ is even. For the first class, scanning $a,P,a,P$ gives
\begin{equation}\label{eq:alternating1}
 D_a(WW)=a^{-1}U b^{-1}\rev(U).
\end{equation}
Let $V=Ub^{-1}\rev(U)$. This is an odd-length signed palindrome
whose central letter has even absolute value. Under $D_b$, the
first letter $a^{-1}$ in \eqref{eq:alternating1} emits
$a^{[-v(a)]}=a$ and switches the phase to $a$. Thus
\[
 D_b(D_a(WW))=aD_a(V).
\]
Lemma~\ref{lem:reversal} says that $D_a(V)$ is an even-length
signed palindrome.

For the second class, scan $P,a,P,a$, starting with phase $b$.
The corresponding identity is
\begin{equation}\label{eq:alternating2}
 D_b(WW)=U b^{-1}\rev(U)a^{-1}=Va^{-1}.
\end{equation}
The scan of $V$ under $D_a$ emits the even-length palindrome
$D_a(V)$. Since the input length $|V|$ is odd, the incoming phase
for the final $a^{-1}$ is $b$. This last letter emits $a$, as before,
so \eqref{eq:alternating2} gives
\[
 D_a(D_b(WW))=D_a(V)a.
\]
Notice that it is the odd \emph{input} length of $V$, rather than
the length of its emitted word, that determines the phase for this
last letter.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
We first prove part (i) in the stronger form that every word $aP$,
with $P$ an even-length signed palindrome, has period
$2^{\lceil d/2\rceil}$ at $a^d$. The assertion is true at depths
zero and one by Lemma~\ref{lem:doubling}. If $d\geq2$, the
two-symbol prefix is $aa$. Proposition~\ref{prop:ones} puts the
section of the square in the same word class. Deleting this prefix
leaves $a^{d-2}$. Lemma~\ref{lem:doubling} and induction now give
\[
 \per_{G_{aP}}(a^d)
 =2\,2^{\lceil(d-2)/2\rceil}
 =2^{\lceil d/2\rceil}.
\]
The initial word $a$ belongs to the class by taking $P$ empty.

For part (ii), prove simultaneously that every $aP$ has this period
at $\alpha_d$, and every $Pa$ has this period at $\beta_d$.
The initial depths are again Lemma~\ref{lem:doubling}. When
$d\geq2$, the two-symbol prefixes are $ab$ and $ba$;
Proposition~\ref{prop:alternating} preserves the corresponding
word class. Deleting two symbols leaves $\alpha_{d-2}$ and
$\beta_{d-2}$. Exact doubling and induction give the same displayed
value. Taking $P$ empty in both classes gives the result for $G_a$.
\end{proof}

\section{The positive odd-expansion formulation}

Assume in this section that $m=1$ and $n>0$ is even. All words
constructed below have positive letters. For such a word $W$,
$D_s(W)$ is ordinary run-length expansion starting with the symbol
$s$. Write $E(W,s_1\cdots s_r)$ for iterating these expansions in
the order $s_1,\ldots,s_r$, and let $E(W,\varnothing)=W$.
This is Shen's expansion notation, after relabeling $a,b$ by $1,n$.

\begin{lemma}\label{lem:expansion}
For positive words $U,V$ and a phase word $t$,
\[
 E(UV,t)=E(U,t)E(V,G_U(t)).
\]
In particular, the section of $G_U$ at $t$ is $G_{E(U,t)}$.
\end{lemma}
\begin{proof}
For a one-symbol $t$, the identity is \eqref{eq:concat}.
Induct on $|t|$, applying that identity to the two words obtained
at the previous expansion level. The outgoing next phase is the
appropriate coordinate of $G_U(t)$ by \eqref{eq:section}, so the
induction gives the formula as stated. Repeated application of
\eqref{eq:section} proves the section assertion.
\end{proof}

\begin{corollary}\label{cor:odd}
For every integer $j\geq0$, the word
\[
 E(a^{2^j},a^{2j})
\]
has odd length. For $j>0$ this is the odd-expansion statement of
\cite[Proposition 3.5]{Shen}.
\end{corollary}
\begin{proof}
Define $W_0=a$ and $W_{j+1}=D_a(D_a(W_jW_j))$.
Proposition~\ref{prop:ones} implies inductively that $W_j=aP_j$
with $P_j$ an even-length palindrome. In particular, $|W_j|$ is odd.
We prove
\begin{equation}\label{eq:identify}
 W_j=E(a^{2^j},a^{2j}).
\end{equation}
The case $j=0$ is immediate. Proposition~\ref{prop:upper} says that
$G_a^{2^j}$ fixes every phase word of length $2j$. By
Lemma~\ref{lem:expansion}, expansion of two consecutive copies of
$a^{2^j}$ through those $2j$ levels therefore gives $W_jW_j$.
Expanding through the next two $a$-levels gives
\[
 E(a^{2^{j+1}},a^{2j+2})
 =D_a(D_a(W_jW_j))=W_{j+1},
\]
which proves \eqref{eq:identify} by induction. Its left side has
odd length, giving the result.
\end{proof}

\begin{thebibliography}{9}
\bibitem{MacAulay}
Noah MacAulay, \emph{Group theory of the Kolakoski sequence},
preprint, 2026, arXiv:2605.14234v1,
\url{https://arxiv.org/abs/2605.14234v1}.

\bibitem{Shen}
Bobby Shen, \emph{The Kolakoski sequence and related conjectures
about orbits}, Experimental Mathematics \textbf{29} (2020), no.~1,
54--65, \url{https://doi.org/10.1080/10586458.2018.1434703}.
The numbering used here is that of arXiv:1702.08156v2 (2017),
\url{https://arxiv.org/abs/1702.08156v2}.
\end{thebibliography}
\end{document}