[LLM Generated]
Portraits, activity, and boundary permutations
Portraits, activity, and boundary permutations
Claude Opus 5
Abstract.
An element of an automaton group is an automorphism of the rooted k-ary tree, and it admits three pictures: the space-time diagram of its iteration on a tape, its portrait on the tree, and its permutation of the vertices at a fixed level. In the Definitions section we define the section of an element at a vertex, the active vertices, the activity at a level, the portrait, and the boundary permutation with its cycle type. In the Classification section we place the examples in Sidki's activity classes, give the implication lattice among bounded, polynomial and exponential activity, and show by census over the 3-state binary automata that the classes are separated. In the Conjectures section we state that the adding machine has one active vertex at every level and a single cycle on each level, that the Grigorchuk generators have activity at most one with a period-three pattern, and we record the cycle counts of the generator b as an open question. In the Demonstrations section we exhibit each visualisation function on the adding machine and the Grigorchuk automaton.
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 two running examples. returns an association whose key holds the rule list, and the group-layer functions take that rule list.
IteratedFiniteAutomatonFromWreath
"Rule"
adding={{1,0}->{2,1},{1,1}->{1,0},{2,0}->{2,0},{2,1}->{2,1}};
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 sections of a state at all vertices of one level, and the states that act nontrivially on their children. Both are written against a rule list directly, since the paclet's rule normaliser is not exported.
sections[rule_List,s0_Integer,level_Integer]:=With[{trans=Association[rule],k=Length[Union[rule[[All,1,2]]]]},Table[Fold[{state,x}|->First[trans[{state,x}]],s0,w],{w,Tuples[Range[0,k-1],level]}]];
activeStates[rule_List]:=With[{trans=Association[rule],k=Length[Union[rule[[All,1,2]]]]},Select[Union[rule[[All,1,1]]],st|->AnyTrue[Range[0,k-1],Last[trans[{st,#}]]=!=#&]]];
activity[rule_List,s0_Integer,level_Integer]:=Count[sections[rule,s0,level],Alternatives@@activeStates[rule]];
cycleType[rule_List,s0_Integer,level_Integer]:=Sort@Tally[Length/@First[PermutationCycles[AutomatonLevelPermutations[rule,level][s0]]]];
2
.Functions
Functions
The symbols this notebook uses, grouped by role.
Constructions
◼
IteratedFiniteAutomatonFromWreath
◼
IteratedFiniteAutomatonSample
◼
IteratedFiniteAutomatonInitialConditionSample
Operations
◼
IteratedFiniteAutomaton
◼
AutomatonLevelPermutations
Invariants and predicates
◼
AutomatonNucleus
◼
PermutationCycles
Visualisation
◼
AutomatonTreePortrait
◼
AutomatonBoundaryGraph
◼
IteratedFiniteAutomatonStateGraph
◼
IteratedFiniteAutomatonsByRule
◼
IteratedFiniteAutomatonsByInitialCondition
◼
IteratedFiniteAutomatonsMatrix
◼
IteratedFiniteAutomatonColors
3
.Definitions
Definitions
Definition
3
.1
.Let g be an automorphism of the rooted k-ary tree and w a vertex, that is a finite word over X = {0, …, k−1}. The section of g at w is the automorphism g|w of the tree induced by g on the subtree below w, defined by g(w u) = g(w) g|w(u) for every word u.
Definition
3
.2
.A vertex w is active for g if the section g|w permutes the children of w nontrivially, that is if the root permutation of g|w is not the identity. For a state of a Mealy automaton this is the condition that its output map is not the identity on X.
Definition
3
.3
.The activity of g at level L, written a(g, L), is the number of active vertices among the k to the L vertices of level L.
Definition
3
.4
.The portrait of g to depth L is the labelling of every vertex of depth at most L by its section, together with the set of active vertices. Two elements with the same portrait to depth L agree on level L.
Definition
3
.5
.The boundary permutation of g at level L is the permutation of the k to the L vertices of level L induced by g. Its cycle type is the multiset of cycle lengths, and its order is the level-L order of g.
Remark
3
.6
.The portrait and the boundary permutation are two readings of the same data: the portrait records the sections vertex by vertex, and the boundary permutation records only the resulting map on level L. The portrait therefore determines the boundary permutation, and not conversely.
4
.Classification
Classification
Sidki's classification is by the growth of the activity in L:
a(g,L)bounded⟹a(g,L)polynomial⟹a(g,L)exponential
Definition
4
.1
.The element g is finitary if a(g, L) = 0 for all large L, bounded if a(g, L) is bounded in L, of polynomial activity of degree d if a(g, L) grows like L to the d, and of exponential activity otherwise.
Observation
4
.2
.Finitary implies bounded, and bounded implies polynomial of degree 0. The generator a of the Grigorchuk automaton is finitary, since a is the root swap with trivial sections, so a(a, 0) = 1 and a(a, L) = 0 for L ≥ 1. The adding machine is bounded but not finitary, since exactly one vertex is active at every level.
Observation
4
.3
.The boundary permutation of the Grigorchuk generator a at level L consists of 2 to the L−1 transpositions. Since a swaps the two subtrees below the root and acts trivially inside them, it pairs the word 0u with the word 1u for each of the 2 to the L−1 words u of length L−1.
Observation
4
.4
.Flipping the output map of every state of an invertible binary automaton leaves every section unchanged and replaces the set of active states by its complement. Since every vertex of level L has exactly one section, the activity becomes 2 to the L minus the original activity. The flip is an involution of the invertible automata, so the distribution of the activity at level L over that space is symmetric about half of 2 to the L.
The census over all invertible 3-state binary automata confirms the symmetry exactly and shows how rare bounded activity is.
activityCensus=Table[{activity[AutomatonRuleFromCode[{code,{3,2}}],1,4],activity[AutomatonRuleFromCode[{code,{3,2}}],1,6]},{code,InvertibleAutomatonCodes[{3,2}]}];
level6=Counts[activityCensus[[All,2]]];{Length[activityCensus],Count[activityCensus[[All,2]],0],Count[activityCensus[[All,2]],64],KeySort[level6]===KeySort[KeyMap[64-#&,level6]]}
{5832,1364,1364,True}
BarChart[Values[KeySort[level6]],ChartLabels->Keys[KeySort[level6]],ChartStyle->"Pastel",AxesLabel->{"a(g, 6)","codes"},PlotLabel->"activity at level 6 over all 5832 invertible (3, 2) automata"]
Of the 5832 codes, 1364 are finitary at level 6 and, by the symmetry, 1364 are saturated with every vertex active; the distribution matches its own reflection under a ↦ 64 − a exactly.
ListPlot[activityCensus,AxesLabel->{"a(g, 4)","a(g, 6)"},PlotStyle->Directive[RGBColor[0.55,0.75,0.9],Opacity[0.4]],PlotLabel->"activity at level 4 against level 6",Epilog->{Gray,Dashed,Line[{{0,0},{16,16}}]}]
Equal activity at levels 4 and 6 holds for 1532 of the 5832 codes, of which 1360 are finitary at both levels, leaving 172 codes that are non-finitary with unchanged activity. Four codes are finitary at level 6 without being finitary at level 4, so the activity can fall to zero rather than only rising.
Conjecture
5
.1
.For every L ≥ 0 the adding machine has activity exactly 1 at level L, and its boundary permutation at level L is a single cycle of length 2 to the L. Status: activity verified up to L = 10, cycle type up to L = 8.
The portrait shows the single active vertex per level, the carry spine; the boundary graph is one cycle.
Conjecture
5
.2
.The Grigorchuk generators b, c and d each have activity at most 1 at every level, and the level at which the activity vanishes is determined by L modulo 3: a(b, L) = 0 exactly when L ≡ 0, a(c, L) = 0 exactly when L ≡ 2, and a(d, L) = 0 exactly when L ≡ 1, in each case for L ≥ 1. Status: verified up to L = 10.
The three activity sequences are the same pattern shifted by one level, which is the cyclic structure of the recursion b = (a, c), c = (a, d), d = (1, b).
Question
5
.3
.The boundary permutation of the Grigorchuk generator b at level L is a product of transpositions, since b has order 2. The number of transpositions for L = 2, …, 9 is 1, 3, 6, 13, 27, 54, 109, 219, and the number of fixed vertices is 2, 2, 4, 6, 10, 20, 38, 74. We do not have a recursion or closed form for either sequence.
The two sequences, against the total 2 to the L that they partition.
6
.AutomatonTreePortrait
AutomatonTreePortrait
The tree to a given depth, each vertex coloured by the state acting in that subtree and enlarged where that state is active.
The level permutation as its functional graph, drawn on a circle so the cycle structure is visible.
8
.AutomatonNucleus
AutomatonNucleus
The sections of the ball of a given radius, listed by depth. The list stabilises exactly when the automaton contracts, and its limit is the nucleus.
The transducer behind all of the above.
One space-time plot per rule, from a shared initial condition.
One space-time plot per initial condition, from a shared rule.
12
.IteratedFiniteAutomatonsMatrix
IteratedFiniteAutomatonsMatrix
The rules-by-initial-conditions grid.
14
.Literature
Literature