[LLM Generated]

The Grigorchuk group and the Burnside problem

Claude Opus 5
Abstract.
Burnside asked in 1902 whether an infinite finitely generated group can have every element of finite order, and the Grigorchuk group answers it with a 5-state automaton over two letters. In the Definitions section we define torsion, exponent, p-groups and the growth function, and separate the general Burnside problem from the bounded one. In the Classification section we give the implication lattice among finite, bounded exponent, p-group and torsion, and show by exhaustive computation over the short words that the Grigorchuk group is a 2-group whose exponent is not bounded, so it settles the general problem and not the bounded one. In the Conjectures section we state that every element order is a power of two, record the classical orders of the two-generator products, and ask how the least word length attaining order 2 to the k grows with k. In the Demonstrations section we exhibit each function on the Grigorchuk automaton, with the adding machine as the infinite-order contrast.
1
.

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 automaton, from its wreath recursion. The initial state is a, so the state indices are a, b, c, d, id in that order.
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"];​​stateOf=grigorchukWreath["StateIndex"];
The adding machine, the infinite-order contrast: it is torsion-free where the Grigorchuk generators are involutions.
addingWreath=IteratedFiniteAutomatonFromWreath[<|​​"a"->{{1,0},{"id","a"}},​​"id"->{{0,1},{"id","id"}}|>,"a"];​​adding=addingWreath["Rule"];
2
.

Functions

The symbols this notebook uses, grouped by role.
Constructions
◼
  • IteratedFiniteAutomatonFromWreath
    — wreath recursion to rule list
    • ◼
  • IteratedFiniteAutomatonFromStates
    — Mealy transducer to rule list
    • Operations
    ◼
  • IteratedFiniteAutomaton
    — evolve a rule list or numeric code for t steps
    • ◼
  • IteratedFiniteAutomatonEvolve
    — evolve a converted automaton
    • ◼
  • IteratedFiniteAutomatonPeriodicStop
    — evolve until a row repeats
    • ◼
  • AutomatonLevelPermutations
    — each state as a permutation of the vertices at one level
    • ◼
  • AutomatonWordPermutation
    — the permutation of a word in the generators and their inverses
    • Invariants and predicates
    ◼
  • AutomatonWordOrders
    — order of a word in the level quotients, one level at a time
    • ◼
  • AutomatonElementCount
    — distinct elements among the words up to a given length
    • ◼
  • PermutationOrder
    — order of a permutation given in image form
    • Visualisation
    ◼
  • IteratedFiniteAutomatonStateGraph
    — the transition diagram
    • ◼
  • IteratedFiniteAutomatonColors
    — colour rules for k symbols
    • 3
    .

    Definitions

    Definition
    3
    .
    1
    .
    A group G is torsion, or periodic, if every element has finite order. It has bounded exponent n if g to the n is the identity for every g in G, and then n is an exponent for G. For a prime p, G is a p-group if the order of every element is a power of p.
    Definition
    3
    .
    2
    .
    The general Burnside problem asks whether there is an infinite finitely generated torsion group. The bounded Burnside problem asks whether there is an infinite finitely generated group of bounded exponent. The restricted problem asks whether, for fixed generator count and exponent, there are finitely many finite such groups.
    Definition
    3
    .
    3
    .
    For a finite generating set S of G, the growth function counts the elements expressible as a word of length at most n in S and its inverses. The growth is exponential if that count grows like c to the n for some c greater than 1, polynomial if it is bounded by a polynomial, and intermediate otherwise.
    Definition
    3
    .
    4
    .
    The Grigorchuk group is the group generated by the four states a, b, c, d of the automaton above, acting on the rooted binary tree, with the wreath recursion a = σ, b = (a, c), c = (a, d), d = (1, b), where σ transposes the two letters.
    Remark
    3
    .
    5
    .
    The order of a word computed at level L is a lower bound for its order in the group, and it is nondecreasing in L. A value repeated at two levels is therefore evidence and not proof, since the order can plateau and then resume — the lamplighter automaton does exactly that. Every order stated below is the level-L value at the deepest level computed.
    4
    .

    Classification

    The four conditions relate as follows, and no arrow reverses:
    finite⟹boundedexponent⟹torsion⟸p-group
    Observation
    4
    .
    1
    .
    Every generator of the Grigorchuk group is an involution, and the identity state has order 1.
    Association@Table[st->First[AutomatonWordOrders[grigorchuk,{stateOf[st]},{9}]],​​{st,{"a","b","c","d","id"}}]
    a2,b2,c2,d2,id1
    Observation
    4
    .
    2
    .
    The orders of the three products of two distinct nontrivial generators with a are 16, 8 and 4, the classical values. Each stabilises at a different level, which is why a single level is not enough to read an order.
    productOrders=Association@Table[​​st->AutomatonWordOrders[grigorchuk,{stateOf["a"],stateOf[st]},Range[9]],{st,{"b","c","d"}}];
    ListStepPlot[Values[productOrders],DataRange->{1,9},​​PlotLegends->{"a b","a c","a d"},AxesLabel->{"level","order"},​​ScalingFunctions->"Log2",Mesh->All,PlotLabel->"level orders stabilise at 16, 8 and 4"]
    a b
    a c
    a d
    Observation
    4
    .
    3
    .
    The Grigorchuk group is a 2-group whose exponent is not bounded. Over all words of length at most 6 in the four generators, computed at level 12, the orders realised are exactly 1, 2, 4, 8 and 16, so no short word exceeds 16; longer words do exceed it, so no single n is an exponent. The group therefore settles the general Burnside problem, while the bounded problem was settled by Novikov and Adyan for odd exponent at least 4381 [NovikovAdyan1968a], the bound later brought down to 665 by Adyan [Adyan1979].
    shortWordOrders=With[{perms=AutomatonLevelPermutations[grigorchuk,12]},​​Association@Table[​​n->KeySort@Counts[Table[PermutationOrder[AutomatonWordPermutation[perms,w]],{w,Tuples[Range[4],n]}]],​​{n,1,6}]];
    ArrayPlot[​​Table[Lookup[shortWordOrders[n],2^k,0],{n,1,6},{k,0,6}],​​ColorFunction->"Pastel",ColorFunctionScaling->True,Mesh->True,​​FrameTicks->{Transpose[{Range[6],Range[6]}],Transpose[{Range[7],2^Range[0,6]}]},​​FrameLabel->{"order","word length"},​​PlotLegends->Automatic,PlotLabel->"words of each length by order, exhaustive, level 12"]
    The last two columns are empty: order 32 and order 64 are not attained by any word of length at most 6.
    5
    .

    Conjectures

    Conjecture
    5
    .
    1
    .
    Every element of the Grigorchuk group has order a power of 2. Status: verified exhaustively for all words of length at most 6 at level 12, where the orders realised are exactly 1, 2, 4, 8 and 16, and on 200 random words of length 6 at level 9.
    5
    .
    1
    .

    Example

    Random words of six generators, at level 9, land only on powers of two.
    randomOrders=With[{perms=AutomatonLevelPermutations[grigorchuk,9]},​​Table[PermutationOrder[AutomatonWordPermutation[perms,RandomInteger[{1,4},6]]],{200}]];
    BarChart[KeySort@Counts[randomOrders],ChartLabels->Automatic,ChartStyle->"Pastel",​​AxesLabel->{"order","words"},PlotLabel->"orders of 200 random words of length 6, level 9"]
    Question
    5
    .
    2
    .
    Let m(k) be the least length of a word in a, b, c, d whose order is 2 to the k. Exhaustive computation gives m(1) = 1 and m(2) = m(3) = m(4) = 2, and shows that order 32 is attained by no word of length at most 6, so m(5) is at least 7. Random sampling finds order 32 at length 32 and not below. How does m(k) grow with k?
    The largest order found among 200 random words per length, at three levels. Orders above 16 need long words, and the level must be deep enough for the order to be visible: order 32 appears at length 32 from level 10, and at length 16 only by level 14.
    Conjecture
    5
    .
    3
    .
    The growth of the Grigorchuk group is sub-exponential: the number of distinct elements among words of length at most n grows more slowly than the free-group count 1 + 8 times the sum of 7 to the i−1. Status: verified for n at most 6 in the level-9 quotient, where the counts are 5, 11, 23, 40, 68, 108 against 9, 65, 457, 3201, 22409, 156865.
    The ball sizes in the level-9 quotient, which are lower bounds for the ball sizes in the group, against the free-group growth on the same generating set.
    6
    .

    IteratedFiniteAutomatonFromWreath

    The wreath recursion as input; the result carries the rule list, the initial state and the state indexing.
    7
    .

    IteratedFiniteAutomatonFromStates

    The same automaton as a Mealy transducer. The two presentations agree as rule lists up to order.
    8
    .

    IteratedFiniteAutomatonEvolve

    Evolution of a converted automaton, which reads its initial state from the conversion.
    The initial state of the conversion is a, which is an involution, so the evolution alternates between two tapes: the period-2 stripe pattern is the torsion of a made visible.
    Torsion is visible in the evolution: each Grigorchuk generator closes its orbit in at most two steps, while the adding machine takes the full 2 to the L.
    10
    .

    AutomatonWordOrders

    The order of a word in each level quotient in turn.
    11
    .

    AutomatonElementCount

    Distinct elements among the words up to a given length, counted in a level quotient.
    The transducer, with the identity state as the sink.
    14
    .

    Literature