misc.tex

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

In this chapter we present the functionality that does not quite fit in other chapters and the list of predefined groups and semigroups.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Converters to and from FR package}

\>`FR2AutomGrp'{FR2AutomGrp}@{`FR2AutomGrp'} 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.

\beginexample
gap> ZZ := FRGroup("t=<,t>[2,1]");
<state-closed group over [ 1 .. 2 ] with 1 generator>
gap> AZZ := FR2AutomGrp(ZZ);
< t >
gap> Display(AZZ);
< t = (1, t)(1,2) >
\endexample
\beginexample
gap> i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");
<state-closed 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] >
\endexample
\beginexample
gap> S := FRGroup("a=<a*b^-2,b^3>(1,2)","b=<b^-1*a,1>");
<state-closed 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  Global variable `a' is already defined and will be overwritten
#I  Global variable `b' is already defined and will be overwritten
#I  Assigned the global variables [ "a", "b" ]
gap> x := a^3*b*a^-2;
<2||a^3*b*a^-2>
gap> DecompositionOfFRElement(x);
[ [ <2||a*b^-2>, <2||b^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)
\endexample

\>`AutomGrp2FR'{AutomGrp2FR}@{`AutomGrp2FR'} 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 self-similari
(or, functionally recursive in L.Bartholdi's terminology) groups,
semigroups, their sub(semi)groups and elements.

\beginexample
gap> G:=AutomatonGroup("a=(b,a)(1,2),b=(a,b)");
< a, b >
gap> FG := AutomGrp2FR(G);
<state-closed group over [ 1 .. 2 ] with 2 generators>
gap> DecompositionOfFRElement(FG.1);
[ [ <2||b>, <2||a> ], [ 2, 1 ] ]
gap> DecompositionOfFRElement(FG.2);
[ [ <2||a>, <2||b> ], [ 1, 2 ] ]
\endexample
\beginexample
gap> G := SelfSimilarGroup("a=(a*b^-2,b*a)(1,2),b=(b^-1,a*b*a)");
< a, b >
gap> F := AutomGrp2FR(G);
<state-closed group over [ 1 .. 2 ] with 1 generator>
gap> DecompositionOfFRElement(F.1);
[ [ <2||a*b^-2>, <2||b*a> ], [ 2, 1 ] ]
\endexample
\beginexample
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);
[ [ <2||b^2>, <2||a^2> ], [ 2, 1 ] ]
\endexample
\beginexample
gap> G := SelfSimilarSemigroup("a=(a*b^2,b*a)[1,1],b=(b,a*b*a)(1,2)");
< a, b >
gap> S := AutomGrp2FR(G);
<state-closed semigroup over [ 1 .. 2 ] with 2 generators>
gap> DecompositionOfFRElement(S.1);
[ [ <2||a*b^2>, <2||b*a> ], [ 1, 1 ] ]
\endexample
\beginexample
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);
<2||a*b^-2>
gap> DecompositionOfFRElement(x);
[ [ <2||b^-1>, <2||a^-1> ], [ 2, 1 ] ]
\endexample




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

\>NumberOfVertex( <ver>, <deg> ) F

One can naturally enumerate all the vertices of the $n$-th level of the tree
by the numbers $1,\ldots,<deg>^{<n>}$.
This function returns the number that corresponds to the vertex <ver>
of the <deg>-ary tree. The vertex can be defined either as a list or as a string.
\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' V

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)\.$$
The group is stored in the global variable `AG_Groups.GrigorchukGroup'

\>`UniversalGrigorchukGroup' V

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)\.$$
The group is stored in the global variable `AG_Groups.UniversalGrigorchukGroup'

\>`Basilica' V

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)\.$$
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~\cite{GLSZ00}). It is generated by the automaton
$$a=(a,b)(1,2),\quad b=(a,b)\.$$
The group is stored in the global variable `AG_Groups.Lamplighter'

\>`AddingMachine' V

is the free abelian group of rank 1 (see~\cite{GNS00}) generated by the automaton
$$a=(1,a)(1,2)\.$$
The group is stored in the global variable `AG_Groups.AddingMachine'

\>`InfiniteDihedral' V

is the infinite dihedral group (see~\cite{GNS00}) generated by the automaton
$$a=(a,a)(1,2),\quad b=(b,a)\.$$
The group is stored in the global variable `AG_Groups.InfiniteDihedral'

\>`AleshinGroup' V

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

\>`Bellaterra' V

is a group generated by the Aleshin automaton (see~\cite{Ale83}) defined by the
following wreath recursion:
$$a=(c,c)(1,2),\quad b=(a,b),\quad c=(b,a)\.$$
It is isomorphic to the free product of 3 cyclic groups of order 2 (see~\cite{BGK07})
The group is stored in the global variable `AG_Groups.Bellaterra'

\>`SushchanskyGroup' V

is the self-similar closure of the faithful level-transitive action of the 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.
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~\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)\.$$
The groups are stored in the global variables `AG_Groups.Hanoi3' and `AG_Groups.Hanoi4'

\>`GuptaSidki3Group' V

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)\.$$
The group is stored in the global variable `AG_Groups.GuptaSidki3Group'

\>`GuptaFabrikowskiGroup' V

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)\.$$
The group is stored in the global variable `AG_Groups.GuptaFabrikowskiGroup'

\>`BartholdiGrigorchukGroup' V

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)\.$$
The group is stored in the global variable `AG_Groups.BartholdiGrigorchukGroup'

\>`GrigorchukErschlerGroup' V

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)\.$$
The group is stored in the global variable `AG_Groups.GrigorchukErschlerGroup'

\>`BartholdiNonunifExponGroup' V

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)\.$$
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~\cite{BP06})
and was studied in \cite{GSS07}.
$$a=(1,1)(1,2),\quad 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~\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)\.$$
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~\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].$$
The group is stored in the global variable `AG_Groups.TwoStateSemigroupOfIntermediateGrowth'

\>`UniversalD_omega' V

is the group constructed in~\cite{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 4-ary tree):
$$a=(1,2)(3,4),\quad b=(a,c,a,c),\quad c=(b,1,1,b)\.$$
The group is stored in the global variable `AG_Groups.UniversalD_omega'

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