10 Examples
  
  FR  predefines  a  large  collection of machines and groups. The groups are,
  whenever   possible,  defined  as  state  closures  of  corresponding  Mealy
  machines.
  
  
  10.1 Examples of groups
  
  10.1-1 FullBinaryGroup
  
  > FullBinaryGroup____________________________________________global variable
  > FiniteDepthBinaryGroup( l ) ______________________________________function
  > FinitaryBinaryGroup________________________________________global variable
  > BoundedBinaryGroup_________________________________________global variable
  > PolynomialGrowthBinaryGroup________________________________global variable
  > FiniteStateBinaryGroup_____________________________________global variable
  
  These   are  the  finitary,  bounded,  polynomial-growth,  finite-state,  or
  unrestricted  groups  acting  on  the  binary  tree.  They  are respectively
  shortcuts        for       FullSCGroup([1..2]),       FullSCGroup([1..2],l),
  FullSCGroup([1..2],IsFinitaryFRSemigroup),
  FullSCGroup([1..2],IsBoundedFRSemigroup),
  FullSCGroup([1..2],IsPolynomialGrowthFRSemigroup),                       and
  FullSCGroup([1..2],IsFiniteStateFRSemigroup).
  
  They may be used to draw random elements, or to test membership.
  
  10.1-2 BinaryKneadingGroup
  
  > BinaryKneadingGroup( angle/ks ) __________________________________function
  > BinaryKneadingMachine( angle/ks ) ________________________________function
  Returns:  The  [machine  generating  the]  iterated  monodromy  group  of  a
            quadratic polynomial.
  
  The  first  function  constructs  a Mealy machine whose state closure is the
  binary kneading group.
  
  The  second  function  constructs  a  new  FR group G, which is the iterated
  monodromy  group of a quadratic polynomial, either specified by its angle or
  by its kneading sequence(s).
  
  If  the argument is a (rational) angle, the attribute Correspondence(G) is a
  function returning, for any rational, the corresponding generator of G.
  
  If  there is one argument, which is a list or a string, it is treated as the
  kneading  sequence  of a periodic (superattracting) polynomial. The sequence
  is  implicity  assumed  to  end by '*'. The attribute Correspondence(G) is a
  list of the generators of G.
  
  If  there are two arguments, which are lists or strings, they are treated as
  the  preperiod  and  period  of  the  kneading  sequence  of  a  preperiodic
  polynomial.  The  last  symbol  of  the arguments must differ. The attribute
  Correspondence(G)  is a pair of lists of generators; Correspondence(G)[1] is
  the  preperiod,  and  Correspondence(G)[2]  is  the  period.  The  attribute
  KneadingSequence(G)  returns  the  kneading  sequence,  as a pair of strings
  representing preperiod and period respectively.
  
  As  particular  examples,  BinaryKneadingMachine()  is  the  adding machine;
  BinaryKneadingGroup() is the adding machine; and BinaryKneadingGroup("1") is
  BasilicaGroup (10.1-3).
  
  ---------------------------  Example  ----------------------------
    gap> BinaryKneadingGroup()=AddingGroup(2);
    true
    gap> BinaryKneadingGroup(1/3)=BasilicaGroup;
    true
    gap> g := BinaryKneadingGroup([0,1],[0]);
    BinaryKneadingGroup("01","0")
    gap> ForAll(Correspondence(g)[1],IsFinitaryFRElement);
    true
    gap> ForAll(Correspondence(g)[2],IsFinitaryFRElement);
    false
    gap> ForAll(Correspondence(g)[2],IsBoundedFRElement);
    true
  ------------------------------------------------------------------
  
  10.1-3 BasilicaGroup
  
  > BasilicaGroup______________________________________________global variable
  
  The  Basilica  group. This is a shortcut for BinaryKneadingGroup("1"). It is
  the  first-discovered  amenable group that is not subexponentially amenable,
  see [BV05] and [GŻ02a].
  
  ---------------------------  Example  ----------------------------
    gap> IsBoundedFRSemigroup(BasilicaGroup);
    true
    gap> pi := EpimorphismFromFreeGroup(BasilicaGroup); F := Source(pi);;
    [ x1, x2 ] -> [ a, b ]
    gap> sigma := GroupHomomorphismByImages(F,F,[F.1,F.2],[F.2,F.1^2]);
    [ x1, x2 ] -> [ x2, x1^2 ]
    gap> ForAll([0..10],i->IsOne(Comm(F.2,F.2^F.1)^(sigma^i*pi)));
    true
  ------------------------------------------------------------------
  
  10.1-4 AddingGroup
  
  > AddingGroup( n ) _________________________________________________function
  > AddingMachine( n ) _______________________________________________function
  > AddingElement( n ) _______________________________________________function
  
  The  second  function  constructs the adding machine on the alphabet [1..n].
  This machine has a trivial state 1, and a non-trivial state 2. It implements
  the operation "add 1 with carry" on sequences.
  
  The  third function constructs the Mealy element on the adding machine, with
  initial state 2.
  
  The first function constructs the state-closed group generated by the adding
  machine on [1..n]. This group is isomorphic to the Integers.
  
  ---------------------------  Example  ----------------------------
    gap> Display(AddingElement(3));
       |  1     2     3
    ---+-----+-----+-----+
     a | a,1   a,2   a,3
     b | a,2   a,3   b,1
    ---+-----+-----+-----+
    Initial state: b
    gap> Activity(FRElement(AddingMachine(3),2),2);
    (1,4,7,2,5,8,3,6,9)
    gap> G := AddingGroup(3);
    <self-similar group over [ 1 .. 3 ] with 1 generator>
    gap> Size(G);
    infinity
    gap> IsRecurrent(G);
    true
    gap> IsLevelTransitive(G);
    true
  ------------------------------------------------------------------
  
  10.1-5 BinaryAddingGroup
  
  > BinaryAddingGroup__________________________________________global variable
  > BinaryAddingMachine________________________________________global variable
  > BinaryAddingElement________________________________________global variable
  
  These  are  respectively  the  same  as AddingGroup(2), AddingMachine(2) and
  AddingElement(2).
  
  10.1-6 MixerGroup
  
  > MixerGroup( A, B, f[, g] ) _______________________________________function
  > MixerMachine( A, B, f[, g] ) _____________________________________function
  Returns:  A Mealy "mixer" machine/group.
  
  The  second function constructs a Mealy "mixer" machine m. This is a machine
  determined  by  a  permutation  group A, a finitely generated group B, and a
  matrix of homomorphisms from B to A. If A acts on [1..d], then each row of f
  contains  at  most  d-1  homomorphisms.  The  optional  last  argument is an
  endomorphism of B. If absent, it is treated as the identity map on B.
  
  The  states of the machine are 1, followed by some elements a of A, followed
  by  as  many  copies  of  some  elements  b of B as there are rows in f. The
  elements  in  B  that  are taken is the smallest sublist of B containing its
  generators  and  closed  under  g.  The elements in A that are taken are the
  generators of A and all images of all taken elements of B under maps in f.
  
  The transitions from a are towards 1 and the outputs are the permutations in
  A.  The transitions from b are periodically given by f, completed by trivial
  elements, and finally by b^g; the output of b is trivial.
  
  This construction is described in more detail in [BÅ 01] and [BGÅ 03].
  
  Correspondence(m) is a list, with in first position the subset of the states
  that  correspond  to A, in second position the states that correspond to the
  first copy of B, etc.
  
  The  first function constructs the group generated by the mixer machine. For
  examples    see    GrigorchukGroups    (10.1-8),   NeumannGroup   (10.1-19),
  GuptaSidkiGroups (10.1-17), and OtherSpinalGroup (10.1-21).
  
  ---------------------------  Example  ----------------------------
    gap> grigorchukgroup := MixerGroup(Group((1,2)),Group((1,2)),
         [[IdentityMapping(Group((1,2)))],[IdentityMapping(Group((1,2)))],[]]));
    <self-similar group over [ 1 .. 2 ] with 4 generators>
    gap> IdGroup(Group(grigorchukgroup.1,grigorchukgroup.2));
    [ 32, 18 ]
  ------------------------------------------------------------------
  
  10.1-7 SunicGroup
  
  > SunicGroup( phi ) ________________________________________________function
  > Sunicmachine( phi ) ______________________________________________function
  Returns:  The Sunic machine associated with the polynomial phi.
  
  A  "Sunic  machine" is a special kind of MixerMachine (10.1-6), in which the
  group  A  is  a  finite field GF(q), the group B is an extension A[x]/(phi),
  where  phi  is  a  monic  polynomial;  there  is a map f:B-> A, given say by
  evaluation;  and there is an endomorphism of g:B-> B given by multiplication
  by phi.
  
  These  groups  were  described  in  [Å un07]. In particular, the case q=2 and
  phi=x^2+x+1 gives the original GrigorchukGroup (10.1-9).
  
  ---------------------------  Example  ----------------------------
    gap> x := Indeterminate(GF(2));;
    gap> g := SunicGroup(x^2+x+1);
    SunicGroup(x^2+x+Z(2)^0)
    gap> g = GrigorchukGroup;
    true
  ------------------------------------------------------------------
  
  10.1-8 GrigorchukMachines
  
  > GrigorchukMachines( omega ) ______________________________________function
  > GrigorchukGroups( omega ) ________________________________________function
  Returns:  One of the Grigorchuk groups.
  
  This function constructs the Grigorchuk machine or group associated with the
  infinite  sequence  omega, which is assumed (pre)periodic; omega is either a
  periodic  list  (see  PeriodicList  (12.1-6)) or a plain list describing the
  period. Entries in the list are integers in [1..3].
  
  These   groups   are  MixerGroup  (10.1-6)s.  The  most  famous  example  is
  GrigorchukGroups([1,2,3]), which is also called GrigorchukGroup (10.1-9).
  
  These  groups  are  all  4-generated  and  infinite.  They  are described in
  [Gri84].  GrigorchukGroups([1])  is  infinite dihedral. If omega contains at
  least  2  different  digits,  GrigorchukGroups([1])  has  intermediate  word
  growth. If omega contains all 3 digits, GrigorchukGroups([1]) is torsion.
  
  The growth of GrigorchukGroups([1,2]) has been studied in [Ers04].
  
  ---------------------------  Example  ----------------------------
    gap> G := GrigorchukGroups([1]);
    <self-similar group over [ 1 .. 2 ] with 4 generators>
    gap> Index(G,DerivedSubgroup(G)); IsAbelian(DerivedSubgroup(G));
    4
    true
    gap> H := GrigorchukGroups([1,2]);
    <self-similar group over [ 1 .. 2 ] with 4 generators>
    gap> Order(H.1*H.2);
    8
    gap> Order(H.1*H.4);
    infinity
    gap> IsSubgroup(H,G);
    true
  ------------------------------------------------------------------
  
  10.1-9 GrigorchukMachine
  
  > GrigorchukMachine__________________________________________global variable
  > GrigorchukGroup____________________________________________global variable
  
  This is Grigorchuk's first group, introduced in [Gri80]. It is a 4-generated
  infinite torsion group, and has intermediate word growth. It could have been
  defined  as  FRGroup("a=(1,2)","b=<a,c>","c=<a,d>","d=<,b>"),  but is rather
  defined using Mealy elements.
  
  The command EpimorphismFromFpGroup(GrigorchukGroup,n) will will construct an
  approximating  presentation  for the Grigorchuk group, as proven in [Lys85].
  Adding  the relations Image(sigma^(n-2),(a*d)^2), Image(sigma^(n-1),(a*b)^2)
  and  Image(sigma^(n-2),(a*c)^4) yields the quotient acting on 2^n points, as
  a finitely presented group.
  
  10.1-10 GrigorchukOverGroup
  
  > GrigorchukOverGroup________________________________________global variable
  
  This   is   a   group   strictly   containing   the  Grigorchuk  group  (see
  GrigorchukGroup  (10.1-9)). It also has intermediate growth (see [BG02], but
  it  contains  elements  of  infinite  order.  It  could have been defined as
  FRGroup("a=(1,2)","b=<a,c>","c=<,d>","d=<,b>"),  but is rather defined using
  Mealy elements.
  
  ---------------------------  Example  ----------------------------
    gap> IsSubgroup(GrigorchukOverGroup,GrigorchukGroup);
    true
    gap> Order(Product(GeneratorsOfGroup(GrigorchukOverGroup)));
    infinity
    gap> GrigorchukGroup.2=GrigorchukSuperGroup.2*GrigorchukSuperGroup.3;
    true
  ------------------------------------------------------------------
  
  The    command   EpimorphismFromFpGroup(GrigorchukOverGroup,n)   will   will
  construct  an  approximating  presentation  for the Grigorchuk overgroup, as
  proven in [Bar03b].
  
  10.1-11 GrigorchukEvilTwin
  
  > GrigorchukEvilTwin_________________________________________global variable
  
  This   is   a   group  with  same  closure  as  the  Grigorchuk  group  (see
  GrigorchukGroup  (10.1-9)),  but  not  isomorphic  to it. It could have been
  defined  as  FRGroup("a=(1,2)","x=<y,a>","y=<a,z>","z=<,x>"),  but is rather
  defined using Mealy elements.
  
  ---------------------------  Example  ----------------------------
    gap> AbelianInvariants(GrigorchukEvilTwin);
    [ 2, 2, 2, 2 ]
    gap> AbelianInvariants(GrigorchukGroup);
    [ 2, 2, 2 ]
    gap> PermGroup(GrigorchukGroup,8)=PermGroup(GrigorchukEvilTwin,8);
    true
  ------------------------------------------------------------------
  
  10.1-12 BrunnerSidkiVieiraGroup
  
  > BrunnerSidkiVieiraGroup____________________________________global variable
  > BrunnerSidkiVieiraMachine__________________________________global variable
  
  This machine is the sum of two adding machines, one in standard form and one
  conjugated  by the element d described below. The group that it generates is
  described     in    [BSV99].    It    could    have    been    defined    as
  FRGroup("tau=<,tau>(1,2)","mu=<,mu^-1>(1,2)"),  but  is rather defined using
  Mealy elements.
  
  ---------------------------  Example  ----------------------------
    gap> V := FRGroup("d=<e,e>(1,2)","e=<d,d>");
    <self-similar group over [ 1 .. 2 ] with 2 generators>
    gap> Elements(V);
    [ <2|identity ...>, <2|e>, <2|d>, <2|e*d> ]
    gap> AssignGeneratorVariables(BrunnerSidkiVieiraGroup);
    #I  Assigned the global variables [ "tau", "mu", "" ]
    gap> List(V,x->tau^x)=[tau,mu,mu^-1,tau^-1];
    true
  ------------------------------------------------------------------
  
  10.1-13 AleshinGroups
  
  > AleshinGroups( l ) _______________________________________________function
  > AleshinMachines( l ) _____________________________________________function
  Returns:  The Aleshin machine with Length(l) states.
  
  This  function constructs the bireversible machines introduced by Aleshin in
  [Ale83].  The  argument l is a list of permutations, either () or (1,2). The
  groups that they generate are contructed as AleshinGroups.
  
  If  l=[(1,2),(1,2),()],  this  is AleshinGroup (10.1-14). More generally, if
  l=[(1,2,(1,2),(),...,()]  has  odd  length,  this  is  a  free group of rank
  Length(l), see [VV06].
  
  If  l=[(1,2),(1,2),...] has even length and contains an even number of ()'s,
  then this is also a free group of rank Length(l), see [SVV06].
  
  If  l=[(),(),(1,2)],  this is BabyAleshinGroup (10.1-15). more generally, if
  l=[(),(),...]  has  even length and contains an even number of (1,2)'s, then
  this is the free product of Length(l) copies of the order-2 group.
  
  10.1-14 AleshinGroup
  
  > AleshinGroup_______________________________________________global variable
  > AleshinMachine_____________________________________________global variable
  
  This  is  the  first  example  of  non-abelian  free  group. It is the group
  generated by AleshinMachine([(1,2),(1,2),()]). It could have been defined as
  FRGroup("a=<b,c>(1,2)","b=<c,b>(1,2)","c=<a,a>"),   but  is  rather  defined
  using Mealy elements.
  
  10.1-15 BabyAleshinGroup
  
  > BabyAleshinGroup___________________________________________global variable
  > BabyAleshinMachine_________________________________________global variable
  
  There are only two connected, transitive bireversible machines on a 2-letter
  alphabet, with 3 generators: AleshinMachine(3) and the baby Aleshin machine.
  
  The  group generated by this machine is abstractly the free product of three
  C_2's,    see   [Nek05,   1.10.3].   It   could   have   been   defined   as
  FRGroup("a=<b,c>","b=<c,b>","c=<a,a>(1,2)"),  but  is  rather  defined  here
  using Mealy elements.
  
  ---------------------------  Example  ----------------------------
    gap> K := Kernel(GroupHomomorphismByImagesNC(BabyAleshinGroup,Group((1,2)),
                     GeneratorsOfGroup(BabyAleshinGroup),[(1,2),(1,2),(1,2)]));
    <self-similar group over [ 1 .. 2 ] with 4 generators>
    gap> Index(BabyAleshinGroup,K);
    2
    gap> IsSubgroup(AleshinGroup,K);
    true
  ------------------------------------------------------------------
  
  10.1-16 SidkiFreeGroup
  
  > SidkiFreeGroup_____________________________________________global variable
  
  This  is  a  group  suggested  by  Sidki  as  an  example  of  a non-abelian
  state-closed  free  group.  Nothing is known about that group: whether it is
  free as conjectured; whether generator a is state-closed, etc. It is defined
  as FRGroup("a=<a^2,a^t>","t=<,t>(1,2)")]]>.
  
  10.1-17 GuptaSidkiGroups
  
  > GuptaSidkiGroups( n ) ____________________________________________function
  > GeneralizedGuptaSidkiGroups( n ) _________________________________function
  > GuptaSidkiMachines( n ) __________________________________________function
  Returns:  The Gupta-Sidki machine on an n-letter alphabet.
  
  This  function  constructs  the  machines  introduced  by Gupta and Sidki in
  [GS83].  They  generate  finitely  generated  infinite  torsion  groups: the
  exponent  of  every element divides some power of n. The special case n=3 is
  defined as GuptaSidkiGroup (10.1-18) and GuptaSidkiMachine (10.1-18).
  
  For n>3, there are (at least) two natural ways to generalize the Gupta-Sidki
  construction:     the     original     one     involves     the    recursion
  "t=<a,a^-1,1,...,1,t>",   while   the  second  (called  here  `generalized')
  involves  the  recursion "t=<a,a^2,...,a^-1,t>". A finite L-presentation for
  the  latter  is  implemented.  It is not as computationally efficient as the
  L-presentation  of the normal closure of t (a subgroup of index p), which is
  an  ascending  L-presented  group.  The  inclusion  of  that subgroup may be
  recoverd via EmbeddingOfAscendingSubgroup(GuptaSidkiGroup).
  
  10.1-18 GuptaSidkiGroup
  
  > GuptaSidkiGroup____________________________________________global variable
  > GuptaSidkiMachine__________________________________________global variable
  
  This  is  an  infinite,  2-generated,  torsion  3-group.  It could have been
  defined  as FRGroup("a=(1,2,3)","t=<a,a^-1,t>"), but is rather defined using
  Mealy elements.
  
  10.1-19 NeumannGroup
  
  > NeumannGroup( P ) ________________________________________________function
  > NeumannMachine( P ) ______________________________________________function
  Returns:  The Neumann machine/group on the permutation group P.
  
  The  first  function  constructs  the  Neumann  machine  associated  to  the
  permutation      group      P.      It      is      a      shortcut      for
  MixerMachine(P,P,[[IdentityMapping(P)]]).
  
  The second function constructs the Neumann group on the permutation group P.
  These   groups   were   first   considered   in   [Neu86].   In  particular,
  NeumannGroup(PSL(3,2))  is  a  group  of non-uniform exponential growth (see
  [Bar03a]),   and   NeumannGroup(Group((1,2,3)))   is   FabrykowskiGuptaGroup
  (10.1-20).
  
  The  attribute Correspondence(G) is set to a list of homomorphisms from P to
  the A and B copies of P.
  
  10.1-20 FabrykowskiGuptaGroup
  
  > FabrykowskiGuptaGroup______________________________________global variable
  > FabrykowskiGuptaGroups( p ) ______________________________________function
  
  This  is  an infinite, 2-generated group of intermediate word growth. It was
  studied   in   [FG85]   and   [FG91].   It   could   have  been  defined  as
  FRGroup("a=(1,2,3)","t=<a,,t>"), but is rather defined using Mealy elements.
  It has a torsion-free subgroup of index 3 and is branched.
  
  The  natural  generalization, replacing 3 by p, is constructed by the second
  form.  It  is a specific case of Neumann group (see NeumannGroup (10.1-19)),
  for which an ascending L-presentation is known.
  
  10.1-21 OtherSpinalGroup
  
  > OtherSpinalGroup___________________________________________global variable
  
  This  is an infinite, 2-generated group, which was studied in [BG02]. It has
  a  torsion-free  subgroup  of  index  3,  and  is virtually branched but not
  branched.  It  could  have been defined as FRGroup("a=(1,2,3)","t=<a,a,t>"),
  but is rather defined using Mealy elements.
  
  10.1-22 GammaPQMachine
  
  > GammaPQMachine( p, q ) ___________________________________________function
  > GammaPQGroup( p, q ) _____________________________________________function
  Returns:  The quaternion-based machine / SC group.
  
  The  first  function  constructs a bireversible (see IsBireversible (5.2-7))
  Mealy  machine  based  on quaternions, see [BM00a] and [BM00b]. This machine
  has  p+1 states indexed by integer quaternions of norm p, and an alphabet of
  size  q+1  indexed by quaternions of norm q. These quaternions are congruent
  to  1mod  2 or imod 2 depending on whether the odd prime p or q is 1 or 3mod
  4.
  
  The  structure  of the machine is such that there is a transition from (q,a)
  to  (q',a')  precisely  when qa'=pm q'a. In particular, the relations of the
  StructuralGroup  (3.5-1)  hold up to a sign, when the alphabet/state letters
  are substituted for the appropriate quaternions.
  
  The quaternions themselves can be recovered through Correspondence (3.5-11),
  which  is  a  list  with  in first position the quaternions of norm p and in
  second those of norm q.
  
  The   second   function  constructs  the  quaternion  lattice  that  is  the
  StructuralGroup  (3.5-1) of that machine. It has actions on two trees, given
  by  VerticalAction  (10.5-2)  and  HorizontalAction  (10.5-2); the ranges of
  these    actions    are    groups   generated   by   automata,   which   are
  infinitely-transitive  (see  IsInfinitelyTransitive  (7.2-12))  and  free by
  [GM05, Proposition 3.3]; see also [Ale83].
  
  10.1-23 HanoiGroup
  
  > HanoiGroup( n ) __________________________________________________function
  Returns:  The Hanoi group on an n pegs.
  
  This  function constructs the Hanoi group on n pegs. Generators of the group
  correspond   to   moving   a  peg,  and  tree  vertices  correspond  to  peg
  configurations. This group is studied in [GÅ 06].
  
  10.1-24 DahmaniGroup
  
  > DahmaniGroup_______________________________________________global variable
  
  This  is an example of a non-contracting weakly branched group. It was first
  studied     in     [Dah05].     It    could    have    been    defined    as
  FRGroup("a=<c,a>(1,2)","b=<b,a>(1,2)","c=<b,c>"),   but  is  rather  defined
  using Mealy elements.
  
  It  has  relators abc, [a^2c,[a,c]], [cab,a^-1c^-1ab] and [ac^2,c^-1b^-1c^2]
  among others.
  
  It    admits    an    endomorphism   on   its   derived   subgroup.   Indeed
  FRElement(1,Comm(a,b))=Comm(c^-1,b/a),   FRElement(1,Comm(a,c))=Comm(a/b,c),
  FRElement(1,Comm(b,c))=Comm(c,(a/b)^c).
  
  10.1-25 MamaghaniGroup
  
  > MamaghaniGroup_____________________________________________global variable
  
  This  group  was  studied in [Mam03]. It is fractal, but not contracting. It
  could              have              been             defined             as
  FRGroup("a=<,b>(1,2)","b=<a,c>","c=<a,a^-1>(1,2)")]]>, but is rather defined
  using  Mealy  elements.  It  partially  admits  branching  on  its  subgroup
  Subgroup(G,[a^2,(a^2)^b,(a^2)^c]),    and,    setting    x=Comm(a^2,b),   on
  Subgroup(G,[x,x^a,x^b,x^(b*a),x^(b/a)]). One has FRElement(1,x)=(x^-1)^b/x.
  
  10.1-26 WeierstrassGroup
  
  > WeierstrassGroup___________________________________________global variable
  
  This  is  the  iterated  monodromy  group  associated  with  the Weierstrass
  wp-function.
  
  Some     relators     in    the    group:    (atbt)^4,    ((atbt)(bt)^4n)^4,
  ((atbt)^2(bt)^4n)^2.
  
  Set x=[a,t], y=[b,t], z=[c,t], and w=[x,y]. Then G'=< x,y,z> of index 8, and
  gamma_3=<[{x,y,z},{a,b,c}]>  of  index  32, and gamma_4=G''=< w>^G, of index
  256, and G''>(G'')^4 since [[t^a,t],[t^b,t]]=(w,1,1,1).
  
  The  Schreier  graph is obtained in the complex plane as the image of a 2^nx
  2^n lattice in the torus, via Weierstrass's wp-function.
  
  The element at has infinite order.
  
  [c,t,b][b,t,c][a,t,c][c,t,a] has order 2, and belongs to G''; so there exist
  elements of arbitrary large finite order in the group.
  
  10.1-27 FRAffineGroup
  
  > FRAffineGroup( d, R, u[, transversal] ) _________________________operation
  Returns:  The d-dimensional affine group over R.
  
  This function constructs a new FR group G, which is finite-index subgroup of
  the  d-dimensional affine group over R_u, the local ring over R in which all
  non-multiples  of u are invertible. Since no generators of G are known, G is
  in  fact  returned as a full SC group; only its attribute Correspondence(G),
  which is a homomorphism from GL_d+1(R_u) to G, is relevant.
  
  The  affine  group  can  also  be  described  as  a subgroup of GL_d+1(R_u),
  consisting   of  those  matrices  M  with  M_i,d+1=0  and  M_d+1,d+1=1.  The
  finite-index subgroup is defined by the conditions u|M_i,j for all j<i.
  
  The only valid arguments are R=Integers and R=PolynomialRing(S) for a finite
  ring  S.  The alphabet of the affine group is R/RuR; an explicit transversal
  of RuR be specified as last argument.
  
  The    following    examples    construct   the   "Baumslag-Solitar   group"
  Z[frac12]rtimes_2  Z  first  introduced in [BS62], the "lamplighter group" (
  Z/2)wr  Z, and a 2-dimensional affine group. Note that the lamplighter group
  may also be defined via CayleyGroup (10.1-28).
  
  ---------------------------  Example  ----------------------------
    gap> A := FRAffineGroup(1,Integers,3);
    <self-similar group over [ 1 .. 3 ]>
    gap> f := Correspondence(A);
    MappingByFunction( ( Integers^
    [ 2, 2 ] ), <self-similar group over [ 1 .. 3 ]>, function( mat ) ... end )
    gap> BaumslagSolitar := Group([[2,0],[0,1]]^f,[[1,0],[1,1]]^f);
    <self-similar group over [ 1 .. 3 ] with 2 generators>
    gap> BaumslagSolitar.2^BaumslagSolitar.1=BaumslagSolitar.2^2;
    true
    gap> R := PolynomialRing(GF(2));;
    gap> A := FRAffineGroup(1,R,R.1);;
    gap> f := Correspondence(A);;
    gap> Lamplighter := Group(([[1+R.1,0],[0,1]]*One(R))^f,([[1,0],[1,1]]*One(R))^f);
    <self-similar group over [ 1 .. 2 ] with 2 generators>
    gap> Lamplighter = CayleyGroup(Group((1,2)));
    true
    gap> StructureDescription(Group(Lamplighter.2,Lamplighter.2^Lamplighter.1));    
    "C2 x C2"
    gap> ForAll([1..10],i->IsOne(Comm(Lamplighter.2,Lamplighter.2^(Lamplighter.1^i))));
    true
    gap> A := FRAffineGroup(2,Integers,2);;
    gap> f := Correspondence(A);;
    gap> a := [[1,4,0],[2,3,0],[1,0,1]];
    [ [ 1, 4, 0 ], [ 2, 3, 0 ], [ 1, 0, 1 ] ]
    gap> b := [[1,2,0],[4,3,0],[0,1,1]];
    [ [ 1, 2, 0 ], [ 4, 3, 0 ], [ 0, 1, 1 ] ]
    gap> Display(b^f);
        |   1      2
    ----+------+------+
      a |  b,1    c,2
      b |  d,2    e,1
      c |  a,2    f,1
    ...
     bh | cb,1   be,2
     ca | bd,1   bf,2
     cb | ae,2   bh,1
    ----+------+------+
    Initial state:  a
    gap> a^f*b^f=(a*b)^f;
    true
  ------------------------------------------------------------------
  
  10.1-28 CayleyGroup
  
  > CayleyGroup( G ) _________________________________________________function
  > CayleyMachine( G ) _______________________________________________function
  > LamplighterGroup( G ) ___________________________________________operation
  Returns:  The Cayley machine/group of the group G.
  
  The  Cayley  machine  of  a  group G is a machine with alphabet and stateset
  equal to G, and with output and transition functions given by multiplication
  in the group, in the order state*letter.
  
  The   second   function  constructs  a  new  FR  group  CG,  which  acts  on
  [1..Size(G)].  Its  generators  are in bijection with the elements of G, and
  have  as  output  the  corresponding  permutation  of  G  induced  by  right
  multiplication,  and  as  transitions  all elements of G; see CayleyMachine.
  This construction was introduced in [SS05].
  
  If  G  is an abelian group, CG is the wreath product Gwr Z; it is created by
  the constructor LamplighterGroup(IsFRGroup,G).
  
  The   attribute   Correspondence(CG)  is  a  list.  Its  first  entry  is  a
  homomorphism  from  G  into CG. Its second entry is the generator of CG that
  has  trivial  output. CG is generated Correspondence(CG)[2] and the image of
  Correspondence(CG)[1].
  
  In the example below, recall the definition of Lamplighter in the example of
  FRAffineGroup (10.1-27).
  
  ---------------------------  Example  ----------------------------
    gap> L := CayleyGroup(Group((1,2)));
    CayleyGroup(Group( [ (1,2) ] ))
    gap> L=LamplighterGroup(IsFRGroup,CyclicGroup(2));
    true
    gap> (1,2)^Correspondence(L)[1];
    <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>
    gap> IsFinitaryFRElement(last); Display(last2);
    true
       |  1     2
    ---+-----+-----+
     a | b,2   b,1
     b | b,1   b,2
    ---+-----+-----+
    Initial state: a
  ------------------------------------------------------------------
  
  
  10.2 Examples of semigroups
  
  10.2-1 I2Machine
  
  > I2Machine__________________________________________________global variable
  > I2Monoid___________________________________________________global variable
  
  The  Mealy  machine  I_2,  and  the  monoid  that  it generates. This is the
  smallest  Mealy machine generating a monoid of intermediate word growth; see
  [BRS06].
  
  For sample calculations in this monoid see SCSemigroup (7.1-2).
  
  10.2-2 I4Machine
  
  > I4Machine__________________________________________________global variable
  > I4Monoid___________________________________________________global variable
  
  The  Mealy machine generating I_4, and the monoid that it generates. This is
  a  very small Mealy machine generating a monoid of intermediate word growth;
  see [BR05].
  
  For sample calculations in this monoid see SCMonoid (7.1-2).
  
  
  10.3 Examples of algebras
  
  10.3-1 PSZAlgebra
  
  > PSZAlgebra( k ) __________________________________________________function
  
  This function creates an associative algebra A, over the field k of positive
  characteristic,   generated   by  two  derivations  u,v.  This  algebra  has
  polynomial growth, and is not nilpotent. Petrogradsky showed in [Pet06] that
  the  Lie  subalgebra  of PSZAlgebra(GF(2)) generated by v,[u,v] is nil; this
  result was generalized by Shestakov and Zelmanov in [SZ08] to arbitrary k.
  
  ---------------------------  Example  ----------------------------
    gap> a := PSZAlgebra(2);
    PSZAlgebra(GF(2))
    gap> Nillity(a.1); Nillity(a.2);
    2
    4
    gap> IsNilpotentElement(LieBracket(a.1,a.2));
    true
    gap> DecompositionOfFRElement(LieBracket(a.1,a.2))=DiagonalMat([a.2,a.2]);
    true
  ------------------------------------------------------------------
  
  10.3-2 GrigorchukThinnedAlgebra
  
  > GrigorchukThinnedAlgebra( k ) ____________________________________function
  
  This  function  creates  the  associative  envelope  A, over the field k, of
  Grigorchuk's group GrigorchukGroup (10.1-9). !!!
  
  ---------------------------  Example  ----------------------------
    gap> !!!
  ------------------------------------------------------------------
  
  10.3-3 GuptaSidkiThinnedAlgebra
  
  > GuptaSidkiThinnedAlgebra( k ) ____________________________________function
  
  This  function  creates  the  associative  envelope  A, over the field k, of
  Gupta-Sidki's group GuptaSidkiGroup (10.1-18). !!!
  
  ---------------------------  Example  ----------------------------
    gap> !!!
  ------------------------------------------------------------------
  
  10.3-4 SidkiFreeAlgebra
  
  > SidkiFreeAlgebra( k ) ____________________________________________function
  
  !!!
  
  ---------------------------  Example  ----------------------------
    gap> !!!
  ------------------------------------------------------------------
  
  
  10.4 Bacher's determinant identities
  
  In   his  paper  [Bac07],  Roland  Bacher  exhibits  striking  formulas  for
  determinants of matrices obtained from binomial coefficients.
  
  The general construction is as follows: let P be an infinite matrix, and let
  P(n)  be  its upper nx n corner. To evaluate det P(n), decompose P=LDR where
  L,D,R  are  respectively  lower  triangular, diagonal, and upper triangular,
  with  1's  on the diagonals of L and R. Then that determinant is the product
  of the first n entries of D.
  
  Bacher  considers  some  natural  examples of matrices arising from binomial
  coefficients,  and  notes  that  the  matrix  P is the limit of a convergent
  vector   element   (see  IsConvergent  (6.1-8)).  He  also  notes  that  the
  decomposition P=LDR may be achieved within vector elements.
  
  As  a  first  example,  consider  the  nx  n  matrix  P(n) with coefficients
  P_s,t=s+t  choose smod 2. Here and below, indices start at 0. Let also ds(n)
  denote the digit-sum of the integer n. Then
  
  
       \det(P(n))=\cases{ (-1)^{n/2} & if $n$ is even,\cr
       (-1)^{(n-1)/2+ds((n-1)/2)} & if $n$ is odd.}
  
  
  For  the  proof,  note  that  P  is  a convergent infinite matrix; it may be
  presented  as a self-similar linear element by FRAlgebra("P=[[P,P],[P,0]]").
  It  then  suffices  to  construct  an LR decomposition of P within FR vector
  elements, following Bacher:
  
  ---------------------------  Example  ----------------------------
    gap> AssignGeneratorVariables(FRAlgebra(Rationals,
        "P=[[P,P],[P,0]]","L=[[L,0],[L,L]]","D=[[D,0],[0,-D]]"));
    gap> L*D*TransposedFRElement(L)=P;
    true
  ------------------------------------------------------------------
  
  and to analyse the elements of the diagonal matrix D.
  
  For  a  more  complicated example, let v_2 denote 2-valuation of a rational,
  and  construct the nx n matrix V(n) with coefficients V_s,t=i^v_2(s+t choose
  s). Then
  
  
       \det(V(n))=\det(P(n))\prod_{k=1}^{n-1}(1-f(k)i),
  
  
  where  f(k)  is  the  regular paper-folding sequence defined by f(2^n)=1 and
  f(2^n+a)=-f(2^n-a) for 1le a<2^n.
  
  This  is  again  proved  by  noticing  that  V is a corner in a self-similar
  element, namely
  
  ---------------------------  Example  ----------------------------
    gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
         "V1=[[V1,V2],[V2,E(4)*V1]]",
         "V2=[[V1,-E(4)*V1+(1+E(4))*V2],[-E(4)*V1+(1+E(4))*V2,-V1]]"));
    gap> Activity(V1,3)=
         List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));
    true
  ------------------------------------------------------------------
  
  The LR decomposition of V=V1 can be checked as follows:
  
  ---------------------------  Example  ----------------------------
    gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
         "L1=[[L1,0],[L3,L4]]",
         "L2=[[0,-E(4)*L2],[-L1+L3,-E(4)*L2-E(4)*L4]]:0",
         "L3=[[L1,L2],[-E(4)*L1+(1+E(4))*L3,L2+(1+E(4))*L4]]",
         "L4=[[L1,0],[(1-E(4))*L1+E(4)*L3,L4]]",
         "D1=[[D1,0],[0,D2]]",
         "D2=[[D3,0],[0,2*D1-D2+2*D3]]:-1+E(4)",
         "D3=[[D3,0],[0,-D2]]:-1+E(4)"));
    gap> L1*D1*TransposedFRElement(L1)=V1;
    true
  ------------------------------------------------------------------
  
  The LR decomposition can also, in favourable situations, be discovered by FR
  through  the  command LDUDecompositionFRElement (6.1-10). This approach will
  be followed below.
  
  For     the     next     example,     consider     "Beeblebrox    reduction"
  beta(4kpm1)=pm1,beta(2k)=0,  and construct the nx n matrix Z(n) (named after
  Zaphod Beeblebrox) with coefficients Z_s,t=beta(s+t choose s). Then
  
  
       \det(Z(n))=\prod_{k=1}^{n-1}g(k),
  
  
  where  g(sum  a_i2^i)=(-1)^a_03^#{i:a_i=a_i+1=1}-#{i:a_i<> a_i+1=1} with all
  a_iin{0,1}.
  
  This  is  again  proved  by  noticing  that  Z is a corner in a self-similar
  element, namely
  
  ---------------------------  Example  ----------------------------
    gap> beta := n->Jacobi(-1,n)*(n mod 2);;
    gap> Zaphod := GuessVectorElement(List([0..7],i->List([0..7],j->beta(Binomial(i+j,j)))));
    <Linear element on alphabet Rationals^2 with 3-dimensional stateset>
    gap> Display(Zaphod);
     Rationals |    1     |    2     |
    -----------+----------+----------+
             1 |  1  0  0 |  0  1  0 |
               |  1  0  0 |  0  1  0 |
               |  1  0  0 |  0 -1  0 |
    -----------+----------+----------+
             2 |  0  0  1 |  0  0  0 |
               |  0  0 -1 |  0  0  0 |
               |  0  0  1 |  0  0  0 |
    -----------+----------+----------+
    Output:  1  1  1
    Initial state:  1  0  0
    gap> LDUDecompositionFRElement(guessZ);
    [ <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
      <Linear element on alphabet Rationals^2 with 2-dimensional stateset>,
      <Linear element on alphabet Rationals^2 with 4-dimensional stateset> ]
    gap> Display(last[2]);
     Rationals |    1    |    2    |
    -----------+---------+---------+
             1 |   1   0 |   0   0 |
               |   3   0 |   0   0 |
    -----------+---------+---------+
             2 |   0   0 |   0   1 |
               |   0   0 |   0 1/3 |
    -----------+---------+---------+
    Output:   1  -1
    Initial state:   1   0
  ------------------------------------------------------------------
  
  and  now  the  recursion  read  on  this  diagonal self-similar matrix gives
  immediately Bacher's recursion for det(Z(n)).
  
  Bacher  notes  that  the group generated by a=L_1,b=L_2/2,c=L_3,d=L_4 in the
  last  example  may  be  of  interest.  A  quick check produces the following
  relations (slightly rewritten):
  
  ---------------------------  Example  ----------------------------
    gap> AssignGeneratorVariables(FRAlgebra(Rationals,
         "a=[[a,0],[c,d]]","b=[[-1/3*a,2*b],[1/3*c,d]]",
         "c=[[a,2*b],[c,d]]","d=[[a,0],[1/3*c,d]]"));
    gap> g := Group(List([a,b,c,d], x->Activity(x,3)));
    <matrix group with 4 generators>
    gap> FindShortGroupRelations(g,10);
    [ b*d^-1*c*a^-1,
      c*a^-1*c*a^-1,
      c*a*d^-1*a^-1*d^2*a^-1*b^-1,
      c*a*d^-1*c^-1*b*d*a^-1*b^-1,
      c*d*a^-2*d*a*d^-1*b^-1,
      c*a^2*d^-1*a^-2*d*a*d*a^-2*b^-1,
      d^2*a*d^-2*b^-1*c*a*d*a^-3,
      c*d*a*d^-2*a^-1*d*a*d*a^-2*b^-1 ]
  ------------------------------------------------------------------
  
  Consider  next  the "triangular Beeblebrox matrix" with entries L_s,t=beta(s
  choose t). The recurrence is now given by
  
  ---------------------------  Example  ----------------------------
    gap> A := FRAlgebra(Rationals,
         "L1=[[L1,0],[L2,L3]]",
         "L2=[[L1,0],[L2,-L3]]",
         "L3=[[L1,0],[-L2,L3]]");
    <self-similar algebra on alphabet Rationals^2 with 3 generators>
  ------------------------------------------------------------------
  
  and  it is striking that A is a graded algebra, with L_1,L_2,L_3 homogeneous
  of  degree  1,  and  each  homogeneous  component  is  3-dimensional; all of
  L_1,L_2,L_3  are  invertible  (with inverses have degree -1), and generate a
  group that admits a faithful 3x 3 linear representation. As a final example,
  Bacher           considers          the          "Jacobi          character"
  chi(8ℤpm1)=1,chi(8ℤpm3)=-1,chi(2ℤ)=0,     and    the    associated    matrix
  J_s,t=chi(s+t  choose  s).  He  gives  an  easily-computed,  but complicated
  formula for det(J(n)). We can recover this formula, as before, by "guessing"
  an LR decomposition for J, which is self-similar and convergent:
  
  ---------------------------  Example  ----------------------------
    gap> chi := function(x)
            if x mod 8 in [1,7] then return 1;
            elif x mod 8 in [3,5] then return -1;
            else return 0; fi;
         end;;
    gap> m := List([0..63],i->List([0..63],j->chi(Binomial(i+j,j))));;
    gap> J := GuessVectorElement(m,2);
    <Linear element on alphabet Rationals^2 with 9-dimensional stateset>
    gap> LDUDecompositionFRElement(J);
    [ <Linear element on alphabet Rationals^2 with 20-dimensional stateset>,
      <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
      <Linear element on alphabet Rationals^2 with 20-dimensional stateset> ]
    gap> time;
    26869
    gap> Display(last2[2]);
     Rationals |        1        |        2        |
    -----------+-----------------+-----------------+
             1 |   1   0   0   0 |   0   0   0   0 |
               |   0   0   1   0 |   0   0   0   0 |
               |   3   0   0   0 |   0   0   0   0 |
               |   0   0   3   0 |   0   0   0   0 |
    -----------+-----------------+-----------------+
             2 |   0   0   0   0 |   0   1   0   0 |
               |   0   0   0   0 |   0   0   0   1 |
               |   0   0   0   0 |   0 1/3   0   0 |
               |   0   0   0   0 |   0   0   0 1/3 |
    -----------+-----------------+-----------------+
    Output:   1  -1   3 -1/3
    Initial state:   1   0   0   0
  ------------------------------------------------------------------
  
  
  10.5 VH groups
  
  [!!! introduction to do]
  
  10.5-1 VHStructure
  
  > VHStructure( g ) ________________________________________________operation
  > IsVHGroup( g ) _____________________________________________________filter
  Returns:  A VH-structure for the group g.
  
  A VH-structure on a group g is a partition of the generators in two sets V,H
  such  that  every  relator of g is of the form vhv'h', and such that for all
  vin V,hin H there exist unique v'in V,h'in H such that vhv'h'=1.
  
  The  VH  structure is stored as a record with fields v,h containing lists of
  generators,    and    integer    matrices   transitions,output   such   that
  transitions[v][h']=v' and output[v][h']=h.
  
  The filter recognizes groups with a VH structure.
  
  ---------------------------  Example  ----------------------------
    true
  ------------------------------------------------------------------
  
  10.5-2 VerticalAction
  
  > VerticalAction( g ) _____________________________________________attribute
  > HorizontalAction( g ) ___________________________________________attribute
  Returns:  A homomorphism to an FR group.
  
  A  group  with  VH  structure admits a vertical action of its subgroup < V>;
  this  is  the  group generated by the automaton MealyMachine(trans,out). The
  function  returns  the  group homomorphism from the subgroup < V> to that FR
  group.
  
  The  horizontal  action  is  that  of  the  dual  automaton (see DualMachine
  (5.2-3)).
  
  ---------------------------  Example  ----------------------------
    true
  ------------------------------------------------------------------
  
  10.5-3 VHGroup
  
  > VHGroup( l1, l2, ... ) ___________________________________________function
  Returns:  A new VH group.
  
  This  function constructs the VH group specified by the squares l1, l2, ....
  Each li is a list of length 4, of the form [v,h,v',h']. Here the entries are
  indices  of  vertical,  respectively horizontal generators, if positive; and
  their inverses if negative.
  
  ---------------------------  Example  ----------------------------
    true
  ------------------------------------------------------------------
  
  10.5-4 IsIrreducibleVHGroup
  
  > IsIrreducibleVHGroup( g ) ________________________________________property
  Returns:  Whether g is an irreducible lattice.
  
  A VH group is irreducible if its projections on both trees is dense.
  
  ---------------------------  Example  ----------------------------
    true
  ------------------------------------------------------------------
  
  10.5-5 MaximalSimpleSubgroup
  
  > MaximalSimpleSubgroup( g ) _______________________________________property
  Returns:  A maximal simple subgroup of g, if possible.
  
  A VH group is never simple, but in favourable cases it admits a finite-index
  simple  subgroup,  see  [BM97].  This  function attempts to construct such a
  subgroup. It returns fail if no such subgroup can be found.
  
  ---------------------------  Example  ----------------------------
    true
  ------------------------------------------------------------------