[Up] [Previous] [Index]
5 Miscellaneous
Sections
 Converters to and from FR package
 Trees
 Some predefined groups
In this chapter we present the functionality that does not quite fit in other chapters and the list of predefined groups and semigroups.
FR2AutomGrp(
G ) O
This operation is designed to convert data structures defined in FR
package written by Laurent Bartholdi to corresponding structures in
AutomGrp package. Currently it is implemented for functionally recursive
groups, semigroups, and their sub(semi)groups and elements.
gap> ZZ := FRGroup("t=<,t>[2,1]");
<stateclosed group over [ 1 .. 2 ] with 1 generator>
gap> AZZ := FR2AutomGrp(ZZ);
< t >
gap> Display(AZZ);
< t = (1, t)(1,2) >
gap> i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");
<stateclosed monoid over [ 1 .. 2 ] with 2 generators>
gap> Ai4 := FR2AutomGrp(i4);
< 1, s, f >
gap> Display(Ai4);
< 1 = (1, 1),
s = (1, 1)(1,2),
f = (s, f)[1,1] >
gap> S := FRGroup("a=<a*b^2,b^3>(1,2)","b=<b^1*a,1>");
<stateclosed group over [ 1 .. 2 ] with 2 generators>
gap> AS := FR2AutomGrp(S);
< a, b >
gap> Display(AS);
< a = (a*b^2, b^3)(1,2),
b = (b^1*a, 1) >
gap> AssignGeneratorVariables(S);
#I Assigned the global variables [ "a", "b" ]
gap> x := a^3*b*a^2;
<2a^3*b*a^2>
gap> DecompositionOfFRElement(x);
[ [ <2a*b^2>, <2b^3*a^2*b^1*a^1> ], [ 2, 1 ] ]
gap> y := FR2AutomGrp(x);
a^3*b*a^2
gap> Decompose(y);
(a*b^2, b^3*a^2*b^1*a^1)(1,2)
AutomGrp2FR(
G ) O
This operation is designed to convert data structures defined in AutomGrp
to corresponding structures in AutomGrp package written by Laurent
Bartholdi. Currently it is implemented for automaton and selfsimilari
(or, functionally recursive in L.Bartholdi's terminology) groups,
semigroups, their sub(semi)groups and elements.
gap> G:=AutomatonGroup("a=(b,a)(1,2),b=(a,b)");
< a, b >
gap> FG := AutomGrp2FR(G);
<stateclosed group over [ 1 .. 2 ] with 2 generators>
gap> DecompositionOfFRElement(FG.1);
[ [ <2b>, <2a> ], [ 2, 1 ] ]
gap> DecompositionOfFRElement(FG.2);
[ [ <2a>, <2b> ], [ 1, 2 ] ]
gap> G := SelfSimilarGroup("a=(a*b^2,b)(1,2),b=(b^2,a*b*a^2)");
< a, b >
gap> F := AutomGrp2FR(G);
<stateclosed group over [ 1 .. 2 ] with 2 generators>
gap> DecompositionOfFRElement(F.1);
[ [ <2a*b^2>, <2b> ], [ 2, 1 ] ]
gap> G := AutomatonGroup("a=(b,a)(1,2),b=(a,b),c=(c,a)(1,2)");
< a, b, c >
gap> H := Group([a*b,b*c^2,a]);
< a*b, b*c^2, a >
gap> FH := AutomGrp2FR(H);
<recursive group over [ 1 .. 2 ] with 3 generators>
gap> DecompositionOfFRElement(FH.1);
[ [ <2b^2>, <2a^2> ], [ 2, 1 ] ]
gap> G := SelfSimilarSemigroup("a=(a*b^2,b*a)[1,1],b=(b,a*b*a)(1,2)");
< a, b >
gap> S := AutomGrp2FR(G);
<stateclosed semigroup over [ 1 .. 2 ] with 2 generators>
gap> DecompositionOfFRElement(S.1);
[ [ <2a*b^2>, <2b*a> ], [ 1, 1 ] ]
gap> G := AutomatonGroup("a=(b,a)(1,2),b=(a,b),c=(c,a)(1,2)");
< a, b, c >
gap> Decompose(a*b^2);
(b^1, a^1)(1,2)
gap> x := AutomGrp2FR(a*b^2);
<2a*b^2>
gap> DecompositionOfFRElement(x);
[ [ <2b^1>, <2a^1> ], [ 2, 1 ] ]
NumberOfVertex(
ver,
deg ) F
One can naturally enumerate all the vertices of the nth level of the tree
by the numbers 1,…,deg ^{n }.
This function returns the number that corresponds to the vertex ver
of the degary tree. The vertex can be defined either as a list or as a string.
gap> NumberOfVertex([1,2,1,2], 2);
6
gap> NumberOfVertex("333", 3);
27
VertexNumber(
num,
lev,
deg ) F
One can naturally enumerate all the vertices of the levth level of
the degary tree by the numbers 1,…,deg ^{n }.
This function returns the vertex of this level that has number num.
gap> VertexNumber(1, 3, 2);
[ 1, 1, 1 ]
gap> VertexNumber(4, 4, 3);
[ 1, 1, 2, 1 ]
Several groups are predefined as fields in the global variable
AG_Groups
. Here is how to access, for example, Grigorchuk group
gap> G:=AG_Groups.GrigorchukGroup;
< a, b, c, d >
To perform operations with elements of G
one can use AssignGeneratorVariables
function.
gap> AssignGeneratorVariables(G);
#I Global variable `a' is already defined and will be overwritten
#I Global variable `b' is already defined and will be overwritten
#I Global variable `c' is already defined and will be overwritten
#I Global variable `d' is already defined and will be overwritten
#I Assigned the global variables [ a, b, c, d ]
gap> Decompose(a*b);
(c, a)(1,2)
Below is a list of all predefined groups with short description and references.
GrigorchukGroup V
is the first Grigorchuk group, an infinite 2group of intermediate growth constructed
in Gri80 (see Gri05 for a survey on this group). It is
defined as the group generated by the automaton
a=(1,1)(1,2), b=(a,c), c=(a,d), d=(1,b). 

The group is stored in the global variable AG_Groups.GrigorchukGroup
UniversalGrigorchukGroup V
is the universal group for the family of groups G_{ω} (see Gri84). It is
defined as a group acting on the 6ary tree, generated by the automaton
a=(1,1,1,1,1,1)(1,2), b=(a,a,1,b,b,b), c=(a,1,a,c,c,c), d=(1,a,a,d,d,d). 

The group is stored in the global variable AG_Groups.UniversalGrigorchukGroup
Basilica V
is the Basilica group. It was first studied in GZ02a and
GZ02b. Later it became the first example of amenable, but not subexponentially
amenable group (see BV05). It is the iterated monodromy group of the map f(z)=z^{2}−1.
It is generated by the automaton
The group is stored in the global variable AG_Groups.Basilica
Lamplighter V
is the lamplighter group. This group was the key ingredient in the counterexample
to the strong Atiyah conjecture (see GLSZ00). It is generated by the automaton
The group is stored in the global variable AG_Groups.Lamplighter
AddingMachine V
is the free abelian group of rank 1 (see GNS00) generated by the automaton
The group is stored in the global variable AG_Groups.AddingMachine
InfiniteDihedral V
is the infinite dihedral group (see GNS00) generated by the automaton
The group is stored in the global variable AG_Groups.InfiniteDihedral
AleshinGroup V
is a group generated by the Aleshin automaton (see Ale83) defined by the
following wreath recursion:
a=(b,c)(1,2), b=(c,b)(1,2), c=(a,a). 

It is isomorphic to the free group of rank 3 as was proved by M.Vorobets and
Y.Vorobets (see VV05).
The group is stored in the global variable AG_Groups.AleshinGroup
Bellaterra V
is a group generated by the Aleshin automaton (see Ale83) defined by the
following wreath recursion:
a=(c,c)(1,2), b=(a,b), c=(b,a). 

It is isomorphic to the free product of 3 cyclic groups of order 2 (see BGK07)
The group is stored in the global variable AG_Groups.Bellaterra
SushchanskyGroup V
is the selfsimilar closure of the faithful leveltransitive action of the Sushchansky group on the
ternary tree. The original groups constructed in Sus79 are infinite pgroups
of intermediate growth acting on the pary tree. In BS07 the action of these
groups on the tree was simplified, so that, in particular, the selfsimilar closure of one of the 3groups
is generated by the automaton
A=(1,1,1)(1,2,3), A^{2}=(1,1,1)(1,3,2), B=(r_{1},q_{1},A), 

r_{1}=(r_{2},A,1), r_{2}=(r_{3},1,1), r_{3}=(r_{4},1,1), 

r_{4}=(r_{5},A,1), r_{5}=(r_{6},A^{2},1), r_{6}=(r_{7},A,1), 

r_{7}=(r_{8},A,1), r_{8}=(r_{9},A,1), r_{9}=(r_{1},A^{2},1), 

q_{1}=(q_{2},1,1), q_{2}=(q_{3},A,1), q_{3}=(q_{1},A,1). 

The group 〈A,B〉 is isomorphic to the original Sushchansky 3group.
The group is stored in the global variable AG_Groups.SushchanskyGroup
Hanoi3 V
Hanoi4 V
Groups related to the Hanoi towers game on 3 and 4 pegs correspondingly
(see GS06a and GS06b).
For 3 pegs Hanoi3
is generated by the automaton
a_{23}=(a_{23},1,1)(2,3), a_{13}=(1,a_{13},1)(1,3), a_{12}=(1,1,a_{12})(1,2), 

while the automaton generating Hanoi4
is
a_{12}=(1,1,a_{12},a_{12})(1,2), a_{13}=(1,a_{13},1,a_{13})(1,3), a_{14}=(1,a_{14},a_{14},1)(1,4), 

a_{23}=(a_{23},1,1,a_{23})(2,3), a_{24}=(a_{24},1,a_{24},1)(2,4), a_{34}=(a_{34},a_{34},1,1)(3,4). 

The groups are stored in the global variables AG_Groups.Hanoi3
and AG_Groups.Hanoi4
GuptaSidki3Group V
is the GuptaSidki infinite 3group constructed in GS83 and generated by the automaton
a=(1,1,1)(1,2,3), b=(a,a^{−1},b). 

The group is stored in the global variable AG_Groups.GuptaSidki3Group
GuptaFabrikowskiGroup V
is the GuptaFabrykowski group of intermediate growth constructed in FG85 and
generated by the automaton
a=(1,1,1)(1,2,3), b=(a,1,b). 

The group is stored in the global variable AG_Groups.GuptaFabrikowskiGroup
BartholdiGrigorchukGroup V
is the BartholdiGrigorchuk group studied in BG02 and generated by the automaton
a=(1,1,1)(1,2,3), b=(a,a,b). 

The group is stored in the global variable AG_Groups.BartholdiGrigorchukGroup
GrigorchukErschlerGroup V
is the group of subexponential growth studied by Erschler in Ers04.
It grows faster than exp(n^{α}) for any α < 1. It belongs to the class of groups
constructed by Grigorchuk in Gri84 and corresponds to the sequence 01010101….
It is generated by the automaton
a=(1,1)(1,2), b=(a,b), c=(a,d), d=(1,c). 

The group is stored in the global variable AG_Groups.GrigorchukErschlerGroup
BartholdiNonunifExponGroup V
is the group of nonuniformly exponential growth constructed by Bartholdi in Bar03. Similar
examples were constructed earlier in Wil04 by Wilson. It is generated by the automaton
x=(1,1,1,1,1,1,1)(1,5)(3,7), y=(1,1,1,1,1,1,1)(2,3)(6,7), z=(1,1,1,1,1,1,1)(4,6)(5,7), 

x_{1}=(x_{1},x,1,1,1,1,1), y_{1}=(y_{1},y,1,1,1,1,1), z_{1}=(z_{1},z,1,1,1,1,1). 

The group is stored in the global variable AG_Groups.BartholdiNonunifExponGroup
IMG_z2plusI V
The iterated monodromy group of the map f(z)=z^{2}+i. It has intermediate growth (see BP06)
and was studied in GSS07.
a=(1,1)(1,2), b=(a,c), c=(b,1). 

The group is stored in the global variable AG_Groups.IMG_z2plusI
Airplane V
Rabbit V
These are iterated monodromy groups of certain quadratic polynomials studied in BN06.
It was proved there that they are not isomorphic. The automata generating them are the following
a=(b,1)(1,2), b=(c,1), c=(a,1); 

a=(b,1)(1,2), b=(1,c), c=(a,1). 

The groups are stored in the global variables AG_Groups.Airplane
and AG_Groups.Rabbit
TwoStateSemigroupOfIntermediateGrowth V
is the semigroup of intermediate growth studied in BRS06. It is generated by the automaton
f_{0}=(f_{0},f_{0})(1,2), f_{1}=(f_{1},f_{0})[2,2]· 

The group is stored in the global variable AG_Groups.TwoStateSemigroupOfIntermediateGrowth
UniversalD_omega V
is the group constructed in Nek07 as the universal group which covers an uncountable family
of groups parameterized by infinite binary sequences. It is contracting with nucleus consisting of 35
elements. Its generating automaton is as follows (it acts on the 4ary tree):
a=(1,2)(3,4), b=(a,c,a,c), c=(b,1,1,b). 

The group is stored in the global variable AG_Groups.UniversalD_omega
[Up] [Previous] [Index]
automgrp manual
September 2019