|
|
|
|
SSL chap9.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/fr/doc/chap9.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (FR) - Chapter 9: Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap9" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap8.html">[Previous Chapter]</a> <a href="chap10.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap9_mj.html">[MathJax on]</a></p>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>
<div class="ChapSects"><a href="chap9.html#X7A489A5D79DA9E5C">9 <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X7AF5DEF08531AFA5">9.1 <span class="Heading">Examples of groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7D774B847D81E6DE">9.1-1 FullBinaryGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X813F53C57F41F5F5">9.1-2 BinaryKneadingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7B8D49D079D336E8">9.1-3 BasilicaGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X8449487686E00D22">9.1-4 FornaessSibonyGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X85F4FDF787173863">9.1-5 AddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7A4BB24A805CDF63">9.1-6 BinaryAddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X78AFA63B86C94227">9.1-7 MixerGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X84C97E0687F119C0">9.1-8 SunicGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X79E3F3BE80F34590">9.1-9 GrigorchukMachines</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X85BAE48780E665A4">9.1-10 GrigorchukMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X800640597E9C707D">9.1-11 GrigorchukOverGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7E765AF77AAC21A6">9.1-12 GrigorchukTwistedTwin</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7F93EC437B5AE276">9.1-13 BrunnerSidkiVieiraGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7F8A028B799946D3">9.1-14 AleshinGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7C286D3A84790ECE">9.1-15 AleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7E024B4D7BA411B1">9.1-16 BabyAleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X8108E3A8872A6FFE">9.1-17 SidkiFreeGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X82D3CB6A7C189C78">9.1-18 GuptaSidkiGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X83E59288860EF661">9.1-19 GuptaSidkiGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X8521B4FF7BA189B2">9.1-20 NeumannGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X878D1C7080EA9797">9.1-21 FabrykowskiGuptaGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7C5ADAE77EA3876D">9.1-22 ZugadiSpinalGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7A0319827CB51ED0">9.1-23 GammaPQMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X80B617717C2887D4">9.1-24 RattaggiGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7A0BE9F57B401C5C">9.1-25 HanoiGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7C7A0EEF7EFF8B99">9.1-26 DahmaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7C958AB78484E256">9.1-27 MamaghaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X86D952E8784E4D97">9.1-28 WeierstrassGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X80D59AFF7E7D3B8B">9.1-29 StrichartzGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X86B124758135DFBD">9.1-30 FRAffineGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7CFBE31A78F2681B">9.1-31 CayleyGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X81B82FA1811AAF8D">9.2 <span class="Heading">Examples of semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X87541DA582705033">9.2-1 I2Machine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7B32ED3D8715FA4B">9.2-2 I4Machine</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X803B02408573A30E">9.3 <span class="Heading">Examples of algebras</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X80E15ABC879F8EE2">9.3-1 PSZAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7D015CA5829FAA2A">9.3-2 GrigorchukThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7B66ED537D0A43AF">9.3-3 GuptaSidkiThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X86CE9A8787F69DBC">9.3-4 GrigorchukLieAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7B0B5B09878C7CEA">9.3-5 SidkiFreeAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7988B29F836BAA62">9.3-6 SidkiMonomialAlgebra</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X7989134C83AF38AE">9.4 <span class="Heading">Bacher's determinant identities
</ span>
</ div>
< div class= "ContSect">< span class= "tocline">< span class= "nocss"> </ span><a href= "chap9.html#X7C4A51947E1609A8">9.5 < span class= "Heading">VH groups</ span></a>
</ span>
< div class= "ContSSBlock">
< span class= "ContSS">< br />< span class= "nocss"> </ span><a href= "chap9.html#X7E0071D4838B239D">9 .5-1 VHStructure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7F852A357D7E2E76">9.5-2 VerticalAction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X86B1C2F079FE8D82">9.5-3 VHGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7D1FCB877D1B96EA">9.5-4 IsIrreducibleVHGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X84DB7FA4846075A7">9.5-5 MaximalSimpleSubgroup</a></span>
</div></div>
</div>
<h3>9 <span class="Heading">Examples</span></h3>
<p><strong class="pkg">FR</strong> predefines a large collection of machines and groups. The groups are, whenever possible, defined as state closures of corresponding Mealy machines.</p>
<p><a id="X7AF5DEF08531AFA5" name="X7AF5DEF08531AFA5"></a></p>
<h4>9.1 <span class="Heading">Examples of groups</span></h4>
<p><a id="X7D774B847D81E6DE" name="X7D774B847D81E6DE"></a></p>
<h5>9.1-1 FullBinaryGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FullBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FiniteDepthBinaryGroup</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FinitaryBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BoundedBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PolynomialGrowthBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FiniteStateBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These are the finitary, bounded, polynomial-growth, finite-state, or unrestricted groups acting on the binary tree. They are respectively shortcuts for <code class="code">FullSCGroup([1..2])</code>, <code class="code">FullSCGroup([1..2],l)</code>, <code class="code">FullSCGroup([1..2],IsFinitaryFRSemigroup)</code>, <code class="code">FullSCGroup([1..2],IsBoundedFRSemigroup)</code>, <code class="code">FullSCGroup([1..2],IsPolynomialGrowthFRSemigroup)</code>, and <code class="code">FullSCGroup([1..2],IsFiniteStateFRSemigroup)</code>.</p>
<p>They may be used to draw random elements, or to test membership.</p>
<p><a id="X813F53C57F41F5F5" name="X813F53C57F41F5F5"></a></p>
<h5>9.1-2 BinaryKneadingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryKneadingGroup</code>( <var class="Arg">angle/ks</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryKneadingMachine</code>( <var class="Arg">angle/ks</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The [machine generating the] iterated monodromy group of a quadratic polynomial.</p>
<p>The first function constructs a Mealy machine whose state closure is the binary kneading group.</p>
<p>The second function constructs a new FR group <code class="code">G</code>, which is the iterated monodromy group of a quadratic polynomial, either specified by its angle or by its kneading sequence(s).</p>
<p>If the argument is a (rational) angle, the attribute <code class="code">Correspondence(G)</code> is a function returning, for any rational, the corresponding generator of <code class="code">G</code>.</p>
<p>If there is one argument, which is a list or a string, it is treated as the kneading sequence of a periodic (superattracting) polynomial. The sequence is implicity assumed to end by '*'. The attribute <code class="code">Correspondence(G)</code> is a list of the generators of <code class="code">G</code>.</p>
<p>If there are two arguments, which are lists or strings, they are treated as the preperiod and period of the kneading sequence of a preperiodic polynomial. The last symbol of the arguments must differ. The attribute <code class="code">Correspondence(G)</code> is a pair of lists of generators; <code class="code">Correspondence(G)[1]</code> is the preperiod, and <code class="code">Correspondence(G)[2]</code> is the period. The attribute <code class="code">KneadingSequence(G)</code> returns the kneading sequence, as a pair of strings representing preperiod and period respectively.</p>
<p>As particular examples, <code class="code">BinaryKneadingMachine()</code> is the adding machine; <code class="code">BinaryKneadingGroup()</code> is the adding machine; and <code class="code">BinaryKneadingGroup("1")</code> is <code class="func">BasilicaGroup</code> (<a href="chap9.html#X7B8D49D079D336E8"><span class="RefLink">9.1-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BinaryKneadingGroup()=AddingGroup(2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">BinaryKneadingGroup(1/3)=BasilicaGroup;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := BinaryKneadingGroup([0,1],[0]);</span>
BinaryKneadingGroup("01","0")
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll(Correspondence(g)[1],IsFinitaryFRElement);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll(Correspondence(g)[2],IsFinitaryFRElement);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll(Correspondence(g)[2],IsBoundedFRElement);</span>
true
</pre></div>
<p><a id="X7B8D49D079D336E8" name="X7B8D49D079D336E8"></a></p>
<h5>9.1-3 BasilicaGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BasilicaGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The <em>Basilica group</em>. This is a shortcut for <code class="code">BinaryKneadingGroup("1")</code>. It is the first-discovered amenable group that is not subexponentially amenable, see <a href="chapBib.html#biBMR2176547">[BV05]</a> and <a href="chapBib.html#biBMR1902367">[G{\.Z}02]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBoundedFRSemigroup(BasilicaGroup);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := EpimorphismFromFreeGroup(BasilicaGroup); F := Source(pi);;</span>
[ x1, x2 ] -> [ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">sigma := GroupHomomorphismByImages(F,F,[F.1,F.2],[F.2,F.1^2]);</span>
[ x1, x2 ] -> [ x2, x1^2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([0..10],i->IsOne(Comm(F.2,F.2^F.1)^(sigma^i*pi)));</span>
true
</pre></div>
<p><a id="X8449487686E00D22" name="X8449487686E00D22"></a></p>
<h5>9.1-4 FornaessSibonyGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FornaessSibonyGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The <em>Fornaess-Sibony group</em>. This group was studied by Nekrashevych in <a href="chapBib.html#biB0811.2777">[Nek08b]</a>. It is the iterated monodromy group of the endomorphism of <span class="SimpleMath">CP^2</span> defined by <span class="SimpleMath">(z,p)↦((1-2z/p)^2,(1-2/p)^2)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(NucleusOfFRSemigroup(FornaessSibonyGroup));</span>
288
<span class="GAPprompt">gap></span> <span class="GAPinput">List(AdjacencyBasesWithOne(FornaessSibonyGroup),Length);</span>
[ 128, 128, 36, 36, 16, 16, 8 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">p := AdjacencyPoset(FornaessSibonyGroup);</span>
<general mapping: <object> -> <object> >
<span class="GAPprompt">gap></span> <span class="GAPinput">Draw(HasseDiagramBinaryRelation(p));</span>
</pre></div>
<p>This produces (in a new window) the following picture: <img alt="Hasse Diagram" src="fornaess-sibony.jpg"></p>
<p><a id="X85F4FDF787173863" name="X85F4FDF787173863"></a></p>
<h5>9.1-5 AddingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddingGroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddingMachine</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddingElement</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The second function constructs the adding machine on the alphabet <code class="code">[1..n]</code>. This machine has a trivial state 1, and a non-trivial state 2. It implements the operation "add 1 with carry" on sequences.</p>
<p>The third function constructs the Mealy element on the adding machine, with initial state 2.</p>
<p>The first function constructs the state-closed group generated by the adding machine on <code class="code">[1..n]</code>. This group is isomorphic to the <code class="code">Integers</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(AddingElement(3));</span>
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 b,1
---+-----+-----+-----+
Initial state: b
<span class="GAPprompt">gap></span> <span class="GAPinput">ActivityPerm(FRElement(AddingMachine(3),2),2);</span>
(1,4,7,2,5,8,3,6,9)
<span class="GAPprompt">gap></span> <span class="GAPinput">G := AddingGroup(3);</span>
<self-similar group over [ 1 .. 3 ] with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(G);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRecurrentFRSemigroup(G);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLevelTransitiveFRGroup(G);</span>
true
</pre></div>
<p><a id="X7A4BB24A805CDF63" name="X7A4BB24A805CDF63"></a></p>
<h5>9.1-6 BinaryAddingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryAddingGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryAddingMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BinaryAddingElement</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These are respectively the same as <code class="code">AddingGroup(2)</code>, <code class="code">AddingMachine(2)</code> and <code class="code">AddingElement(2)</code>.</p>
<p><a id="X78AFA63B86C94227" name="X78AFA63B86C94227"></a></p>
<h5>9.1-7 MixerGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MixerGroup</code>( <var class="Arg">A</var>, <var class="Arg">B</var>, <var class="Arg">f</var>[, <var class="Arg">g</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MixerMachine</code>( <var class="Arg">A</var>, <var class="Arg">B</var>, <var class="Arg">f</var>[, <var class="Arg">g</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A Mealy "mixer" machine/group.</p>
<p>The second function constructs a Mealy "mixer" machine <code class="code">m</code>. This is a machine determined by a permutation group <var class="Arg">A</var>, a finitely generated group <var class="Arg">B</var>, and a matrix of homomorphisms from <var class="Arg">B</var> to <var class="Arg">A</var>. If <var class="Arg">A</var> acts on <code class="code">[1..d]</code>, then each row of <var class="Arg">f</var> contains at most <span class="SimpleMath">d-1</span> homomorphisms. The optional last argument is an endomorphism of <var class="Arg">B</var>. If absent, it is treated as the identity map on <var class="Arg">B</var>.</p>
<p>The states of the machine are 1, followed by some elements <code class="code">a</code> of <var class="Arg">A</var>, followed by as many copies of some elements <code class="code">b</code> of <var class="Arg">B</var> as there are rows in <var class="Arg">f</var>. The elements in <var class="Arg">B</var> that are taken is the smallest sublist of <var class="Arg">B</var> containing its generators and closed under <var class="Arg">g</var>. The elements in <var class="Arg">A</var> that are taken are the generators of <var class="Arg">A</var> and all images of all taken elements of <var class="Arg">B</var> under maps in <var class="Arg">f</var>.</p>
<p>The transitions from <code class="code">a</code> are towards 1 and the outputs are the permutations in <var class="Arg">A</var>. The transitions from <code class="code">b</code> are periodically given by <var class="Arg">f</var>, completed by trivial elements, and finally by <span class="SimpleMath">b^g</span>; the output of <code class="code">b</code> is trivial.</p>
<p>This construction is described in more detail in <a href="chapBib.html#biBMR1856923">[B{Š}01]</a> and <a href="chapBib.html#biBMR2035113">[BG{Š}03]</a>.</p>
<p><code class="code">Correspondence(m)</code> is a list, with in first position the subset of the states that correspond to <var class="Arg">A</var>, in second position the states that correspond to the first copy of <var class="Arg">B</var>, etc.</p>
<p>The first function constructs the group generated by the mixer machine. For examples see <code class="func">GrigorchukGroups</code> (<a href="chap9.html#X79E3F3BE80F34590"><span class="RefLink">9.1-9</span></a>), <code class="func">NeumannGroup</code> (<a href="chap9.html#X8521B4FF7BA189B2"><span class="RefLink">9.1-20</span></a>), <code class="func">GuptaSidkiGroups</code> (<a href="chap9.html#X82D3CB6A7C189C78"><span class="RefLink">9.1-18</span></a>), and <code class="func">ZugadiSpinalGroup</code> (<a href="chap9.html#X7C5ADAE77EA3876D"><span class="RefLink">9.1-22</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">grigorchukgroup := MixerGroup(Group((1,2)),Group((1,2)),</span>
[[IdentityMapping(Group((1,2)))],[IdentityMapping(Group((1,2)))],[]]));
<self-similar group over [ 1 .. 2 ] with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IdGroup(Group(grigorchukgroup.1,grigorchukgroup.2));</span>
[ 32, 18 ]
</pre></div>
<p><a id="X84C97E0687F119C0" name="X84C97E0687F119C0"></a></p>
<h5>9.1-8 SunicGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SunicGroup</code>( <var class="Arg">phi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SunicMachine</code>( <var class="Arg">phi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The Sunic machine associated with the polynomial <var class="Arg">phi</var>.</p>
<p>A "Sunic machine" is a special kind of <code class="func">MixerMachine</code> (<a href="chap9.html#X78AFA63B86C94227"><span class="RefLink">9.1-7</span></a>), in which the group <span class="SimpleMath">A</span> is a finite field <span class="SimpleMath">GF(q)</span>, the group <span class="SimpleMath">B</span> is an extension <span class="SimpleMath">A[x]/(ϕ)</span>, where <span class="SimpleMath">ϕ</span> is a monic polynomial; there is a map <span class="SimpleMath">f:B-> A</span>, given say by evaluation; and there is an endomorphism of <span class="SimpleMath">g:B-> B</span> given by multiplication by <span class="SimpleMath">ϕ</span>.</p>
<p>These groups were described in <a href="chapBib.html#biBMR2318546">[{Š}un07]</a>. In particular, the case <span class="SimpleMath">q=2</span> and <span class="SimpleMath">ϕ=x^2+x+1</span> gives the original <code class="func">GrigorchukGroup</code> (<a href="chap9.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Indeterminate(GF(2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := SunicGroup(x^2+x+1);</span>
SunicGroup(x^2+x+Z(2)^0)
<span class="GAPprompt">gap></span> <span class="GAPinput">g = GrigorchukGroup;</span>
true
</pre></div>
<p><a id="X79E3F3BE80F34590" name="X79E3F3BE80F34590"></a></p>
<h5>9.1-9 GrigorchukMachines</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukMachines</code>( <var class="Arg">omega</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukGroups</code>( <var class="Arg">omega</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: One of the Grigorchuk groups.</p>
<p>This function constructs the Grigorchuk machine or group associated with the infinite sequence <var class="Arg">omega</var>, which is assumed (pre)periodic; <var class="Arg">omega</var> is either a periodic list (see <code class="func">PeriodicList</code> (<a href="chap11.html#X7B401DFE817D3927"><span class="RefLink">11.2-2</span></a>)) or a plain list describing the period. Entries in the list are integers in <code class="code">[1..3]</code>.</p>
<p>These groups are <code class="func">MixerGroup</code> (<a href="chap9.html#X78AFA63B86C94227"><span class="RefLink">9.1-7</span></a>)s. The most famous example is <code class="code">GrigorchukGroups([1,2,3])</code>, which is also called <code class="func">GrigorchukGroup</code> (<a href="chap9.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>).</p>
<p>These groups are all 4-generated and infinite. They are described in <a href="chapBib.html#biBMR764305">[Gri84]</a>. <code class="code">GrigorchukGroups([1])</code> is infinite dihedral. If <var class="Arg">omega</var> contains at least 2 different digits, <code class="code">GrigorchukGroups([1])</code> has intermediate word growth. If <var class="Arg">omega</var> contains all 3 digits, <code class="code">GrigorchukGroups([1])</code> is torsion.</p>
<p>The growth of <code class="code">GrigorchukGroups([1,2])</code> has been studied in <a href="chapBib.html#biBMR2144977">[Ers04]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := GrigorchukGroups([1]);</span>
GrigorchukGroups([ 1 ])
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(G,DerivedSubgroup(G)); IsAbelian(DerivedSubgroup(G));</span>
4
true
<span class="GAPprompt">gap></span> <span class="GAPinput">H := GrigorchukGroups([1,2]);</span>
GrigorchukGroups([ 1, 2 ])
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(H.1*H.2);</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(H.1*H.4);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(H,G);</span>
true
</pre></div>
<p><a id="X85BAE48780E665A4" name="X85BAE48780E665A4"></a></p>
<h5>9.1-10 GrigorchukMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is Grigorchuk's first group, introduced in [Gri80]. It is a 4-generated infinite torsion group, and has intermediate word growth. It could have been defined as FRGroup("a=(1,2)","b=<a,c>","c=<a,d>","d=<,b>"), but is rather defined using Mealy elements.
<p>The command <code class="code">EpimorphismFromFpGroup(GrigorchukGroup,n)</code> constructs an approximating presentation for the Grigorchuk group, as proven in <a href="chapBib.html#biBMR819415">[Lys85]</a>. Adding the relations <code class="code">Image(sigma^(n-2),(a*d)^2)</code>, <code class="code">Image(sigma^(n-1),(a*b)^2)</code> and <code class="code">Image(sigma^(n-2),(a*c)^4)</code> yields the quotient acting on <span class="SimpleMath">2^n</span> points, as a finitely presented group.</p>
<p><a id="X800640597E9C707D" name="X800640597E9C707D"></a></p>
<h5>9.1-11 GrigorchukOverGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukOverGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a group strictly containing the Grigorchuk group (see <code class="func">GrigorchukGroup</code> (<a href="chap9.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>)). It also has intermediate growth (see <a href="chapBib.html#biBMR1899368">[BG02]</a>, but it contains elements of infinite order. It could have been defined as <code class="code">FRGroup("a=(1,2)","b=<a,c>","c=<,d>","d=<,b>")</code>, but is rather defined using Mealy elements.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(GrigorchukOverGroup,GrigorchukGroup);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(Product(GeneratorsOfGroup(GrigorchukOverGroup)));</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">GrigorchukGroup.2=GrigorchukSuperGroup.2*GrigorchukSuperGroup.3;</span>
true
</pre></div>
<p>The command <code class="code">EpimorphismFromFpGroup(GrigorchukOverGroup,n)</code> will will construct an approximating presentation for the Grigorchuk overgroup, as proven in <a href="chapBib.html#biBMR2009317">[Bar03a]</a>.</p>
<p><a id="X7E765AF77AAC21A6" name="X7E765AF77AAC21A6"></a></p>
<h5>9.1-12 GrigorchukTwistedTwin</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrigorchukTwistedTwin</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a group with same closure as the Grigorchuk group (see <code class="func">GrigorchukGroup</code> (<a href="chap9.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>)), but not isomorphic to it. It could have been defined as <code class="code">FRGroup("a=(1,2)","x=<y,a>","y=<a,z>","z=<,x>")</code>, but is rather defined using Mealy elements.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AbelianInvariants(GrigorchukTwistedTwin);</span>
[ 2, 2, 2, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AbelianInvariants(GrigorchukGroup);</span>
[ 2, 2, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PermGroup(GrigorchukGroup,8)=PermGroup(GrigorchukTwistedTwin,8);</span>
true
</pre></div>
<p><a id="X7F93EC437B5AE276" name="X7F93EC437B5AE276"></a></p>
<h5>9.1-13 BrunnerSidkiVieiraGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BrunnerSidkiVieiraGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BrunnerSidkiVieiraMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This machine is the sum of two adding machines, one in standard form and one conjugated by the element <code class="code">d</code> described below. The group that it generates is described in <a href="chapBib.html#biBMR1656573">[BSV99]</a>. It could have been defined as <code class="code">FRGroup("tau=<,tau>(1,2)","mu=<,mu^-1>(1,2)")</code>, but is rather defined using Mealy elements.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">V := FRGroup("d=<e,e>(1,2)","e=<d,d>");</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Elements(V);</span>
[ <2|identity ...>, <2|e>, <2|d>, <2|e*d> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(BrunnerSidkiVieiraGroup);</span>
#I Assigned the global variables [ "tau", "mu", "" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List(V,x->tau^x)=[tau,mu,mu^-1,tau^-1];</span>
true
</pre></div>
<p><a id="X7F8A028B799946D3" name="X7F8A028B799946D3"></a></p>
<h5>9.1-14 AleshinGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AleshinGroups</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AleshinMachines</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The Aleshin machine with <code class="code">Length(l)</code> states.</p>
<p>This function constructs the bireversible machines introduced by Aleshin in <a href="chapBib.html#biBMR713968">[Ale83]</a>. The argument <var class="Arg">l</var> is a list of permutations, either <code class="code">()</code> or <code class="code">(1,2)</code>. The groups that they generate are contructed as <code class="func">AleshinGroups</code>.</p>
<p>If <code class="code">l=[(1,2),(1,2),()]</code>, this is <code class="func">AleshinGroup</code> (<a href="chap9.html#X7C286D3A84790ECE"><span class="RefLink">9.1-15</span></a>). More generally, if <code class="code">l=[(1,2,(1,2),(),...,()]</code> has odd length, this is a free group of rank <code class="code">Length(l)</code>, see <a href="chapBib.html#biBMR2318547">[VV07]</a> and <a href="chapBib.html#biB0604328">[VV06]</a>.</p>
<p>If <code class="code">l=[(1,2),(1,2),...]</code> has even length and contains an even number of <code class="code">()</code>'s, then this is also a free group of rank Length(l), see [SVV06].
<p>If <code class="code">l=[(),(),(1,2)]</code>, this is <code class="func">BabyAleshinGroup</code> (<a href="chap9.html#X7E024B4D7BA411B1"><span class="RefLink">9.1-16</span></a>). more generally, if <code class="code">l=[(),(),...]</code> has even length and contains an even number of <code class="code">(1,2)</code>'s, then this is the free product of Length(l) copies of the order-2 group.
<p><a id="X7C286D3A84790ECE" name="X7C286D3A84790ECE"></a></p>
<h5>9.1-15 AleshinGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AleshinGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AleshinMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is the first example of non-abelian free group. It is the group generated by <code class="code">AleshinMachine([(1,2),(1,2),()])</code>. It could have been defined as <code class="code">FRGroup("a=<b,c>(1,2)","b=<c,b>(1,2)","c=<a,a>")</code>, but is rather defined using Mealy elements.</p>
<p><a id="X7E024B4D7BA411B1" name="X7E024B4D7BA411B1"></a></p>
<h5>9.1-16 BabyAleshinGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BabyAleshinGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BabyAleshinMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>There are only two connected, transitive bireversible machines on a 2-letter alphabet, with 3 generators: <code class="code">AleshinMachine(3)</code> and the baby Aleshin machine.</p>
<p>The group generated by this machine is abstractly the free product of three <span class="SimpleMath">C_2</span>'s, see [Nek05, 1.10.3]. It could have been defined as FRGroup("a=<b,c>","b=<c,b>","c=<a,a>(1,2)"), but is rather defined here using Mealy elements.
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">K := Kernel(GroupHomomorphismByImagesNC(BabyAleshinGroup,Group((1,2)),</span>
GeneratorsOfGroup(BabyAleshinGroup),[(1,2),(1,2),(1,2)]));
<self-similar group over [ 1 .. 2 ] with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(BabyAleshinGroup,K);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(AleshinGroup,K);</span>
true
</pre></div>
<p><a id="X8108E3A8872A6FFE" name="X8108E3A8872A6FFE"></a></p>
<h5>9.1-17 SidkiFreeGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SidkiFreeGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a group suggested by Sidki as an example of a non-abelian state-closed free group. Nothing is known about that group: whether it is free as conjectured; whether generator <var class="Arg">a</var> is state-closed, etc. It is defined as <code class="code">FRGroup("a=<a^2,a^t>","t=<,t>(1,2)")]]></code>.</p>
<p><a id="X82D3CB6A7C189C78" name="X82D3CB6A7C189C78"></a></p>
<h5>9.1-18 GuptaSidkiGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GuptaSidkiGroups</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneralizedGuptaSidkiGroups</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GuptaSidkiMachines</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The Gupta-Sidki group/machine on an <var class="Arg">n</var>-letter alphabet.</p>
<p>This function constructs the machines introduced by Gupta and Sidki in <a href="chapBib.html#biBMR696534">[GS83]</a>. They generate finitely generated infinite torsion groups: the exponent of every element divides some power of <var class="Arg">n</var>. The special case <span class="SimpleMath">n=3</span> is defined as <code class="func">GuptaSidkiGroup</code> (<a href="chap9.html#X83E59288860EF661"><span class="RefLink">9.1-19</span></a>) and <code class="func">GuptaSidkiMachine</code> (<a href="chap9.html#X83E59288860EF661"><span class="RefLink">9.1-19</span></a>).</p>
<p>For <span class="SimpleMath">n>3</span>, there are (at least) two natural ways to generalize the Gupta-Sidki construction: the original one involves the recursion <code class="code">"t=<a,a^-1,1,...,1,t>"</code>, while the second (called here `generalized') involves the recursion "t=<a,a^2,...,a^-1,t>". A finite L-presentation for the latter is implemented. It is not as computationally efficient as the L-presentation of the normal closure of t (a subgroup of index p), which is an ascending L-presented group. The inclusion of that subgroup may be recoverd via EmbeddingOfAscendingSubgroup(GuptaSidkiGroup).
<p><a id="X83E59288860EF661" name="X83E59288860EF661"></a></p>
<h5>9.1-19 GuptaSidkiGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GuptaSidkiGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GuptaSidkiMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an infinite, 2-generated, torsion 3-group. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,a^-1,t>")</code>, but is rather defined using Mealy elements.</p>
<p><a id="X8521B4FF7BA189B2" name="X8521B4FF7BA189B2"></a></p>
<h5>9.1-20 NeumannGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NeumannGroup</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NeumannMachine</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The Neumann group/machine on the permutation group <var class="Arg">P</var>.</p>
<p>The first function constructs the Neumann group associated with the permutation group <var class="Arg">P</var>. These groups were first considered in <a href="chapBib.html#biBMR840129">[Neu86]</a>. In particular, <code class="code">NeumannGroup(PSL(3,2))</code> is a group of non-uniform exponential growth (see <a href="chapBib.html#biBMR1981466">[Bar03b]</a>), and <code class="code">NeumannGroup(Group((1,2,3)))</code> is <code class="func">FabrykowskiGuptaGroup</code> (<a href="chap9.html#X878D1C7080EA9797"><span class="RefLink">9.1-21</span></a>).</p>
<p>The second function constructs the Neumann machine associated to the permutation group <var class="Arg">P</var>. It is a shortcut for <code class="code">MixerMachine(P,P,[[IdentityMapping(P)]])</code>.</p>
<p>The attribute <code class="code">Correspondence(G)</code> is set to a list of homomorphisms from <var class="Arg">P</var> to the <code class="code">A</code> and <code class="code">B</code> copies of <code class="code">P</code>.</p>
<p><a id="X878D1C7080EA9797" name="X878D1C7080EA9797"></a></p>
<h5>9.1-21 FabrykowskiGuptaGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FabrykowskiGuptaGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FabrykowskiGuptaGroups</code>( <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is an infinite, 2-generated group of intermediate word growth. It was studied in <a href="chapBib.html#biBMR942349">[FG85]</a> and <a href="chapBib.html#biBMR1153150">[FG91]</a>. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,,t>")</code>, but is rather defined using Mealy elements. It has a torsion-free subgroup of index 3 and is branched.</p>
<p>The natural generalization, replacing 3 by <span class="SimpleMath">p</span>, is constructed by the second form. It is a specific case of Neumann group (see <code class="func">NeumannGroup</code> (<a href="chap9.html#X8521B4FF7BA189B2"><span class="RefLink">9.1-20</span></a>)), for which an ascending L-presentation is known.</p>
<p><a id="X7C5ADAE77EA3876D" name="X7C5ADAE77EA3876D"></a></p>
<h5>9.1-22 ZugadiSpinalGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ZugadiSpinalGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an infinite, 2-generated group, which was studied in <a href="chapBib.html#biBMR1899368">[BG02]</a>. It has a torsion-free subgroup of index 3, and is virtually branched but not branched. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,a,t>")</code>, but is rather defined using Mealy elements.</p>
<p>Amaia Zugadi computed its Hausdorff dimension to be <span class="SimpleMath">1/2</span>.</p>
<p><a id="X7A0319827CB51ED0" name="X7A0319827CB51ED0"></a></p>
<h5>9.1-23 GammaPQMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GammaPQMachine</code>( <var class="Arg">p</var>, <var class="Arg">q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GammaPQGroup</code>( <var class="Arg">p</var>, <var class="Arg">q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The quaternion-based machine / SC group.</p>
<p>The first function constructs a bireversible (see <code class="func">IsBireversible</code> (<a href="chap5.html#X80D2545D7D0990A2"><span class="RefLink">5.2-7</span></a>)) Mealy machine based on quaternions, see <a href="chapBib.html#biBMR1839488">[BM00a]</a> and <a href="chapBib.html#biBMR1839489">[BM00b]</a>. This machine has <span class="SimpleMath">p+1</span> states indexed by integer quaternions of norm <var class="Arg">p</var>, and an alphabet of size <span class="SimpleMath">q+1</span> indexed by quaternions of norm <var class="Arg">q</var>. These quaternions are congruent to <span class="SimpleMath">1mod 2</span> or <span class="SimpleMath">imod 2</span> depending on whether the odd prime <span class="SimpleMath">p</span> or <span class="SimpleMath">q</span> is <span class="SimpleMath">1</span> or <span class="SimpleMath">3mod 4</span>.</p>
<p>The structure of the machine is such that there is a transition from <span class="SimpleMath">(q,a)</span> to <span class="SimpleMath">(q',a')</span> precisely when <span class="SimpleMath">qa'=± q'a</span>. In particular, the relations of the <code class="func">StructuralGroup</code> (<a href="chap3.html#X8289C2F77D67EDC3"><span class="RefLink">3.5-1</span></a>) hold up to a sign, when the alphabet/state letters are substituted for the appropriate quaternions.</p>
<p>The quaternions themselves can be recovered through <code class="func">Correspondence</code> (<a href="chap3.html#X7C107A42815F91DA"><span class="RefLink">3.5-12</span></a>), which is a list with in first position the quaternions of norm <span class="SimpleMath">p</span> and in second those of norm <span class="SimpleMath">q</span>.</p>
<p>The second function constructs the quaternion lattice that is the <code class="func">StructuralGroup</code> (<a href="chap3.html#X8289C2F77D67EDC3"><span class="RefLink">3.5-1</span></a>) of that machine. It has actions on two trees, given by <code class="func">VerticalAction</code> (<a href="chap9.html#X7F852A357D7E2E76"><span class="RefLink">9.5-2</span></a>) and <code class="func">HorizontalAction</code> (<a href="chap9.html#X7F852A357D7E2E76"><span class="RefLink">9.5-2</span></a>); the ranges of these actions are groups generated by automata, which are infinitely-transitive (see <code class="func">IsInfinitelyTransitive</code> (<a href="chap7.html#X7D95219481AEDD20"><span class="RefLink">7.2-13</span></a>)) and free by <a href="chapBib.html#biBMR2155175">[GM05, Proposition 3.3]</a>; see also <a href="chapBib.html#biBMR713968">[Ale83]</a>.</p>
<p><a id="X80B617717C2887D4" name="X80B617717C2887D4"></a></p>
<h5>9.1-24 RattaggiGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RattaggiGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This record contains interesting examples of VH groups, that were studied by Rattaggi in his PhD thesis <a href="chapBib.html#biBRattaggi">[Rat04]</a>. His Example 2.x appears as <code class="code">RattaggiGroup.2_x</code>.</p>
<p>The following summary of the examples' properties are copied from Rattaggi's thesis. RF means "residually finite"; JI means "just infinite"; VS means "virtually simple".</p>
<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdright">Example</td>
<td class="tdcenter"><span class="SimpleMath">P_h</span></td>
<td class="tdcenter"><span class="SimpleMath">P_v</span></td>
<td class="tdcenter">Irred?</td>
<td class="tdcenter">Linear?</td>
<td class="tdcenter">RF?</td>
<td class="tdcenter">JI?</td>
<td class="tdcenter">VS?</td>
</tr>
<tr>
<td class="tdright">2.2</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N?</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y?</td>
</tr>
<tr>
<td class="tdright">2.15</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.18</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.21</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.26</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">q-prim</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
</tr>
<tr>
<td class="tdright">2.30</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y?</td>
</tr>
<tr>
<td class="tdright">2.36</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.39</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.43</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y</td>
</tr>
<tr>
<td class="tdright">2.46</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.48</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.50</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.52</td>
<td class="tdcenter">tr</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
</tr>
<tr>
<td class="tdright">2.56</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">2.58</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">prim</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N?</td>
<td class="tdcenter">N</td>
<td class="tdcenter">N</td>
</tr>
<tr>
<td class="tdright">2.70</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.26</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">2tr</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">Y</td>
<td class="tdcenter">N</td>
</tr>
<tr>
<td class="tdright">3.28</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.31</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.33</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.36</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.38</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.40</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.44</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.46</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr>
<td class="tdright">3.72</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
</table><br />
</div>
<p><a id="X7A0BE9F57B401C5C" name="X7A0BE9F57B401C5C"></a></p>
<h5>9.1-25 HanoiGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HanoiGroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The Hanoi group on an <var class="Arg">n</var> pegs.</p>
<p>This function constructs the Hanoi group on <var class="Arg">n</var> pegs. Generators of the group correspond to moving a peg, and tree vertices correspond to peg configurations. This group is studied in <a href="chapBib.html#biBMR2217913">[G{Š}06]</a>.</p>
<p><a id="X7C7A0EEF7EFF8B99" name="X7C7A0EEF7EFF8B99"></a></p>
<h5>9.1-26 DahmaniGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DahmaniGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an example of a non-contracting weakly branched group. It was first studied in <a href="chapBib.html#biBMR2140091">[Dah05]</a>. It could have been defined as <code class="code">FRGroup("a=<c,a>(1,2)","b=<b,a>(1,2)","c=<b,c>")</code>, but is rather defined using Mealy elements.</p>
<p>It has relators <span class="SimpleMath">abc</span>, <span class="SimpleMath">[a^2c,[a,c]]</span>, <span class="SimpleMath">[cab,a^-1c^-1ab]</span> and <span class="SimpleMath">[ac^2,c^-1b^-1c^2]</span> among others.</p>
<p>It admits an endomorphism on its derived subgroup. Indeed <code class="code">FRElement(1,Comm(a,b))=Comm(c^-1,b/a)</code>, <code class="code">FRElement(1,Comm(a,c))=Comm(a/b,c)</code>, <code class="code">FRElement(1,Comm(b,c))=Comm(c,(a/b)^c)</code>.</p>
<p><a id="X7C958AB78484E256" name="X7C958AB78484E256"></a></p>
<h5>9.1-27 MamaghaniGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MamaghaniGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This group was studied in <a href="chapBib.html#biBMR2139928">[Mam03]</a>. It is fractal, but not contracting. It could have been defined as <code class="code">FRGroup("a=<,b>(1,2)","b=<a,c>","c=<a,a^-1>(1,2)")]]></code>, but is rather defined using Mealy elements. It partially admits branching on its subgroup <code class="code">Subgroup(G,[a^2,(a^2)^b,(a^2)^c])</code>, and, setting <code class="code">x=Comm(a^2,b)</code>, on <code class="code">Subgroup(G,[x,x^a,x^b,x^(b*a),x^(b/a)])</code>. One has <code class="code">FRElement(1,x)=(x^-1)^b/x</code>.</p>
<p><a id="X86D952E8784E4D97" name="X86D952E8784E4D97"></a></p>
<h5>9.1-28 WeierstrassGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WeierstrassGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is the iterated monodromy group associated with the Weierstrass <span class="SimpleMath">℘</span>-function.</p>
<p>Some relators in the group: <span class="SimpleMath">(atbt)^4</span>, <span class="SimpleMath">((atbt)(bt)^4n)^4</span>, <span class="SimpleMath">((atbt)^2(bt)^4n)^2</span>.</p>
<p>Set <span class="SimpleMath">x=[a,t]</span>, <span class="SimpleMath">y=[b,t]</span>, <span class="SimpleMath">z=[c,t]</span>, and <span class="SimpleMath">w=[x,y]</span>. Then <span class="SimpleMath">G'=⟨ x,y,z⟩ of index 8, and γ_3=⟨[{x,y,z},{a,b,c}]⟩ of index 32, and γ_4=G''=⟨ w⟩^G, of index 256, and G''>(G'')^4 since [[t^a,t],[t^b,t]]=(w,1,1,1).
<p>The Schreier graph is obtained in the complex plane as the image of a <span class="SimpleMath">2^n× 2^n</span> lattice in the torus, via Weierstrass's ℘-function.
<p>The element <span class="SimpleMath">at</span> has infinite order.</p>
<p><span class="SimpleMath">[c,t,b][b,t,c][a,t,c][c,t,a]</span> has order 2, and belongs to <span class="SimpleMath">G''</span>; so there exist elements of arbitrary large finite order in the group.</p>
<p><a id="X80D59AFF7E7D3B8B" name="X80D59AFF7E7D3B8B"></a></p>
<h5>9.1-29 StrichartzGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StrichartzGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This group generates the graph of the Strichartz hexacarpet.</p>
<p>The Strichartz hexacarpet is the dual graph to the infinitely iterated barycentric subdivision of the triangle. The Strichartz group acts on <span class="SimpleMath">{1,dots,6}^n</span> for all <span class="SimpleMath">n</span>, and the Schreier graph with <span class="SimpleMath">6^n</span> vertices is the <span class="SimpleMath">n</span>th Strichartz graph.</p>
<p>Conjecturally, that graph's radius is 1/18(2^(n+1)(13+3n)+(-1)^n-9) and its diameter is 1/9(2^(n-1)(31+12n)+2(-1)^(n-1)-18).
<p>See <a href="chapBib.html#biBMR3004256">[BKN+12]</a> for details.</p>
<p><a id="X86B124758135DFBD" name="X86B124758135DFBD"></a></p>
<h5>9.1-30 FRAffineGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FRAffineGroup</code>( <var class="Arg">d</var>, <var class="Arg">R</var>, <var class="Arg">u</var>[, <var class="Arg">transversal</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The <var class="Arg">d</var>-dimensional affine group over <var class="Arg">R</var>.</p>
<p>This function constructs a new FR group <code class="code">G</code>, which is finite-index subgroup of the <var class="Arg">d</var>-dimensional affine group over <span class="SimpleMath">R_u</span>, the local ring over <var class="Arg">R</var> in which all non-multiples of <var class="Arg">u</var> are invertible. Since no generators of <code class="code">G</code> are known, <code class="code">G</code> is in fact returned as a full SC group; only its attribute <code class="code">Correspondence(G)</code>, which is a homomorphism from <span class="SimpleMath">GL_d+1(R_u)</span> to <code class="code">G</code>, is relevant.</p>
<p>The affine group can also be described as a subgroup of <span class="SimpleMath">GL_d+1(R_u)</span>, consisting of those matrices <span class="SimpleMath">M</span> with <span class="SimpleMath">M_i,d+1=0</span> and <span class="SimpleMath">M_d+1,d+1=1</span>. The finite-index subgroup is defined by the conditions <span class="SimpleMath">u|M_i,j</span> for all <span class="SimpleMath">j<i</span>.</p>
<p>The only valid arguments are <code class="code">R=Integers</code> and <code class="code">R=PolynomialRing(S)</code> for a finite ring <code class="code">S</code>. The alphabet of the affine group is < | | |
