Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/walrus/tst/   (GAP Algebra Version 4.15.1©)  Datei vom 21.1.2022 mit Größe 91 B image not shown  

Quelle  chap9_mj.html   Sprache: unbekannt

 
<?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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap8_mj.html">[Previous Chapter]</a>    <a href="chap10_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap9.html">[MathJax off]</a></p>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>
<div class="ChapSects"><a href="chap9_mj.html#X7A489A5D79DA9E5C">9 <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.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_mj.html#X7D774B847D81E6DE">9.1-1 FullBinaryGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X813F53C57F41F5F5">9.1-2 BinaryKneadingGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B8D49D079D336E8">9.1-3 BasilicaGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X8449487686E00D22">9.1-4 FornaessSibonyGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X85F4FDF787173863">9.1-5 AddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7A4BB24A805CDF63">9.1-6 BinaryAddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X78AFA63B86C94227">9.1-7 MixerGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X84C97E0687F119C0">9.1-8 SunicGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X79E3F3BE80F34590">9.1-9 GrigorchukMachines</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X85BAE48780E665A4">9.1-10 GrigorchukMachine</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X800640597E9C707D">9.1-11 GrigorchukOverGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7E765AF77AAC21A6">9.1-12 GrigorchukTwistedTwin</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7F93EC437B5AE276">9.1-13 BrunnerSidkiVieiraGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7F8A028B799946D3">9.1-14 AleshinGroups</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C286D3A84790ECE">9.1-15 AleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7E024B4D7BA411B1">9.1-16 BabyAleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X8108E3A8872A6FFE">9.1-17 SidkiFreeGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X82D3CB6A7C189C78">9.1-18 GuptaSidkiGroups</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X83E59288860EF661">9.1-19 GuptaSidkiGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X8521B4FF7BA189B2">9.1-20 NeumannGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X878D1C7080EA9797">9.1-21 FabrykowskiGuptaGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C5ADAE77EA3876D">9.1-22 ZugadiSpinalGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7A0319827CB51ED0">9.1-23 GammaPQMachine</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X80B617717C2887D4">9.1-24 RattaggiGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7A0BE9F57B401C5C">9.1-25 HanoiGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C7A0EEF7EFF8B99">9.1-26 DahmaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C958AB78484E256">9.1-27 MamaghaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X86D952E8784E4D97">9.1-28 WeierstrassGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X80D59AFF7E7D3B8B">9.1-29 StrichartzGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X86B124758135DFBD">9.1-30 FRAffineGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7CFBE31A78F2681B">9.1-31 CayleyGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.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_mj.html#X87541DA582705033">9.2-1 I2Machine</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B32ED3D8715FA4B">9.2-2 I4Machine</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.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_mj.html#X80E15ABC879F8EE2">9.3-1 PSZAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7D015CA5829FAA2A">9.3-2 GrigorchukThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B66ED537D0A43AF">9.3-3 GuptaSidkiThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X86CE9A8787F69DBC">9.3-4 GrigorchukLieAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B0B5B09878C7CEA">9.3-5 SidkiFreeAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7988B29F836BAA62">9.3-6 SidkiMonomialAlgebra</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X7989134C83AF38AE">9.4 <span class="Heading">Bacher's determinant identities</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.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_mj.html#X7E0071D4838B239D">9.5-1 VHStructure</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7F852A357D7E2E76">9.5-2 VerticalAction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X86B1C2F079FE8D82">9.5-3 VHGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7D1FCB877D1B96EA">9.5-4 IsIrreducibleVHGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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">&#an style='color: green'>8227; 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_mj.html#biBMR2176547">[BV05]</a> and <a href="chapBib_mj.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">&#an style='color: green'>8227; 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_mj.html#biB0811.2777">[Nek08b]</a>. It is the iterated monodromy group of the endomorphism of <span class="SimpleMath">\(\mathbb CP^2\)</span> defined by <span class="SimpleMath">\((z,p)\mapsto((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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.html#biBMR1856923">[B{Š}01]</a> and <a href="chapBib_mj.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_mj.html#X79E3F3BE80F34590"><span class="RefLink">9.1-9</span></a>), <code class="func">NeumannGroup</code> (<a href="chap9_mj.html#X8521B4FF7BA189B2"><span class="RefLink">9.1-20</span></a>), <code class="func">GuptaSidkiGroups</code> (<a href="chap9_mj.html#X82D3CB6A7C189C78"><span class="RefLink">9.1-18</span></a>), and <code class="func">ZugadiSpinalGroup</code> (<a href="chap9_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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]/(\phi)\)</span>, where <span class="SimpleMath">\(\phi\)</span> is a monic polynomial; there is a map <span class="SimpleMath">\(f:B\to A\)</span>, given say by evaluation; and there is an endomorphism of <span class="SimpleMath">\(g:B\to B\)</span> given by multiplication by <span class="SimpleMath">\(\phi\)</span>.</p>

<p>These groups were described in <a href="chapBib_mj.html#biBMR2318546">[{Š}un07]</a>. In particular, the case <span class="SimpleMath">\(q=2\)</span> and <span class="SimpleMath">\(\phi=x^2+x+1\)</span> gives the original <code class="func">GrigorchukGroup</code> (<a href="chap9_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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_mj.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_mj.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_mj.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_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; GrigorchukGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is Grigorchuk's first group, introduced in <a href="chapBib_mj.html#biBMR565099">[Gri80]</a>. It is a 4-generated infinite torsion group, and has intermediate word growth. It could have been defined as <code class="code">FRGroup("a=(1,2)","b=<a,c>","c=<a,d>","d=<,b>")</code>, but is rather defined using Mealy elements.</p>

<p>The command <code class="code">EpimorphismFromFpGroup(GrigorchukGroup,n)</code> constructs an approximating presentation for the Grigorchuk group, as proven in <a href="chapBib_mj.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">&#an style='color: green'>8227; 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_mj.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>)). It also has intermediate growth (see <a href="chapBib_mj.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_mj.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">&#an style='color: green'>8227; 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_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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_mj.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_mj.html#biBMR2318547">[VV07]</a> and <a href="chapBib_mj.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 <code class="code">Length(l)</code>, see <a href="chapBib_mj.html#biB0610033">[SVV06]</a>.</p>

<p>If <code class="code">l=[(),(),(1,2)]</code>, this is <code class="func">BabyAleshinGroup</code> (<a href="chap9_mj.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 <code class="code">Length(l)</code> copies of the order-2 group.</p>

<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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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 <a href="chapBib_mj.html#biBMR2162164">[Nek05, 1.10.3]</a>. It could have been defined as <code class="code">FRGroup("a=<b,c>","b=<c,b>","c=<a,a>(1,2)")</code>, but is rather defined here using Mealy elements.</p>


<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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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_mj.html#X83E59288860EF661"><span class="RefLink">9.1-19</span></a>) and <code class="func">GuptaSidkiMachine</code> (<a href="chap9_mj.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 <code class="code">"t=<a,a^2,...,a^-1,t>"</code>. A finite L-presentation for the latter is implemented. It is not as computationally efficient as the L-presentation of the normal closure of <code class="code">t</code> (a subgroup of index <span class="SimpleMath">\(p\)</span>), which is an ascending L-presented group. The inclusion of that subgroup may be recoverd via <code class="code">EmbeddingOfAscendingSubgroup(GuptaSidkiGroup)</code>.</p>

<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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.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_mj.html#biBMR1981466">[Bar03b]</a>), and <code class="code">NeumannGroup(Group((1,2,3)))</code> is <code class="func">FabrykowskiGuptaGroup</code> (<a href="chap9_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.html#biBMR942349">[FG85]</a> and <a href="chapBib_mj.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_mj.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">&#an style='color: green'>8227; 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_mj.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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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_mj.html#X80D2545D7D0990A2"><span class="RefLink">5.2-7</span></a>)) Mealy machine based on quaternions, see <a href="chapBib_mj.html#biBMR1839488">[BM00a]</a> and <a href="chapBib_mj.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">\(1\pmod 2\)</span> or <span class="SimpleMath">\(i\pmod 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">\(3\pmod 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'=\pm q'a\)</span>. In particular, the relations of the <code class="func">StructuralGroup</code> (<a href="chap3_mj.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_mj.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_mj.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_mj.html#X7F852A357D7E2E76"><span class="RefLink">9.5-2</span></a>) and <code class="func">HorizontalAction</code> (<a href="chap9_mj.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_mj.html#X7D95219481AEDD20"><span class="RefLink">7.2-13</span></a>)) and free by <a href="chapBib_mj.html#biBMR2155175">[GM05, Proposition 3.3]</a>; see also <a href="chapBib_mj.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">&#an style='color: green'>8227; 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_mj.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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">2.18</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">2.21</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">2.39</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">2.48</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">2.50</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.31</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.33</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.36</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.38</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.40</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.44</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.46</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
</tr>
<tr>
<td class="tdright">3.72</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</td>
<td>&#160;</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">&#an style='color: green'>8227; 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_mj.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">&#an style='color: green'>8227; 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_mj.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^{-1}c^{-1}ab]\)</span> and <span class="SimpleMath">\([ac^2,c^{-1}b^{-1}c^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">&#an style='color: green'>8227; MamaghaniGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This group was studied in <a href="chapBib_mj.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">&#an style='color: green'>8227; 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">\(\wp\)</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'=\langle x,y,z\rangle\)</span> of index 8, and <span class="SimpleMath">\(\gamma_3=\langle[\{x,y,z\},\{a,b,c\}]\rangle\)</span> of index 32, and <span class="SimpleMath">\(\gamma_4=G''=\langle w\rangle^G\)</span>, of index 256, and <span class="SimpleMath">\(G''>(G'')^4\)</span> since <span class="SimpleMath">\([[t^a,t],[t^b,t]]=(w,1,1,1)\)</span>.</p>

<p>The Schreier graph is obtained in the complex plane as the image of a <span class="SimpleMath">\(2^n\times 2^n\)</span> lattice in the torus, via Weierstrass's <span class="SimpleMath">\(\wp\)</span>-function.</p>

<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">&#an style='color: green'>8227; 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 <span class="SimpleMath">\(1/18(2^(n+1)(13+3n)+(-1)^n-9)\)</span> and its diameter is <span class="SimpleMath">\(1/9(2^(n-1)(31+12n)+2(-1)^(n-1)-18)\)</span>.</p>

<p>See <a href="chapBib_mj.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">&#an style='color: green'>8227; 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 <span class="SimpleMath">\(R/RuR\)</span>; an explicit transversal of <span class="SimpleMath">\(RuR\)</span> be specified as last argument.</p>

<p>The following examples construct the "Baumslag-Solitar group" <span class="SimpleMath">\(\mathbb Z[\frac12]\rtimes_2\mathbb Z\)</span> first introduced in <a href="chapBib_mj.html#biBMR0142635">[BS62]</a>, the "lamplighter group" <span class="SimpleMath">\((\mathbb Z/2)\wr\mathbb Z\)</span>, and a 2-dimensional affine group. Note that the lamplighter group may also be defined via <code class="func">CayleyGroup</code> (<a href="chap9_mj.html#X7CFBE31A78F2681B"><span class="RefLink">9.1-31</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := FRAffineGroup(1,Integers,3);</span>
<self-similar group over [ 1 .. 3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := Correspondence(A);</span>
MappingByFunction( ( Integers^
[ 2, 2 ] ), <self-similar group over [ 1 .. 3 ]>, function( mat ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">BaumslagSolitar := Group([[2,0],[0,1]]^f,[[1,0],[1,1]]^f);</span>
<self-similar group over [ 1 .. 3 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">BaumslagSolitar.2^BaumslagSolitar.1=BaumslagSolitar.2^2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">R := PolynomialRing(GF(2));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := FRAffineGroup(1,R,R.1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := Correspondence(A);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lamplighter := Group(([[1+R.1,0],[0,1]]*One(R))^f,([[1,0],[1,1]]*One(R))^f);</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Lamplighter = CayleyGroup(Group((1,2)));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(Group(Lamplighter.2,Lamplighter.2^Lamplighter.1));</span>
"C2 x C2"
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([1..10],i->IsOne(Comm(Lamplighter.2,Lamplighter.2^(Lamplighter.1^i))));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">A := FRAffineGroup(2,Integers,2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := Correspondence(A);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := [[1,4,0],[2,3,0],[1,0,1]];</span>
[ [ 1, 4, 0 ], [ 2, 3, 0 ], [ 1, 0, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b := [[1,2,0],[4,3,0],[0,1,1]];</span>
[ [ 1, 2, 0 ], [ 4, 3, 0 ], [ 0, 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(b^f);</span>
    |   1      2
----+------+------+
  a |  b,1    c,2
  b |  d,2    e,1
  c |  a,2    f,1
...
 bh | cb,1   be,2
 ca | bd,1   bf,2
 cb | ae,2   bh,1
----+------+------+
Initial state:  a
<span class="GAPprompt">gap></span> <span class="GAPinput">a^f*b^f=(a*b)^f;</span>
true
</pre></div>

<p><a id="X7CFBE31A78F2681B" name="X7CFBE31A78F2681B"></a></p>

<h5>9.1-31 CayleyGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; CayleyGroup</code>( <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">&#an style='color: green'>8227; CayleyMachine</code>( <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">&#an style='color: green'>8227; LamplighterGroup</code>( <var class="Arg">IsFRGroup</var>, <var class="Arg">G</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Returns: The Cayley machine/group of the group <var class="Arg">G</var>.</p>

<p>The <em>Cayley machine</em> of a group <var class="Arg">G</var> is a machine with alphabet and stateset equal to <var class="Arg">G</var>, and with output and transition functions given by multiplication in the group, in the order <code class="code">state*letter</code>.</p>

<p>The second function constructs a new FR group <code class="code">CG</code>, which acts on <code class="code">[1..Size(G)]</code>. Its generators are in bijection with the elements of <var class="Arg">G</var>, and have as output the corresponding permutation of <var class="Arg">G</var> induced by right multiplication, and as transitions all elements of <var class="Arg">G</var>; see <code class="func">CayleyMachine</code>. This construction was introduced in <a href="chapBib_mj.html#biBMR2197829">[SS05]</a>.</p>

<p>If <var class="Arg">G</var> is an abelian group, then <code class="code">CG</code> is the wreath product <span class="SimpleMath">\(G\wr\mathbb Z\)</span>; it is created by the constructor <code class="code">LamplighterGroup(IsFRGroup,G)</code>.</p>

<p>The attribute <code class="code">Correspondence(CG)</code> is a list. Its first entry is a homomorphism from <var class="Arg">G</var> into <code class="code">CG</code>. Its second entry is the generator of <code class="code">CG</code> that has trivial output. <code class="code">CG</code> is generated <code class="code">Correspondence(CG)[2]</code> and the image of <code class="code">Correspondence(CG)[1]</code>.</p>

<p>In the example below, recall the definition of <code class="code">Lamplighter</code> in the example of <code class="func">FRAffineGroup</code> (<a href="chap9_mj.html#X86B124758135DFBD"><span class="RefLink">9.1-30</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">L := CayleyGroup(Group((1,2)));</span>
CayleyGroup(Group( [ (1,2) ] ))
<span class="GAPprompt">gap></span> <span class="GAPinput">L=LamplighterGroup(IsFRGroup,CyclicGroup(2));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">(1,2)^Correspondence(L)[1];</span>
<Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinitaryFRElement(last); Display(last2);</span>
true
   |  1     2
---+-----+-----+
 a | b,2   b,1
 b | b,1   b,2
---+-----+-----+
Initial state: a
</pre></div>

<p><a id="X81B82FA1811AAF8D" name="X81B82FA1811AAF8D"></a></p>

<h4>9.2 <span class="Heading">Examples of semigroups</span></h4>

<p><a id="X87541DA582705033" name="X87541DA582705033"></a></p>

<h5>9.2-1 I2Machine</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; I2Machine</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">&#an style='color: green'>8227; I2Monoid</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The Mealy machine <span class="SimpleMath">\(I_2\)</span>, and the monoid that it generates. This is the smallest Mealy machine generating a monoid of intermediate word growth; see <a href="chapBib_mj.html#biBMR2194959">[BRS06]</a>.</p>

<p>For sample calculations in this monoid see <code class="func">SCSemigroup</code> (<a href="chap7_mj.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>).</p>

<p><a id="X7B32ED3D8715FA4B" name="X7B32ED3D8715FA4B"></a></p>

<h5>9.2-2 I4Machine</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; I4Machine</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">&#an style='color: green'>8227; I4Monoid</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The Mealy machine generating <span class="SimpleMath">\(I_4\)</span>, and the monoid that it generates. This is a very small Mealy machine generating a monoid of intermediate word growth; see <a href="chapBib_mj.html#biBMR2394721">[BR08]</a>.</p>

<p>For sample calculations in this monoid see <code class="func">SCMonoid</code> (<a href="chap7_mj.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>).</p>

<p><a id="X803B02408573A30E" name="X803B02408573A30E"></a></p>

<h4>9.3 <span class="Heading">Examples of algebras</span></h4>

<p><a id="X80E15ABC879F8EE2" name="X80E15ABC879F8EE2"></a></p>

<h5>9.3-1 PSZAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PSZAlgebra</code>( <var class="Arg">k</var>[, <var class="Arg">m</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function creates an associative algebra <code class="code">A</code>, over the field <var class="Arg">k</var> of positive characteristic, generated by <var class="Arg">m</var> derivations <code class="code">d0,...,d(m-1),v</code>. If the argument <var class="Arg">m</var> is absent, it is taken to be <code class="code">2</code>.</p>

<p>This algebra has polynomial growth, and is not nilpotent. Petrogradsky showed in <a href="chapBib_mj.html#biBMR2293788">[Pet06]</a> that the Lie subalgebra of <code class="code">PSZAlgebra(GF(2))</code> generated by <span class="SimpleMath">\(v,[u,v]\)</span> is nil; this result was generalized by Shestakov and Zelmanov in <a href="chapBib_mj.html#biBMR2390328">[SZ08]</a> to arbitrary <var class="Arg">k</var> and <span class="SimpleMath">\(m=2\)</span>.</p>

<p>This ring is <span class="SimpleMath">\(\mathbb Z^m\)</span>-graded; the attribute <code class="code">Grading</code> is set. It is graded nil <a href="chapBib_mj.html#biBPSZ">[PSZ]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := PSZAlgebra(2);</span>
PSZAlgebra(GF(2))
<span class="GAPprompt">gap></span> <span class="GAPinput">Nillity(a.1); Nillity(a.2);</span>
2
4
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNilElement(LieBracket(a.1,a.2));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DecompositionOfFRElement(LieBracket(a.1,a.2))=DiagonalMat([a.2,a.2]);</span>
true
</pre></div>

<p><a id="X7D015CA5829FAA2A" name="X7D015CA5829FAA2A"></a></p>

<h5>9.3-2 GrigorchukThinnedAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GrigorchukThinnedAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function creates the associative envelope <code class="code">A</code>, over the field <var class="Arg">k</var>, of Grigorchuk's group <code class="func">GrigorchukGroup</code> (<a href="chap9_mj.html#X85BAE48780E665A4"><span class="RefLink">9.1-10</span></a>).</p>

<p><var class="Arg">k</var> may be a field or an prime representing the prime field <code class="code">GF(k)</code>. In characteristic 2, this ring is graded, and the attribute <code class="code">Grading</code> is set.</p>

<p>For more information on the structure of this thinned algebra, see <a href="chapBib_mj.html#biBMR2254535">[Bar06]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := GrigorchukThinnedAlgebra(2);</span>
<self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators, of dimension infinity>
<span class="GAPprompt">gap></span> <span class="GAPinput">GrigorchukGroup.1^Embedding(GrigorchukGroup,R)=R.1;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Nillity(R.2+R.1);</span>
16
<span class="GAPprompt">gap></span> <span class="GAPinput">x := 1+R.1+R.2+(R.1-1)*(R.4-1); # x has infinite order</span>
<Linear element on alphabet GF(2)^2 with 5-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Inverse(x);</span>
<Linear element on alphabet GF(2)^2 with 9-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Grading(R).hom_components(4);</span>
<vector space of dimension 6 over GF(2)>
<span class="GAPprompt">gap></span> <span class="GAPinput">Random(last);</span>
<Linear element on alphabet GF(2)^2 with 6-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Nillity(last);</span>
4
</pre></div>

<p><a id="X7B66ED537D0A43AF" name="X7B66ED537D0A43AF"></a></p>

<h5>9.3-3 GuptaSidkiThinnedAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GuptaSidkiThinnedAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function creates the associative envelope <code class="code">A</code>, over the field <var class="Arg">k</var>, of Gupta-Sidki's group <code class="func">GuptaSidkiGroup</code> (<a href="chap9_mj.html#X83E59288860EF661"><span class="RefLink">9.1-19</span></a>).</p>

<p><var class="Arg">k</var> may be a field or an prime representing the prime field <code class="code">GF(k)</code>.</p>

<p>For more information on the structure of this thinned algebra, see <a href="chapBib_mj.html#biBMR1423285">[Sid97]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := GuptaSidkiThinnedAlgebra(3);</span>
<self-similar algebra-with-one on alphabet GF(3)^3 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(R.1);</span>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">R.1*R.3;</span>
<Identity linear element on alphabet GF(3)^3>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOne(R.2*R.4);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := 1+R.2*(1+R.1+R.3); # a non-invertible element</span>
<Linear element on alphabet GF(3)^3 with 5-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Inverse(x);</span>
#I  InverseOp: extending to depth 3
#I  InverseOp: extending to depth 4
#I  InverseOp: extending to depth 5
#I  InverseOp: extending to depth 6
Error, user interrupt in
</pre></div>

<p><a id="X86CE9A8787F69DBC" name="X86CE9A8787F69DBC"></a></p>

<h5>9.3-4 GrigorchukLieAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GrigorchukLieAlgebra</code>( <var class="Arg">k</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">&#an style='color: green'>8227; GuptaSidkiLieAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Two more examples of self-similar Lie algebras; see <a href="chapBib_mj.html#biB1003.1125">[Bar10]</a>.</p>

<p><a id="X7B0B5B09878C7CEA" name="X7B0B5B09878C7CEA"></a></p>

<h5>9.3-5 SidkiFreeAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SidkiFreeAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is an example of a free 2-generated associative ring over the <span class="SimpleMath">\(\mathbb Z\)</span>, defined by self-similar matrices. It is due to S. Sidki. The argument is a field on which to construct the algebra. The recursion is <code class="code">s=[[1,0],[0,2*s]]</code> and <code class="code">t=[[0,2*s],[0,2*t]]</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := SidkiFreeAlgebra(Rationals);</span>
<self-similar algebra-with-one on alphabet Rationals^2 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">V := VectorSpace(Rationals,[R.1,R.2]);</span>
<vector space over Rationals, with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := [V];; for i in [1..3] do Add(P,ProductSpace(P[i],V)); od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(P,Dimension);</span>
[ 2, 4, 8, 16 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">R := SidkiFreeAlgebra(GF(3));</span>
<self-similar algebra-with-one on alphabet GF(3)^2 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">V := VectorSpace(GF(3),[R.1,R.2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := [V];; for i in [1..3] do Add(P,ProductSpace(P[i],V)); od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List(P,Dimension);</span>
[ 2, 4, 7, 12 ]
</pre></div>

<p><a id="X7988B29F836BAA62" name="X7988B29F836BAA62"></a></p>

<h5>9.3-6 SidkiMonomialAlgebra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SidkiMonomialAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is an example of a self-similar algebra that does not come from a semigroup; it is due to S. Sidki. The argument is a field on which to construct the algebra. The recursion is <code class="code">s=[[0,0],[1,0]]</code> and <code class="code">t=[[0,t],[0,s]]</code>. Sidki shows that this algebra, like the Grigorchuk thinned algebra in characteristic 2 (see <code class="func">GrigorchukThinnedAlgebra</code> (<a href="chap9_mj.html#X7D015CA5829FAA2A"><span class="RefLink">9.3-2</span></a>)), admits a monomial presentation, and in particular is a graded ring.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := SidkiMonomialAlgebra(Rationals);</span>
<self-similar algebra-with-one on alphabet Rationals^2 with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := FreeSemigroup("s","t");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">lambda := MagmaEndomorphismByImagesNC(m,[m.2,m.1*m.2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u := [m.1^2];; for i in [1..3] do u[2*i] := m.2*u[2*i-1]^lambda; u[2*i+1] := u[2*i]^lambda; od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">u; # first relations</span>
[ s^2, t^3, s*t*s*t*s*t, t^2*s*t^2*s*t^2*s*t,
  s*t*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t,
  t^2*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t,
  s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := MagmaHomomorphismByImagesNC(m,R,[R.1,R.2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Image(pi,u);</span>
[ <Zero linear element on alphabet Rationals^2> ]
<span class="GAPprompt">gap></span> <span class="GAPinput"># growth given by fibonacci numbers</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([0..6],Grading(R).hom_components);</span>
[ <vector space over Rationals, with 1 generators>, <vector space over Rationals, with 2 generators>,
  <vector space of dimension 3 over Rationals>, <vector space of dimension 4 over Rationals>,
  <vector space of dimension 5 over Rationals>, <vector space of dimension 7 over Rationals>,
  <vector space of dimension 8 over Rationals> ]
</pre></div>

<p><a id="X7989134C83AF38AE" name="X7989134C83AF38AE"></a></p>

<h4>9.4 <span class="Heading">Bacher's determinant identities</span></h4>

<p>In his paper <a href="chapBib_mj.html#biBMR2422072">[Bac08]</a>, Roland Bacher exhibits striking formulas for determinants of matrices obtained from binomial coefficients.</p>

<p>The general construction is as follows: let <span class="SimpleMath">\(P\)</span> be an infinite matrix, and let <span class="SimpleMath">\(P(n)\)</span> be its upper <span class="SimpleMath">\(n\times n\)</span> corner. To evaluate <span class="SimpleMath">\(\det P(n)\)</span>, decompose <span class="SimpleMath">\(P=LDR\)</span> where <span class="SimpleMath">\(L,D,R\)</span> are respectively lower triangular, diagonal, and upper triangular, with 1's on the diagonals of <span class="SimpleMath">\(L\)</span> and <span class="SimpleMath">\(R\)</span>. Then that determinant is the product of the first <span class="SimpleMath">\(n\)</span> entries of <span class="SimpleMath">\(D\)</span>.</p>

<p>Bacher considers some natural examples of matrices arising from binomial coefficients, and notes that the matrix <span class="SimpleMath">\(P\)</span> is the limit of a convergent vector element (see <code class="func">IsConvergent</code> (<a href="chap6_mj.html#X7EF5B7417AE6B3F8"><span class="RefLink">6.1-9</span></a>)). He also notes that the decomposition <span class="SimpleMath">\(P=LDR\)</span> may be achieved within vector elements.</p>

<p>As a first example, consider the <span class="SimpleMath">\(n\times n\)</span> matrix <span class="SimpleMath">\(P(n)\)</span> with coefficients <span class="SimpleMath">\(P_{s,t}={s+t \choose s}\pmod 2\)</span>. Here and below, indices start at 0. Let also <span class="SimpleMath">\(ds(n)\)</span> denote the digit-sum of the integer <span class="SimpleMath">\(n\)</span>. Then</p>

<p class="center">\[\det(P(n))=\cases{
(-1)^{n/2} & if $n$ is even,\cr
(-1)^{(n-1)/2+ds((n-1)/2)} & if $n$ is odd.}
\]</p>

<p>For the proof, note that <span class="SimpleMath">\(P\)</span> is a convergent infinite matrix; it may be presented as a self-similar linear element by <code class="code">FRAlgebra("P=[[P,P],[P,0]]")</code>. It then suffices to construct an LR decomposition of <span class="SimpleMath">\(P\)</span> within FR vector elements, following Bacher:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(FRAlgebra(Rationals,</span>
    "P=[[P,P],[P,0]]","L=[[L,0],[L,L]]","D=[[D,0],[0,-D]]"));
<span class="GAPprompt">gap></span> <span class="GAPinput">L*D*TransposedFRElement(L)=P;</span>
true
</pre></div>

<p>and to analyse the elements of the diagonal matrix <span class="SimpleMath">\(D\)</span>.</p>

<p>For a more complicated example, let <span class="SimpleMath">\(v_2\)</span> denote 2-valuation of a rational, and construct the <span class="SimpleMath">\(n\times n\)</span> matrix <span class="SimpleMath">\(V(n)\)</span> with coefficients <span class="SimpleMath">\(V_{s,t}=i^{v_2({s+t \choose s})}\)</span>. Then</p>

<p class="center">\[\det(V(n))=\det(P(n))\prod_{k=1}^{n-1}(1-f(k)i),\]</p>

<p>where <span class="SimpleMath">\(f(k)\)</span> is the regular paper-folding sequence defined by <span class="SimpleMath">\(f(2^n)=1\)</span> and <span class="SimpleMath">\(f(2^n+a)=-f(2^n-a)\)</span> for <span class="SimpleMath">\(1\le a<2^n\)</span>.</p>

<p>This is again proved by noticing that <span class="SimpleMath">\(V\)</span> is a corner in a self-similar element, namely</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(FRAlgebra(GaussianRationals,</span>
     "V1=[[V1,V2],[V2,E(4)*V1]]",
     "V2=[[V1,-E(4)*V1+(1+E(4))*V2],[-E(4)*V1+(1+E(4))*V2,-V1]]"));
<span class="GAPprompt">gap></span> <span class="GAPinput">Activity(V1,3)=</span>
     List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));
true
</pre></div>

<p>The LR decomposition of <span class="SimpleMath">\(V=V1\)</span> can be checked as follows:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(FRAlgebra(GaussianRationals,</span>
     "L1=[[L1,0],[L3,L4]]",
     "L2=[[0,-E(4)*L2],[-L1+L3,-E(4)*L2-E(4)*L4]]:0",
     "L3=[[L1,L2],[-E(4)*L1+(1+E(4))*L3,L2+(1+E(4))*L4]]",
     "L4=[[L1,0],[(1-E(4))*L1+E(4)*L3,L4]]",
     "D1=[[D1,0],[0,D2]]",
     "D2=[[D3,0],[0,2*D1-D2+2*D3]]:-1+E(4)",
     "D3=[[D3,0],[0,-D2]]:-1+E(4)"));
<span class="GAPprompt">gap></span> <span class="GAPinput">L1*D1*TransposedFRElement(L1)=V1;</span>
true
</pre></div>

<p>The LR decomposition can also, in favourable situations, be discovered by <strong class="pkg">FR</strong> through the command <code class="func">LDUDecompositionFRElement</code> (<a href="chap6_mj.html#X796B736286CACF85"><span class="RefLink">6.1-11</span></a>). This approach will be followed below.</p>

<p>For the next example, consider "Beeblebrox reduction" <span class="SimpleMath">\(\beta(4k\pm1)=\pm1,\beta(2k)=0\)</span>, and construct the <span class="SimpleMath">\(n\times n\)</span> matrix <span class="SimpleMath">\(Z(n)\)</span> (named after Zaphod Beeblebrox) with coefficients <span class="SimpleMath">\(Z_{s,t}=\beta({s+t \choose s})\)</span>. Then</p>

<p class="center">\[\det(Z(n))=\prod_{k=1}^{n-1}g(k),\]</p>

<p>where <span class="SimpleMath">\(g(\sum a_i2^i)=(-1)^{a_0}3^{\#\{i:a_i=a_{i+1}=1\}-\#\{i:a_i\neq a_{i+1}=1\}}\)</span> with all <span class="SimpleMath">\(a_i\in\{0,1\}\)</span>.</p>

<p>This is again proved by noticing that <span class="SimpleMath">\(Z\)</span> is a corner in a self-similar element, namely</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">beta := n->Jacobi(-1,n)*(n mod 2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Zaphod := GuessVectorElement(List([0..7],i->List([0..7],j->beta(Binomial(i+j,j)))));</span>
<Linear element on alphabet Rationals^2 with 3-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(Zaphod);</span>
 Rationals |    1     |    2     |
-----------+----------+----------+
  1 |  1  0  0 |  0  1  0 |
    |  1  0  0 |  0  1  0 |
    |  1  0  0 |  0 -1  0 |
-----------+----------+----------+
  2 |  0  0  1 |  0  0  0 |
    |  0  0 -1 |  0  0  0 |
    |  0  0  1 |  0  0  0 |
-----------+----------+----------+
Output:  1  1  1
Initial state:  1  0  0
<span class="GAPprompt">gap></span> <span class="GAPinput">LDUDecompositionFRElement(guessZ);</span>
[ <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
  <Linear element on alphabet Rationals^2 with 2-dimensional stateset>,
  <Linear element on alphabet Rationals^2 with 4-dimensional stateset> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last[2]);</span>
 Rationals |    1    |    2    |
-----------+---------+---------+
  1 |   1   0 |   0   0 |
    |   3   0 |   0   0 |
-----------+---------+---------+
  2 |   0   0 |   0   1 |
    |   0   0 |   0 1/3 |
-----------+---------+---------+
Output:   1  -1
Initial state:   1   0
</pre></div>

<p>and now the recursion read on this diagonal self-similar matrix gives immediately Bacher's recursion for <span class="SimpleMath">\(\det(Z(n))\)</span>.</p>

<p>Bacher notes that the group generated by <span class="SimpleMath">\(a=L_1,b=L_2/2,c=L_3,d=L_4\)</span> in the last example may be of interest. A quick check produces the following relations (slightly rewritten):</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(FRAlgebra(Rationals,</span>
     "a=[[a,0],[c,d]]","b=[[-1/3*a,2*b],[1/3*c,d]]",
     "c=[[a,2*b],[c,d]]","d=[[a,0],[1/3*c,d]]"));
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Group(List([a,b,c,d], x->Activity(x,3)));</span>
<matrix group with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">FindShortGroupRelations(g,10);</span>
[ b*d^-1*c*a^-1,
  c*a^-1*c*a^-1,
  c*a*d^-1*a^-1*d^2*a^-1*b^-1,
  c*a*d^-1*c^-1*b*d*a^-1*b^-1,
  c*d*a^-2*d*a*d^-1*b^-1,
  c*a^2*d^-1*a^-2*d*a*d*a^-2*b^-1,
  d^2*a*d^-2*b^-1*c*a*d*a^-3,
  c*d*a*d^-2*a^-1*d*a*d*a^-2*b^-1 ]
</pre></div>

<p>Consider next the "triangular Beeblebrox matrix" with entries <span class="SimpleMath">\(L_{s,t}=\beta({s \choose t})\)</span>. The recurrence is now given by</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := FRAlgebra(Rationals,</span>
     "L1=[[L1,0],[L2,L3]]",
     "L2=[[L1,0],[L2,-L3]]",
     "L3=[[L1,0],[-L2,L3]]");
<self-similar algebra on alphabet Rationals^2 with 3 generators>
</pre></div>

<p>and it is striking that <span class="SimpleMath">\(A\)</span> is a graded algebra, with <span class="SimpleMath">\(L_1,L_2,L_3\)</span> homogeneous of degree 1, and each homogeneous component is 3-dimensional; all of <span class="SimpleMath">\(L_1,L_2,L_3\)</span> are invertible (with inverses have degree <span class="SimpleMath">\(-1\)</span>), and generate a group that admits a faithful <span class="SimpleMath">\(3\times 3\)</span> linear representation. As a final example, Bacher considers the "Jacobi character" <span class="SimpleMath">\(\chi(8ℤ\pm1)=1,\chi(8ℤ\pm3)=-1,\chi(2ℤ)=0\)</span>, and the associated matrix <span class="SimpleMath">\(J_{s,t}=\chi({s+t \choose s})\)</span>. He gives an easily-computed, but complicated formula for <span class="SimpleMath">\(\det(J(n))\)</span>. We can recover this formula, as before, by "guessing" an LR decomposition for <span class="SimpleMath">\(J\)</span>, which is self-similar and convergent:</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">chi := function(x)</span>
 if x mod 8 in [1,7] then return 1;
 elif x mod 8 in [3,5] then return -1;
 else return 0; fi;
     end;;
<span class="GAPprompt">gap></span> <span class="GAPinput">m := List([0..63],i->List([0..63],j->chi(Binomial(i+j,j))));;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">J := GuessVectorElement(m,2);</span>
<Linear element on alphabet Rationals^2 with 9-dimensional stateset>
<span class="GAPprompt">gap></span> <span class="GAPinput">LDUDecompositionFRElement(J);</span>
[ <Linear element on alphabet Rationals^2 with 20-dimensional stateset>,
  <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
  <Linear element on alphabet Rationals^2 with 20-dimensional stateset> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">time;</span>
26869
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last2[2]);</span>
 Rationals |        1        |        2        |
-----------+-----------------+-----------------+
  1 |   1   0   0   0 |   0   0   0   0 |
    |   0   0   1   0 |   0   0   0   0 |
    |   3   0   0   0 |   0   0   0   0 |
    |   0   0   3   0 |   0   0   0   0 |
-----------+-----------------+-----------------+
  2 |   0   0   0   0 |   0   1   0   0 |
    |   0   0   0   0 |   0   0   0   1 |
    |   0   0   0   0 |   0 1/3   0   0 |
    |   0   0   0   0 |   0   0   0 1/3 |
-----------+-----------------+-----------------+
Output:   1  -1   3 -1/3
Initial state:   1   0   0   0
</pre></div>

<p><a id="X7C4A51947E1609A8" name="X7C4A51947E1609A8"></a></p>

<h4>9.5 <span class="Heading">VH groups</span></h4>

<p><strong class="pkg">FR</strong> understands a special kind of finitely presented groups, called <em>VH groups</em>. These are groups with two distinguished sets of generators, <span class="SimpleMath">\(V\)</span> and <span class="SimpleMath">\(H\)</span>, and such that for every choice of <span class="SimpleMath">\(v\in V,h\in H\)</span> there are unique <span class="SimpleMath">\(v'\in V,h'\in H\)</span> such that <span class="SimpleMath">\(vh=h'v'\)</span> and conversely. In other words, these are finitely presented groups whose Cayley complex is a product of two trees.</p>

<p>These groups are of particular interest thanks to the work of Burger and Mozes, see <a href="chapBib_mj.html#biBMR1839488">[BM00a]</a> and <a href="chapBib_mj.html#biBMR1839489">[BM00b]</a>, who constructed the first examples of finitely presented simple groups in this manner.</p>

<p>VH groups are connected to groups generated by automata as follows. Given a VH group, consider the automaton with stateset <span class="SimpleMath">\(V\)</span>, acting on alphabet <span class="SimpleMath">\(H\)</span>; its output and transition are determined by <span class="SimpleMath">\(\Phi(v,h)=(h',v')\)</span> where <span class="SimpleMath">\(v',h'\)</span> are determined by the equation <span class="SimpleMath">\(vh=h'v'\)</span>.</p>

<p>Conversely, any bireversible automaton gives rise to a VH group by the inverse construction.</p>

<p><strong class="pkg">FR</strong> contains commands that automatize the verification that a VH group is non-residually finite, or virtually simple. Inspiration came from Diego Rattaggi's PhD thesis <a href="chapBib_mj.html#biBRattaggi">[Rat04]</a>.</p>

<p><a id="X7E0071D4838B239D" name="X7E0071D4838B239D"></a></p>

<h5>9.5-1 VHStructure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; VHStructure</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsVHGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: A VH-structure for the group <var class="Arg">g</var>.</p>

<p>A <em>VH-structure</em> on a group <var class="Arg">g</var> is a partition of the generators in two sets <span class="SimpleMath">\(V,H\)</span> such that every relator of <var class="Arg">g</var> is of the form <span class="SimpleMath">\(vhv'h'\)</span>, and such that for all <span class="SimpleMath">\(v\in V,h\in H\)</span> there exist unique <span class="SimpleMath">\(v'\in V,h'\in H\)</span> such that <span class="SimpleMath">\(vhv'h'=1\)</span>.</p>

<p>The VH structure is stored as a record with fields <code class="code">v,h</code> containing lists of generators, and integer matrices <code class="code">transitions,output</code> such that <code class="code">transitions[v][h']=v'</code> and <code class="code">output[v][h']=h</code>.</p>

<p>The filter recognizes groups with a VH structure.</p>

<p><a id="X7F852A357D7E2E76" name="X7F852A357D7E2E76"></a></p>

<h5>9.5-2 VerticalAction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; VerticalAction</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; HorizontalAction</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A homomorphism to an FR group.</p>

<p>A group with VH structure admits a <em>vertical action</em> of its subgroup <span class="SimpleMath">\(\langle V\rangle\)</span>; this is the group generated by the automaton <code class="code">MealyMachine(trans,out)</code>. The function returns the group homomorphism from the subgroup <span class="SimpleMath">\(\langle V\rangle\)</span> to that FR group.</p>

<p>The horizontal action is that of the dual automaton (see <code class="func">DualMachine</code> (<a href="chap5_mj.html#X809F069B798ED985"><span class="RefLink">5.2-3</span></a>)).</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">v := VerticalAction(RattaggiGroup.2_21);</span>
[ a1, a2, a3 ] -> [ <Mealy element on alphabet [ 1 .. 8 ] with 6 states>,
                    <Mealy element on alphabet [ 1 .. 8 ] with 6 states>,
                    <Mealy element on alphabet [ 1 .. 8 ] with 6 states> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RattaggiGroup.2_21.1^v;</span>
<Mealy element on alphabet [ 1 .. 8 ] with 6 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Range(v);</span>
<state-closed group over [ 1, 2, 3, 4, 5, 6, 7, 8 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">PermGroup(last,1);</span>
Group([ (3,4)(5,6), (1,7,8,2)(3,4,6,5), (1,7,5,3)(2,8,6,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayCompositionSeries(last);</span>
G (3 gens, size 1344)
 | A(1,7) = L(2,7) ~ B(1,7) = O(3,7) ~ C(1,7) = S(2,7) ~ 2A(1,7) = U(2,7) ~ A(2,2) = L(3,2)
S (3 gens, size 8)
 | Z(2)
S (2 gens, size 4)
 | Z(2)
S (1 gens, size 2)
 | Z(2)
1 (0 gens, size 1)
</pre></div>

<p><a id="X86B1C2F079FE8D82" name="X86B1C2F079FE8D82"></a></p>

<h5>9.5-3 VHGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; VHGroup</code>( <var class="Arg">l1</var>, <var class="Arg">l2</var>, <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A new VH group.</p>

<p>This function constructs the VH group specified by the squares <var class="Arg">l1, l2, ...</var>. Each <var class="Arg">li</var> is a list of length 4, of the form <code class="code">[v,h,v',h']</code>. Here the entries are indices of vertical, respectively horizontal generators, if positive; and their inverses if negative.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput"># the Baby-Aleshin group</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := VHGroup([[1,1,-2,-1],[1,2,-3,-2],[2,1,-3,-1],</span>
                   [2,2,-2,-2],[3,1,-1,-2],[3,2,-1,-1]]);
<VH group on the generators [ a1, a2, a3 | b1, b2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(g);</span>
generators = [ a1, a2, a3, b1, b2 ]                                          ## relators = [
 a1*b1*a2^-1*b1^-1,
 a1*b2*a3^-1*b2^-1,
 a2*b1*a3^-1*b1^-1,
 a2*b2*a2^-1*b2^-1,
 a3*b1*a1^-1*b2^-1,
 a3*b2*a1^-1*b1^-1 ]
</pre></div>

<p><a id="X7D1FCB877D1B96EA" name="X7D1FCB877D1B96EA"></a></p>

<h5>9.5-4 IsIrreducibleVHGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsIrreducibleVHGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: Whether <var class="Arg">g</var> is an irreducible lattice.</p>

<p>A VH group is <em>irreducible</em> if its projections on both trees is dense.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(RattaggiGroup.2_21);</span>
generators = [ a1, a2, a3, b1, b2, b3, b4 ]
relators = [
 a1*b1*a1^-1*b1^-1,
 a1*b2*a1^-1*b2^-1,
 a1*b3*a1^-1*b4^-1,
 a1*b4*a2^-1*b3^-1,
 a1*b4^-1*a2^-1*b3,
 a2*b1*a2^-1*b2^-1,
 a2*b2*a3^-1*b1,
 a2*b3*a2^-1*b4,
 a2*b2^-1*a3*b1^-1,
 a3*b1*a3*b3^-1,
 a3*b2*a3*b4^-1,
 a3*b3*a3*b4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIrreducibleVHGroup(RattaggiGroup.2_21);</span>
true
</pre></div>

<p><a id="X84DB7FA4846075A7" name="X84DB7FA4846075A7"></a></p>

<h5>9.5-5 MaximalSimpleSubgroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MaximalSimpleSubgroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A maximal simple subgroup of <var class="Arg">g</var>, if possible.</p>

<p>A VH group is never simple, but in favourable cases it admits a finite-index simple subgroup, see <a href="chapBib_mj.html#biBMR1446574">[BM97]</a>. This function attempts to construct such a subgroup. It returns <code class="keyw">fail</code> if no such subgroup can be found.</p>

<p>The current implementation is not smart enough to work with the Rattaggi examples (see <code class="func">IsVirtuallySimpleGroup</code> (<a href="chap7_mj.html#X873C0A7C8422C0C9"><span class="RefLink">7.3-4</span></a>)).</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap8_mj.html">[Previous Chapter]</a>    <a href="chap10_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

Messung V0.5 in Prozent
C=100 H=100 G=100

[Verzeichnis aufwärts0.102unsichere VerbindungÜbersetzung europäischer Sprachen durch Browser2026-06-18]