[LLM Generated]
Open problems in group theory, as statements about finite automata
Open problems in group theory, as statements about finite automata
Claude Opus 5
Abstract.
This notebook is the runnable half of the catalog in the paclet repository: nineteen problems in group theory, each paired with the statement about a finite Mealy automaton that would settle it, and each with the paclet call that searches for or checks a witness. In the Definitions section we fix the level quotient, the ball, the nucleus and the group ring over a level quotient, and we state the vocabulary that grades how faithful a translation is — equivalent, sufficient, necessary, heuristic, or none. In the Recipes section we run one test per problem, grouped as the catalog groups them: group rings, torsion and growth, amenability and L² invariants, decision problems. Four problems have no recipe and the section says which and why, because a catalog that quietly omitted them would read as wider than it is. In the Conjectures section we state what the computations support: that the Aleshin automaton sits inside the swept three-state binary space with free-group ball counts, that contraction shows in the nucleus counts as a decrease rather than as a plateau, and that period is independent of the initial condition for exactly fifty-six of the sixty-four invertible rules on two states and two colors. In the Questions section we record what the recipes cannot reach, most of it traceable to one missing function: a word-problem test.
OpenProblems.md
1
.Setup
Setup
PacletInstall["https://www.wolframcloud.com/obj/hajek_pavel/IteratedFiniteAutomaton.paclet",ForceVersionInstall->True];Needs["WolframInstitute`IteratedFiniteAutomaton`"];
SeedRandom[1];
Row[{"IteratedFiniteAutomaton ",PacletObject["WolframInstitute/IteratedFiniteAutomaton"]["Version"]," — built ",DateString["ISODate"]}]
IteratedFiniteAutomaton 0.2.0 — built 2026-07-28
Five automata run through the whole notebook. The adding machine and the lamplighter are the two-state binary pair; the Grigorchuk automaton is the torsion witness; canonical code 5125 is the Aleshin automaton, and canonical code 7964 is one of the two Basilica codes. The first three are built from their wreath recursions so the notebook does not depend on the numbering; the last two are given by code, since locating them by code inside the swept space is itself one of the results.
adding=IteratedFiniteAutomatonFromWreath[<|"a"->{{1,0},{"id","a"}},"id"->{{0,1},{"id","id"}}|>,"a"]["Rule"];lamplighter=IteratedFiniteAutomatonFromWreath[<|"a"->{{1,0},{"b","a"}},"b"->{{0,1},{"b","a"}}|>,"a"]["Rule"];grigorchuk=IteratedFiniteAutomatonFromWreath[<|"a"->{{1,0},{"e","e"}},"e"->{{0,1},{"e","e"}},"b"->{{0,1},{"a","c"}},"c"->{{0,1},{"a","d"}},"d"->{{0,1},{"e","b"}}|>,"a"]["Rule"];aleshin={5125,{3,2}};basilica={7964,{3,2}};
Grid[{{"adding",AutomatonCodeFromRule[adding],AutomatonWreathRecursion[adding,Method->"String"]},{"lamplighter",AutomatonCodeFromRule[lamplighter],AutomatonWreathRecursion[lamplighter,Method->"String"]},{"Aleshin",aleshin,AutomatonWreathRecursion[aleshin,Method->"String"]},{"Basilica",basilica,AutomatonWreathRecursion[basilica,Method->"String"]}},Frame->All,Alignment->Left,Background->{None,{{None,RGBColor[0.95,0.97,1]}}}]
adding | {62,{2,2}} | {a = σ(b, a),b = (b, b)} |
lamplighter | {54,{2,2}} | {a = σ(b, a),b = (b, a)} |
Aleshin | {5125,{3,2}} | {a = σ(b, a),b = (c, c),c = σ(a, b)} |
Basilica | {7964,{3,2}} | {a = (a, a),b = σ(c, a),c = (b, a)} |
Two helpers the recipes need and the paclet does not export. restores the fixed points that drops, without which every cycle-type computation in the notebook is wrong. is the number of elements of the ball of radius n in the free group on s generators.
padCycleType
PermutationCycles
freeCount
padCycleType[perm_]:=Sort@Join[Length/@First[PermutationCycles[perm]],ConstantArray[1,Count[Range[Length[perm]],v_/;perm[[v]]===v]]];
freeCount[s_,n_]:=1+Sum[2s(2s-1)^(j-1),{j,n}];
2
.Functions
Functions
The symbols the recipes use, grouped by the role they play in the catalog.
Presentations and enumeration
◼
AutomatonRuleFromCode
AutomatonCodeFromRule
◼
CanonicalAutomatonCode
◼
BGKMNSSNumber
◼
InvertibleAutomatonCodes
InvertibleAutomatonQ
◼
AutomatonWreathRecursion
Action on the tree
◼
AutomatonLevelPermutations
◼
AutomatonWordPermutation
◼
AutomatonWordOrders
◼
AutomatonWordBall
AutomatonGroupBall
AutomatonElementCount
Invariants and predicates
◼
AutomatonAbelianQ
◼
AutomatonTorsionFreeCandidateQ
◼
AutomatonGroupFingerprint
◼
AutomatonNucleus
◼
AutomatonSection
AutomatonSectionTable
AutomatonWordSection
The group ring
◼
GroupRingLevelProduct
◼
GroupRingLeftAnnihilator
◼
GroupRingZeroDivisorSurvival
GroupRingIdempotentSurvival
◼
GroupRingIdempotentSearch
GroupRingIdempotentQ
◼
MaxTerms
Infinity
3
.Definitions
Definitions
Definition
3
.1
.An automaton here is a finite invertible Mealy automaton on s states over the alphabet X = {0, …, k−1}, given either as a rule list {state, input} → {nextState, output} or as a numeric code together with the pair {s, k}. Its states act on the rooted k-ary tree T by tree automorphisms, and the group G they generate is an automaton group.
Definition
3
.2
.The level-L quotient G_L is the image of G in its action on the k^L vertices at depth L. Every G_L is finite, G_{L+1} surjects onto G_L, and the actions are faithful in the limit, so G is residually finite and an equality in G holds if and only if it holds in every G_L. This is the fact every recipe in the notebook rests on, and every limitation of every recipe comes from testing finitely many L.
Definition
3
.3
.The ball of radius r is the set of elements of G represented by a word of length at most r in the generators and their inverses. gives the reduced words, gives one shortest word per distinct element of a chosen level quotient, and gives the count. A ball computed at level L is a ball in G_L, and it is a ball in G only once L is deep enough to separate its elements.
AutomatonWordBall
AutomatonGroupBall
AutomatonElementCount
Definition
3
.4
.The section of an element g at a vertex v is the automorphism g|_v of the subtree at v induced by g. The automaton is contracting if there is a finite set N, the nucleus, such that the sections of every element at all sufficiently deep vertices lie in N. returns the depth-d sections of a ball for each d up to a chosen depth, kept distinct as automorphisms of a reference level.
AutomatonNucleus
Definition
3
.5
.The activity of g at depth d is the number of level-d vertices at which the section of g is nontrivial. Bounded activity means this count is bounded in d; the activity degree is the polynomial degree of its growth.
Definition
3
.6
.An element of the group ring is a list of {coefficient, word} pairs, so the empty list is 0 and {{1, {}}} is 1. computes over the field with p elements and over the integers. A product is computed in a level quotient by , whose result is empty exactly when the product vanishes there.
Modulus -> p
Modulus -> 0
GroupRingLevelProduct
Definition
3
.7
.A translation of a group problem into an automaton statement is graded by how much a witness on the automaton side would prove. It is equivalent when the two statements imply each other; sufficient when a witness settles the group problem but its absence proves nothing; necessary when it is implied by the group statement, so it is usable as a filter and nothing more; heuristic when no theorem connects the two sides; and none when no translation is known. The catalog carries this grade in a field, so a translation that is only an analogy cannot be buried in prose.
Remark
3
.8
.Four of the nineteen problems have no test recipe, for four different reasons, and the distinction matters more than the count. Zassenhaus is structurally empty — it is about integral group rings of finite groups, and the automaton encoding of a finite group is its multiplication table. Bounded-exponent Burnside is impossible — residual finiteness plus Zel'manov's restricted Burnside theorem forbid an infinite automaton group of finite exponent, so a witness cannot exist at any size. Activity growth is unimplemented — the paclet has no activity function, only a lower bound assembled from . The unit conjecture has a check but no search — the tower filter is built on nullspaces and the unit condition is an inhomogeneous solve.
AutomatonSection
4
.The catalog at a glance
The catalog at a glance
The nineteen entries, with the grade of their translation and whether a recipe exists.
catalog={{"Kaplansky zero-divisor","group rings","equivalent","search"},{"Kaplansky idempotent","group rings","equivalent","search"},{"Kaplansky unit","group rings","sufficient","check only"},{"Zassenhaus","group rings","none","none"},{"Burnside, infinite torsion","torsion and growth","equivalent","filter"},{"Burnside, bounded exponent","torsion and growth","none","none"},{"Milnor growth","torsion and growth","heuristic","search"},{"gap conjecture","torsion and growth","sufficient","filter"},{"von Neumann-Day","amenability","sufficient","filter"},{"Day, elementary amenability","amenability","sufficient","filter"},{"amenability by activity","amenability","sufficient","none"},{"amenability of an automaton","amenability","equivalent","filter"},{"Atiyah","amenability","sufficient","search"},{"finiteness","decision problems","equivalent","filter"},{"order","decision problems","equivalent","filter"},{"conjugacy","decision problems","necessary","filter"},{"freeness","decision problems","equivalent","filter"},{"triviality","decision problems","equivalent","search"},{"periodicity","decision problems","equivalent","search"}};Length[catalog]
19
BarChart[Values[Counts[catalog[[All,4]]]],ChartLabels->Keys[Counts[catalog[[All,4]]]],ChartStyle->"Pastel",AxesLabel->{None,"entries"},PlotLabel->"what the paclet can do per problem"]
Definition
5
.1
.A zero divisor supported on the radius-r ball is a pair of nonzero coefficient vectors c, d over that ball with the corresponding product vanishing in every level quotient. The kernels nest along the tower, so one empty level refutes that radius, field and weight bound outright.
The positive control is the lamplighter padded with a trivial third state, canonical code 4210, which has torsion and therefore must produce a survivor.
The idempotent search is the same filter with the second factor forced, so it is strictly weaker: an empty zero-divisor pass over the same ball already implies an empty idempotent pass over it.
The torsion filter, and the two sides it fails on. Orders are nondecreasing in the level and constant from some level on exactly when the word has finite order, so growth is evidence of infinite order and a plateau is evidence of finite order — and neither is a proof.
Remark
6
.1
.No recipe here decides a growth type. Separating a stretched exponential from a polynomial needs radius in the hundreds, against the radius 4 these counts reach, which is why the Milnor entry's translation is graded heuristic rather than equivalent.
Contraction is the one computable ingredient of the only general amenability criterion, because bounded activity implies contraction, so a non-contracting automaton is provably not bounded. The reading is not the obvious one: contraction shows as the depth counts decreasing to a limit that does not grow with the radius, not as the list holding still.
Activity has no function, but a lower bound does run: count the depth-d sections that act nontrivially at a reference level. On the lamplighter it returns 2^d, so the automaton is nowhere near bounded — the correct answer, reached without a word-problem test, because a lower bound only needs the sections it can prove nontrivial.
The Atiyah entry is the only one whose quantity the paclet can approximate, by Lück's theorem: the level stabilisers are a nested tower of finite-index normal subgroups intersecting trivially, so the L² dimension of a kernel is the limit of the finite-quotient ranks divided by the quotient orders. One level of that limit is a left annihilator.
Finiteness, in the shape that shows why it is a filter and never a certificate. The adding machine generates the integers, and its ball count at a fixed word length saturates as the level grows — because the word length caps it, not because the group is finite.
Conjugacy, the catalog's one necessary condition: conjugate elements have equal cycle type on every level, so unequal types at one level is a proof of non-conjugacy and equal types at every level tested proves nothing.
Freeness, by comparing the ball counts against the free group. A count below the free value is a relation, once the level is deep enough that the collision is not an artifact of the quotient.
Triviality, the one problem whose recipe is complete for the group: an automaton generates the trivial group exactly when no state permutes its colors, and across the two-state binary space that count is sixteen.
Periodicity, the only recipe that decides its question outright at each level. The one-pass map on tapes of length L is the level-L permutation of the marked state, so the period from a tape is a cycle length, and the period is independent of the initial condition exactly when all cycle lengths agree.
Conjecture
9
.1
.The Aleshin automaton is canonical code 5125 of the three-state binary space, and its ball counts in the level-8 quotient agree with those of the free group on three generators for every radius up to 3. Status: verified for radii 1, 2, 3 at level 8, where the same counts at level 6 are short by 3 percent at radius 3.
The level-8 counts match the free-group counts exactly; the level-6 counts do not, and the discrepancy is a quotient artifact rather than a relation.
The flat list belongs to the automaton that generates a free group, which is the most emphatically non-contracting automaton in the space, so a plateau cannot be read as contraction.
Conjecture
9
.3
.Of the 64 invertible rules on two states and two colors, exactly 56 have period independent of the initial condition at every level, and the 8 that do not all fail already at level 2. Status: verified for levels 2 through 8.
The census, and the failures collected. Every failure has an inactive marked state, which 32 of the 64 rules have, so that condition is necessary and far from sufficient.
Question
9
.4
.Two of the four relabelling classes among those 8 failures are the lamplighter automaton pointed at its inactive generator, which is also the automaton behind the counterexample to the Atiyah conjecture. The two properties have no known connection. Is the coincidence structural, or an artifact of the two-state binary space being small enough that everything meets everything?
11
.Literature
Literature