arxiv: 2605.14234 · v1 · pith:PANEHHS6new · submitted 2026-05-14 · 🧮 math.GR

Group Theory of the Kolakoski Sequence

Noah MacAulay This is my paper

Pith reviewed 2026-05-15 02:42 UTC · model grok-4.3

classification 🧮 math.GR

keywords Kolakoski sequencerun-length decodingpermutation automatatransformation groupsweakly regular branch groupsorbit countingbinary tree automorphismsgroup theory

0 comments

The pith

Transformation groups of run-length decoding automata for Kolakoski sequences permit explicit counting of maximal orbits for odd iteration depths.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the transformation groups generated by permutation automata that perform n-fold run-length decoding on sequences built from a two-symbol alphabet. These groups act on finite-depth binary trees and sit inside a larger group defined by a recursive construction. The central result uses the recursive structure to compute the number of longest orbits under the group action for any starting sequence when n is odd. A reader would care because the Kolakoski sequence arises precisely from this decoding process, so the groups offer a symmetry description that may clarify its construction and statistical properties.

Core claim

The transformation groups K^{p,q}_n of the automata A^{p,q}_n are subgroups of the recursively defined group J_n^{p,q}, which has an intricate recursive structure, and whose limit is weakly regular branch. As an application, the number of maximal-length orbits of the automata on an arbitrary input sequence is determined when n is odd.

What carries the argument

The recursively defined group J_n^{p,q} containing the transformation groups K^{p,q}_n of the run-length decoding automata, acting inside the automorphism group of binary trees of depth n+1.

Load-bearing premise

The transformation groups of the automata are subgroups of and likely equal to the recursively defined group J_n^{p,q} whose limit is weakly regular branch.

What would settle it

An explicit computation of the orbit counts for the automaton at a small odd n, such as n=1, that produces a different number from the count predicted by the structure of J_n^{p,q}.

Figures

Figures reproduced from arXiv: 2605.14234 by Noah MacAulay.

**Figure 1.** Figure 1: Illustration of A 1,2 3 . Edges are labeled by the input inducing that transition. Proof. We will proceed by induction in n. Now for the base case we have A1(x, s) = ( x, if |s| is even, (p + q) − x, if |s| is odd Clearly this is invertible. Now, for the inductive step, we have An(x, s) = ( (x1, An−1(x2:n, RLD(x1, s))), if |s| is even, ((p + q) − x1, An−1(x2:n, RLD(x1, s))) if |s| is odd Which can thus be … view at source ↗

read the original abstract

Run-length decoding is an operation on sequences in which a positive integer $a$ is replaced by a run(sequence of repeated elements) of length $a$. Iterated run-length decodings applied to sequences with alphabets consisting of pairs of positive integers $\{p, q\}$ have attracted attention from mathematicians, most notably in their role defining the well-known Kolakoski sequence. $n$-th-iterated run-length decodings are controlled by naturally associated permutation automata $A^{p,q}_n$. Here we study the transformation groups $\mathcal{K}^{p,q}_n$ of these automata. They are subgroups of the automorphism group of binary trees of depth $n+1$. They are naturally subgroups of(and likely equal to) a certain group $\mathcal{J}_n^{p,q}$ with an intricate recursive structure; their limit group is plausibly weakly regular branch. As an application we determine the number of maximal-length orbits of the automata given an arbitrary input sequence for odd $n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sets up permutation automata for run-length decodings tied to Kolakoski and studies the groups they generate, but the claimed subgroup relation to the recursive J and the orbit-count application rest on steps not shown in the text.

read the letter

The fresh part is the automata A^{p,q}_n that encode iterated run-length decoding on pairs {p,q}, together with the transformation groups K^{p,q}_n inside the automorphism group of finite binary trees. That gives a concrete algebraic object attached to the sequence instead of just the usual word combinatorics. The suggestion that these groups sit inside a recursively defined J_n^{p,q} whose limit is weakly regular branch is the main structural claim, and the orbit-counting formula for odd n is offered as an application of that structure. Those pieces are new enough to be worth looking at if you care about algebraic models for self-describing sequences. The manuscript does not supply the recursive presentation of J, the generators or relations that would establish the inclusion K inside J, or the derivation that turns the group action into the stated orbit count. The qualifiers “likely” and “plausibly” in the abstract flag that the identification itself is not yet verified in the visible argument. Without those steps the orbit result cannot be checked, so the central application remains unconfirmed. The rest of the setup—automata definition, embedding into tree automorphisms—looks straightforward and reproducible from the description given. This is for readers already working on Kolakoski or automatic sequences who want to see whether group theory yields new counting formulas. A serious referee could check the missing derivations and decide whether the subgroup claim holds; the paper is concrete enough to deserve that look rather than a desk rejection.

Referee Report

2 major / 2 minor

Summary. The paper associates permutation automata A^{p,q}_n to iterated run-length decodings on sequences over the alphabet {p,q}, studies the transformation groups K^{p,q}_n of these automata as subgroups of the automorphism group of binary trees of depth n+1, asserts that these groups are subgroups of (and likely equal to) a recursively defined group J_n^{p,q} whose limit is weakly regular branch, and applies the structure to compute the number of maximal-length orbits under arbitrary input sequences when n is odd.

Significance. If the asserted subgroup relation and recursive presentation of J_n^{p,q} are established with explicit generators, relations, and derivations, the work would supply a group-theoretic framework linking run-length decoding automata to branch groups, potentially yielding new invariants for the Kolakoski sequence and related combinatorial dynamics.

major comments (2)

[Abstract and application section] The manuscript states that K^{p,q}_n are subgroups of (and likely equal to) the recursively defined group J_n^{p,q} but supplies neither the recursive definition of J_n^{p,q} nor generators/relations establishing the inclusion; this identification is required for the orbit-count application yet remains unverified in the text.
[Application paragraph] The derivation of the number of maximal-length orbits for odd n is presented as an application of the group structure, but no explicit computation or reduction from the (unexhibited) recursive presentation of J_n^{p,q} to the orbit formula is given, leaving the central claim without supporting derivations.

minor comments (2)

[Abstract] The qualifiers 'likely' and 'plausibly' appear in the abstract when describing the relation to J_n^{p,q}; these should be replaced by precise statements once the inclusion is proved.
[Introduction] Notation for the automata A^{p,q}_n and groups K^{p,q}_n is introduced without an early reference table or diagram clarifying the dependence on n, p, q.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to incorporate the requested clarifications and derivations.

read point-by-point responses

Referee: [Abstract and application section] The manuscript states that K^{p,q}_n are subgroups of (and likely equal to) the recursively defined group J_n^{p,q} but supplies neither the recursive definition of J_n^{p,q} nor generators/relations establishing the inclusion; this identification is required for the orbit-count application yet remains unverified in the text.

Authors: We agree that the recursive definition of J_n^{p,q}, together with explicit generators and relations establishing the inclusion K^{p,q}_n ≤ J_n^{p,q}, was not exhibited with sufficient detail. In the revised manuscript we will insert a dedicated subsection that (i) defines J_n^{p,q} by its recursive presentation on the binary tree of depth n+1, (ii) lists a finite set of generators and relations, and (iii) proves the subgroup relation by exhibiting an explicit embedding of the transformation group of the automaton into this presentation. This will make the identification verifiable and will directly support the orbit-counting application. revision: yes
Referee: [Application paragraph] The derivation of the number of maximal-length orbits for odd n is presented as an application of the group structure, but no explicit computation or reduction from the (unexhibited) recursive presentation of J_n^{p,q} to the orbit formula is given, leaving the central claim without supporting derivations.

Authors: We acknowledge that the reduction from the recursive structure of J_n^{p,q} to the explicit count of maximal-length orbits was omitted. The revised version will contain a self-contained computation that proceeds by induction on the recursive definition: for odd iteration depth we first determine the action on the top level of the tree, then use the recursive decomposition of J_n^{p,q} to count the fixed-point-free orbits of maximal length, and finally obtain the closed-form formula. All intermediate steps will be written out explicitly. revision: yes

Circularity Check

0 steps flagged

No circularity: groups defined directly from automata; orbit count presented as independent application

full rationale

The paper defines the transformation groups K^{p,q}_n directly as the groups generated by the permutation automata A^{p,q}_n acting on binary trees of depth n+1. The larger group J_n^{p,q} is introduced separately with its own recursive structure, and the claim that K is a subgroup (possibly equal) is stated without any equation or construction that makes the orbit-count formula reduce to a re-labeling of the input data or to a self-citation. No fitted parameters are renamed as predictions, no ansatz is smuggled via prior work, and the central application is not shown to be forced by definition. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper introduces two new groups K^{p,q}_n and J_n^{p,q} whose definitions rest on standard facts about permutation groups and tree automorphisms; no free parameters or invented physical entities appear.

axioms (2)

standard math The set of all permutations realized by the n-fold iterated run-length automaton forms a group under composition.
Invoked when defining the transformation group K^{p,q}_n.
domain assumption These groups embed into the automorphism group of the binary tree of depth n+1.
Stated directly in the abstract as the ambient group containing K.

invented entities (1)

Group J_n^{p,q} no independent evidence
purpose: A recursively defined supergroup that is conjectured to equal K^{p,q}_n and whose limit is weakly regular branch.
Introduced to organize the structure of the transformation groups; no independent evidence outside the paper is given.

pith-pipeline@v0.9.0 · 5460 in / 1394 out tokens · 28609 ms · 2026-05-15T02:42:53.011340+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean, AlexanderDuality.lean reality_from_one_distinction; alexander_duality_circle_linking echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

K^{p,q}_n … subgroups of the automorphism group of binary trees of depth n+1 … naturally subgroups of (and likely equal to) a certain group J_n^{p,q} with an intricate recursive structure; their limit group is plausibly weakly regular branch.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

Rufus Oldenburger, Exponent trajectories in symbolic dynamics, Trans. Amer. Math. Soc., Vol. 46 (1939), pp. 453-466

work page 1939
[2]

Kolakoski, Self Generating Runs, Problem 5304, American Math

W. Kolakoski, Self Generating Runs, Problem 5304, American Math. Monthly 72 (1965), 674. Solution: American Math. Monthly 73 (1966), 681–682

work page 1965
[3]

The Kolakoski sequence and related conjectures about orbits

Shen, Bobby. “The Kolakoski sequence and related conjectures about orbits.” Experimental Mathe- matics 29.1 (2020): 54-65

work page 2020
[4]

Notes on the Kolakoski sequence

Chv´ atal, Vaˇ sek. “Notes on the Kolakoski sequence.” Rapport, DIMACS Techn. Rep (1994)

work page 1994
[5]

Branch groups

Bartholdi, Laurent, Rostislav I. Grigorchuk, and Zoran ˇSuni. “Branch groups.” Handbook of algebra. Vol. 3. North-Holland, 2003. 989-1112. 14

work page 2003