% This file was created automatically from misc.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Miscellaneous}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Trees}

\>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,\ldots,<deg>^{<n>}$.
This function returns the number that corresponds to the vertex <ver>.
\beginexample
gap> NumberOfVertex([1,2,1,2], 2);
6
gap> NumberOfVertex("333", 3);
27
\endexample


\>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,\ldots,<deg>^{<n>}$.
This function returns the vertex of this level that has number <num>.
\beginexample
gap> VertexNumber(1, 3, 2);
[ 1, 1, 1 ]
gap> VertexNumber(4, 4, 3);
[ 1, 1, 2, 1 ]
\endexample



%  how to construct all leaves of the finite tree



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Some predefined groups}

Several groups are predefined as fields in the global variable
`AG_Groups'. Here is how to access, for example, Grigorchuk group

\beginexample
gap> G:=AG_Groups.GrigorchukGroup;
< a, b, c, d >
\endexample

To perform operations with elements of `G' one can use `AssignGeneratorVariables' function.

\beginexample
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)
\endexample

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~\cite{Gri80} (see~\cite{Gri05} for a survey on this group). It is
defined as the group generated by the automaton
$$a=(1,1)(1,2),\quad b=(a,c),\quad c=(a,d),\quad d=(1,b)\.$$

\>UniversalGrigorchukGroup

is the universal group for the family of groups $G_{\omega}$ (see~\cite{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),\quad b=(a,a,1,b,b,b),\quad c=(a,1,a,c,c,c),\quad d=(1,a,a,d,d,d)\.$$

\>Basilica

is the Basilica group. It was first studied in \cite{GZ02a} and
\cite{GZ02b}. Later it became the first example of amenable, but not subexponentially
amenable group (see \cite{BV05}). It is the iterated monodromy group of the map $f(z)=z^2-1$.
It is generated by the automaton
$$u=(v,1)(1,2),\quad v=(u,1)\.$$

\>Lamplighter

is the Lamplighter group. This group was a key to the counterexample (see~\cite{GLSZ00})
to the strong Atiyah conjecture. It is generated by the automaton
$$a=(a,b)(1,2),\quad b=(a,b)\.$$

\>AddingMachine

is a the free abelian group of rank 1 (see~\cite{GNS00}) generated by the automaton
$$a=(1,a)(1,2)\.$$

\>InfiniteDihedral

is the infinite dihedral group (see~\cite{GNS00}) generated by the automaton
$$a=(a,a)(1,2),\quad b=(b,a)\.$$

\>AleshinGroup

is the free group of rank 3 generated by the Aleshin automaton (see~\cite{Ale83})
$$a=(b,c)(1,2),\quad b=(c,b)(1,2),\quad c=(a,a)\.$$
It was proved just recently by M.Vorobets and Ya.Vorobets (see~\cite{VV05})
that the group is indeed free of rank 3.

\>Bellaterra

is the free product of 3 cyclic groups of oreder 2 (see~\cite{BGK07})
$$a=(c,c)(1,2),\quad b=(a,b),\quad 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~\cite{Sus79} are infinite $p$-groups
of intermediate growth acting on the $p$-ary tree. In~\cite{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),\quad A^2=(1,1,1)(1,3,2),\quad B=(r_1,q_1,A),$$
$$r_1=(r_2,A,1),\quad r_2=(r_3,1,1),\quad r_3=(r_4,1,1),$$
$$r_4=(r_5,A,1),\quad r_5=(r_6,A^2,1),\quad r_6=(r_7,A,1),$$
$$r_7=(r_8,A,1),\quad r_8=(r_9,A,1),\quad r_9=(r_1,A^2,1),$$
$$q_1=(q_2,1,1),\quad q_2=(q_3,A,1),\quad q_3=(q_1,A,1)\.$$
The group $\langle A,B\rangle$ is isomorphic to the original Sushchansky 3-group.

\>Hanoi3
\>Hanoi4

Groups related to the Hanoi towers game on 3 and 4 pegs correspondingly
(see~\cite{GS06a} and \cite{GS06b}).
For 3 pegs `Hanoi3' is generated by the automaton
$$a_{23}=(a_{23},1,1)(2,3),\quad a_{13}=(1,a_{13},1)(1,3),\quad a_{12}=(1,1,a_{12})(1,2),$$
while the automaton generating `Hanoi4' is
$$a_{12}=(1,1,a_{12},a_{12})(1,2),\quad a_{13}=(1,a_{13},1,a_{13})(1,3),\quad a_{14}=(1,a_{14},a_{14},1)(1,4),$$
$$a_{23}=(a_{23},1,1,a_{23})(2,3),\quad a_{24}=(a_{24},1,a_{24},1)(2,4),\quad a_{34}=(a_{34},a_{34},1,1)(3,4)\.$$


\>GuptaSidki3Group

is the Gupta-Sidki infinite 3-group constructed in~\cite{GS83} and generated by the automaton
$$a=(1,1,1)(1,2,3),\quad b=(a,a^{-1},b)\.$$

\>GuptaFabrikowskiGroup

is the Gupta-Fabrykowski group of intermediate growth constructed in~\cite{FG85} and
generated by the automaton
$$a=(1,1,1)(1,2,3),\quad b=(a,1,b)\.$$

\>BartholdiGrigorchukGroup

is the Bartholdi-Grigorchuk group studied in~\cite{BG02} and generated by the automaton
$$a=(1,1,1)(1,2,3),\quad b=(a,a,b)\.$$

\>GrigorchukErschlerGroup

is the group of subexponential growth studied by Erschler in~\cite{Ers04}.
It grows faster than $\exp(n^\alpha)$ for any $\alpha\<1$. It belongs to the class of groups
constructed by Grigorchuk in~\cite{Gri84} and corresponds to the sequence $01010101\ldots$.
It is generated by the automaton
$$a=(1,1)(1,2),\quad b=(a,b),\quad c=(a,d),\quad d=(1,c)\.$$

\>BartholdiNonunifExponGroup

is the group of nonuniformly exponential growth constructed by Bartholdi in~\cite{Bar03}. Similar
examples were constructed earlier in \cite{Wil04} by Wilson. It is generated by the automaton
$$x=(1,1,1,1,1,1,1)(1,5)(3,7),\quad y=(1,1,1,1,1,1,1)(2,3)(6,7),\quad z=(1,1,1,1,1,1,1)(4,6)(5,7),$$
$$x_1=(x_1,x,1,1,1,1,1),\quad y_1=(y_1,y,1,1,1,1,1),\quad z_1=(z_1,z,1,1,1,1,1)\.$$

\>IMG_z2plusI

The iterated monodromy group of the map $f(z)=z^2+i$. It has intermediate growth (see~\cite{BP06})
and was studied in \cite{GSS07}.
$$a=(1,1)(1,2),\quad b=(a,c), c=(b,1)\.$$


\>Airplane
\>Rabbit

These are iterated monodromy groups of certain quadratic polynomials studied in~\cite{BN06}.
It was proved there that they are not isomorphic. The automata generating them are the following
$$a=(b,1)(1,2),\quad b=(c,1),\quad c=(a,1);$$
$$a=(b,1)(1,2),\quad b=(1,c),\quad c=(a,1)\.$$

\>TwoStateSemigroupOfIntermediateGrowth

is the semigroup of intermediate growth studied in~\cite{BRS06}. It is generated by the automaton
$$f_0=(f_0,f_0)(1,2),\quad f_1=(f_1,f_0)[2,2].$$

\>UniversalD_omega

is the group constructed in~\cite{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),\quad b=(a,c,a,c),\quad c=(b,1,1,b)\.$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%