[LLM Generated]
Zero divisors in the group ring of an automaton group
Zero divisors in the group ring of an automaton group
Claude Opus 5
Abstract.
Kaplansky asked whether the group ring of a torsion-free group can have a zero divisor, and an automaton group is a machine-sized place to ask it. In the Definitions section we define the group ring, its zero divisors and idempotents, the level quotients of an automaton group, and the radius-r candidate that the search enumerates. In the Classification section we give the implication lattice between orderability, unique product, absence of zero divisors and torsion-freeness, and we stratify the 64 invertible automata on 2 states and 2 letters by exhaustive computation: 16 generate the trivial group, 8 are torsion-free candidates, and the remaining 40 carry a surviving pair. We also show that the level-order filter rejects the lamplighter automaton on a word of infinite order, so a rejection is evidence of torsion and not proof of it. In the Conjectures section we state Kaplansky's conjecture, the observation that the level at which a group is refuted does not depend on the field, and the observation that it does not depend on the weight bound either, each with the computed evidence. In the Demonstrations section we exhibit each group-ring function on the Grigorchuk group, which has a zero divisor, against the adding machine and the Basilica group, which are refuted.
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 Grigorchuk group, a torsion group, is the positive control: it has a zero divisor and the search must find one.
grigorchukWreath=IteratedFiniteAutomatonFromWreath[<|"a"->{{1,0},{"id","id"}},"b"->{{0,1},{"a","c"}},"c"->{{0,1},{"a","d"}},"d"->{{0,1},{"id","b"}},"id"->{{0,1},{"id","id"}}|>,"a"];grigorchuk=grigorchukWreath["Rule"];
The adding machine generates a copy of the integers, where Kaplansky's conjecture is a theorem, and the lamplighter automaton has generators of infinite order in a group with torsion.
addingWreath=IteratedFiniteAutomatonFromWreath[<|"a"->{{1,0},{"id","a"}},"id"->{{0,1},{"id","id"}}|>,"a"];adding=addingWreath["Rule"];lamplighter=AutomatonRuleFromCode[{156,{2,2}}];
Three groups from the space of 3-state binary automata, in the numbering of Bondarenko and coauthors [BGKMNSS2008]. The Baumslag–Solitar group BS(1, 3) is bi-orderable and the Klein bottle group is left-orderable, so both satisfy the conjecture by a theorem; the Basilica group is torsion-free, amenable and not elementary amenable, and no general theorem covers it.
basilica=AutomatonRuleFromCode[{7964,{3,2}}];baumslagSolitar=AutomatonRuleFromCode[{23120,{3,2}}];kleinBottle=AutomatonRuleFromCode[{4621,{3,2}}];
Row[Labeled@@@{{IteratedFiniteAutomatonStateGraph[basilica],"Basilica"},{IteratedFiniteAutomatonStateGraph[baumslagSolitar],"BS(1, 3)"},{IteratedFiniteAutomatonStateGraph[kleinBottle],"Klein bottle"}}]
Basilica |
BS(1, 3) |
Klein bottle |
2
.Functions
Functions
The symbols this notebook uses, grouped by role.
Constructions
◼
IteratedFiniteAutomatonFromWreath
◼
AutomatonRuleFromCode
◼
AutomatonCodeFromRule
◼
InvertibleAutomatonCodes
◼
CanonicalAutomatonCode
Operations
◼
AutomatonLevelPermutations
◼
AutomatonWordPermutation
◼
GroupRingLevelProduct
Invariants and predicates
◼
AutomatonWordOrders
◼
AutomatonElementCount
◼
AutomatonWordBall
◼
AutomatonGroupBall
◼
AutomatonTorsionFreeCandidateQ
◼
GroupRingIdempotentQ
Visualisation
◼
IteratedFiniteAutomatonStateGraph
Searches
◼
GroupRingIdempotentSearch
◼
GroupRingIdempotentSurvival
◼
GroupRingLeftAnnihilator
◼
GroupRingZeroDivisorSurvival
◼
MaxTerms
3
.Definitions
Definitions
Definition
3
.1
.Let k be a commutative ring and G a group. The group ring k[G] is the set of finitely supported functions from G to k, written A = Σ A(g) g, with pointwise addition and the product (A B)(h) = Σ A(g) B(g⁻¹ h). The support of A is the finite set of g with A(g) ≠ 0.
Definition
3
.2
.A nonzero A in k[G] is a zero divisor if there is a nonzero B in k[G] with A B = 0. An element A is idempotent if A (A − 1) = 0, and nontrivial if A ≠ 0 and A ≠ 1. A nontrivial idempotent is a zero divisor, since A and A − 1 are then both nonzero.
Definition
3
.3
.A group G has unique product if for all finite nonempty subsets S and T of G there is an element of S T with exactly one representation s t with s in S and t in T. A group is left-orderable if it carries a total order invariant under left multiplication, bi-orderable if the order is invariant on both sides, and locally indicable if every nontrivial finitely generated subgroup surjects onto the integers.
Definition
3
.4
.For an automaton on s states over k letters, the level-L quotient G_L is the image of G in the symmetric group of the k^L vertices at depth L. Restriction to depth L is a surjection G_(L+1) → G_L, and it extends to a surjection of group rings k[G_(L+1)] → k[G_L].
Definition
3
.5
.The radius-r support of an automaton is the set of distinct group elements represented by reduced words of length at most r in the states and their inverses, together with the identity. A radius-r candidate over the field with p elements is a nonzero coefficient vector on that support, taken up to scaling.
Remark
3
.6
.In the code an element of k[G] is a list of pairs, each a coefficient and a word, and a word is a list of signed state indices. So the empty list is 0 and the list holding the single pair {1, {}} is 1.
Remark
3
.7
.The level test is one-sided. If A B = 0 in k[G] then the relation pushes forward along every quotient map, so a level in which no nonzero B annihilates A refutes that support once and for all; the annihilators nest, so refutation at one level is refutation at every deeper one. Survival to any finite level is not a counterexample: the annihilators are subspaces of a fixed p-element vector space, so the decreasing chain must stabilise, and finitely many equal terms never show that it has.
4
.Classification
Classification
Two chains of implications relate the conditions, and no arrow in either reverses.
The first chain is standard and the second is Higman's theorem [Higman1940] together with the Burns–Hale criterion [BurnsHale1972]. The last arrow of the second chain is the only one whose converse is Kaplansky's conjecture; the converse of the first is false, since the Promislow group is torsion-free without unique product [Promislow1988].
Observation
4
.1
.Torsion gives a zero divisor with no search. If g has order n greater than 1 then (1 − g) (1 + g + ⋯ + g^(n−1)) = 1 − g^n = 0, and both factors are nonzero. In the Grigorchuk group the word a b has order 16, so the product of the two factors is empty exactly when the geometric series is truncated at 16 terms and at no smaller length.
Observation
4
.2
.Exhaustive over the 2-state binary automata: of the 256 rules, 64 are invertible, of those 16 generate the trivial group and 8 pass the level-order filter, and the 8 fall into 2 classes under relabelling of states and letters, both isomorphic to the integers.
Observation
4
.3
.Radius-1 search over the field with two elements refutes exactly the 24 automata that are trivial or torsion-free candidates, and the other 40 keep a surviving pair through level 8. So on this space the search separates the two strata with no error in either direction, which it is not guaranteed to do: a group with torsion whose torsion elements all lie outside the radius-1 ball would also be refuted.
Remark
4
.5
.The graded data and the boolean verdict do not interact. A search records a survivor count at each level and a level at which the count first reaches zero. The counts depend on the field, on the radius and on the weight bound; the level at which they reach zero, on the evidence below, depends on none of the three.
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. Status: open, and open even in the special case where B = A − 1 [Kaplansky1970]. Verified here at radius 1 for both torsion-free groups of the (2, 2) space over the field with two elements, and for the Basilica group, BS(1, 3) and the Klein bottle group over the fields with 2 and 3 elements, in the level quotients up to depth 9.
The survivor count at each level, for three torsion-free groups against the torsion Grigorchuk group. Each torsion-free trace ends at the level where it reaches zero, which is the level that refutes the group; the Grigorchuk trace is flat at 8 and never ends.
Conjecture
5
.2
.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 here for the Basilica group at radius 1 and weight at most 4 over the fields with 2, 3, 5, 7, 11 and 13 elements, where the survivor count at level 3 ranges from 30 to 10205 and every trace reaches zero at level 6; verified group by group on all 133 groups of the (3, 2) space and on two further spaces in the companion sweep notebook.
The two halves of the observation in one picture: reading down a column, the survivor counts grow by two orders of magnitude with the prime; reading across, the white cells all begin at level 6.
Conjecture
5
.3
.Fix an automaton, a radius and a field. The least level at which the survivor set is empty is the same for every weight bound. Status: verified here for the Basilica group at radius 1 over the field with 5 elements for weight bounds 2 through 7, where the radius-1 support has 5 elements, so the bound 5 and above is exhaustive; verified in the (2, 3) space in the companion sweep notebook, where an exhaustive radius-2 pass and two weight-bounded ones give the same level histogram.
The candidate set grows by a factor of 17 between the smallest bound and the exhaustive one, and the refutation level is 6 throughout.
Question
5
.4
.Both observations above say that a coarse feature of the search — the refutation level — is invariant under changes that move the search itself by orders of magnitude. Is the refutation level a function of the automaton alone, and if so which function? Two explanations are ruled out by the (3, 2) data in the companion sweep notebook: it is not the first level at which the products of the support span enough group elements to make full rank possible, and it is not determined by the survivor count at the first level.
The product of two elements inside one level quotient, where two words are the same group element exactly when they induce the same permutation of the vertices. The generator a of the Grigorchuk group is an involution, so 1 − a and 1 + a multiply to zero at every level, and this is a proof rather than evidence: the recursion a = σ(1, 1) gives a² = 1 outright.
The multiplication table of the radius-1 support at level 6, each cell coloured by which of the 11 distinct products it is.
Whether A (A − 1) vanishes in one level quotient. For an involution a the element c (1 + a) is idempotent exactly when 2 c² = c, that is when c is the inverse of 2, so there is one nontrivial solution for every odd prime and none in characteristic two.
Every idempotent of the level group ring supported on the radius ball, with coefficients drawn from a given list. Over the field with three elements at level 5 the Grigorchuk group has 16 of them on the radius-1 ball. The search returns one word per group element, and every Grigorchuk generator is its own inverse, so the representative words it keeps are the inverse letters and the first five columns are empty.
The same search filtered through a tower of levels. The Grigorchuk group keeps all 16 idempotents at every level, and the Basilica group loses both of its level-3 idempotents by level 4. The Grigorchuk group has no idempotent at all over the field with two elements, although it does have a zero divisor there: in characteristic two the square of a sum is the sum of squares, so the support of an idempotent is closed under squaring, which no nontrivial element of finite odd order and no involution can achieve.
The coefficient vectors B with A B = 0 at every level in a list, as the nullspace of left multiplication by A. Writing that matrix out is the whole of the inner test: its columns are the products of A with the support, and A is a zero divisor on that support exactly when the matrix drops rank.
The rank drop is one, and the kernel vector is 1 + a itself, so 1 + a is a square-zero divisor.
The search over every candidate on the radius ball, returning the survivors with a witness each. On the Grigorchuk group at radius 1 over the field with two elements there are 8 survivors, all of them genuine: the generators are involutions and satisfy b c = d, c d = b, b d = c, so each row below is an identity in the group and not only in the level quotients.
11
.1
.Method -> "Annihilator"
Method -> "Annihilator"
The default method filters level by level, using that the annihilators nest. The alternative stacks all the levels into one matrix and takes a single nullspace per candidate, which does not lean on the nesting argument and so is the reference the default is checked against. The two agree on the survivor set, and the traces differ only in that the reference reports one count at the deepest level.
11
.2
.MaxTerms -> 2
MaxTerms -> 2
The weight bound restricts the candidates to those with at most that many nonzero coefficients, which is what makes a radius-2 support tractable, and it is the setting the third conjecture above concerns. At radius 2 the Basilica support has 17 elements, so an exhaustive pass over the field with three elements would enumerate 64570081 coefficient vectors; weight 2 enumerates 289 and still refutes the group, at level 8 rather than the level 6 that radius 1 reaches.
12
.AutomatonTorsionFreeCandidateQ
AutomatonTorsionFreeCandidateQ
14
.Literature
Literature