[Up] [Previous] [Index]
5 Miscellaneous
Sections
- Trees
- Some predefined groups
NumberOfVertex(
ver,
deg ) F
Let ver belong to the n-th level of the deg-ary tree. One can
naturally enumerate all the vertices of this level by the numbers 1,…,deg n .
This function returns the number that corresponds to the vertex ver.
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 lev-th level of
the deg-ary 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
is the first Grigorchuk group, an infinite 2-group 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). |
|
UniversalGrigorchukGroup
is the universal group for the family of groups Gω (see Gri84). It is
defined as a group acting on the 6-ary 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). |
|
Basilica
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)=z2−1.
It is generated by the automaton
Lamplighter
is the Lamplighter group. This group was a key to the counterexample (see GLSZ00)
to the strong Atiyah conjecture. It is generated by the automaton
AddingMachine
is a the free abelian group of rank 1 (see GNS00) generated by the automaton
InfiniteDihedral
is the infinite dihedral group (see GNS00) generated by the automaton
AleshinGroup
is the free group of rank 3 generated by the Aleshin automaton (see Ale83)
a=(b,c)(1,2), b=(c,b)(1,2), c=(a,a). |
|
It was proved just recently by M.Vorobets and Ya.Vorobets (see VV05)
that the group is indeed free of rank 3.
Bellaterra
is the free product of 3 cyclic groups of oreder 2 (see BGK07)
a=(c,c)(1,2), b=(a,b), c=(b,a). |
|
SushchanskyGroup
is the self-similar closure of the faithful level-transitive action of Sushchansky group on the
ternary tree. The original groups constructed in Sus79 are infinite p-groups
of intermediate growth acting on the p-ary tree. In BS07 the action of these
groups on the tree was simplified, so that, in particular, the self-similar closure of one of the 3-groups
is generated by the automaton
A=(1,1,1)(1,2,3), A2=(1,1,1)(1,3,2), B=(r1,q1,A), |
|
r1=(r2,A,1), r2=(r3,1,1), r3=(r4,1,1), |
|
r4=(r5,A,1), r5=(r6,A2,1), r6=(r7,A,1), |
|
r7=(r8,A,1), r8=(r9,A,1), r9=(r1,A2,1), |
|
q1=(q2,1,1), q2=(q3,A,1), q3=(q1,A,1). |
|
The group 〈A,B〉 is isomorphic to the original Sushchansky 3-group.
Hanoi3
Hanoi4
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
a23=(a23,1,1)(2,3), a13=(1,a13,1)(1,3), a12=(1,1,a12)(1,2), |
|
while the automaton generating Hanoi4
is
a12=(1,1,a12,a12)(1,2), a13=(1,a13,1,a13)(1,3), a14=(1,a14,a14,1)(1,4), |
|
a23=(a23,1,1,a23)(2,3), a24=(a24,1,a24,1)(2,4), a34=(a34,a34,1,1)(3,4). |
|
GuptaSidki3Group
is the Gupta-Sidki infinite 3-group constructed in GS83 and generated by the automaton
a=(1,1,1)(1,2,3), b=(a,a−1,b). |
|
GuptaFabrikowskiGroup
is the Gupta-Fabrykowski group of intermediate growth constructed in FG85 and
generated by the automaton
a=(1,1,1)(1,2,3), b=(a,1,b). |
|
BartholdiGrigorchukGroup
is the Bartholdi-Grigorchuk group studied in BG02 and generated by the automaton
a=(1,1,1)(1,2,3), b=(a,a,b). |
|
GrigorchukErschlerGroup
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). |
|
BartholdiNonunifExponGroup
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), |
|
x1=(x1,x,1,1,1,1,1), y1=(y1,y,1,1,1,1,1), z1=(z1,z,1,1,1,1,1). |
|
IMG_z2plusI
The iterated monodromy group of the map f(z)=z2+i. It has intermediate growth (see BP06)
and was studied in GSS07.
a=(1,1)(1,2), b=(a,c), c=(b,1). |
|
Airplane
Rabbit
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). |
|
TwoStateSemigroupOfIntermediateGrowth
is the semigroup of intermediate growth studied in BRS06. It is generated by the automaton
f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]· |
|
UniversalD_omega
is the group constructed in Nek07 as a universal group which covers an uncountable family
of groups parametrized by infinite binary sequences. It is contracting with nucleus consisting of 35
elements. The automaton generating it is the following (it acts on the 4-ary tree)
a=(1,2)(3,4), b=(a,c,a,c), c=(b,1,1,b). |
|
[Up] [Previous] [Index]
automgrp manual
September 2008