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 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 xin 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 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 Mealy
  machine associated with a.
  
  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 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  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 vin X^*
  there  is  a  non-trivial  a_vin  G that fixes X^* \ vX^*. It is branched 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 contracting 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 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.
  
  ---------------------------  Example  ----------------------------
    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 10. 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.
  
  ---------------------------  Example  ----------------------------
    gap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>":IsFRElement);
    <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:
  
  ---------------------------  Example  ----------------------------
    gap> DecompositionOfFRElement(a); DecompositionOfFRElement(b);
    [ [ <2|identity ...>, <2|b> ], (1,2) ]
    [ [ <2|identity ...>, <2|a> ], () ]
  ------------------------------------------------------------------
  
  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 (11.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 (11.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.
  
  Elements act on sequences over {1,2}. The action is computed in the standard
  manner:
  
  ---------------------------  Example  ----------------------------
    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 "/":
  
  ---------------------------  Example  ----------------------------
    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,
  
  ---------------------------  Example  ----------------------------
    gap> Bm := Image(IsomorphismMealyGroup(B));
    <self-similar group over [ 1 .. 2 ] with 2 generators>
    gap> a := Bm.1; b := Bm.2;
    <Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
    <Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
  ------------------------------------------------------------------
  
  This  could have been done automatically by specifying :IsMealyElement as an
  option 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:
  
  ---------------------------  Example  ----------------------------
    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' 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 VertexElement (4.1-5):
  
  ---------------------------  Example  ----------------------------
    gap> c := Comm(a,b);
    <Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
    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)],()];
    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 (12.1-13).
  
  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:
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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):
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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:
  
  ---------------------------  Example  ----------------------------
    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.