This chapter assumes that you have no familiarity with groups generated by automata. If you do, and wish to see their usage within GAP through a sample session, please skip to Section 2.2. For a more thourough introduction on self-similar groups see [BGN03] or [BG{Š}03].
We shall here be interested in groups \(G\) defined by their action on a regular rooted tree. Let \(X\) be a finite set; and let \(X^*\) denote the set of words (free monoid) over \(X\). Then \(X^*\) naturally has the structure of a regular rooted tree: the root is the empty word, and vertex \(v \in X^*\) is connected to vertex \(vx\) for all choices of \(x \in X\). Each vertex except the root therefore has \(\#X+1\) neighbours.
Let \(W\) denote the automorphism group of the graph \(X^*\). Given \(a \in W\), we may restrict its action to \(X \subset X^*\), and obtain a permutation \(\pi_a\) on \(X\), called the activity of \(a\). We may also obtain, for all \(x\in X\), a tree automorphism \(a_x \in W\), called the state of \(a\) at \(x\), by the formula
\[(v){a_x} = w \quad\textrm{if}\quad (xv)a = x^{\pi_a}w.\]
The data \((a_x,\pi_a)\) determine uniquely the automorphism \(a\), and any choice of \(a_x\) and \(\pi_a\) defines a tree isometry. We therefore have a group isomorphism
\[\phi: W \to W\wr \mathop{Sym}(X),\]
called the Wreath recursion. The image of \(\phi\) is the permutational wreath product \(W^X \rtimes \mathop{Sym}(X)\).
The state \(a_x\) should be interpreted as the restriction of the action of \(a\) on the subtree \(xX^*\); the automorphism \(a\) is defined by acting first on each of the subtrees of the form \(xX^*\) by its respective state, and then permuting these subtrees according to \(\pi_a\). The wreath recursion can be iterated on the states of \(a\), to define states \(a_v\) for any \(v \in X^*\).
The automorphism \(a \in W\) may be represented by a graph, as follows. There is one vertex for each state \(a_v\) of \(a\), labeled \(\pi_{a_v}\); and for each \(x \in X\) there is one edge from state \(a_v\) to state \(a_{vx}\), labeled \(x\). This graph is nothing but a quotient of the regular rooted tree \(X^*\), where vertices \(v\) and \(w\) are identified if \(a_v=a_w\). Again, this graph, with a choice of initial vertex, determines uniquely the automorphism \(a\).
This graph may be conveniently encoded in what is called a Moore machine: it consists of a set \(Q\), the vertex set of the graph; an alphabet, \(X\); a `transition' function \(\phi:Q\times X\to Q\), where \(\phi(q,x)\) is the endpoint of the edge starting at \(q\) and labeled \(x\); and a labeling \(\pi\) of \(X\) by the symmetric group on \(X\). We will use the equivalent Mealy machines, given by a `transition' function \(\phi:Q\times X\to X\times Q\), encoding both \(\phi\) and \(\pi\) together.
Of particular interest are finite-state automorphisms: these are automorphisms whose Mealy machine has finitely many states. The product and inverse of finite-state automorphisms is again finite-state.
A subgroup \(G \le W\) is self-similar if \(G^\phi \subset G\wr\mathop{Sym}(X)\). This is equivalent to asking, for every \(a \in G\), that all of its states \(a_x\) also belong to \(G\).
The following important properties have also been considered. A subgroup \(G \le W\) is level-transitive if its action is transitive on all the \(G\)-subsets \(X^n\). It is weakly branched if it is level-transitive, and for every \(v\in X^*\) there is a non-trivial \(a_v\in G\) that fixes \(X^* \setminus vX^*\). It is branched if furthermore for each \(n \in \mathbb N\) the group generated by all such \(a_v\) for all \(v\) of length \(n\) has finite index in \(G\).
A self-similar finitely generated group \(G \le W\) is contracting if there are constants \(K,n \in \mathbb N\) and \(\lambda<1\) such that \(|a_v|\le\lambda|a|+K\) for all \(a\in G\) and \(v\in X^n\); here \(|a|\) denotes the minimal number of generators needed to express \(a\). It then follows that there exists a finite set \(N\subset G\) such that for all \(a\in G\), all but finitely many of the states of \(a\) belong to \(N\). The minimal such \(N\) is called the nucleus of \(G\). Since the states of elements of the nucleus are again in the nucleus, we see that the nucleus is naturally a Mealy machine. By considering all elements of \(W\) obtained from this Mealy machine by choosing all possible initial states, we obtain a generating set for \(G\) made of all states of a single machine; this is the group generated by the machine.
In this package, we are mainly interested in self-similar groups of finite-state automorphisms. The reason is historical: Aleshin [Ale83], and later Grigorchuk [Gri80] and Gupta and Sidki [GS83] constructed peculiar examples of groups using self-similar finite-state automorphisms. All these groups can be defined by drawing a small machine (at most five vertices) and considering the group that they generate.
We assumed for simplicity that the elements \(a\) were invertible. Actually, in the definition of Mealy machines it makes sense to accept arbitrary maps, and not necessarily bijections of \(X\) as a label at each vertex. One may in this way define peculiar semigroups.
This is a brief introduction describing some of the simpler features of the FR package. It assumes you have some familiarity with the theory of groups defined by automata; if not, a brief mathematical introduction may be found in Section 2.1. We show here and comment a typical use of the package.
The package is installed by unpacking the archive in the pkg/ directory of your GAP installation. It can also be placed in a local directory, which must be added to the load-path by invoking gap with the -l option.
gap> LoadPackage("fr"); ---------------------------------------------------------------- Loading FR 0.857142p5 (Functionally recursive and automata groups) by Laurent Bartholdi (http://www.uni-math.gwdg.de/laurent) ---------------------------------------------------------------- true
Many FR groups are predefined by FR, see Chapter 9. We consider here the Basilica group, considered in [G{\.Z}02] and [BV05].
We may start by defining a group: it has two generators \(a\) and \(b\), satisfying the specified recursions.
gap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>",IsFRMealyElement); <self-similar group over [ 1 .. 2 ] with 2 generators> gap> AssignGeneratorVariables(B); #I Assigned the global variables [ a, b ]
We have just created the group \(B=\langle a,b\rangle\).
Note that this group is predefined as BasilicaGroup. We now compute the decompositions of the generators:
gap> DecompositionOfFRElement(a); DecompositionOfFRElement(b); [ [ <2|identity ...>, <2|b> ], [ 2, 1 ] ] [ [ <2|identity ...>, <2|a> ], [ 1, 2 ] ]
Elements are described as words in the generators; they are printed as <2|a>, where the \(2\) reminds of the degree of the tree on which \(a\) acts.
The optional argument IsFRElement (10.2-11) tells FR to store elements in this way. This representation is always possible, but it is usually inefficient for calculations. The argument IsMealyElement (10.2-4) forces FR to use a more efficient representation, which in some cases may take an infinite time to set up. With no extra argument, FR does what it thinks is best. The advantages of both representations are sometimes obtained by the argument IsFRMealyElement (10.2-12), which stores both representations.
Elements act on sequences over \(\{1,2\}\). The action is computed in the standard manner:
gap> 1^a; [1]^a; [1,1]^a; 2 [ 2 ] [ 2, 1 ]
Periodic sequences are also implemented in FR; they are constructed by giving the period and preperiod. The period is printed by preceding it with a "/":
gap> v := PeriodicList([1],[2]); [ 1, / 2 ] gap> v^a; v^(a^2); [/ 2 ] [/ 1, 2 ] gap> last{[1..10]}; [ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ]
Most computations are much more efficient if \(B\)'s elements are converted to Mealy representation,
gap> Bm := Image(IsomorphismMealyGroup(B)); <recursive group over [ 1 .. 2 ] with 2 generators> gap> a := Bm.1; b := Bm.2; <Mealy element on alphabet [ 1, 2 ] with 3 states> <Mealy element on alphabet [ 1, 2 ] with 3 states>
This could have been done automatically by specifying IsMealyElement as last argument in the call to FRGroup.
The group \(B\) is torsion-free, and its elements are bounded automata. Although torsion-freeness is difficult to check for FR, it can be checked on individual elements:
gap> IsBoundedFRSemigroup(Bm); true gap> Order(a); Order(b); infinity infinity gap> g := PseudoRandom(B);; Length(InitialState(g)); 4679 gap> Order(g); time; infinity 2599
The group \(B\) is weakly branched; more precisely, the derived subgroup \(B'\) contains \(B' \times B'\). To prove that, it suffices to check \([a,b] \times 1\in B'\) and \(1 \times [a,b]\in B'\). These elements are constructed using VertexElement (4.1-5):
gap> c := Comm(a,b); <Mealy element on alphabet [ 1, 2 ] with 9 states> gap> K := NormalClosure(Bm,Group(c)); <self-similar group over [ 1 .. 2 ] with 3 generators> gap> VertexElement(1,c) in K; VertexElement(1,c) in K; true true gap> DecompositionOfFRElement(VertexElement(1,c))=[[c,One(Bm)],[1,2]]; true gap> VertexElement(2,c)=Comm(b,a^2); true
Note that we had to guess the form of the element VertexElement(2,c) above. This could have been found out by GAP using ShortGroupWordInSet (11.4-2).
We may also check the relations \([b^p,(b^p)^{a^p}]=1\) and \([a^{2p},(a^{2p})^{b^p}]\) for \(p\) any power of \(2\):
gap> ForAll([0..10],i->IsOne(Comm(b^(2^i),(b^(2^i))^((a^(2^i)))))); time; true 1361
Since the group \(B\) is bounded, it is contracting. We compute its nucleus:
gap> NucleusOfFRSemigroup(B); [ <2|identity ...>, <2|b>, <2|b^-1>, <2|a>, <2|a^-1>, <2|b^-1*a>, <2|a^-1*b> ]
We then compute the Mealy machine with stateset this nucleus, and draw it graphically (this requires the external programs graphviz and imagemagick):
gap> N := NucleusMachine(B); <Mealy machine on alphabet [ 1, 2 ] with 7 states> gap> Draw(N);
We may also draw powers of the dual automaton: these are approximations to the Schreier graph of \(B\). However, we also construct a smaller Mealy machine with states only \(a\) and \(b\), which give better images:
gap> Draw(DualMachine(N)^3); gap> M := AsMealyMachine(FRMachine(a))[1]; <Mealy machine on alphabet [ 1, 2 ] with 3 states> gap> Draw(DualMachine(M)^4);
These Schreier graphs are orbits of the group; they can be displayed as follows:
gap> WordGrowth(B:point:=[1,1,1,1],draw);
More properties of \(B\) can be checked, or experimented with, on its finite quotients obtained by truncating the tree on which \(B\) acts at a given length. PermGroup(B,n) constructs a permutation group which is the natural quotient of \(B\) acting on \(2^n\) points:
gap> G := PermGroup(B,7); <permutation group with 2 generators> gap> Size(G); LogInt(last,2); 309485009821345068724781056 88
We may "guess" the structure of the Lie algebra of \(B\) by examining the ranks of the successive quotients along its Jennings series:
gap> J := JenningsLieAlgebra(G); time; <Lie algebra of dimension 88 over GF(2)> 18035 gap> List([1..15],i->Dimension(Grading(J).hom_components(i))); [ 2, 3, 1, 4, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 ]
The "\(4\)" in position \(8\) of that list should really be a "\(5\)"; computations on finite quotients of \(B\) usually give lower bounds for invariants of \(B\). In that case, we guess that the ranks behave like a "ruler" function, i.e. that the rank of the homogeneous component of degree \(i\) is \(2+\nu_2(i)\) if \(i\) is a power of \(2\) and is \(1+\nu_2(i)\) otherwise; here \(\nu_2(i)\) is the number of times \(2\) divides \(i\).
generated by GAPDoc2HTML