Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

2 FR package
 2.1 A brief mathematical introduction
 2.2 An example session

2 FR package

2.1 A brief mathematical introduction

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 ∈ 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.

2.2 An example session

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 (

Many FR groups are predefined by FR, see Chapter 9. We consider here the Basilica group, considered in [GŻ02a] 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, 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);
gap> Order(a); Order(b);
gap> g := PseudoRandom(B);; Length(InitialState(g));
gap> Order(g); time;

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;
gap> DecompositionOfFRElement(VertexElement(1,c))=[[c,One(Bm)],[1,2]];
gap> VertexElement(2,c)=Comm(b,a^2);

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;

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);

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)>
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.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML