  
  [1X2 FR package[0X
  
  
  [1X2.1 A brief mathematical introduction[0X
  
  This  chapter  assumes that you have no familiarity with groups generated by
  automata. If you do, and wish to see their usage within [5XGAP[0m through a sample
  session,  please  skip  to Section [14X2.2[0m. 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  [13Xactivity[0m  of  a.  We  may  also  obtain,  for all xin X, a tree
  automorphism a_x in W, called the [13Xstate of a at x[0m, 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  [13XWreath  recursion[0m. The image of phi is the permutational wreath
  product W^X rtimes 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.  It is called the [13XMealy
  machine[0m associated with a.
  
  Of   particular   interest   are   [13Xfinite-state   automorphisms[0m:  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  [13Xself-similar[0m  if  G^phi subset GwrSym(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  [13Xlevel-transitive[0m if its action is transitive on all the G-subsets
  X^n.  It is [13Xweakly branched[0m if it is level-transitive, and for every vin X^*
  there  is  a  non-trivial  a_vin  G that fixes X^* \ vX^*. It is [13Xbranched[0m if
  furthermore for each n in 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 is [13Xcontracting[0m if there are
  constants  K,n  in N and lambda<1 such that |a_v|lelambda|a|+K for all ain G
  and  vin  X^n;  here  |a| denotes the minimal number of generators needed to
  express  a.  It  then  follows that there exists a finite set Nsubset G such
  that  for  all  ain G, all but finitely many of the states of a belong to N.
  The  minimal such N is called the [13Xnucleus[0m 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
  [13Xgroup generated[0m 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.
  
  
  [1X2.2 An example session[0X
  
  This  is a brief introduction describing some of the simpler features of the
  [5XFR[0m  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 [14X2.1[0m. We show here and comment a typical use of the package.
  
  The  package  is installed by unpacking the archive in the [11Xpkg/[0m directory of
  your  [5XGAP[0m  installation.  It  can also be placed in a local directory, which
  must be added to the load-path by invoking [10Xgap[0m with the [10X-l[0m option.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> LoadPackage("fr");[0X
    [4X----------------------------------------------------------------[0X
    [4XLoading FR 0.857142p5 (Functionally recursive and automata groups)[0X
    [4Xby Laurent Bartholdi (http://www.uni-math.gwdg.de/laurent)[0X
    [4X----------------------------------------------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  Many  FR  groups  are predefined by [5XFR[0m, see Chapter [14X10[0m. We consider here the
  [13XBasilica group[0m, considered in [GŻ02a] and [BV05].
  
  We  may start by defining a group: it has two generators a and b, satisfying
  the specified recursions.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>":IsFRElement);[0X
    [4X<self-similar group over [ 1 .. 2 ] with 2 generators>[0X
    [4Xgap> AssignGeneratorVariables(B);[0X
    [4X#I  Assigned the global variables [ a, b ][0X
  [4X------------------------------------------------------------------[0X
  
  We have just created the group B=< a,b>.
  
  Note  that  this  group  is  predefined as [10XBasilicaGroup[0m. We now compute the
  decompositions of the generators:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> DecompositionOfFRElement(a); DecompositionOfFRElement(b);[0X
    [4X[ [ <2|identity ...>, <2|b> ], (1,2) ][0X
    [4X[ [ <2|identity ...>, <2|a> ], () ][0X
  [4X------------------------------------------------------------------[0X
  
  Elements  are  described  as  words  in  the generators; they are printed as
  [10X<2|a>[0m, where the 2 reminds of the degree of the tree on which a acts.
  
  The  optional  argument  [2XIsFRElement[0m ([14X11.2-11[0m) tells [5XFR[0m to store elements in
  this  way.  This  representation  is  always  possible,  but  it  is usually
  inefficient for calculations. The argument [2XIsMealyElement[0m ([14X11.2-4[0m) forces [5XFR[0m
  to  use  a  more  efficient  representation, which in some cases may take an
  infinite  time  to set up. With no extra argument, [5XFR[0m does what it thinks is
  best.
  
  Elements act on sequences over {1,2}. The action is computed in the standard
  manner:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> 1^a; [1]^a; [1,1]^a;[0X
    [4X2[0X
    [4X[ 2 ][0X
    [4X[ 2, 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  Periodic  sequences  are  also  implemented  in  [5XFR[0m; they are constructed by
  giving  the period and preperiod. The period is printed by preceding it with
  a "/":
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> v := PeriodicList([1],[2]);[0X
    [4X[ 1, / 2 ][0X
    [4Xgap> v^a; v^(a^2);[0X
    [4X[/ 2 ][0X
    [4X[/ 1, 2 ][0X
    [4Xgap> last{[1..10]};[0X
    [4X[ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ][0X
  [4X------------------------------------------------------------------[0X
  
  Most  computations  are much more efficient if B's elements are converted to
  [13XMealy representation[0m,
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> Bm := Image(IsomorphismMealyGroup(B));[0X
    [4X<self-similar group over [ 1 .. 2 ] with 2 generators>[0X
    [4Xgap> a := Bm.1; b := Bm.2;[0X
    [4X<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>[0X
    [4X<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>[0X
  [4X------------------------------------------------------------------[0X
  
  This  could have been done automatically by specifying [10X:IsMealyElement[0m as an
  option in the call to [10XFRGroup[0m.
  
  The group B is torsion-free, and its elements are bounded automata. Although
  torsion-freeness  is  difficult  to  check  for  [5XFR[0m,  it  can  be checked on
  individual elements:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> IsBoundedFRSemigroup(Bm);[0X
    [4Xtrue[0X
    [4Xgap> Order(a); Order(b);[0X
    [4Xinfinity[0X
    [4Xinfinity[0X
    [4Xgap> g := PseudoRandom(B);; Length(InitialState(g));[0X
    [4X4679[0X
    [4Xgap> Order(g); time;[0X
    [4Xinfinity[0X
    [4X2599[0X
  [4X------------------------------------------------------------------[0X
  
  The  group  B  is  weakly  branched; more precisely, the derived subgroup B'
  contains B' x B'. To prove that, it suffices to check [a,b] x 1in B' and 1 x
  [a,b]in B'. These elements are constructed using [2XVertexElement[0m ([14X4.1-5[0m):
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> c := Comm(a,b);[0X
    [4X<Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>[0X
    [4Xgap> K := NormalClosure(Bm,Group(c));[0X
    [4X<self-similar group over [ 1 .. 2 ] with 3 generators>[0X
    [4Xgap> VertexElement(1,c) in K; VertexElement(1,c) in K;[0X
    [4Xtrue[0X
    [4Xtrue[0X
    [4Xgap> DecompositionOfFRElement(VertexElement(1,c)=[[c,One(Bm)],()];[0X
    [4Xtrue[0X
    [4Xgap> VertexElement(2,c)=Comm(b,a^2);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  Note  that we had to guess the form of the element [10XVertexElement(2,c)[0m above.
  This could have been found out by [5XGAP[0m using [2XShortGroupWordInSet[0m ([14X12.1-13[0m).
  
  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:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> ForAll([0..10],i->IsOne(Comm(b^(2^i),(b^(2^i))^((a^(2^i)))))); time;[0X
    [4Xtrue[0X
    [4X1361[0X
  [4X------------------------------------------------------------------[0X
  
  Since the group B is bounded, it is contracting. We compute its nucleus:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> NucleusOfFRSemigroup(B);[0X
    [4X[ <2|identity ...>, <2|b>, <2|b^-1>, <2|a>, <2|a^-1>, <2|b^-1*a>, <2|a^-1*b> ][0X
  [4X------------------------------------------------------------------[0X
  
  We  then  compute  the Mealy machine with stateset this nucleus, and draw it
  graphically (this requires the external programs [5Xgraphviz[0m and [5Ximagemagick[0m):
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> N := NucleusMachine(B);[0X
    [4X<Mealy machine on alphabet [ 1, 2 ] with 7 states>[0X
    [4Xgap> Draw(N);[0X
  [4X------------------------------------------------------------------[0X
  
  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:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> Draw(DualMachine(N)^3);[0X
    [4Xgap> M := AsMealyMachine(FRMachine(a))[1];[0X
    [4X<Mealy machine on alphabet [ 1, 2 ] with 3 states>[0X
    [4Xgap> Draw(DualMachine(M)^4);[0X
  [4X------------------------------------------------------------------[0X
  
  These  Schreier  graphs  are  orbits  of the group; they can be displayed as
  follows:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> WordGrowth(B:point:=[1,1,1,1],draw);[0X
  [4X------------------------------------------------------------------[0X
  
  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.
  [10XPermGroup(B,n)[0m  constructs a permutation group which is the natural quotient
  of B acting on 2^n points:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> G := PermGroup(B,7);[0X
    [4X<permutation group with 2 generators>[0X
    [4Xgap> Size(G); LogInt(last,2);[0X
    [4X309485009821345068724781056[0X
    [4X88[0X
  [4X------------------------------------------------------------------[0X
  
  We  may "guess" the structure of the Lie algebra of B by examining the ranks
  of the successive quotients along its Jennings series:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> J := JenningsLieAlgebra(G); time;[0X
    [4X<Lie algebra of dimension 88 over GF(2)>[0X
    [4X18035[0X
    [4Xgap> List([1..15],i->Dimension(Grading(J).hom_components(i)));[0X
    [4X[ 2, 3, 1, 4, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  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.
  
