A Reversibility Characterization of Locally Finite Groups by Cellular Automata

Jiang Yang

A Reversibility Characterization of Locally Finite Groups by Cellular Automata

T0 review · 0 major / 2 minor · reviewed 2026-06-30 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A group is locally finite exactly when every bijective cellular automaton on its configurations is reversible over any alphabet.

desk verdict The paper settles the open problem with an if-and-only-if: G is locally finite exactly when every bijective CA over any alphabet is reversible. read the letter →

arxiv 2606.29958 v1 pith:OMFJYI5T submitted 2026-06-29 math.GR math.GN

Jiang Yang This is my paper · ORCID

classification math.GRmath.GN

keywords locallyfinitegroupscellularautomatareversibilitybijectivemapsconfigurationspacesgroupactions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that local finiteness of a group G is the precise group-theoretic condition guaranteeing that every bijective cellular automaton from A^G to A^G remains reversible, no matter how large the alphabet A is chosen. For finite alphabets the implication from bijectivity to reversibility is already known to hold in general; the new result removes any periodicity assumption and handles infinite alphabets by showing that non-local-finiteness always produces a counterexample. The counterexample is built on a countable alphabet whose local rule uses three tracks to produce a triangular shift along arbitrarily long finite chains; the resulting map is bijective yet its inverse cannot be realized by any finite-radius local rule. This directly answers the open question whether the implication survives without periodicity.

What carries the argument

Triangular forward map along finite directed chains of arbitrary length, realized by a three-track local rule (rank, direction, binary data) that exploits the existence of such chains precisely when G is not locally finite.

What would settle it

An explicit locally finite group together with a bijective cellular automaton on some alphabet whose inverse cannot be realized by any finite-radius local rule would falsify the characterization.

Watch

Extended reading notes

Core claim

A group G is locally finite if and only if, over every alphabet, every bijective cellular automaton A^G→A^G is reversible. Equivalently, if G is not locally finite, then for every infinite alphabet A there exists a bijective cellular automaton A^G→A^G whose inverse is not a cellular automaton. The counterexample is already obtained on a countable alphabet whose local rule has a rank track, a direction track and a binary data track; the forward map is triangular along finite directed chains of arbitrary length, so its inverse is defined pointwise but has no uniform finite memory.

Load-bearing premise

When a group fails to be locally finite it contains finite directed chains of arbitrary length that can be used to build a triangular map whose inverse requires unbounded memory.

Editorial extensions

If this is right

Every bijective cellular automaton over a locally finite group is reversible for alphabets of any cardinality.
The periodicity hypothesis is unnecessary for constructing counterexamples when the group is not locally finite.
Open Problem 2 receives an affirmative answer: bijectivity implies reversibility precisely on locally finite groups.
The same counterexample construction works already on countable alphabets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same chain-length obstruction may control other dynamical properties such as the existence of continuous inverses for injective maps on configuration spaces.
Analogous characterizations could be sought for reversibility of cellular automata on semigroups or other algebraic structures that admit directed chains of unbounded length.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main result is the characterization: a group G is locally finite if and only if, for every alphabet A, every bijective cellular automaton on A^G is reversible. This directly answers Open Problem 2 from the Ceccherini-Silberstein–Coornaert book and removes the periodicity restriction on the negative side.

The construction for the negative direction is the clearest new piece. When G is not locally finite it has an infinite finitely generated subgroup, which supplies finite directed chains of arbitrary length. The authors encode these on a three-track countable alphabet (rank, direction, binary data) and define a triangular forward map that shifts data along the chains. The map is bijective because it is invertible pointwise, yet the inverse must reach back to the head of a chain whose length is unbounded, so it cannot have a uniform finite radius. The positive direction follows because local finiteness bounds chain lengths inside each finitely generated subgroup, giving a uniform memory bound once bijectivity is assumed.

The argument is direct and avoids circularity or fitted parameters. The stress-test sketch shows no internal gap in the equivalence. One small thing worth checking in the full text is whether the local rule is written with an explicit finite radius that works uniformly across all configurations; the description suggests it does, but the verification matters for the claim that the forward map is genuinely a cellular automaton.

The paper is short, focused, and aimed at people who work on cellular automata over groups or algebraic symbolic dynamics. Anyone who has cited the open problem will want the details. It is worth sending to referees because the central claim is a clean, falsifiable group-theoretic statement backed by an explicit construction.

Referee Report

0 major / 2 minor

Summary. The paper proves that a group G is locally finite if and only if, for every alphabet A, every bijective cellular automaton A^G → A^G is reversible. Equivalently, when G is not locally finite, for every infinite A there exists a bijective CA whose inverse fails to be a CA. The negative direction constructs an explicit counterexample on a countable alphabet via a three-track local rule (rank, direction, binary data) that implements a triangular forward map along finite directed chains of arbitrary length; bijectivity holds but the inverse requires inspecting arbitrarily distant chain origins and thus lacks uniform finite radius. The positive direction follows because local finiteness bounds chain lengths within each finitely generated subgroup, yielding a uniform memory bound once bijectivity is assumed.

Significance. If the details hold, the result supplies a complete group-theoretic characterization resolving Open Problem 2 of Ceccherini-Silberstein–Coornaert without any periodicity hypothesis. The construction is direct, parameter-free, and self-contained, with an explicit local rule and a falsifiable distinction between bounded versus unbounded chain lengths; this constitutes a clean equivalence in the theory of cellular automata over groups.

minor comments (2)

The abstract states that the counterexample works on a countable alphabet; the main text should explicitly record the cardinality of A used in the construction (e.g., in the paragraph introducing the three-track alphabet) to facilitate immediate verification.
A brief sentence recalling the precise wording of Open Problem 2 (including its page reference in the monograph) would improve accessibility for readers who have not consulted the source.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and for the positive assessment of the manuscript. The report correctly summarizes the main result and its relation to Open Problem 2. We are pleased that the referee finds the construction direct and the equivalence clean.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper proves a direct if-and-only-if equivalence between local finiteness of G and the property that every bijective CA over any alphabet is reversible. The negative direction constructs an explicit bijective CA on a three-track alphabet whose forward rule is triangular along finite directed chains (enabled by the existence of infinite f.g. subgroups when G is not locally finite); the inverse is pointwise-defined but requires unbounded memory. The positive direction uses the uniform bound on chain lengths inside f.g. subgroups of locally finite groups to obtain a uniform finite radius for the inverse. No equations reduce to inputs by definition, no parameters are fitted and relabeled as predictions, no load-bearing self-citations appear, and the argument invokes only standard facts about groups and CA without circular reduction or ansatz smuggling.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The result is a pure mathematical characterization theorem with no fitted parameters or invented entities; it rests on standard definitions of groups, cellular automata, and local finiteness from the cited literature.

assumptions (1)

standard math Standard axioms and definitions of groups and cellular automata as in Ceccherini-Silberstein and Coornaert
The paper builds directly on the definitions and open problem stated in the referenced book.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Reversibility Characterization of Locally Finite Groups by Cellular Automata." pith.science (2026). https://pith.science/paper/OMFJYI5T

@misc{pith2026260629958,
  author       = {Pith},
  title        = {Pith review of: A Reversibility Characterization of Locally Finite Groups by Cellular Automata},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OMFJYI5T}},
  note         = {Machine review of arXiv:2606.29958}
}

abstract

For cellular automata over finite alphabets, bijectivity already implies reversibility. Over infinite alphabets this implication may fail, and the remaining obstruction in the periodic case was recorded by Ceccherini-Silberstein and Coornaert as Open Problem 2 in \emph{Cellular Automata and Groups}. We prove an exact group-theoretic characterization. A group $G$ is locally finite if and only if, over every alphabet, every bijective cellular automaton $A^G\to A^G$ is reversible. Equivalently, if $G$ is not locally finite, then for every infinite alphabet $A$ there exists a bijective cellular automaton $A^G\to A^G$ whose inverse is not a cellular automaton. The counterexample is already obtained on a countable alphabet. Its local rule has a rank track, a direction track and a binary data track; the forward map is triangular along finite directed chains of arbitrary length, so its inverse is defined pointwise but has no uniform finite memory. As a consequence, Open Problem 2 has an affirmative answer, and the periodicity hypothesis is unnecessary for the negative direction.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 4 canonical work pages

[1]

On a characterization of locally finite groups in terms of linear cellular automata

T. Ceccherini-Silberstein and M. Coornaert,On a characterization of locally finite groups in terms of linear cellular automata, J. Cell. Autom.6(2011), no. 2–3, 207–213; arXiv:0906.4891

work page Pith review arXiv 2011
[2]

Ceccherini-Silberstein and M

T. Ceccherini-Silberstein and M. Coornaert,On the reversibility and the closed image property of linear cellular automata, Theoret. Comput. Sci.412(2011), no. 4–5, 300–306; doi:10.1016/j.tcs.2010.09.020

work page doi:10.1016/j.tcs.2010.09.020 2011
[3]

13992, pp

T. Ceccherini-Silberstein and M. Coornaert,Cellular Automata and Groups, 2nd ed., Springer Monographs in Mathematics, Springer, Cham, 2024; doi:10.1007/978-3-031- 43328-3

work page doi:10.1007/978-3-031- 2024
[4]

T. G. Ceccherini-Silberstein, A. Machì and F. Scarabotti,Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble)49(1999), no. 2, 673–685; doi:10.5802/aif.1686

work page doi:10.5802/aif.1686 1999
[5]

R. I. Grigorchuk,On Burnside’s problem on periodic groups, Funct. Anal. Appl.14 (1980), no. 1, 41–43

1980
[6]

G. A. Hedlund,Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory3(1969), 320–375. School of Mathematical Sciences, Guangxi Minzu University, Nanning, China Email address:yangjiangdy@126.com

1969

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.

[1] [1]

On a characterization of locally finite groups in terms of linear cellular automata

T. Ceccherini-Silberstein and M. Coornaert,On a characterization of locally finite groups in terms of linear cellular automata, J. Cell. Autom.6(2011), no. 2–3, 207–213; arXiv:0906.4891

work page Pith review arXiv 2011

[2] [2]

Ceccherini-Silberstein and M

T. Ceccherini-Silberstein and M. Coornaert,On the reversibility and the closed image property of linear cellular automata, Theoret. Comput. Sci.412(2011), no. 4–5, 300–306; doi:10.1016/j.tcs.2010.09.020

work page doi:10.1016/j.tcs.2010.09.020 2011

[3] [3]

13992, pp

T. Ceccherini-Silberstein and M. Coornaert,Cellular Automata and Groups, 2nd ed., Springer Monographs in Mathematics, Springer, Cham, 2024; doi:10.1007/978-3-031- 43328-3

work page doi:10.1007/978-3-031- 2024

[4] [4]

T. G. Ceccherini-Silberstein, A. Machì and F. Scarabotti,Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble)49(1999), no. 2, 673–685; doi:10.5802/aif.1686

work page doi:10.5802/aif.1686 1999

[5] [5]

R. I. Grigorchuk,On Burnside’s problem on periodic groups, Funct. Anal. Appl.14 (1980), no. 1, 41–43

1980

[6] [6]

G. A. Hedlund,Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory3(1969), 320–375. School of Mathematical Sciences, Guangxi Minzu University, Nanning, China Email address:yangjiangdy@126.com

1969