[LLM Generated]
A sweep of the three-state binary automata for zero divisors
A sweep of the three-state binary automata for zero divisors
Claude Opus 5
Abstract.
We sweep the space of automata on three states over two letters for a counterexample to Kaplansky's zero-divisor conjecture, and report a negative result together with the certificate that makes it a proof rather than a failed search. In the Definitions section we define the space, the relabelling equivalence that reduces it, the funnel of filters that selects the candidate groups, the level tower that tests them, and the left-inverse certificate that witnesses one level's verdict. In the Classification section we run the funnel — 46656 rules, 5832 invertible, 1548 surviving the level-order filter at word length 2, 1524 at word length 3, and 133 distinct groups up to relabelling of states and letters — measure how the filter's two parameters move the count in opposite directions, stratify the 133 by ball growth into 36 abelian, 65 free-like and 32 remaining groups, and identify the 32 with 14 isomorphism classes of the classification of Bondarenko and coauthors, of which 3 classes and 10 codes are left-orderable and so already settled. In the Conjectures section we state Kaplansky's conjecture and prove, on all 133 groups and over the fields with 2, 3 and 5 elements, the case in which both factors are supported on the ball of radius 1, with refutation levels 3 to 7 against a ceiling of 12; we record that the level at which a group is refuted is the same for the primes 2, 3, 5, 7 and 11 and the same under the weight bound 4 as under no bound; and we ask which function of the automaton the level is, ruling out two candidate answers. In the Demonstrations section we exhibit the functions that enumerate and reduce a space, fingerprint a group, name it in the published classification, and compute its nucleus.
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-27
The escalation driver deepens the level tower until the survivor set is empty, and returns the level and the whole trace rather than a verdict. It belongs to the notebook rather than to the paclet, because the paclet's tests a fixed list of levels and escalation is a policy on top of it.
GroupRingZeroDivisorSurvival
escalate[automaton_,radius_,startLevel_,maxLevel_,modulus_,maxTerms_]:=Module[{survivors=None,level=startLevel-1},With[{trace=Reap[While[level<maxLevel&&survivors=!={},level++;survivors=GroupRingZeroDivisorSurvival[automaton,radius,Range[startLevel,level],Modulus->modulus,MaxTerms->maxTerms]["Survivors"];Sow[{level,Length[survivors]}]]][[2]]},<|"Refuted"->(survivors==={}),"Level"->level,"Trace"->First[trace,{}]|>]];
The certificate of one level's verdict. records the distinct values taken by the products of the support and which value each product is, is left multiplication in those coordinates, and returns the field-free row selection when the standard basis sits among the rows and an inverse of the first independent rows otherwise.
certificateTable
multiplicationMatrix
leftInverse
certificateTable[automaton_,radius_,level_]:=With[{perms=AutomatonLevelPermutations[automaton,level]},{support=Prepend[AutomatonGroupBall[automaton,radius,level],{}]},{elements=AutomatonWordPermutation[perms,#]&/@support},{products=Outer[#1[[#2]]&,elements,elements,1]},{point=Union@@products},<|"Vertices"->Length[First[perms]],"Support"->support,"Elements"->elements,"Point"->point,"Index"->Map[AssociationThread[point->Range[Length[point]]],products,{2}]|>];
multiplicationMatrix[index_,points_,coefficients_]:=Table[Total@Pick[coefficients,index[[All,j]],r],{r,points},{j,Length[index]}];rowSelection[rows_,m_]:=Normal@SparseArray[Thread[Transpose[{Range[Length[rows]],rows}]->1],{Length[rows],m}];leftInverse[matrix_,prime_]:=With[{n=Length[First[matrix]],m=Length[matrix]},{selection=Flatten[FirstPosition[matrix,UnitVector[n,#],{0}]&/@Range[n]]},If[FreeQ[selection,0],rowSelection[selection,m],With[{rows=Fold[If[MatrixRank[matrix[[Append[#1,#2]]],Modulus->prime]>Length[#1],Append[#1,#2],#1]&,{},Range[m]]},Mod[Inverse[matrix[[rows]],Modulus->prime].rowSelection[rows,m],prime]]]];
certificate[automaton_,radius_,level_,prime_]:=With[{table=certificateTable[automaton,radius,level]},{n=Length[table["Support"]],m=Length[table["Point"]]},{vectors=Rest@Tuples[Range[0,prime-1],n]},{matrices=multiplicationMatrix[table["Index"],m,#]&/@vectors},<|table,"Prime"->prime,"Vectors"->vectors,"Matrices"->matrices,"Ranks"->(MatrixRank[#,Modulus->prime]&/@matrices),"LeftInverses"->(leftInverse[#,prime]&/@matrices)|>];
The isomorphism classes and names of the classification of Bondarenko and coauthors [BGKMNSS2008], keyed by that paper's automaton number, together with the order type of the three classes it settles. and are read off the paper's tables; records that BS(1, 3) is bi-orderable and that BS(1, −3) and the Klein bottle group are left-orderable, so all three are locally indicable and their group rings are domains by Higman [Higman1940] and Burns–Hale [BurnsHale1972].
isoClass
groupName
orderType
isoClass=<|2855->849,3809->2199,893->741,3890->2212,4052->2239,1136->777,4133->2203,1217->741,1298->777,4070->2294,1397->849,2882->929,3845->929,929->929,3926->2212,1253->929,3854->2398,2891->2850,2738->2398,4106->2294,1433->849,1558->852,4717->2841,1720->852,1882->849,2044->849,1883->870,1919->870,3750->2294,996->870,2328->2294,870->870|>;
groupName=<|741->"contains Z, not free",777->"contains Brunner–Sidki–Vieira",849->"branch over G', free monoid",852->"Basilica, IMG(z² − 1)",870->"BS(1, 3)",929->"branch over G', free monoid",2199->"contains Z, not free",2203->"contains Z, not free",2212->"Klein bottle",2239->"contains Z, not free",2294->"BS(1, −3)",2398->"Dahmani, branch over G'",2841->"free monoid",2850->"branch over G', free monoid"|>;orderType=<|870->"bi-orderable",2294->"left-orderable",2212->"left-orderable"|>;
2
.Functions
Functions
The symbols this notebook uses, grouped by role.
Constructions
◼
AutomatonRuleFromCode
◼
InvertibleAutomatonCodes
◼
CanonicalAutomatonCode
Operations
◼
AutomatonLevelPermutations
◼
AutomatonWordPermutation
◼
AutomatonWreathRecursion
Invariants and predicates
◼
AutomatonGroupBall
◼
AutomatonAbelianQ
◼
AutomatonTorsionFreeCandidateQ
◼
AutomatonGroupFingerprint
◼
AutomatonNucleus
◼
BGKMNSSNumber
Visualisation
◼
IteratedFiniteAutomatonStateGraph
Searches
◼
GroupRingZeroDivisorSurvival
◼
MaxTerms
3
.Definitions
Definitions
Definition
3
.1
.An automaton on s states over k letters is a map from state–letter pairs to letter–state pairs, so there are (k s)^(s k) of them, and each is named by its code, the digits of the map read in a fixed order. The automaton is invertible if every state permutes the letters. An invertible automaton generates a group of automorphisms of the rooted k-ary tree, its automaton group, on the s states as generators.
Definition
3
.2
.Two automata are equivalent under relabelling if one is carried to the other by a permutation of the states together with a permutation of the letters. The canonical code of an automaton is the least code in its orbit, and equivalent automata generate the same group on relabelled generators.
Definition
3
.3
.The level-L quotient of an automaton group G is its image in the symmetric group of the k^L vertices at depth L, written G_L. Restriction to depth L is a surjection G_(L+1) → G_L, and it extends to a surjection of group rings.
Definition
3
.4
.The radius-r support of an automaton, at level L, is the set of distinct elements of G_L represented by reduced words of length at most r in the states and their inverses, together with the identity. A radius-r pair over the field with p elements is a pair of nonzero coefficient vectors c and d on that support, and it is a zero-divisor pair in G_L when the corresponding elements A and B satisfy A B = 0 there.
Definition
3
.5
.The multiplication matrix M_L(c) of a coefficient vector c has one row for each distinct value taken by the products of the support in G_L and one column for each support element, and its entry in row h and column j is the sum of the c_i over the i with s_i s_j = h. So A B = 0 in G_L holds exactly when M_L(c) d = 0, and the vector c is refuted at level L when M_L(c) has trivial kernel.
Definition
3
.6
.A certificate for the refutation of the support at level L over the field with p elements is a left inverse N(c), one for each nonzero c, with N(c) M_L(c) the identity. A certificate is a row selection when it picks n rows of M_L(c) that are already the standard basis, and then it is the same matrix in every characteristic.
Remark
3
.7
.Refutation is final, and this is what makes an empty level a proof rather than the end of a search. Two products of the support that are equal in G_(L+1) are equal in G_L, so each row of M_L(c) is a sum of rows of M_(L+1)(c) and the kernels nest, giving the first chain below. A relation A B = 0 in the group ring of G pushes forward along every quotient map, which gives the second. Neither step needs residual finiteness; that would be needed only for the converse, which the sweep never uses.
kerM(c)⊆kerM(c)
L+1
L
M(c)injective for every nonzero c⟹no radius-r zero-divisor pair in G
L
Remark
3
.8
.The support is read off the level quotient, so a proof at level L covers the ball as G_L sees it. This is a real gap only if the ball is still collapsing at that level, and it is not: on all 133 groups below the radius-1 support has the same size at the refuting level as at level 12.
4
.Classification
Classification
The funnel is four filters. Invertibility is a condition on the automaton; the level-order filter and the relabelling reduction are conditions on the group.
all rules⊇invertible⊇candidate at word length 2⊇candidate at word length 3↠distinct groups
invertible=InvertibleAutomatonCodes[{3,2}];growing=Select[invertible,AutomatonTorsionFreeCandidateQ[{#,{3,2}},2,{5,7}]&];strict=Select[growing,AutomatonTorsionFreeCandidateQ[{#,{3,2}},3,{6,8}]&];reps=First/@GatherBy[strict,CanonicalAutomatonCode[{#,{3,2}}]&];
BarChart[<|"all rules"->(3*2)^(3*2),"invertible"->Length[invertible],"length 2"->Length[growing],"length 3"->Length[strict],"groups"->Length[reps]|>,ChartLabels->Placed[Automatic,Below],LabelingFunction->Above,ChartStyle->"Pastel",ScalingFunctions->"Log",ImageSize->420,PlotLabel->"the (3, 2) funnel, exhaustive over the 46656 rules"]
Observation
4
.1
.The two parameters of the level-order filter move the accepted count in opposite directions, so neither can be raised to strengthen it. Comparing orders at two well-separated levels accepts more automata than comparing adjacent ones, because an order is likelier to repeat at neighbouring levels and a repeat is a rejection; testing longer words accepts fewer, because there are more words whose order can repeat. A rejection is evidence of torsion and not proof of it, so the sweep takes the larger candidate set at each choice and the two stages of the funnel above are an intersection, not a refinement.
The accepted count over the 5832 invertible automata, for three word lengths against two pairs of levels.
Observation
4
.2
.Ball growth splits the 133 groups into three strata. Thirty-six are abelian, hence free abelian of finite rank, and their balls reach at most 64 elements at word length 4. Sixty-five have a free submonoid on the generators and their balls reach at least 752, within a factor of 1.25 of the free value 937. The remaining 32 lie strictly between, from 41 to 481, and it is on those that the conjecture is not already a theorem for a structural reason.
Observation
4
.3
.The 32 remaining codes are 14 isomorphism classes in the classification of [BGKMNSS2008]. Three of the classes, comprising 10 of the codes, are locally indicable — BS(1, 3), BS(1, −3) and the Klein bottle group — so their group rings are domains and Kaplansky's conjecture is a theorem for them. Two classes contract, the Basilica group and the Klein bottle group, and contraction is read off the radius direction of the nucleus rather than the depth direction, since a finite ball's sections always stabilise in depth.
The names the classification gives them, with the codes of each class.
Observation
4
.4
.The nucleus is a property of the generating set, not of the group, so a classification that identifies two codes does not equate their nucleus profiles. The two codes of the Klein bottle group both contract, one to a nucleus of 7 sections and the other to 3.
Conjecture
5
.1
.For every torsion-free group G and every field k, if A and B in k[G] are both nonzero then A B ≠ 0 [Kaplansky1970]. Status: open in general. Proved below for every one of the 133 groups of the (3, 2) space, for A and B supported on the ball of radius 1, over the fields with 2, 3 and 5 elements.
Escalating the level tower to the first empty survivor set, exhaustively over the radius-1 support, whose 3, 5 or 7 elements admit at most 127 nonzero coefficient vectors over the field with two elements. Every group is refuted, the deepest at level 7 against a ceiling of 12, and the histogram is the same over all three fields.
Refutation over the three fields happens group by group at the same level, and the deepest is 7 against the ceiling of 12.
Observation
5
.2
.The refuting level is pinned by the size of the radius-1 support at the smallest value it takes, and not determined by it otherwise. Twenty-one of the 133 groups have a support of only 3 elements — the identity and one generator with its inverse, the other two generators acting trivially or equal to the first — and every one of them is abelian, so each is the group of integers and each is refuted at level 3, the first level at which the products can span 3 values. The 26 groups with support 5 and the 86 with support 7 spread over levels 4 to 7.
The support size against the refuting level. The row for support 3 is concentrated in one cell; the other two rows are not.
The support at the refuting level is the support at level 12, so no proof above rests on a ball that was still collapsing; and the 21 groups of the first row are abelian.
Conjecture
5
.3
.Fix an automaton, a radius and a weight bound. The least level at which the survivor set over the field with p elements is empty is the same for every prime p. Status: verified group by group on all 133 groups of the (3, 2) space at radius 1 and weight at most 4, for the primes 2, 3, 5, 7 and 11, where the candidate set on a support of 7 grows from 98 vectors to 38717; and, without a weight bound, for the primes 2, 3 and 5.
The refuting level of each of the 133 groups, one row per prime, the groups in the order the funnel produced them. The rows are equal, so the picture is five copies of one row.
The largest disagreement between two primes, on any of the 133 groups, is zero; the weight bound does not move the level either; and the candidate set the bound leaves on a support of 7 grows by a factor of 395 across the five primes.
Observation
5
.4
.The refutation is certified, not merely reported. For a group refuted at level L over the field with p elements, the certificate is one left inverse per nonzero coefficient vector on the support, and checking it is matrix arithmetic over a finite field: p^n − 1 products of an n by m matrix with an m by n one, plus n² comparisons of permutations of k^L vertices. Nothing else is needed — no search is replayed and no property of the group is assumed.
The full certificate for the automaton with code 4611, refuted at level 3 over the field with two elements. Its support is the identity, a generator and its inverse; the nine products take 5 values; the 7 nonzero coefficient vectors give 7 matrices, each of rank 3, and each with a left inverse. Four of the seven left inverses are row selections and so hold in every characteristic; the three that are not are exactly those in which the coefficient of the identity is nonzero and the weight is at least 2.
Observation
5
.5
.What bounds a machine-checked certificate is the coefficient vectors, not the sweep. The 21 groups refuted at level 3 need 7 vectors, a 5 by 3 matrix and 9 comparisons of permutations of 8 vertices. The 112 refuted at levels 4 to 7 need up to 127 vectors, a 37 by 7 matrix and 49 comparisons of permutations of up to 128 vertices, which is where a decision procedure in a proof assistant stops being cheap.
Each of the 133 groups placed by the vertices at its refuting level against the work of checking it, the product of the number of coefficient vectors and the entries of one multiplication matrix.
Question
5
.6
.The refuting level is unchanged by the field and by the weight bound, both of which move the size of the search by orders of magnitude. Is it a function of the automaton alone, and if so which? Two answers are ruled out by the data below. It is not the first level at which the products of the support span at least as many values as the support has elements: that level is 3 for all 133 groups, while the refuting level runs from 3 to 7. It is not determined by the survivor count at level 3 either: the counts range over 1 to 7 among the groups refuted at level 4 and over 9 to 15 among those refuted at level 7, which is a correlation and not a function.
Support size against the number of distinct products, both at level 3, for the 133 groups sorted by the latter. The products always outnumber the support, so level 3 is informative for every group.
The survivor count at level 3 against the refuting level. Every column but the first spans a range of counts, and the ranges overlap.
6
.InvertibleAutomatonCodes
InvertibleAutomatonCodes
The codes of the automata all of whose states permute the letters, which is the condition for the automaton to generate a group rather than a monoid. There are (k! s^k)^s of them, so 5832 of the 46656 rules on three states over two letters, and the count is exact rather than a bound.
The state graph of the first, the last, and the Basilica automaton.
7
.CanonicalAutomatonCode
CanonicalAutomatonCode
The least code in the orbit of the automaton under the s! k! relabellings of states and letters, which is the reduction that turns 1524 candidate automata into 133 groups. It is coarser than the equivalence of [BGKMNSS2008], which also minimises over inversion, so the 32 codes it leaves in the last stratum are only 14 groups.
The orbit sizes of the 133 representatives. An automaton with a symmetry has a short orbit, which is why the 1524 candidates give more than 1524 / 12 classes.
Commutativity together with the ball growth, as a key for comparing groups without deciding isomorphism. It separates the three strata of the sweep and it does not separate the groups within a stratum, since it is a property of the generating set.
Neither component of the fingerprint separates the strata alone, which is why it carries both. The ball at word length 4 runs from 9 to 64 over the abelian groups and from 41 to 937 over the others, so the two ranges overlap; the commutativity flag decides the overlap.
9
.BGKMNSSNumber
BGKMNSSNumber
The automaton's number in the classification of the 3-state binary automata [BGKMNSS2008], recovered from the wreath recursion by the paper's own formula, which is what lets the sweep name its groups instead of only counting them.
The two numberings of the 32 codes of the last stratum against each other, coloured by the isomorphism class. Neither order refines the other, so the paper's numbering has to be computed and cannot be guessed from ours.
10
.AutomatonNucleus
AutomatonNucleus
The set of sections that recur, computed on the ball of a given radius to a given depth. The group is contracting when the count stabilises as the radius grows, and the radius is the direction to read: the depth direction always stabilises, because a finite ball has finitely many sections.
The profiles of the 32, contracting ones apart. Two classes contract, the Basilica group and the Klein bottle group, and the Klein bottle group's two codes contract to nuclei of different sizes.
The candidates on the radius ball whose left annihilator on that ball is nonzero at every level tested, each with a witness. The survivor count is what escalation watches: a group is refuted at the first level where it is zero, and that is a proof, while a plateau is only a level at which nothing was found.
Traces of four groups of the last stratum against the Grigorchuk group, which has torsion and whose count is flat at 8 and never reaches zero.
13
.Literature
Literature