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{\v S}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 ∈ X^* is connected to vertex vx for all choices of x ∈ X. Each vertex except the root therefore has #X+1 neighbours.

Let W denote the automorphism group of the graph X^*. Given a ∈ W, we may restrict its action to X ⊂ X^*, and obtain a permutation π_a on X, called the *activity* of a. We may also obtain, for all x∈ X, a tree automorphism a_x ∈ 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,π_a) determine uniquely the automorphism a, and any choice of a_x and π_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 ϕ is the permutational wreath product W^X ⋊ 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 π_a. The wreath recursion can be iterated on the states of a, to define states a_v for any v ∈ X^*.

The automorphism a ∈ W may be represented by a graph, as follows. There is one vertex for each state a_v of a, labeled π_a_v; and for each x ∈ 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 ϕ:Q× X-> Q, where ϕ(q,x) is the endpoint of the edge starting at q and labeled x; and a labeling π of X by the symmetric group on X. We will use the equivalent *Mealy machines*, given by a `transition' function ϕ:Q× X-> X× Q, encoding both ϕ and π 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^ϕ ⊂ G≀Sym(X). This is equivalent to asking, for every a ∈ 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∈ X^* there is a non-trivial a_v∈ G that fixes X^* ∖ vX^*. It is *branched* if furthermore for each n ∈ 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 ∈ N and λ<1 such that |a_v|leλ|a|+K for all a∈ G and v∈ X^n; here |a| denotes the minimal number of generators needed to express a. It then follows that there exists a finite set N⊂ G such that for all a∈ 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=⟨ a,b⟩.

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' × B'. To prove that, it suffices to check [a,b] × 1∈ B' and 1 × [a,b]∈ 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+ν_2(i) if i is a power of 2 and is 1+ν_2(i) otherwise; here ν_2(i) is the number of times 2 divides i.

generated by GAPDoc2HTML