  
  [1X10 Examples[0X
  
  [5XFR[0m  predefines  a  large  collection of machines and groups. The groups are,
  whenever   possible,  defined  as  state  closures  of  corresponding  Mealy
  machines.
  
  
  [1X10.1 Examples of groups[0X
  
  [1X10.1-1 FullBinaryGroup[0m
  
  [2X> FullBinaryGroup____________________________________________[0Xglobal variable
  [2X> FiniteDepthBinaryGroup( [0X[3Xl[0X[2X ) ______________________________________[0Xfunction
  [2X> FinitaryBinaryGroup________________________________________[0Xglobal variable
  [2X> BoundedBinaryGroup_________________________________________[0Xglobal variable
  [2X> PolynomialGrowthBinaryGroup________________________________[0Xglobal variable
  [2X> FiniteStateBinaryGroup_____________________________________[0Xglobal variable
  
  These   are  the  finitary,  bounded,  polynomial-growth,  finite-state,  or
  unrestricted  groups  acting  on  the  binary  tree.  They  are respectively
  shortcuts        for       [10XFullSCGroup([1..2])[0m,       [10XFullSCGroup([1..2],l)[0m,
  [10XFullSCGroup([1..2],IsFinitaryFRSemigroup)[0m,
  [10XFullSCGroup([1..2],IsBoundedFRSemigroup)[0m,
  [10XFullSCGroup([1..2],IsPolynomialGrowthFRSemigroup)[0m,                       and
  [10XFullSCGroup([1..2],IsFiniteStateFRSemigroup)[0m.
  
  They may be used to draw random elements, or to test membership.
  
  [1X10.1-2 BinaryKneadingGroup[0m
  
  [2X> BinaryKneadingGroup( [0X[3Xangle/ks[0X[2X ) __________________________________[0Xfunction
  [2X> BinaryKneadingMachine( [0X[3Xangle/ks[0X[2X ) ________________________________[0Xfunction
  [6XReturns:[0X  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 [10XG[0m, 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 [10XCorrespondence(G)[0m is a
  function returning, for any rational, the corresponding generator of [10XG[0m.
  
  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 [10XCorrespondence(G)[0m is a
  list of the generators of [10XG[0m.
  
  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
  [10XCorrespondence(G)[0m  is a pair of lists of generators; [10XCorrespondence(G)[1][0m is
  the  preperiod,  and  [10XCorrespondence(G)[2][0m  is  the  period.  The  attribute
  [10XKneadingSequence(G)[0m  returns  the  kneading  sequence,  as a pair of strings
  representing preperiod and period respectively.
  
  As  particular  examples,  [10XBinaryKneadingMachine()[0m  is  the  adding machine;
  [10XBinaryKneadingGroup()[0m is the adding machine; and [10XBinaryKneadingGroup("1")[0m is
  [2XBasilicaGroup[0m ([14X10.1-3[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> BinaryKneadingGroup()=AddingGroup(2);[0X
    [4Xtrue[0X
    [4Xgap> BinaryKneadingGroup(1/3)=BasilicaGroup;[0X
    [4Xtrue[0X
    [4Xgap> g := BinaryKneadingGroup([0,1],[0]);[0X
    [4XBinaryKneadingGroup("01","0")[0X
    [4Xgap> ForAll(Correspondence(g)[1],IsFinitaryFRElement);[0X
    [4Xtrue[0X
    [4Xgap> ForAll(Correspondence(g)[2],IsFinitaryFRElement);[0X
    [4Xfalse[0X
    [4Xgap> ForAll(Correspondence(g)[2],IsBoundedFRElement);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-3 BasilicaGroup[0m
  
  [2X> BasilicaGroup______________________________________________[0Xglobal variable
  
  The  [13XBasilica  group[0m. This is a shortcut for [10XBinaryKneadingGroup("1")[0m. It is
  the  first-discovered  amenable group that is not subexponentially amenable,
  see [BV05] and [GŻ02a].
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> IsBoundedFRSemigroup(BasilicaGroup);[0X
    [4Xtrue[0X
    [4Xgap> pi := EpimorphismFromFreeGroup(BasilicaGroup); F := Source(pi);;[0X
    [4X[ x1, x2 ] -> [ a, b ][0X
    [4Xgap> sigma := GroupHomomorphismByImages(F,F,[F.1,F.2],[F.2,F.1^2]);[0X
    [4X[ x1, x2 ] -> [ x2, x1^2 ][0X
    [4Xgap> ForAll([0..10],i->IsOne(Comm(F.2,F.2^F.1)^(sigma^i*pi)));[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-4 AddingGroup[0m
  
  [2X> AddingGroup( [0X[3Xn[0X[2X ) _________________________________________________[0Xfunction
  [2X> AddingMachine( [0X[3Xn[0X[2X ) _______________________________________________[0Xfunction
  [2X> AddingElement( [0X[3Xn[0X[2X ) _______________________________________________[0Xfunction
  
  The  second  function  constructs the adding machine on the alphabet [10X[1..n][0m.
  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 [10X[1..n][0m. This group is isomorphic to the [10XIntegers[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> Display(AddingElement(3));[0X
    [4X   |  1     2     3[0X
    [4X---+-----+-----+-----+[0X
    [4X a | a,1   a,2   a,3[0X
    [4X b | a,2   a,3   b,1[0X
    [4X---+-----+-----+-----+[0X
    [4XInitial state: b[0X
    [4Xgap> Activity(FRElement(AddingMachine(3),2),2);[0X
    [4X(1,4,7,2,5,8,3,6,9)[0X
    [4Xgap> G := AddingGroup(3);[0X
    [4X<self-similar group over [ 1 .. 3 ] with 1 generator>[0X
    [4Xgap> Size(G);[0X
    [4Xinfinity[0X
    [4Xgap> IsRecurrent(G);[0X
    [4Xtrue[0X
    [4Xgap> IsLevelTransitive(G);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-5 BinaryAddingGroup[0m
  
  [2X> BinaryAddingGroup__________________________________________[0Xglobal variable
  [2X> BinaryAddingMachine________________________________________[0Xglobal variable
  [2X> BinaryAddingElement________________________________________[0Xglobal variable
  
  These  are  respectively  the  same  as [10XAddingGroup(2)[0m, [10XAddingMachine(2)[0m and
  [10XAddingElement(2)[0m.
  
  [1X10.1-6 MixerGroup[0m
  
  [2X> MixerGroup( [0X[3XA, B, f[, g][0X[2X ) _______________________________________[0Xfunction
  [2X> MixerMachine( [0X[3XA, B, f[, g][0X[2X ) _____________________________________[0Xfunction
  [6XReturns:[0X  A Mealy "mixer" machine/group.
  
  The  second function constructs a Mealy "mixer" machine [10Xm[0m. This is a machine
  determined  by  a  permutation  group [3XA[0m, a finitely generated group [3XB[0m, and a
  matrix of homomorphisms from [3XB[0m to [3XA[0m. If [3XA[0m acts on [10X[1..d][0m, then each row of [3Xf[0m
  contains  at  most  d-1  homomorphisms.  The  optional  last  argument is an
  endomorphism of [3XB[0m. If absent, it is treated as the identity map on [3XB[0m.
  
  The  states of the machine are 1, followed by some elements [10Xa[0m of [3XA[0m, followed
  by  as  many  copies  of  some  elements  [10Xb[0m of [3XB[0m as there are rows in [3Xf[0m. The
  elements  in  [3XB[0m  that  are taken is the smallest sublist of [3XB[0m containing its
  generators  and  closed  under  [3Xg[0m.  The elements in [3XA[0m that are taken are the
  generators of [3XA[0m and all images of all taken elements of [3XB[0m under maps in [3Xf[0m.
  
  The transitions from [10Xa[0m are towards 1 and the outputs are the permutations in
  [3XA[0m.  The transitions from [10Xb[0m are periodically given by [3Xf[0m, completed by trivial
  elements, and finally by b^g; the output of [10Xb[0m is trivial.
  
  This construction is described in more detail in [BŠ01] and [BGŠ03].
  
  [10XCorrespondence(m)[0m is a list, with in first position the subset of the states
  that  correspond  to [3XA[0m, in second position the states that correspond to the
  first copy of [3XB[0m, etc.
  
  The  first function constructs the group generated by the mixer machine. For
  examples    see    [2XGrigorchukGroups[0m    ([14X10.1-8[0m),   [2XNeumannGroup[0m   ([14X10.1-19[0m),
  [2XGuptaSidkiGroups[0m ([14X10.1-17[0m), and [2XOtherSpinalGroup[0m ([14X10.1-21[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> grigorchukgroup := MixerGroup(Group((1,2)),Group((1,2)),[0X
    [4X     [[IdentityMapping(Group((1,2)))],[IdentityMapping(Group((1,2)))],[]]));[0X
    [4X<self-similar group over [ 1 .. 2 ] with 4 generators>[0X
    [4Xgap> IdGroup(Group(grigorchukgroup.1,grigorchukgroup.2));[0X
    [4X[ 32, 18 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-7 SunicGroup[0m
  
  [2X> SunicGroup( [0X[3Xphi[0X[2X ) ________________________________________________[0Xfunction
  [2X> Sunicmachine( [0X[3Xphi[0X[2X ) ______________________________________________[0Xfunction
  [6XReturns:[0X  The Sunic machine associated with the polynomial [3Xphi[0m.
  
  A  "Sunic  machine" is a special kind of [2XMixerMachine[0m ([14X10.1-6[0m), 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 [2XGrigorchukGroup[0m ([14X10.1-9[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x := Indeterminate(GF(2));;[0X
    [4Xgap> g := SunicGroup(x^2+x+1);[0X
    [4XSunicGroup(x^2+x+Z(2)^0)[0X
    [4Xgap> g = GrigorchukGroup;[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-8 GrigorchukMachines[0m
  
  [2X> GrigorchukMachines( [0X[3Xomega[0X[2X ) ______________________________________[0Xfunction
  [2X> GrigorchukGroups( [0X[3Xomega[0X[2X ) ________________________________________[0Xfunction
  [6XReturns:[0X  One of the Grigorchuk groups.
  
  This function constructs the Grigorchuk machine or group associated with the
  infinite  sequence  [3Xomega[0m, which is assumed (pre)periodic; [3Xomega[0m is either a
  periodic  list  (see  [2XPeriodicList[0m  ([14X12.1-6[0m)) or a plain list describing the
  period. Entries in the list are integers in [10X[1..3][0m.
  
  These   groups   are  [2XMixerGroup[0m  ([14X10.1-6[0m)s.  The  most  famous  example  is
  [10XGrigorchukGroups([1,2,3])[0m, which is also called [2XGrigorchukGroup[0m ([14X10.1-9[0m).
  
  These  groups  are  all  4-generated  and  infinite.  They  are described in
  [Gri84].  [10XGrigorchukGroups([1])[0m  is  infinite dihedral. If [3Xomega[0m contains at
  least  2  different  digits,  [10XGrigorchukGroups([1])[0m  has  intermediate  word
  growth. If [3Xomega[0m contains all 3 digits, [10XGrigorchukGroups([1])[0m is torsion.
  
  The growth of [10XGrigorchukGroups([1,2])[0m has been studied in [Ers04].
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> G := GrigorchukGroups([1]);[0X
    [4X<self-similar group over [ 1 .. 2 ] with 4 generators>[0X
    [4Xgap> Index(G,DerivedSubgroup(G)); IsAbelian(DerivedSubgroup(G));[0X
    [4X4[0X
    [4Xtrue[0X
    [4Xgap> H := GrigorchukGroups([1,2]);[0X
    [4X<self-similar group over [ 1 .. 2 ] with 4 generators>[0X
    [4Xgap> Order(H.1*H.2);[0X
    [4X8[0X
    [4Xgap> Order(H.1*H.4);[0X
    [4Xinfinity[0X
    [4Xgap> IsSubgroup(H,G);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-9 GrigorchukMachine[0m
  
  [2X> GrigorchukMachine__________________________________________[0Xglobal variable
  [2X> GrigorchukGroup____________________________________________[0Xglobal 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  [10XFRGroup("a=(1,2)","b=<a,c>","c=<a,d>","d=<,b>")[0m,  but is rather
  defined using Mealy elements.
  
  The command [10XEpimorphismFromFpGroup(GrigorchukGroup,n)[0m will will construct an
  approximating  presentation  for the Grigorchuk group, as proven in [Lys85].
  Adding  the relations [10XImage(sigma^(n-2),(a*d)^2)[0m, [10XImage(sigma^(n-1),(a*b)^2)[0m
  and  [10XImage(sigma^(n-2),(a*c)^4)[0m yields the quotient acting on 2^n points, as
  a finitely presented group.
  
  [1X10.1-10 GrigorchukOverGroup[0m
  
  [2X> GrigorchukOverGroup________________________________________[0Xglobal variable
  
  This   is   a   group   strictly   containing   the  Grigorchuk  group  (see
  [2XGrigorchukGroup[0m  ([14X10.1-9[0m)). It also has intermediate growth (see [BG02], but
  it  contains  elements  of  infinite  order.  It  could have been defined as
  [10XFRGroup("a=(1,2)","b=<a,c>","c=<,d>","d=<,b>")[0m,  but is rather defined using
  Mealy elements.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> IsSubgroup(GrigorchukOverGroup,GrigorchukGroup);[0X
    [4Xtrue[0X
    [4Xgap> Order(Product(GeneratorsOfGroup(GrigorchukOverGroup)));[0X
    [4Xinfinity[0X
    [4Xgap> GrigorchukGroup.2=GrigorchukSuperGroup.2*GrigorchukSuperGroup.3;[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  The    command   [10XEpimorphismFromFpGroup(GrigorchukOverGroup,n)[0m   will   will
  construct  an  approximating  presentation  for the Grigorchuk overgroup, as
  proven in [Bar03b].
  
  [1X10.1-11 GrigorchukEvilTwin[0m
  
  [2X> GrigorchukEvilTwin_________________________________________[0Xglobal variable
  
  This   is   a   group  with  same  closure  as  the  Grigorchuk  group  (see
  [2XGrigorchukGroup[0m  ([14X10.1-9[0m)),  but  not  isomorphic  to it. It could have been
  defined  as  [10XFRGroup("a=(1,2)","x=<y,a>","y=<a,z>","z=<,x>")[0m,  but is rather
  defined using Mealy elements.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> AbelianInvariants(GrigorchukEvilTwin);[0X
    [4X[ 2, 2, 2, 2 ][0X
    [4Xgap> AbelianInvariants(GrigorchukGroup);[0X
    [4X[ 2, 2, 2 ][0X
    [4Xgap> PermGroup(GrigorchukGroup,8)=PermGroup(GrigorchukEvilTwin,8);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-12 BrunnerSidkiVieiraGroup[0m
  
  [2X> BrunnerSidkiVieiraGroup____________________________________[0Xglobal variable
  [2X> BrunnerSidkiVieiraMachine__________________________________[0Xglobal variable
  
  This machine is the sum of two adding machines, one in standard form and one
  conjugated  by the element [10Xd[0m described below. The group that it generates is
  described     in    [BSV99].    It    could    have    been    defined    as
  [10XFRGroup("tau=<,tau>(1,2)","mu=<,mu^-1>(1,2)")[0m,  but  is rather defined using
  Mealy elements.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> V := FRGroup("d=<e,e>(1,2)","e=<d,d>");[0X
    [4X<self-similar group over [ 1 .. 2 ] with 2 generators>[0X
    [4Xgap> Elements(V);[0X
    [4X[ <2|identity ...>, <2|e>, <2|d>, <2|e*d> ][0X
    [4Xgap> AssignGeneratorVariables(BrunnerSidkiVieiraGroup);[0X
    [4X#I  Assigned the global variables [ "tau", "mu", "" ][0X
    [4Xgap> List(V,x->tau^x)=[tau,mu,mu^-1,tau^-1];[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-13 AleshinGroups[0m
  
  [2X> AleshinGroups( [0X[3Xl[0X[2X ) _______________________________________________[0Xfunction
  [2X> AleshinMachines( [0X[3Xl[0X[2X ) _____________________________________________[0Xfunction
  [6XReturns:[0X  The Aleshin machine with [10XLength(l)[0m states.
  
  This  function constructs the bireversible machines introduced by Aleshin in
  [Ale83].  The  argument [3Xl[0m is a list of permutations, either [10X()[0m or [10X(1,2)[0m. The
  groups that they generate are contructed as [2XAleshinGroups[0m.
  
  If  [10Xl=[(1,2),(1,2),()][0m,  this  is [2XAleshinGroup[0m ([14X10.1-14[0m). More generally, if
  [10Xl=[(1,2,(1,2),(),...,()][0m  has  odd  length,  this  is  a  free group of rank
  [10XLength(l)[0m, see [VV06].
  
  If  [10Xl=[(1,2),(1,2),...][0m has even length and contains an even number of [10X()[0m's,
  then this is also a free group of rank [10XLength(l)[0m, see [SVV06].
  
  If  [10Xl=[(),(),(1,2)][0m,  this is [2XBabyAleshinGroup[0m ([14X10.1-15[0m). more generally, if
  [10Xl=[(),(),...][0m  has  even length and contains an even number of [10X(1,2)[0m's, then
  this is the free product of [10XLength(l)[0m copies of the order-2 group.
  
  [1X10.1-14 AleshinGroup[0m
  
  [2X> AleshinGroup_______________________________________________[0Xglobal variable
  [2X> AleshinMachine_____________________________________________[0Xglobal variable
  
  This  is  the  first  example  of  non-abelian  free  group. It is the group
  generated by [10XAleshinMachine([(1,2),(1,2),()])[0m. It could have been defined as
  [10XFRGroup("a=<b,c>(1,2)","b=<c,b>(1,2)","c=<a,a>")[0m,   but  is  rather  defined
  using Mealy elements.
  
  [1X10.1-15 BabyAleshinGroup[0m
  
  [2X> BabyAleshinGroup___________________________________________[0Xglobal variable
  [2X> BabyAleshinMachine_________________________________________[0Xglobal variable
  
  There are only two connected, transitive bireversible machines on a 2-letter
  alphabet, with 3 generators: [10XAleshinMachine(3)[0m 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
  [10XFRGroup("a=<b,c>","b=<c,b>","c=<a,a>(1,2)")[0m,  but  is  rather  defined  here
  using Mealy elements.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> K := Kernel(GroupHomomorphismByImagesNC(BabyAleshinGroup,Group((1,2)),[0X
    [4X                 GeneratorsOfGroup(BabyAleshinGroup),[(1,2),(1,2),(1,2)]));[0X
    [4X<self-similar group over [ 1 .. 2 ] with 4 generators>[0X
    [4Xgap> Index(BabyAleshinGroup,K);[0X
    [4X2[0X
    [4Xgap> IsSubgroup(AleshinGroup,K);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-16 SidkiFreeGroup[0m
  
  [2X> SidkiFreeGroup_____________________________________________[0Xglobal 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 [3Xa[0m is state-closed, etc. It is defined
  as [10XFRGroup("a=<a^2,a^t>","t=<,t>(1,2)")]]>[0m.
  
  [1X10.1-17 GuptaSidkiGroups[0m
  
  [2X> GuptaSidkiGroups( [0X[3Xn[0X[2X ) ____________________________________________[0Xfunction
  [2X> GeneralizedGuptaSidkiGroups( [0X[3Xn[0X[2X ) _________________________________[0Xfunction
  [2X> GuptaSidkiMachines( [0X[3Xn[0X[2X ) __________________________________________[0Xfunction
  [6XReturns:[0X  The Gupta-Sidki machine on an [3Xn[0m-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 [3Xn[0m. The special case n=3 is
  defined as [2XGuptaSidkiGroup[0m ([14X10.1-18[0m) and [2XGuptaSidkiMachine[0m ([14X10.1-18[0m).
  
  For n>3, there are (at least) two natural ways to generalize the Gupta-Sidki
  construction:     the     original     one     involves     the    recursion
  [10X"t=<a,a^-1,1,...,1,t>"[0m,   while   the  second  (called  here  `generalized')
  involves  the  recursion [10X"t=<a,a^2,...,a^-1,t>"[0m. A finite L-presentation for
  the  latter  is  implemented.  It is not as computationally efficient as the
  L-presentation  of the normal closure of [10Xt[0m (a subgroup of index p), which is
  an  ascending  L-presented  group.  The  inclusion  of  that subgroup may be
  recoverd via [10XEmbeddingOfAscendingSubgroup(GuptaSidkiGroup)[0m.
  
  [1X10.1-18 GuptaSidkiGroup[0m
  
  [2X> GuptaSidkiGroup____________________________________________[0Xglobal variable
  [2X> GuptaSidkiMachine__________________________________________[0Xglobal variable
  
  This  is  an  infinite,  2-generated,  torsion  3-group.  It could have been
  defined  as [10XFRGroup("a=(1,2,3)","t=<a,a^-1,t>")[0m, but is rather defined using
  Mealy elements.
  
  [1X10.1-19 NeumannGroup[0m
  
  [2X> NeumannGroup( [0X[3XP[0X[2X ) ________________________________________________[0Xfunction
  [2X> NeumannMachine( [0X[3XP[0X[2X ) ______________________________________________[0Xfunction
  [6XReturns:[0X  The Neumann machine/group on the permutation group [3XP[0m.
  
  The  first  function  constructs  the  Neumann  machine  associated  to  the
  permutation      group      [3XP[0m.      It      is      a      shortcut      for
  [10XMixerMachine(P,P,[[IdentityMapping(P)]])[0m.
  
  The second function constructs the Neumann group on the permutation group [3XP[0m.
  These   groups   were   first   considered   in   [Neu86].   In  particular,
  [10XNeumannGroup(PSL(3,2))[0m  is  a  group  of non-uniform exponential growth (see
  [Bar03a]),   and   [10XNeumannGroup(Group((1,2,3)))[0m   is   [2XFabrykowskiGuptaGroup[0m
  ([14X10.1-20[0m).
  
  The  attribute [10XCorrespondence(G)[0m is set to a list of homomorphisms from [3XP[0m to
  the [10XA[0m and [10XB[0m copies of [10XP[0m.
  
  [1X10.1-20 FabrykowskiGuptaGroup[0m
  
  [2X> FabrykowskiGuptaGroup______________________________________[0Xglobal variable
  [2X> FabrykowskiGuptaGroups( [0X[3Xp[0X[2X ) ______________________________________[0Xfunction
  
  This  is  an infinite, 2-generated group of intermediate word growth. It was
  studied   in   [FG85]   and   [FG91].   It   could   have  been  defined  as
  [10XFRGroup("a=(1,2,3)","t=<a,,t>")[0m, 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 [2XNeumannGroup[0m ([14X10.1-19[0m)),
  for which an ascending L-presentation is known.
  
  [1X10.1-21 OtherSpinalGroup[0m
  
  [2X> OtherSpinalGroup___________________________________________[0Xglobal 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 [10XFRGroup("a=(1,2,3)","t=<a,a,t>")[0m,
  but is rather defined using Mealy elements.
  
  [1X10.1-22 GammaPQMachine[0m
  
  [2X> GammaPQMachine( [0X[3Xp, q[0X[2X ) ___________________________________________[0Xfunction
  [2X> GammaPQGroup( [0X[3Xp, q[0X[2X ) _____________________________________________[0Xfunction
  [6XReturns:[0X  The quaternion-based machine / SC group.
  
  The  first  function  constructs a bireversible (see [2XIsBireversible[0m ([14X5.2-7[0m))
  Mealy  machine  based  on quaternions, see [BM00a] and [BM00b]. This machine
  has  p+1 states indexed by integer quaternions of norm [3Xp[0m, and an alphabet of
  size  q+1  indexed by quaternions of norm [3Xq[0m. 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
  [2XStructuralGroup[0m  ([14X3.5-1[0m)  hold up to a sign, when the alphabet/state letters
  are substituted for the appropriate quaternions.
  
  The quaternions themselves can be recovered through [2XCorrespondence[0m ([14X3.5-11[0m),
  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
  [2XStructuralGroup[0m  ([14X3.5-1[0m) of that machine. It has actions on two trees, given
  by  [2XVerticalAction[0m  ([14X10.5-2[0m)  and  [2XHorizontalAction[0m  ([14X10.5-2[0m); the ranges of
  these    actions    are    groups   generated   by   automata,   which   are
  infinitely-transitive  (see  [2XIsInfinitelyTransitive[0m  ([14X7.2-12[0m))  and  free by
  [GM05, Proposition 3.3]; see also [Ale83].
  
  [1X10.1-23 HanoiGroup[0m
  
  [2X> HanoiGroup( [0X[3Xn[0X[2X ) __________________________________________________[0Xfunction
  [6XReturns:[0X  The Hanoi group on an [3Xn[0m pegs.
  
  This  function constructs the Hanoi group on [3Xn[0m pegs. Generators of the group
  correspond   to   moving   a  peg,  and  tree  vertices  correspond  to  peg
  configurations. This group is studied in [GŠ06].
  
  [1X10.1-24 DahmaniGroup[0m
  
  [2X> DahmaniGroup_______________________________________________[0Xglobal variable
  
  This  is an example of a non-contracting weakly branched group. It was first
  studied     in     [Dah05].     It    could    have    been    defined    as
  [10XFRGroup("a=<c,a>(1,2)","b=<b,a>(1,2)","c=<b,c>")[0m,   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
  [10XFRElement(1,Comm(a,b))=Comm(c^-1,b/a)[0m,   [10XFRElement(1,Comm(a,c))=Comm(a/b,c)[0m,
  [10XFRElement(1,Comm(b,c))=Comm(c,(a/b)^c)[0m.
  
  [1X10.1-25 MamaghaniGroup[0m
  
  [2X> MamaghaniGroup_____________________________________________[0Xglobal variable
  
  This  group  was  studied in [Mam03]. It is fractal, but not contracting. It
  could              have              been             defined             as
  [10XFRGroup("a=<,b>(1,2)","b=<a,c>","c=<a,a^-1>(1,2)")]]>[0m, but is rather defined
  using  Mealy  elements.  It  partially  admits  branching  on  its  subgroup
  [10XSubgroup(G,[a^2,(a^2)^b,(a^2)^c])[0m,    and,    setting    [10Xx=Comm(a^2,b)[0m,   on
  [10XSubgroup(G,[x,x^a,x^b,x^(b*a),x^(b/a)])[0m. One has [10XFRElement(1,x)=(x^-1)^b/x[0m.
  
  [1X10.1-26 WeierstrassGroup[0m
  
  [2X> WeierstrassGroup___________________________________________[0Xglobal 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.
  
  [1X10.1-27 FRAffineGroup[0m
  
  [2X> FRAffineGroup( [0X[3Xd, R, u[, transversal][0X[2X ) _________________________[0Xoperation
  [6XReturns:[0X  The [3Xd[0m-dimensional affine group over [3XR[0m.
  
  This function constructs a new FR group [10XG[0m, which is finite-index subgroup of
  the  [3Xd[0m-dimensional affine group over R_u, the local ring over [3XR[0m in which all
  non-multiples  of [3Xu[0m are invertible. Since no generators of [10XG[0m are known, [10XG[0m is
  in  fact  returned as a full SC group; only its attribute [10XCorrespondence(G)[0m,
  which is a homomorphism from GL_d+1(R_u) to [10XG[0m, 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 [10XR=Integers[0m and [10XR=PolynomialRing(S)[0m for a finite
  ring  [10XS[0m.  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 [2XCayleyGroup[0m ([14X10.1-28[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> A := FRAffineGroup(1,Integers,3);[0X
    [4X<self-similar group over [ 1 .. 3 ]>[0X
    [4Xgap> f := Correspondence(A);[0X
    [4XMappingByFunction( ( Integers^[0X
    [4X[ 2, 2 ] ), <self-similar group over [ 1 .. 3 ]>, function( mat ) ... end )[0X
    [4Xgap> BaumslagSolitar := Group([[2,0],[0,1]]^f,[[1,0],[1,1]]^f);[0X
    [4X<self-similar group over [ 1 .. 3 ] with 2 generators>[0X
    [4Xgap> BaumslagSolitar.2^BaumslagSolitar.1=BaumslagSolitar.2^2;[0X
    [4Xtrue[0X
    [4Xgap> R := PolynomialRing(GF(2));;[0X
    [4Xgap> A := FRAffineGroup(1,R,R.1);;[0X
    [4Xgap> f := Correspondence(A);;[0X
    [4Xgap> Lamplighter := Group(([[1+R.1,0],[0,1]]*One(R))^f,([[1,0],[1,1]]*One(R))^f);[0X
    [4X<self-similar group over [ 1 .. 2 ] with 2 generators>[0X
    [4Xgap> Lamplighter = CayleyGroup(Group((1,2)));[0X
    [4Xtrue[0X
    [4Xgap> StructureDescription(Group(Lamplighter.2,Lamplighter.2^Lamplighter.1));    [0X
    [4X"C2 x C2"[0X
    [4Xgap> ForAll([1..10],i->IsOne(Comm(Lamplighter.2,Lamplighter.2^(Lamplighter.1^i))));[0X
    [4Xtrue[0X
    [4Xgap> A := FRAffineGroup(2,Integers,2);;[0X
    [4Xgap> f := Correspondence(A);;[0X
    [4Xgap> a := [[1,4,0],[2,3,0],[1,0,1]];[0X
    [4X[ [ 1, 4, 0 ], [ 2, 3, 0 ], [ 1, 0, 1 ] ][0X
    [4Xgap> b := [[1,2,0],[4,3,0],[0,1,1]];[0X
    [4X[ [ 1, 2, 0 ], [ 4, 3, 0 ], [ 0, 1, 1 ] ][0X
    [4Xgap> Display(b^f);[0X
    [4X    |   1      2[0X
    [4X----+------+------+[0X
    [4X  a |  b,1    c,2[0X
    [4X  b |  d,2    e,1[0X
    [4X  c |  a,2    f,1[0X
    [4X...[0X
    [4X bh | cb,1   be,2[0X
    [4X ca | bd,1   bf,2[0X
    [4X cb | ae,2   bh,1[0X
    [4X----+------+------+[0X
    [4XInitial state:  a[0X
    [4Xgap> a^f*b^f=(a*b)^f;[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.1-28 CayleyGroup[0m
  
  [2X> CayleyGroup( [0X[3XG[0X[2X ) _________________________________________________[0Xfunction
  [2X> CayleyMachine( [0X[3XG[0X[2X ) _______________________________________________[0Xfunction
  [2X> LamplighterGroup( [0X[3XG[0X[2X ) ___________________________________________[0Xoperation
  [6XReturns:[0X  The Cayley machine/group of the group [3XG[0m.
  
  The  [13XCayley  machine[0m  of  a  group [3XG[0m is a machine with alphabet and stateset
  equal to [3XG[0m, and with output and transition functions given by multiplication
  in the group, in the order [10Xstate*letter[0m.
  
  The   second   function  constructs  a  new  FR  group  CG,  which  acts  on
  [10X[1..Size(G)][0m.  Its  generators  are in bijection with the elements of [3XG[0m, and
  have  as  output  the  corresponding  permutation  of  [3XG[0m  induced  by  right
  multiplication,  and  as  transitions  all elements of [3XG[0m; see [2XCayleyMachine[0m.
  This construction was introduced in [SS05].
  
  If  [3XG[0m  is an abelian group, CG is the wreath product Gwr Z; it is created by
  the constructor [10XLamplighterGroup(IsFRGroup,G)[0m.
  
  The   attribute   [10XCorrespondence(CG)[0m  is  a  list.  Its  first  entry  is  a
  homomorphism  from  [3XG[0m  into [10XCG[0m. Its second entry is the generator of [10XCG[0m that
  has  trivial  output. [10XCG[0m is generated [10XCorrespondence(CG)[2][0m and the image of
  [10XCorrespondence(CG)[1][0m.
  
  In the example below, recall the definition of [10XLamplighter[0m in the example of
  [2XFRAffineGroup[0m ([14X10.1-27[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> L := CayleyGroup(Group((1,2)));[0X
    [4XCayleyGroup(Group( [ (1,2) ] ))[0X
    [4Xgap> L=LamplighterGroup(IsFRGroup,CyclicGroup(2));[0X
    [4Xtrue[0X
    [4Xgap> (1,2)^Correspondence(L)[1];[0X
    [4X<Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>[0X
    [4Xgap> IsFinitaryFRElement(last); Display(last2);[0X
    [4Xtrue[0X
    [4X   |  1     2[0X
    [4X---+-----+-----+[0X
    [4X a | b,2   b,1[0X
    [4X b | b,1   b,2[0X
    [4X---+-----+-----+[0X
    [4XInitial state: a[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X10.2 Examples of semigroups[0X
  
  [1X10.2-1 I2Machine[0m
  
  [2X> I2Machine__________________________________________________[0Xglobal variable
  [2X> I2Monoid___________________________________________________[0Xglobal 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 [2XSCSemigroup[0m ([14X7.1-2[0m).
  
  [1X10.2-2 I4Machine[0m
  
  [2X> I4Machine__________________________________________________[0Xglobal variable
  [2X> I4Monoid___________________________________________________[0Xglobal 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 [2XSCMonoid[0m ([14X7.1-2[0m).
  
  
  [1X10.3 Examples of algebras[0X
  
  [1X10.3-1 PSZAlgebra[0m
  
  [2X> PSZAlgebra( [0X[3Xk[0X[2X ) __________________________________________________[0Xfunction
  
  This function creates an associative algebra [10XA[0m, over the field [3Xk[0m of positive
  characteristic,   generated   by  two  derivations  [10Xu,v[0m.  This  algebra  has
  polynomial growth, and is not nilpotent. Petrogradsky showed in [Pet06] that
  the  Lie  subalgebra  of [10XPSZAlgebra(GF(2))[0m generated by v,[u,v] is nil; this
  result was generalized by Shestakov and Zelmanov in [SZ08] to arbitrary [3Xk[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> a := PSZAlgebra(2);[0X
    [4XPSZAlgebra(GF(2))[0X
    [4Xgap> Nillity(a.1); Nillity(a.2);[0X
    [4X2[0X
    [4X4[0X
    [4Xgap> IsNilpotentElement(LieBracket(a.1,a.2));[0X
    [4Xtrue[0X
    [4Xgap> DecompositionOfFRElement(LieBracket(a.1,a.2))=DiagonalMat([a.2,a.2]);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.3-2 GrigorchukThinnedAlgebra[0m
  
  [2X> GrigorchukThinnedAlgebra( [0X[3Xk[0X[2X ) ____________________________________[0Xfunction
  
  This  function  creates  the  associative  envelope  [10XA[0m, over the field [3Xk[0m, of
  Grigorchuk's group [2XGrigorchukGroup[0m ([14X10.1-9[0m). !!!
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> !!![0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.3-3 GuptaSidkiThinnedAlgebra[0m
  
  [2X> GuptaSidkiThinnedAlgebra( [0X[3Xk[0X[2X ) ____________________________________[0Xfunction
  
  This  function  creates  the  associative  envelope  [10XA[0m, over the field [3Xk[0m, of
  Gupta-Sidki's group [2XGuptaSidkiGroup[0m ([14X10.1-18[0m). !!!
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> !!![0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.3-4 SidkiFreeAlgebra[0m
  
  [2X> SidkiFreeAlgebra( [0X[3Xk[0X[2X ) ____________________________________________[0Xfunction
  
  !!!
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> !!![0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X10.4 Bacher's determinant identities[0X
  
  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  [2XIsConvergent[0m  ([14X6.1-8[0m)).  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 [10XFRAlgebra("P=[[P,P],[P,0]]")[0m.
  It  then  suffices  to  construct  an LR decomposition of P within FR vector
  elements, following Bacher:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> AssignGeneratorVariables(FRAlgebra(Rationals,[0X
    [4X    "P=[[P,P],[P,0]]","L=[[L,0],[L,L]]","D=[[D,0],[0,-D]]"));[0X
    [4Xgap> L*D*TransposedFRElement(L)=P;[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  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
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,[0X
    [4X     "V1=[[V1,V2],[V2,E(4)*V1]]",[0X
    [4X     "V2=[[V1,-E(4)*V1+(1+E(4))*V2],[-E(4)*V1+(1+E(4))*V2,-V1]]"));[0X
    [4Xgap> Activity(V1,3)=[0X
    [4X     List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  The LR decomposition of V=V1 can be checked as follows:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,[0X
    [4X     "L1=[[L1,0],[L3,L4]]",[0X
    [4X     "L2=[[0,-E(4)*L2],[-L1+L3,-E(4)*L2-E(4)*L4]]:0",[0X
    [4X     "L3=[[L1,L2],[-E(4)*L1+(1+E(4))*L3,L2+(1+E(4))*L4]]",[0X
    [4X     "L4=[[L1,0],[(1-E(4))*L1+E(4)*L3,L4]]",[0X
    [4X     "D1=[[D1,0],[0,D2]]",[0X
    [4X     "D2=[[D3,0],[0,2*D1-D2+2*D3]]:-1+E(4)",[0X
    [4X     "D3=[[D3,0],[0,-D2]]:-1+E(4)"));[0X
    [4Xgap> L1*D1*TransposedFRElement(L1)=V1;[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  The LR decomposition can also, in favourable situations, be discovered by [5XFR[0m
  through  the  command [2XLDUDecompositionFRElement[0m ([14X6.1-10[0m). 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
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> beta := n->Jacobi(-1,n)*(n mod 2);;[0X
    [4Xgap> Zaphod := GuessVectorElement(List([0..7],i->List([0..7],j->beta(Binomial(i+j,j)))));[0X
    [4X<Linear element on alphabet Rationals^2 with 3-dimensional stateset>[0X
    [4Xgap> Display(Zaphod);[0X
    [4X Rationals |    1     |    2     |[0X
    [4X-----------+----------+----------+[0X
    [4X         1 |  1  0  0 |  0  1  0 |[0X
    [4X           |  1  0  0 |  0  1  0 |[0X
    [4X           |  1  0  0 |  0 -1  0 |[0X
    [4X-----------+----------+----------+[0X
    [4X         2 |  0  0  1 |  0  0  0 |[0X
    [4X           |  0  0 -1 |  0  0  0 |[0X
    [4X           |  0  0  1 |  0  0  0 |[0X
    [4X-----------+----------+----------+[0X
    [4XOutput:  1  1  1[0X
    [4XInitial state:  1  0  0[0X
    [4Xgap> LDUDecompositionFRElement(guessZ);[0X
    [4X[ <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,[0X
    [4X  <Linear element on alphabet Rationals^2 with 2-dimensional stateset>,[0X
    [4X  <Linear element on alphabet Rationals^2 with 4-dimensional stateset> ][0X
    [4Xgap> Display(last[2]);[0X
    [4X Rationals |    1    |    2    |[0X
    [4X-----------+---------+---------+[0X
    [4X         1 |   1   0 |   0   0 |[0X
    [4X           |   3   0 |   0   0 |[0X
    [4X-----------+---------+---------+[0X
    [4X         2 |   0   0 |   0   1 |[0X
    [4X           |   0   0 |   0 1/3 |[0X
    [4X-----------+---------+---------+[0X
    [4XOutput:   1  -1[0X
    [4XInitial state:   1   0[0X
  [4X------------------------------------------------------------------[0X
  
  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):
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> AssignGeneratorVariables(FRAlgebra(Rationals,[0X
    [4X     "a=[[a,0],[c,d]]","b=[[-1/3*a,2*b],[1/3*c,d]]",[0X
    [4X     "c=[[a,2*b],[c,d]]","d=[[a,0],[1/3*c,d]]"));[0X
    [4Xgap> g := Group(List([a,b,c,d], x->Activity(x,3)));[0X
    [4X<matrix group with 4 generators>[0X
    [4Xgap> FindShortGroupRelations(g,10);[0X
    [4X[ b*d^-1*c*a^-1,[0X
    [4X  c*a^-1*c*a^-1,[0X
    [4X  c*a*d^-1*a^-1*d^2*a^-1*b^-1,[0X
    [4X  c*a*d^-1*c^-1*b*d*a^-1*b^-1,[0X
    [4X  c*d*a^-2*d*a*d^-1*b^-1,[0X
    [4X  c*a^2*d^-1*a^-2*d*a*d*a^-2*b^-1,[0X
    [4X  d^2*a*d^-2*b^-1*c*a*d*a^-3,[0X
    [4X  c*d*a*d^-2*a^-1*d*a*d*a^-2*b^-1 ][0X
  [4X------------------------------------------------------------------[0X
  
  Consider  next  the "triangular Beeblebrox matrix" with entries L_s,t=beta(s
  choose t). The recurrence is now given by
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> A := FRAlgebra(Rationals,[0X
    [4X     "L1=[[L1,0],[L2,L3]]",[0X
    [4X     "L2=[[L1,0],[L2,-L3]]",[0X
    [4X     "L3=[[L1,0],[-L2,L3]]");[0X
    [4X<self-similar algebra on alphabet Rationals^2 with 3 generators>[0X
  [4X------------------------------------------------------------------[0X
  
  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:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> chi := function(x)[0X
    [4X        if x mod 8 in [1,7] then return 1;[0X
    [4X        elif x mod 8 in [3,5] then return -1;[0X
    [4X        else return 0; fi;[0X
    [4X     end;;[0X
    [4Xgap> m := List([0..63],i->List([0..63],j->chi(Binomial(i+j,j))));;[0X
    [4Xgap> J := GuessVectorElement(m,2);[0X
    [4X<Linear element on alphabet Rationals^2 with 9-dimensional stateset>[0X
    [4Xgap> LDUDecompositionFRElement(J);[0X
    [4X[ <Linear element on alphabet Rationals^2 with 20-dimensional stateset>,[0X
    [4X  <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,[0X
    [4X  <Linear element on alphabet Rationals^2 with 20-dimensional stateset> ][0X
    [4Xgap> time;[0X
    [4X26869[0X
    [4Xgap> Display(last2[2]);[0X
    [4X Rationals |        1        |        2        |[0X
    [4X-----------+-----------------+-----------------+[0X
    [4X         1 |   1   0   0   0 |   0   0   0   0 |[0X
    [4X           |   0   0   1   0 |   0   0   0   0 |[0X
    [4X           |   3   0   0   0 |   0   0   0   0 |[0X
    [4X           |   0   0   3   0 |   0   0   0   0 |[0X
    [4X-----------+-----------------+-----------------+[0X
    [4X         2 |   0   0   0   0 |   0   1   0   0 |[0X
    [4X           |   0   0   0   0 |   0   0   0   1 |[0X
    [4X           |   0   0   0   0 |   0 1/3   0   0 |[0X
    [4X           |   0   0   0   0 |   0   0   0 1/3 |[0X
    [4X-----------+-----------------+-----------------+[0X
    [4XOutput:   1  -1   3 -1/3[0X
    [4XInitial state:   1   0   0   0[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X10.5 VH groups[0X
  
  [!!! introduction to do]
  
  [1X10.5-1 VHStructure[0m
  
  [2X> VHStructure( [0X[3Xg[0X[2X ) ________________________________________________[0Xoperation
  [2X> IsVHGroup( [0X[3Xg[0X[2X ) _____________________________________________________[0Xfilter
  [6XReturns:[0X  A VH-structure for the group [3Xg[0m.
  
  A [13XVH-structure[0m on a group [3Xg[0m is a partition of the generators in two sets V,H
  such  that  every  relator of [3Xg[0m 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 [10Xv,h[0m containing lists of
  generators,    and    integer    matrices   [10Xtransitions,output[0m   such   that
  [10Xtransitions[v][h']=v'[0m and [10Xoutput[v][h']=h[0m.
  
  The filter recognizes groups with a VH structure.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.5-2 VerticalAction[0m
  
  [2X> VerticalAction( [0X[3Xg[0X[2X ) _____________________________________________[0Xattribute
  [2X> HorizontalAction( [0X[3Xg[0X[2X ) ___________________________________________[0Xattribute
  [6XReturns:[0X  A homomorphism to an FR group.
  
  A  group  with  VH  structure admits a [13Xvertical action[0m of its subgroup < V>;
  this  is  the  group generated by the automaton [10XMealyMachine(trans,out)[0m. The
  function  returns  the  group homomorphism from the subgroup < V> to that FR
  group.
  
  The  horizontal  action  is  that  of  the  dual  automaton (see [2XDualMachine[0m
  ([14X5.2-3[0m)).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.5-3 VHGroup[0m
  
  [2X> VHGroup( [0X[3Xl1, l2, ...[0X[2X ) ___________________________________________[0Xfunction
  [6XReturns:[0X  A new VH group.
  
  This  function constructs the VH group specified by the squares [3Xl1, l2, ...[0m.
  Each [3Xli[0m is a list of length 4, of the form [10X[v,h,v',h'][0m. Here the entries are
  indices  of  vertical,  respectively horizontal generators, if positive; and
  their inverses if negative.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.5-4 IsIrreducibleVHGroup[0m
  
  [2X> IsIrreducibleVHGroup( [0X[3Xg[0X[2X ) ________________________________________[0Xproperty
  [6XReturns:[0X  Whether [3Xg[0m is an irreducible lattice.
  
  A VH group is [13Xirreducible[0m if its projections on both trees is dense.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X10.5-5 MaximalSimpleSubgroup[0m
  
  [2X> MaximalSimpleSubgroup( [0X[3Xg[0X[2X ) _______________________________________[0Xproperty
  [6XReturns:[0X  A maximal simple subgroup of [3Xg[0m, 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 [9Xfail[0m if no such subgroup can be found.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
