<html><head><title>[automgrp] 5 Miscellaneous</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<h1>5 Miscellaneous</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP005.htm#SECT001">Trees</a>
<li> <A HREF="CHAP005.htm#SECT002">Some predefined groups</a>
</ol><p>
<p>
<p>
<h2><a name="SECT001">5.1 Trees</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>NumberOfVertex( </code><var>ver</var><code>, </code><var>deg</var><code> ) F</code>
<p>
Let <var>ver</var> belong to the <i>n</i>-th level of the <var>deg</var>-ary tree. One can
naturally enumerate all the vertices of this level by the numbers 1,…,<i>deg</i> <sup><i>n</i> </sup>.
This function returns the number that corresponds to the vertex <var>ver</var>.
<pre>
gap> NumberOfVertex([1,2,1,2], 2);
6
gap> NumberOfVertex("333", 3);
27
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>VertexNumber( </code><var>num</var><code>, </code><var>lev</var><code>, </code><var>deg</var><code> ) F</code>
<p>
One can naturally enumerate all the vertices of the <var>lev</var>-th level of
the <var>deg</var>-ary tree by the numbers 1,…,<i>deg</i> <sup><i>n</i> </sup>.
This function returns the vertex of this level that has number <var>num</var>.
<pre>
gap> VertexNumber(1, 3, 2);
[ 1, 1, 1 ]
gap> VertexNumber(4, 4, 3);
[ 1, 1, 2, 1 ]
</pre>
<p>
<p>
<h2><a name="SECT002">5.2 Some predefined groups</a></h2>
<p><p>
Several groups are predefined as fields in the global variable
<code>AG_Groups</code>. Here is how to access, for example, Grigorchuk group
<p>
<pre>
gap> G:=AG_Groups.GrigorchukGroup;
< a, b, c, d >
</pre>
<p>
To perform operations with elements of <code>G</code> one can use <code>AssignGeneratorVariables</code> function.
<p>
<pre>
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)
</pre>
<p>
Below is a list of all predefined groups with short description and references.
<p>
<a name = "SSEC002.1"></a>
<li><code>GrigorchukGroup</code>
<p>
is the first Grigorchuk group, an infinite 2-group of intermediate growth constructed
in <a href="biblio.htm#Gri80"><cite>Gri80</cite></a> (see <a href="biblio.htm#Gri05"><cite>Gri05</cite></a> for a survey on this group). It is
defined as the group generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1)(1,2), <i>b</i>=(<i>a</i>,<i>c</i>), <i>c</i>=(<i>a</i>,<i>d</i>), <i>d</i>=(1,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.2"></a>
<li><code>UniversalGrigorchukGroup</code>
<p>
is the universal group for the family of groups <i>G</i><sub>ω</sub> (see <a href="biblio.htm#Gri84"><cite>Gri84</cite></a>). It is
defined as a group acting on the 6-ary tree, generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1,1,1,1,1)(1,2), <i>b</i>=(<i>a</i>,<i>a</i>,1,<i>b</i>,<i>b</i>,<i>b</i>), <i>c</i>=(<i>a</i>,1,<i>a</i>,<i>c</i>,<i>c</i>,<i>c</i>), <i>d</i>=(1,<i>a</i>,<i>a</i>,<i>d</i>,<i>d</i>,<i>d</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.3"></a>
<li><code>Basilica</code>
<p>
is the Basilica group. It was first studied in <a href="biblio.htm#GZ02a"><cite>GZ02a</cite></a> and
<a href="biblio.htm#GZ02b"><cite>GZ02b</cite></a>. Later it became the first example of amenable, but not subexponentially
amenable group (see <a href="biblio.htm#BV05"><cite>BV05</cite></a>). It is the iterated monodromy group of the map <i>f</i>(<i>z</i>)=<i>z</i><sup>2</sup>−1.
It is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>u</i>=(<i>v</i>,1)(1,2), <i>v</i>=(<i>u</i>,1).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.4"></a>
<li><code>Lamplighter</code>
<p>
is the Lamplighter group. This group was a key to the counterexample (see <a href="biblio.htm#GLSZ00"><cite>GLSZ00</cite></a>)
to the strong Atiyah conjecture. It is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>a</i>,<i>b</i>)(1,2), <i>b</i>=(<i>a</i>,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.5"></a>
<li><code>AddingMachine</code>
<p>
is a the free abelian group of rank 1 (see <a href="biblio.htm#GNS00"><cite>GNS00</cite></a>) generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,<i>a</i>)(1,2).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.6"></a>
<li><code>InfiniteDihedral</code>
<p>
is the infinite dihedral group (see <a href="biblio.htm#GNS00"><cite>GNS00</cite></a>) generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>a</i>,<i>a</i>)(1,2), <i>b</i>=(<i>b</i>,<i>a</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.7"></a>
<li><code>AleshinGroup</code>
<p>
is the free group of rank 3 generated by the Aleshin automaton (see <a href="biblio.htm#Ale83"><cite>Ale83</cite></a>)
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>b</i>,<i>c</i>)(1,2), <i>b</i>=(<i>c</i>,<i>b</i>)(1,2), <i>c</i>=(<i>a</i>,<i>a</i>).</td></tr></table></td></tr></table>
It was proved just recently by M.Vorobets and Ya.Vorobets (see <a href="biblio.htm#VV05"><cite>VV05</cite></a>)
that the group is indeed free of rank 3.
<p>
<a name = "SSEC002.8"></a>
<li><code>Bellaterra</code>
<p>
is the free product of 3 cyclic groups of oreder 2 (see <a href="biblio.htm#BGK07"><cite>BGK07</cite></a>)
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>c</i>,<i>c</i>)(1,2), <i>b</i>=(<i>a</i>,<i>b</i>), <i>c</i>=(<i>b</i>,<i>a</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.9"></a>
<li><code>SushchanskyGroup</code>
<p>
is the self-similar closure of the faithful level-transitive action of Sushchansky group on the
ternary tree. The original groups constructed in <a href="biblio.htm#Sus79"><cite>Sus79</cite></a> are infinite <i>p</i>-groups
of intermediate growth acting on the <i>p</i>-ary tree. In <a href="biblio.htm#BS07"><cite>BS07</cite></a> 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
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>A</i>=(1,1,1)(1,2,3), <i>A</i><sup>2</sup>=(1,1,1)(1,3,2), <i>B</i>=(<i>r</i><sub>1</sub>,<i>q</i><sub>1</sub>,<i>A</i>),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>r</i><sub>1</sub>=(<i>r</i><sub>2</sub>,<i>A</i>,1), <i>r</i><sub>2</sub>=(<i>r</i><sub>3</sub>,1,1), <i>r</i><sub>3</sub>=(<i>r</i><sub>4</sub>,1,1),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>r</i><sub>4</sub>=(<i>r</i><sub>5</sub>,<i>A</i>,1), <i>r</i><sub>5</sub>=(<i>r</i><sub>6</sub>,<i>A</i><sup>2</sup>,1), <i>r</i><sub>6</sub>=(<i>r</i><sub>7</sub>,<i>A</i>,1),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>r</i><sub>7</sub>=(<i>r</i><sub>8</sub>,<i>A</i>,1), <i>r</i><sub>8</sub>=(<i>r</i><sub>9</sub>,<i>A</i>,1), <i>r</i><sub>9</sub>=(<i>r</i><sub>1</sub>,<i>A</i><sup>2</sup>,1),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>q</i><sub>1</sub>=(<i>q</i><sub>2</sub>,1,1), <i>q</i><sub>2</sub>=(<i>q</i><sub>3</sub>,<i>A</i>,1), <i>q</i><sub>3</sub>=(<i>q</i><sub>1</sub>,<i>A</i>,1).</td></tr></table></td></tr></table>
The group 〈<i>A</i>,<i>B</i>〉 is isomorphic to the original Sushchansky 3-group.
<p>
<a name = "SSEC002.10"></a>
<li><code>Hanoi3</code>
<a name = "SSEC002.10"></a>
<li><code>Hanoi4</code>
<p>
Groups related to the Hanoi towers game on 3 and 4 pegs correspondingly
(see <a href="biblio.htm#GS06a"><cite>GS06a</cite></a> and <a href="biblio.htm#GS06b"><cite>GS06b</cite></a>).
For 3 pegs <code>Hanoi3</code> is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i><sub>23</sub>=(<i>a</i><sub>23</sub>,1,1)(2,3), <i>a</i><sub>13</sub>=(1,<i>a</i><sub>13</sub>,1)(1,3), <i>a</i><sub>12</sub>=(1,1,<i>a</i><sub>12</sub>)(1,2),</td></tr></table></td></tr></table>
while the automaton generating <code>Hanoi4</code> is
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i><sub>12</sub>=(1,1,<i>a</i><sub>12</sub>,<i>a</i><sub>12</sub>)(1,2), <i>a</i><sub>13</sub>=(1,<i>a</i><sub>13</sub>,1,<i>a</i><sub>13</sub>)(1,3), <i>a</i><sub>14</sub>=(1,<i>a</i><sub>14</sub>,<i>a</i><sub>14</sub>,1)(1,4),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i><sub>23</sub>=(<i>a</i><sub>23</sub>,1,1,<i>a</i><sub>23</sub>)(2,3), <i>a</i><sub>24</sub>=(<i>a</i><sub>24</sub>,1,<i>a</i><sub>24</sub>,1)(2,4), <i>a</i><sub>34</sub>=(<i>a</i><sub>34</sub>,<i>a</i><sub>34</sub>,1,1)(3,4).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.11"></a>
<li><code>GuptaSidki3Group</code>
<p>
is the Gupta-Sidki infinite 3-group constructed in <a href="biblio.htm#GS83"><cite>GS83</cite></a> and generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1,1)(1,2,3), <i>b</i>=(<i>a</i>,<i>a</i><sup>−1</sup>,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.12"></a>
<li><code>GuptaFabrikowskiGroup</code>
<p>
is the Gupta-Fabrykowski group of intermediate growth constructed in <a href="biblio.htm#FG85"><cite>FG85</cite></a> and
generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1,1)(1,2,3), <i>b</i>=(<i>a</i>,1,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.13"></a>
<li><code>BartholdiGrigorchukGroup</code>
<p>
is the Bartholdi-Grigorchuk group studied in <a href="biblio.htm#BG02"><cite>BG02</cite></a> and generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1,1)(1,2,3), <i>b</i>=(<i>a</i>,<i>a</i>,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.14"></a>
<li><code>GrigorchukErschlerGroup</code>
<p>
is the group of subexponential growth studied by Erschler in <a href="biblio.htm#Ers04"><cite>Ers04</cite></a>.
It grows faster than exp(<i>n</i><sup>α</sup>) for any α < 1. It belongs to the class of groups
constructed by Grigorchuk in <a href="biblio.htm#Gri84"><cite>Gri84</cite></a> and corresponds to the sequence 01010101….
It is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1)(1,2), <i>b</i>=(<i>a</i>,<i>b</i>), <i>c</i>=(<i>a</i>,<i>d</i>), <i>d</i>=(1,<i>c</i>).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.15"></a>
<li><code>BartholdiNonunifExponGroup</code>
<p>
is the group of nonuniformly exponential growth constructed by Bartholdi in <a href="biblio.htm#Bar03"><cite>Bar03</cite></a>. Similar
examples were constructed earlier in <a href="biblio.htm#Wil04"><cite>Wil04</cite></a> by Wilson. It is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>x</i>=(1,1,1,1,1,1,1)(1,5)(3,7), <i>y</i>=(1,1,1,1,1,1,1)(2,3)(6,7), <i>z</i>=(1,1,1,1,1,1,1)(4,6)(5,7),</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>x</i><sub>1</sub>=(<i>x</i><sub>1</sub>,<i>x</i>,1,1,1,1,1), <i>y</i><sub>1</sub>=(<i>y</i><sub>1</sub>,<i>y</i>,1,1,1,1,1), <i>z</i><sub>1</sub>=(<i>z</i><sub>1</sub>,<i>z</i>,1,1,1,1,1).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.16"></a>
<li><code>IMG_z2plusI</code>
<p>
The iterated monodromy group of the map <i>f</i>(<i>z</i>)=<i>z</i><sup>2</sup>+<i>i</i>. It has intermediate growth (see <a href="biblio.htm#BP06"><cite>BP06</cite></a>)
and was studied in <a href="biblio.htm#GSS07"><cite>GSS07</cite></a>.
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,1)(1,2), <i>b</i>=(<i>a</i>,<i>c</i>), <i>c</i>=(<i>b</i>,1).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.17"></a>
<li><code>Airplane</code>
<a name = "SSEC002.17"></a>
<li><code>Rabbit</code>
<p>
These are iterated monodromy groups of certain quadratic polynomials studied in <a href="biblio.htm#BN06"><cite>BN06</cite></a>.
It was proved there that they are not isomorphic. The automata generating them are the following
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>b</i>,1)(1,2), <i>b</i>=(<i>c</i>,1), <i>c</i>=(<i>a</i>,1);</td></tr></table></td></tr></table>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(<i>b</i>,1)(1,2), <i>b</i>=(1,<i>c</i>), <i>c</i>=(<i>a</i>,1).</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.18"></a>
<li><code>TwoStateSemigroupOfIntermediateGrowth</code>
<p>
is the semigroup of intermediate growth studied in <a href="biblio.htm#BRS06"><cite>BRS06</cite></a>. It is generated by the automaton
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>f</i><sub>0</sub>=(<i>f</i><sub>0</sub>,<i>f</i><sub>0</sub>)(1,2), <i>f</i><sub>1</sub>=(<i>f</i><sub>1</sub>,<i>f</i><sub>0</sub>)[2,2]·</td></tr></table></td></tr></table>
<p>
<a name = "SSEC002.19"></a>
<li><code>UniversalD_omega</code>
<p>
is the group constructed in <a href="biblio.htm#Nek07"><cite>Nek07</cite></a> 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)
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>a</i>=(1,2)(3,4), <i>b</i>=(<i>a</i>,<i>c</i>,<i>a</i>,<i>c</i>), <i>c</i>=(<i>b</i>,1,1,<i>b</i>).</td></tr></table></td></tr></table>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP004.htm">Previous</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>automgrp manual<br>September 2008
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
890
