\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}
\title[Periodic Kolakoski-transform counterexamples]{Periodic counterexamples to three conjectures on Kolakoski transforms}
% Authors must occur alphabetically by surname, not in the reference PDF's order.
\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}
The simple Kolakoski transform need not preserve the limiting mean of a
periodic word on $\{1,2\}$. We give a counterexample with input period $24$
and output period $12$, and a balanced counterexample whose input has mean
$3/2$ while its output has mean $13/9$. Both examples remain unchanged under
every realization of a nonconstant summable perturbation of the weights.
Their discrepancies from the input means are linear. Consequently they
contradict Conjectures~(1), (2), and~(4) of Cloitre. These statements concern
auxiliary transforms of periodic inputs; the classical Kolakoski frequency
problem remains open.
\end{abstract}
\maketitle

\section{Definitions and scope}

We use positive integer indexing. For a word $a=(a_i)_{i\geq1}$, its mean,
when it exists, is
\[
 m(a)=\lim_{n\to\infty}\frac1n\sum_{i=1}^n a_i.
\]
Cloitre introduced the following transforms in~\cite[pp.~2--3]{Cloitre}.
For an input $w$ on $\{1,2\}$ and positive weights $u=(u_i)_{i\geq1}$,
write
\[
 F_{x,u}(0)=0,\qquad F_{x,u}(i)=\sum_{j=1}^i u_jx_j,\qquad
 G_{x,u}(n)=\min\{i\geq1:F_{x,u}(i)\geq n\}.
\]
With the initialization used here, a weighted transform is a word $x$ satisfying
\begin{equation}\label{eq:transform}
 x_1=1,\quad x_2=2,\qquad x_n=w_{G_{x,u}(n)}\quad(n\geq3).
\end{equation}
The simple transform has $u_i=1$ for every $i$. In that case write $F_x$ and
$G_x$ for the two cumulative functions.

All weights in this paper satisfy $u_i\geq1$. Consequently
\eqref{eq:transform} is a causal recursion and determines $x$ uniquely.
Indeed, for $n\geq3$ its first $n-1$ terms give
\[
 \sum_{j=1}^{n-1}u_jx_j\geq\sum_{j=1}^{n-1}x_j\geq n,
\]
since $x_2=2$ and every other letter is at least one. Thus the least index
in \eqref{eq:transform} is found among the already determined positions.
This also proves existence by induction.

The three assertions addressed here are the following statements
of~\cite[\S\S1, 2.2, 2.4]{Cloitre}:
\begin{enumerate}[label=(\roman*),leftmargin=2em]
\item The simple transform preserves every existing input mean.
\item The same mean preservation holds for random weights which are
$\delta(i)$ with probability $1/f_\alpha(i)$ and one otherwise, where
$\delta$ is bounded and positive, $0<\alpha<1$, and $f_\alpha$ is positive
and regularly varying with index $\alpha$.
\item If $m(w)=\lambda$, the simple transform satisfies
\begin{equation}\label{eq:claimed}
 \sum_{j=1}^n x_j=\lambda n+O(n^{1/2+\varepsilon}).
\end{equation}
\end{enumerate}
They are respectively Conjectures~(1), (2), and~(4). We disprove the last
estimate for every fixed $0<\varepsilon<1/2$. For the random assertion,
our counterexamples fail in every realization, so the interpretation of its
probabilistic mode of convergence is immaterial.

\section{A short periodic certificate}

The following observation turns a finite block identity into an infinite
transform identity. A block is a consecutive finite string; adjacent blocks
may have the same letter.

\begin{lemma}[Block criterion]\label{lem:block}
Let $x$ and $w$ be words on $\{1,2\}$, with $x_1=1$ and $x_2=2$.
If for every $i\geq1$ the positions
\[
 F_x(i-1)+1,\ldots,F_x(i)
\]
all carry the letter $w_i$, then $x$ is the simple transform of $w$.
Suppose, moreover, that $x$ has period $p$, $w$ has period $q$, $p\mid q$,
and $p\mid F_x(q)$. Then it suffices to check these blocks for
$1\leq i\leq q$.
\end{lemma}
\begin{proof}
The blocks partition the positive integer positions. The block containing
$n$ has index $G_x(n)$, giving the required identity, even for $n=1,2$.
For the periodic assertion, write $i=aq+r$ with $a\geq0$ and $1\leq r\leq q$.
Since $q$ is a period of $x$,
\[
 F_x(aq+r)=aF_x(q)+F_x(r).
\]
Translation by $aF_x(q)$ preserves $x$, and translation by $aq$ preserves
$w$. The $i$th block therefore has the same color as the $r$th block.
\end{proof}

\begin{theorem}\label{thm:short}
Let
\[
 x=(122221122111)^\infty,\qquad
 w=(122121112221121122212111)^\infty.
\]
Then $x$ is the simple transform of $w$, and
\[
 m(w)=\frac{35}{24},\qquad m(x)=\frac32.
\]
In particular, simple transforms do not preserve the means of periodic
binary inputs.
\end{theorem}
\begin{proof}
For $i=1,\ldots,24$, the blocks formed by repeating $w_i$ exactly $x_i$
times are, in order,
\[
\begin{array}{rrrrrrrrrrrr}
1&22&22&11&22&1&1&11&22&2&2&1\\[2pt]
1&22&11&11&22&2&2&11&22&1&1&1.
\end{array}
\]
Their concatenation is exactly $(122221122111)^3$.
Here $p=12$, $q=24$, and $F_x(q)=36$, so Lemma~\ref{lem:block} applies.
The displayed output period has six twos, while the input period has eleven.
The respective period sums are therefore $18$ and $35$, which give the stated
means.
\end{proof}

\begin{lemma}[Periodic discrepancy]\label{lem:mean}
If a bounded real word $a$ has period $p$, then
\[
 \sum_{j=1}^n a_j=m(a)n+O(1),\qquad
 m(a)=\frac1p\sum_{j=1}^p a_j.
\]
\end{lemma}
\begin{proof}
Write $n=kp+r$, where $0\leq r<p$. The difference on the left is
$\sum_{j=1}^r a_j-m(a)r$, one of finitely many values.
\end{proof}

\begin{corollary}\label{cor:short-deviation}
For the input in Theorem~\ref{thm:short},
\[
 \sum_{j=1}^n x_j-\frac{35}{24}n=\frac{n}{24}+O(1).
\]
Thus \eqref{eq:claimed} fails whenever $0<\varepsilon<1/2$.
\end{corollary}
\begin{proof}
Apply Lemma~\ref{lem:mean}. Dividing by $n$ yields a nonzero limit $1/24$,
whereas an $O(n^{1/2+\varepsilon})$ discrepancy would give limit zero.
\end{proof}

\section{A balanced input}

The discrepancy can also occur when the input has equal frequencies of
one and two. Define the periodic binary word $y$ by
\begin{equation}\label{eq:y}
 y=(101010101001101001101001000)^\infty.
\end{equation}
Set
\begin{equation}\label{eq:balanced-x}
 x_1=1,\qquad x_{2i}=x_{2i+1}=1+y_i\quad(i\geq1).
\end{equation}
In this section $x$ denotes this new word.

\begin{theorem}\label{thm:balanced}
The word \eqref{eq:balanced-x} is the simple transform of a periodic word
$w$ of period $486$. This input has $243$ twos in one period. Consequently
\[
 m(w)=\frac32,\qquad m(x)=\frac{13}{9},\qquad
 \sum_{j=1}^n x_j-\frac32 n=-\frac{n}{18}+O(1).
\]
\end{theorem}
\begin{proof}
Put
\[
 t_i=\sum_{j<i}(1+y_j),\qquad F_x(2i-1)=1+2t_i.
\]
After its first singleton, the proposed source lengths occur in equal pairs.
The two source blocks corresponding to $2i$ and $2i+1$ together cover the
$1+y_i$ target pairs beginning at positions
\[
 2(t_i+1),\ 2(t_i+2),\ \ldots,\ 2(t_i+1+y_i).
\]
Every target pair has equal letters by \eqref{eq:balanced-x}. If $y_i=1$,
each source block is a whole target pair. If $y_i=0$, the two source blocks
are the two singleton halves of one target pair. All blocks are therefore
monochromatic. Let $w_i$ be the color of the $i$th block.
This defines the input and proves the transform identity by
Lemma~\ref{lem:block}.

The period in \eqref{eq:y} contains twelve ones. Since $y_{27}=0$, the
word $x$ is periodic from its first position, with period $54$.
That period has $24$ twos and sum $78$. In particular,
\[
 F_x(i+486)=F_x(i)+702,\qquad 702=13\cdot54.
\]
Translating a source block by $486$ thus translates its target block by a
period of $x$. Hence $w$ has period $486$.

It remains to count the twos in this input period. Count the $243$ pairs
$w_{2i},w_{2i+1}$ for $1\leq i\leq243$; these are also $486$ consecutive
input letters. If $y_i=1$, their two colors read the target bits
$y_{t_i+1},y_{t_i+2}$ once each. If $y_i=0$, they read $y_{t_i+1}$ twice.
Thus every target bit from $1$ through
\[
 t_{244}=9\sum_{i=1}^{27}(1+y_i)=9\cdot39=351
\]
is read once, with one additional reading of $y_{t_i+1}$ for each zero
source bit. The first readings contribute $13\cdot12=156$ twos.

For the additional readings, let
\[
\begin{aligned}
 A_r&=\#\{1\leq j\leq27:y_j=1,\ j-1\equiv r\pmod3\},\\
 B_r&=\#\{1\leq i\leq27:y_i=0,\ t_i\equiv r\pmod3\}.
\end{aligned}
\]
The period \eqref{eq:y} gives the following small table:
\[
\begin{array}{c|rrr}
 r&0&1&2\\\hline
 A_r&4&1&7\\
 B_r&4&1&10
\end{array}
\]
For completeness, the $t_i$ at zero positions $i$ in this first period are
\[
 \begin{gathered}2,5,8,11,14,15,20,23,\\24,29,32,33,36,37,38,\end{gathered}
\]
which verify the second row.
For a fixed source position $i$, moving to $i+27k$ adds $39k$ to $t_i$.
The nine residues $t_i+39k$ modulo $27$, $0\leq k\leq8$, are exactly the
residue class of $t_i$ modulo $3$, since $\gcd(39,27)=3$.
Its additional readings therefore contribute $A_r$ twos when
$t_i\equiv r\pmod3$. The total number of additional twos is
\[
 \sum_{r=0}^2 B_rA_r=4\cdot4+1\cdot1+10\cdot7=87.
\]
There are $156+87=243$ input twos, as asserted. The two means and the
linear discrepancy now follow from the period sums and
Lemma~\ref{lem:mean}.
\end{proof}

\section{Weights that leave every cut unchanged}

\begin{lemma}[Stability of integer cuts]\label{lem:stability}
Let $x$ be a word on $\{1,2\}$, and suppose
\[
 u_i\geq1,\qquad \sum_{i=1}^\infty 2(u_i-1)<1.
\]
Then for every pair of positive integers $i,n$,
\[
 F_{x,u}(i)\geq n\quad\Longleftrightarrow\quad F_x(i)\geq n.
\]
In particular $G_{x,u}(n)=G_x(n)$ for all $n$.
\end{lemma}
\begin{proof}
For each $i$,
\[
 0\leq F_{x,u}(i)-F_x(i)
 =\sum_{j=1}^i x_j(u_j-1)<1.
\]
Since $F_x(i)$ and $n$ are integers, this perturbation cannot change the
comparison with $n$.
\end{proof}

\begin{theorem}\label{thm:random}
For either input of Theorems~\ref{thm:short} and~\ref{thm:balanced}, put
\[
 \delta(i)=1+2^{-i-2}.
\]
For every choice of weights $u_i\in\{1,\delta(i)\}$, the weighted transform
is the same word $x$ as the simple transform. In particular, the random
weights in Conjecture~(2) do not preserve the input mean.
\end{theorem}
\begin{proof}
The function $\delta$ is positive, bounded, and nonconstant. For every
choice of its permitted weights,
\[
 0\leq\sum_{i=1}^\infty2(u_i-1)
 \leq\sum_{i=1}^\infty 2^{-i-1}=\frac12<1.
\]
Lemma~\ref{lem:stability} shows that all cut indices are unchanged.
Thus $x$ satisfies \eqref{eq:transform} for these weights. Uniqueness of
the causal recursion identifies it with the weighted transform.

For a concrete admissible probability law, fix any $0<\alpha<1$ and set
$f_\alpha(t)=t^\alpha$ for $t\geq1$. It is positive and regularly varying
of index $\alpha$, and $1/f_\alpha(i)$ is a probability. Give $u_i$ the
value $\delta(i)$ with that probability and one otherwise. Every resulting
weight sequence meets the preceding deterministic bound; no independence
assumption is needed. The output mean is therefore $3/2$ instead of
$35/24$ for the short example, or $13/9$ instead of $3/2$ for the balanced
example, in every realization.
\end{proof}

\section{The classical question}

The periodic examples disprove the three universal assertions stated in
Section~1. They do not replace the alternating input $121212\cdots$ by
itself: that input gives the classical Kolakoski word. Nothing in the
argument determines its limiting frequency of either letter. Nor do the
counterexamples address the specifically prescribed alphabet perturbations
in Cloitre's Conjectures~(6)--(8). The classical frequency problem remains
open.

\begin{thebibliography}{1}
\bibitem{Cloitre}
Benoit Cloitre, \emph{The Kolakoski transform of words}, manuscript,
October 6, 2013, 27 pp.,
\url{https://oeis.org/A000002/a000002.pdf}.
\end{thebibliography}
\end{document}