<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (FR) - Chapter 10: 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" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap9.html">Previous Chapter</a> <a href="chap11.html">Next Chapter</a> </div>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>
<div class="ChapSects"><a href="chap10.html#X7A489A5D79DA9E5C">10 <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7AF5DEF08531AFA5">10.1 <span class="Heading">Examples of groups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7D774B847D81E6DE">10.1-1 FullBinaryGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X813F53C57F41F5F5">10.1-2 BinaryKneadingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7B8D49D079D336E8">10.1-3 BasilicaGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X85F4FDF787173863">10.1-4 AddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7A4BB24A805CDF63">10.1-5 BinaryAddingGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X78AFA63B86C94227">10.1-6 MixerGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X84C97E0687F119C0">10.1-7 SunicGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X79E3F3BE80F34590">10.1-8 GrigorchukMachines</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X85BAE48780E665A4">10.1-9 GrigorchukMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X800640597E9C707D">10.1-10 GrigorchukOverGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7C58F33D825A473A">10.1-11 GrigorchukEvilTwin</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7F93EC437B5AE276">10.1-12 BrunnerSidkiVieiraGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7F8A028B799946D3">10.1-13 AleshinGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7C286D3A84790ECE">10.1-14 AleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7E024B4D7BA411B1">10.1-15 BabyAleshinGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X8108E3A8872A6FFE">10.1-16 SidkiFreeGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X82D3CB6A7C189C78">10.1-17 GuptaSidkiGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X83E59288860EF661">10.1-18 GuptaSidkiGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X8521B4FF7BA189B2">10.1-19 NeumannGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X878D1C7080EA9797">10.1-20 FabrykowskiGuptaGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X864A87957D1E1AF6">10.1-21 OtherSpinalGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7A0319827CB51ED0">10.1-22 GammaPQMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7A0BE9F57B401C5C">10.1-23 HanoiGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7C7A0EEF7EFF8B99">10.1-24 DahmaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7C958AB78484E256">10.1-25 MamaghaniGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X86D952E8784E4D97">10.1-26 WeierstrassGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X86B124758135DFBD">10.1-27 FRAffineGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7CFBE31A78F2681B">10.1-28 CayleyGroup</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X81B82FA1811AAF8D">10.2 <span class="Heading">Examples of semigroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X87541DA582705033">10.2-1 I2Machine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7B32ED3D8715FA4B">10.2-2 I4Machine</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X803B02408573A30E">10.3 <span class="Heading">Examples of algebras</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X80E15ABC879F8EE2">10.3-1 PSZAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7D015CA5829FAA2A">10.3-2 GrigorchukThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7B66ED537D0A43AF">10.3-3 GuptaSidkiThinnedAlgebra</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7B0B5B09878C7CEA">10.3-4 SidkiFreeAlgebra</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7989134C83AF38AE">10.4 <span class="Heading">Bacher's determinant identities</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap10.html#X7C4A51947E1609A8">10.5 <span class="Heading">VH groups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7E0071D4838B239D">10.5-1 VHStructure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7F852A357D7E2E76">10.5-2 VerticalAction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X86B1C2F079FE8D82">10.5-3 VHGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X7D1FCB877D1B96EA">10.5-4 IsIrreducibleVHGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap10.html#X84DB7FA4846075A7">10.5-5 MaximalSimpleSubgroup</a></span>
</div>
</div>
<h3>10 <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>10.1 <span class="Heading">Examples of groups</span></h4>
<p><a id="X7D774B847D81E6DE" name="X7D774B847D81E6DE"></a></p>
<h5>10.1-1 FullBinaryGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FullBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FiniteDepthBinaryGroup</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FinitaryBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BoundedBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PolynomialGrowthBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FiniteStateBinaryGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These are the finitary, bounded, polynomial-growth, finite-state, or unrestricted groups acting on the binary tree. They are respectively shortcuts for <code class="code">FullSCGroup([1..2])</code>, <code class="code">FullSCGroup([1..2],l)</code>, <code class="code">FullSCGroup([1..2],IsFinitaryFRSemigroup)</code>, <code class="code">FullSCGroup([1..2],IsBoundedFRSemigroup)</code>, <code class="code">FullSCGroup([1..2],IsPolynomialGrowthFRSemigroup)</code>, and <code class="code">FullSCGroup([1..2],IsFiniteStateFRSemigroup)</code>.</p>
<p>They may be used to draw random elements, or to test membership.</p>
<p><a id="X813F53C57F41F5F5" name="X813F53C57F41F5F5"></a></p>
<h5>10.1-2 BinaryKneadingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BinaryKneadingGroup</code>( <var class="Arg">angle/ks</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BinaryKneadingMachine</code>( <var class="Arg">angle/ks</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>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="chap10.html#X7B8D49D079D336E8"><b>10.1-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> BinaryKneadingGroup()=AddingGroup(2);
true
gap> BinaryKneadingGroup(1/3)=BasilicaGroup;
true
gap> g := BinaryKneadingGroup([0,1],[0]);
BinaryKneadingGroup("01","0")
gap> ForAll(Correspondence(g)[1],IsFinitaryFRElement);
true
gap> ForAll(Correspondence(g)[2],IsFinitaryFRElement);
false
gap> ForAll(Correspondence(g)[2],IsBoundedFRElement);
true
</pre></td></tr></table>
<p><a id="X7B8D49D079D336E8" name="X7B8D49D079D336E8"></a></p>
<h5>10.1-3 BasilicaGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BasilicaGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The <em>Basilica group</em>. This is a shortcut for <code class="code">BinaryKneadingGroup("1")</code>. It is the first-discovered amenable group that is not subexponentially amenable, see <a href="chapBib.html#biBMR2176547">[BV05]</a> and <a href="chapBib.html#biBMR1902367">[GŻ02a]</a>.</p>
<table class="example">
<tr><td><pre>
gap> IsBoundedFRSemigroup(BasilicaGroup);
true
gap> pi := EpimorphismFromFreeGroup(BasilicaGroup); F := Source(pi);;
[ x1, x2 ] -> [ a, b ]
gap> sigma := GroupHomomorphismByImages(F,F,[F.1,F.2],[F.2,F.1^2]);
[ x1, x2 ] -> [ x2, x1^2 ]
gap> ForAll([0..10],i->IsOne(Comm(F.2,F.2^F.1)^(sigma^i*pi)));
true
</pre></td></tr></table>
<p><a id="X85F4FDF787173863" name="X85F4FDF787173863"></a></p>
<h5>10.1-4 AddingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AddingGroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AddingMachine</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AddingElement</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The second function constructs the adding machine on the alphabet <code class="code">[1..n]</code>. This machine has a trivial state 1, and a non-trivial state 2. It implements the operation "add 1 with carry" on sequences.</p>
<p>The third function constructs the Mealy element on the adding machine, with initial state 2.</p>
<p>The first function constructs the state-closed group generated by the adding machine on <code class="code">[1..n]</code>. This group is isomorphic to the <code class="code">Integers</code>.</p>
<table class="example">
<tr><td><pre>
gap> Display(AddingElement(3));
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 b,1
---+-----+-----+-----+
Initial state: b
gap> Activity(FRElement(AddingMachine(3),2),2);
(1,4,7,2,5,8,3,6,9)
gap> G := AddingGroup(3);
<self-similar group over [ 1 .. 3 ] with 1 generator>
gap> Size(G);
infinity
gap> IsRecurrent(G);
true
gap> IsLevelTransitive(G);
true
</pre></td></tr></table>
<p><a id="X7A4BB24A805CDF63" name="X7A4BB24A805CDF63"></a></p>
<h5>10.1-5 BinaryAddingGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BinaryAddingGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BinaryAddingMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BinaryAddingElement</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These are respectively the same as <code class="code">AddingGroup(2)</code>, <code class="code">AddingMachine(2)</code> and <code class="code">AddingElement(2)</code>.</p>
<p><a id="X78AFA63B86C94227" name="X78AFA63B86C94227"></a></p>
<h5>10.1-6 MixerGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MixerGroup</code>( <var class="Arg">A, B, f[, g]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MixerMachine</code>( <var class="Arg">A, B, f[, g]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>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 d-1 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 b^g; the output of <code class="code">b</code> is trivial.</p>
<p>This construction is described in more detail in <a href="chapBib.html#biBMR1856923">[BŠ01]</a> and <a href="chapBib.html#biBMR2035113">[BGŠ03]</a>.</p>
<p><code class="code">Correspondence(m)</code> is a list, with in first position the subset of the states that correspond to <var class="Arg">A</var>, in second position the states that correspond to the first copy of <var class="Arg">B</var>, etc.</p>
<p>The first function constructs the group generated by the mixer machine. For examples see <code class="func">GrigorchukGroups</code> (<a href="chap10.html#X79E3F3BE80F34590"><b>10.1-8</b></a>), <code class="func">NeumannGroup</code> (<a href="chap10.html#X8521B4FF7BA189B2"><b>10.1-19</b></a>), <code class="func">GuptaSidkiGroups</code> (<a href="chap10.html#X82D3CB6A7C189C78"><b>10.1-17</b></a>), and <code class="func">OtherSpinalGroup</code> (<a href="chap10.html#X864A87957D1E1AF6"><b>10.1-21</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> grigorchukgroup := MixerGroup(Group((1,2)),Group((1,2)),
[[IdentityMapping(Group((1,2)))],[IdentityMapping(Group((1,2)))],[]]));
<self-similar group over [ 1 .. 2 ] with 4 generators>
gap> IdGroup(Group(grigorchukgroup.1,grigorchukgroup.2));
[ 32, 18 ]
</pre></td></tr></table>
<p><a id="X84C97E0687F119C0" name="X84C97E0687F119C0"></a></p>
<h5>10.1-7 SunicGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SunicGroup</code>( <var class="Arg">phi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Sunicmachine</code>( <var class="Arg">phi</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>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="chap10.html#X78AFA63B86C94227"><b>10.1-6</b></a>), in which the group A is a finite field GF(q), the group B is an extension A[x]/(phi), where phi is a monic polynomial; there is a map f:B-> A, given say by evaluation; and there is an endomorphism of g:B-> B given by multiplication by phi.</p>
<p>These groups were described in <a href="chapBib.html#biBMR2318546">[Šun07]</a>. In particular, the case q=2 and phi=x^2+x+1 gives the original <code class="func">GrigorchukGroup</code> (<a href="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> x := Indeterminate(GF(2));;
gap> g := SunicGroup(x^2+x+1);
SunicGroup(x^2+x+Z(2)^0)
gap> g = GrigorchukGroup;
true
</pre></td></tr></table>
<p><a id="X79E3F3BE80F34590" name="X79E3F3BE80F34590"></a></p>
<h5>10.1-8 GrigorchukMachines</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukMachines</code>( <var class="Arg">omega</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukGroups</code>( <var class="Arg">omega</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>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="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></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="chap10.html#X78AFA63B86C94227"><b>10.1-6</b></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="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>).</p>
<p>These groups are all 4-generated and infinite. They are described in <a href="chapBib.html#biBMR764305">[Gri84]</a>. <code class="code">GrigorchukGroups([1])</code> is infinite dihedral. If <var class="Arg">omega</var> contains at least 2 different digits, <code class="code">GrigorchukGroups([1])</code> has intermediate word growth. If <var class="Arg">omega</var> contains all 3 digits, <code class="code">GrigorchukGroups([1])</code> is torsion.</p>
<p>The growth of <code class="code">GrigorchukGroups([1,2])</code> has been studied in <a href="chapBib.html#biBMR2144977">[Ers04]</a>.</p>
<table class="example">
<tr><td><pre>
gap> G := GrigorchukGroups([1]);
<self-similar group over [ 1 .. 2 ] with 4 generators>
gap> Index(G,DerivedSubgroup(G)); IsAbelian(DerivedSubgroup(G));
4
true
gap> H := GrigorchukGroups([1,2]);
<self-similar group over [ 1 .. 2 ] with 4 generators>
gap> Order(H.1*H.2);
8
gap> Order(H.1*H.4);
infinity
gap> IsSubgroup(H,G);
true
</pre></td></tr></table>
<p><a id="X85BAE48780E665A4" name="X85BAE48780E665A4"></a></p>
<h5>10.1-9 GrigorchukMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is Grigorchuk's first group, introduced in <a href="chapBib.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> will will construct an approximating presentation for the Grigorchuk group, as proven in <a href="chapBib.html#biBMR819415">[Lys85]</a>. Adding the relations <code class="code">Image(sigma^(n-2),(a*d)^2)</code>, <code class="code">Image(sigma^(n-1),(a*b)^2)</code> and <code class="code">Image(sigma^(n-2),(a*c)^4)</code> yields the quotient acting on 2^n points, as a finitely presented group.</p>
<p><a id="X800640597E9C707D" name="X800640597E9C707D"></a></p>
<h5>10.1-10 GrigorchukOverGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukOverGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a group strictly containing the Grigorchuk group (see <code class="func">GrigorchukGroup</code> (<a href="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>)). It also has intermediate growth (see <a href="chapBib.html#biBMR1899368">[BG02]</a>, but it contains elements of infinite order. It could have been defined as <code class="code">FRGroup("a=(1,2)","b=<a,c>","c=<,d>","d=<,b>")</code>, but is rather defined using Mealy elements.</p>
<table class="example">
<tr><td><pre>
gap> IsSubgroup(GrigorchukOverGroup,GrigorchukGroup);
true
gap> Order(Product(GeneratorsOfGroup(GrigorchukOverGroup)));
infinity
gap> GrigorchukGroup.2=GrigorchukSuperGroup.2*GrigorchukSuperGroup.3;
true
</pre></td></tr></table>
<p>The command <code class="code">EpimorphismFromFpGroup(GrigorchukOverGroup,n)</code> will will construct an approximating presentation for the Grigorchuk overgroup, as proven in <a href="chapBib.html#biBMR2009317">[Bar03b]</a>.</p>
<p><a id="X7C58F33D825A473A" name="X7C58F33D825A473A"></a></p>
<h5>10.1-11 GrigorchukEvilTwin</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrigorchukEvilTwin</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="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></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>
<table class="example">
<tr><td><pre>
gap> AbelianInvariants(GrigorchukEvilTwin);
[ 2, 2, 2, 2 ]
gap> AbelianInvariants(GrigorchukGroup);
[ 2, 2, 2 ]
gap> PermGroup(GrigorchukGroup,8)=PermGroup(GrigorchukEvilTwin,8);
true
</pre></td></tr></table>
<p><a id="X7F93EC437B5AE276" name="X7F93EC437B5AE276"></a></p>
<h5>10.1-12 BrunnerSidkiVieiraGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BrunnerSidkiVieiraGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BrunnerSidkiVieiraMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This machine is the sum of two adding machines, one in standard form and one conjugated by the element <code class="code">d</code> described below. The group that it generates is described in <a href="chapBib.html#biBMR1656573">[BSV99]</a>. It could have been defined as <code class="code">FRGroup("tau=<,tau>(1,2)","mu=<,mu^-1>(1,2)")</code>, but is rather defined using Mealy elements.</p>
<table class="example">
<tr><td><pre>
gap> V := FRGroup("d=<e,e>(1,2)","e=<d,d>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> Elements(V);
[ <2|identity ...>, <2|e>, <2|d>, <2|e*d> ]
gap> AssignGeneratorVariables(BrunnerSidkiVieiraGroup);
#I Assigned the global variables [ "tau", "mu", "" ]
gap> List(V,x->tau^x)=[tau,mu,mu^-1,tau^-1];
true
</pre></td></tr></table>
<p><a id="X7F8A028B799946D3" name="X7F8A028B799946D3"></a></p>
<h5>10.1-13 AleshinGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AleshinGroups</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AleshinMachines</code>( <var class="Arg">l</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The Aleshin machine with <code class="code">Length(l)</code> states.</p>
<p>This function constructs the bireversible machines introduced by Aleshin in <a href="chapBib.html#biBMR713968">[Ale83]</a>. The argument <var class="Arg">l</var> is a list of permutations, either <code class="code">()</code> or <code class="code">(1,2)</code>. The groups that they generate are contructed as <code class="func">AleshinGroups</code>.</p>
<p>If <code class="code">l=[(1,2),(1,2),()]</code>, this is <code class="func">AleshinGroup</code> (<a href="chap10.html#X7C286D3A84790ECE"><b>10.1-14</b></a>). More generally, if <code class="code">l=[(1,2,(1,2),(),...,()]</code> has odd length, this is a free group of rank <code class="code">Length(l)</code>, see <a href="chapBib.html#biBvorobets">[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.html#biBsteinberg-vorobets">[SVV06]</a>.</p>
<p>If <code class="code">l=[(),(),(1,2)]</code>, this is <code class="func">BabyAleshinGroup</code> (<a href="chap10.html#X7E024B4D7BA411B1"><b>10.1-15</b></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>10.1-14 AleshinGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AleshinGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AleshinMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is the first example of non-abelian free group. It is the group generated by <code class="code">AleshinMachine([(1,2),(1,2),()])</code>. It could have been defined as <code class="code">FRGroup("a=<b,c>(1,2)","b=<c,b>(1,2)","c=<a,a>")</code>, but is rather defined using Mealy elements.</p>
<p><a id="X7E024B4D7BA411B1" name="X7E024B4D7BA411B1"></a></p>
<h5>10.1-15 BabyAleshinGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BabyAleshinGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BabyAleshinMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>There are only two connected, transitive bireversible machines on a 2-letter alphabet, with 3 generators: <code class="code">AleshinMachine(3)</code> and the baby Aleshin machine.</p>
<p>The group generated by this machine is abstractly the free product of three C_2's, see <a href="chapBib.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>
<table class="example">
<tr><td><pre>
gap> K := Kernel(GroupHomomorphismByImagesNC(BabyAleshinGroup,Group((1,2)),
GeneratorsOfGroup(BabyAleshinGroup),[(1,2),(1,2),(1,2)]));
<self-similar group over [ 1 .. 2 ] with 4 generators>
gap> Index(BabyAleshinGroup,K);
2
gap> IsSubgroup(AleshinGroup,K);
true
</pre></td></tr></table>
<p><a id="X8108E3A8872A6FFE" name="X8108E3A8872A6FFE"></a></p>
<h5>10.1-16 SidkiFreeGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SidkiFreeGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a group suggested by Sidki as an example of a non-abelian state-closed free group. Nothing is known about that group: whether it is free as conjectured; whether generator <var class="Arg">a</var> is state-closed, etc. It is defined as <code class="code">FRGroup("a=<a^2,a^t>","t=<,t>(1,2)")]]></code>.</p>
<p><a id="X82D3CB6A7C189C78" name="X82D3CB6A7C189C78"></a></p>
<h5>10.1-17 GuptaSidkiGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuptaSidkiGroups</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralizedGuptaSidkiGroups</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuptaSidkiMachines</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The Gupta-Sidki machine on an <var class="Arg">n</var>-letter alphabet.</p>
<p>This function constructs the machines introduced by Gupta and Sidki in <a href="chapBib.html#biBMR696534">[GS83]</a>. They generate finitely generated infinite torsion groups: the exponent of every element divides some power of <var class="Arg">n</var>. The special case n=3 is defined as <code class="func">GuptaSidkiGroup</code> (<a href="chap10.html#X83E59288860EF661"><b>10.1-18</b></a>) and <code class="func">GuptaSidkiMachine</code> (<a href="chap10.html#X83E59288860EF661"><b>10.1-18</b></a>).</p>
<p>For n>3, 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 p), 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>10.1-18 GuptaSidkiGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuptaSidkiGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuptaSidkiMachine</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an infinite, 2-generated, torsion 3-group. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,a^-1,t>")</code>, but is rather defined using Mealy elements.</p>
<p><a id="X8521B4FF7BA189B2" name="X8521B4FF7BA189B2"></a></p>
<h5>10.1-19 NeumannGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NeumannGroup</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NeumannMachine</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The Neumann machine/group on the permutation group <var class="Arg">P</var>.</p>
<p>The first 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 second function constructs the Neumann group on the permutation group <var class="Arg">P</var>. These groups were first considered in <a href="chapBib.html#biBMR840129">[Neu86]</a>. In particular, <code class="code">NeumannGroup(PSL(3,2))</code> is a group of non-uniform exponential growth (see <a href="chapBib.html#biBMR1981466">[Bar03a]</a>), and <code class="code">NeumannGroup(Group((1,2,3)))</code> is <code class="func">FabrykowskiGuptaGroup</code> (<a href="chap10.html#X878D1C7080EA9797"><b>10.1-20</b></a>).</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>10.1-20 FabrykowskiGuptaGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FabrykowskiGuptaGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FabrykowskiGuptaGroups</code>( <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is an infinite, 2-generated group of intermediate word growth. It was studied in <a href="chapBib.html#biBMR942349">[FG85]</a> and <a href="chapBib.html#biBMR1153150">[FG91]</a>. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,,t>")</code>, but is rather defined using Mealy elements. It has a torsion-free subgroup of index 3 and is branched.</p>
<p>The natural generalization, replacing 3 by p, is constructed by the second form. It is a specific case of Neumann group (see <code class="func">NeumannGroup</code> (<a href="chap10.html#X8521B4FF7BA189B2"><b>10.1-19</b></a>)), for which an ascending L-presentation is known.</p>
<p><a id="X864A87957D1E1AF6" name="X864A87957D1E1AF6"></a></p>
<h5>10.1-21 OtherSpinalGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> OtherSpinalGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an infinite, 2-generated group, which was studied in <a href="chapBib.html#biBMR1899368">[BG02]</a>. It has a torsion-free subgroup of index 3, and is virtually branched but not branched. It could have been defined as <code class="code">FRGroup("a=(1,2,3)","t=<a,a,t>")</code>, but is rather defined using Mealy elements.</p>
<p><a id="X7A0319827CB51ED0" name="X7A0319827CB51ED0"></a></p>
<h5>10.1-22 GammaPQMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GammaPQMachine</code>( <var class="Arg">p, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GammaPQGroup</code>( <var class="Arg">p, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The quaternion-based machine / SC group.</p>
<p>The first function constructs a bireversible (see <code class="func">IsBireversible</code> (<a href="chap5.html#X80D2545D7D0990A2"><b>5.2-7</b></a>)) Mealy machine based on quaternions, see <a href="chapBib.html#biBMR1839488">[BM00a]</a> and <a href="chapBib.html#biBMR1839489">[BM00b]</a>. This machine has p+1 states indexed by integer quaternions of norm <var class="Arg">p</var>, and an alphabet of size q+1 indexed by quaternions of norm <var class="Arg">q</var>. These quaternions are congruent to 1mod 2 or imod 2 depending on whether the odd prime p or q is 1 or 3mod 4.</p>
<p>The structure of the machine is such that there is a transition from (q,a) to (q',a') precisely when qa'=pm q'a. In particular, the relations of the <code class="func">StructuralGroup</code> (<a href="chap3.html#X8289C2F77D67EDC3"><b>3.5-1</b></a>) hold up to a sign, when the alphabet/state letters are substituted for the appropriate quaternions.</p>
<p>The quaternions themselves can be recovered through <code class="func">Correspondence</code> (<a href="chap3.html#X7C107A42815F91DA"><b>3.5-11</b></a>), which is a list with in first position the quaternions of norm p and in second those of norm q.</p>
<p>The second function constructs the quaternion lattice that is the <code class="func">StructuralGroup</code> (<a href="chap3.html#X8289C2F77D67EDC3"><b>3.5-1</b></a>) of that machine. It has actions on two trees, given by <code class="func">VerticalAction</code> (<a href="chap10.html#X7F852A357D7E2E76"><b>10.5-2</b></a>) and <code class="func">HorizontalAction</code> (<a href="chap10.html#X7F852A357D7E2E76"><b>10.5-2</b></a>); the ranges of these actions are groups generated by automata, which are infinitely-transitive (see <code class="func">IsInfinitelyTransitive</code> (<a href="chap7.html#X7D95219481AEDD20"><b>7.2-12</b></a>)) and free by <a href="chapBib.html#biBMR2155175">[GM05, Proposition 3.3]</a>; see also <a href="chapBib.html#biBMR713968">[Ale83]</a>.</p>
<p><a id="X7A0BE9F57B401C5C" name="X7A0BE9F57B401C5C"></a></p>
<h5>10.1-23 HanoiGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HanoiGroup</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The Hanoi group on an <var class="Arg">n</var> pegs.</p>
<p>This function constructs the Hanoi group on <var class="Arg">n</var> pegs. Generators of the group correspond to moving a peg, and tree vertices correspond to peg configurations. This group is studied in <a href="chapBib.html#biBMR2217913">[GŠ06]</a>.</p>
<p><a id="X7C7A0EEF7EFF8B99" name="X7C7A0EEF7EFF8B99"></a></p>
<h5>10.1-24 DahmaniGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DahmaniGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is an example of a non-contracting weakly branched group. It was first studied in <a href="chapBib.html#biBMR2140091">[Dah05]</a>. It could have been defined as <code class="code">FRGroup("a=<c,a>(1,2)","b=<b,a>(1,2)","c=<b,c>")</code>, but is rather defined using Mealy elements.</p>
<p>It has relators abc, [a^2c,[a,c]], [cab,a^-1c^-1ab] and [ac^2,c^-1b^-1c^2] 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>10.1-25 MamaghaniGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MamaghaniGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This group was studied in <a href="chapBib.html#biBMR2139928">[Mam03]</a>. It is fractal, but not contracting. It could have been defined as <code class="code">FRGroup("a=<,b>(1,2)","b=<a,c>","c=<a,a^-1>(1,2)")]]></code>, but is rather defined using Mealy elements. It partially admits branching on its subgroup <code class="code">Subgroup(G,[a^2,(a^2)^b,(a^2)^c])</code>, and, setting <code class="code">x=Comm(a^2,b)</code>, on <code class="code">Subgroup(G,[x,x^a,x^b,x^(b*a),x^(b/a)])</code>. One has <code class="code">FRElement(1,x)=(x^-1)^b/x</code>.</p>
<p><a id="X86D952E8784E4D97" name="X86D952E8784E4D97"></a></p>
<h5>10.1-26 WeierstrassGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeierstrassGroup</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is the iterated monodromy group associated with the Weierstrass wp-function.</p>
<p>Some relators in the group: (atbt)^4, ((atbt)(bt)^4n)^4, ((atbt)^2(bt)^4n)^2.</p>
<p>Set x=[a,t], y=[b,t], z=[c,t], and w=[x,y]. Then G'=< x,y,z> of index 8, and gamma_3=<[{x,y,z},{a,b,c}]> of index 32, and gamma_4=G''=< w>^G, of index 256, and G''>(G'')^4 since [[t^a,t],[t^b,t]]=(w,1,1,1).</p>
<p>The Schreier graph is obtained in the complex plane as the image of a 2^nx 2^n lattice in the torus, via Weierstrass's wp-function.</p>
<p>The element at has infinite order.</p>
<p>[c,t,b][b,t,c][a,t,c][c,t,a] has order 2, and belongs to G''; so there exist elements of arbitrary large finite order in the group.</p>
<p><a id="X86B124758135DFBD" name="X86B124758135DFBD"></a></p>
<h5>10.1-27 FRAffineGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRAffineGroup</code>( <var class="Arg">d, R, u[, transversal]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>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 R_u, 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 GL_d+1(R_u) to <code class="code">G</code>, is relevant.</p>
<p>The affine group can also be described as a subgroup of GL_d+1(R_u), consisting of those matrices M with M_i,d+1=0 and M_d+1,d+1=1. The finite-index subgroup is defined by the conditions u|M_i,j for all j<i.</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 R/RuR; an explicit transversal of RuR be specified as last argument.</p>
<p>The following examples construct the "Baumslag-Solitar group" Z[frac12]rtimes_2 Z first introduced in <a href="chapBib.html#biBMR0142635">[BS62]</a>, the "lamplighter group" ( Z/2)wr Z, and a 2-dimensional affine group. Note that the lamplighter group may also be defined via <code class="func">CayleyGroup</code> (<a href="chap10.html#X7CFBE31A78F2681B"><b>10.1-28</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> A := FRAffineGroup(1,Integers,3);
<self-similar group over [ 1 .. 3 ]>
gap> f := Correspondence(A);
MappingByFunction( ( Integers^
[ 2, 2 ] ), <self-similar group over [ 1 .. 3 ]>, function( mat ) ... end )
gap> BaumslagSolitar := Group([[2,0],[0,1]]^f,[[1,0],[1,1]]^f);
<self-similar group over [ 1 .. 3 ] with 2 generators>
gap> BaumslagSolitar.2^BaumslagSolitar.1=BaumslagSolitar.2^2;
true
gap> R := PolynomialRing(GF(2));;
gap> A := FRAffineGroup(1,R,R.1);;
gap> f := Correspondence(A);;
gap> Lamplighter := Group(([[1+R.1,0],[0,1]]*One(R))^f,([[1,0],[1,1]]*One(R))^f);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> Lamplighter = CayleyGroup(Group((1,2)));
true
gap> StructureDescription(Group(Lamplighter.2,Lamplighter.2^Lamplighter.1));
"C2 x C2"
gap> ForAll([1..10],i->IsOne(Comm(Lamplighter.2,Lamplighter.2^(Lamplighter.1^i))));
true
gap> A := FRAffineGroup(2,Integers,2);;
gap> f := Correspondence(A);;
gap> a := [[1,4,0],[2,3,0],[1,0,1]];
[ [ 1, 4, 0 ], [ 2, 3, 0 ], [ 1, 0, 1 ] ]
gap> b := [[1,2,0],[4,3,0],[0,1,1]];
[ [ 1, 2, 0 ], [ 4, 3, 0 ], [ 0, 1, 1 ] ]
gap> Display(b^f);
| 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
gap> a^f*b^f=(a*b)^f;
true
</pre></td></tr></table>
<p><a id="X7CFBE31A78F2681B" name="X7CFBE31A78F2681B"></a></p>
<h5>10.1-28 CayleyGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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">> 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">> LamplighterGroup</code>( <var class="Arg">G</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>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 CG, 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.html#biBMR2197829">[SS05]</a>.</p>
<p>If <var class="Arg">G</var> is an abelian group, CG is the wreath product Gwr Z; 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="chap10.html#X86B124758135DFBD"><b>10.1-27</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> L := CayleyGroup(Group((1,2)));
CayleyGroup(Group( [ (1,2) ] ))
gap> L=LamplighterGroup(IsFRGroup,CyclicGroup(2));
true
gap> (1,2)^Correspondence(L)[1];
<Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>
gap> IsFinitaryFRElement(last); Display(last2);
true
| 1 2
---+-----+-----+
a | b,2 b,1
b | b,1 b,2
---+-----+-----+
Initial state: a
</pre></td></tr></table>
<p><a id="X81B82FA1811AAF8D" name="X81B82FA1811AAF8D"></a></p>
<h4>10.2 <span class="Heading">Examples of semigroups</span></h4>
<p><a id="X87541DA582705033" name="X87541DA582705033"></a></p>
<h5>10.2-1 I2Machine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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">> I2Monoid</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The Mealy machine I_2, and the monoid that it generates. This is the smallest Mealy machine generating a monoid of intermediate word growth; see <a href="chapBib.html#biBMR2194959">[BRS06]</a>.</p>
<p>For sample calculations in this monoid see <code class="func">SCSemigroup</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>).</p>
<p><a id="X7B32ED3D8715FA4B" name="X7B32ED3D8715FA4B"></a></p>
<h5>10.2-2 I4Machine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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">> I4Monoid</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>The Mealy machine generating I_4, and the monoid that it generates. This is a very small Mealy machine generating a monoid of intermediate word growth; see <a href="chapBib.html#biBbartholdi-reznykov">[BR05]</a>.</p>
<p>For sample calculations in this monoid see <code class="func">SCMonoid</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>).</p>
<p><a id="X803B02408573A30E" name="X803B02408573A30E"></a></p>
<h4>10.3 <span class="Heading">Examples of algebras</span></h4>
<p><a id="X80E15ABC879F8EE2" name="X80E15ABC879F8EE2"></a></p>
<h5>10.3-1 PSZAlgebra</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PSZAlgebra</code>( <var class="Arg">k</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 two derivations <code class="code">u,v</code>. This algebra has polynomial growth, and is not nilpotent. Petrogradsky showed in <a href="chapBib.html#biBMR2293788">[Pet06]</a> that the Lie subalgebra of <code class="code">PSZAlgebra(GF(2))</code> generated by v,[u,v] is nil; this result was generalized by Shestakov and Zelmanov in <a href="chapBib.html#biBMR2390328">[SZ08]</a> to arbitrary <var class="Arg">k</var>.</p>
<table class="example">
<tr><td><pre>
gap> a := PSZAlgebra(2);
PSZAlgebra(GF(2))
gap> Nillity(a.1); Nillity(a.2);
2
4
gap> IsNilpotentElement(LieBracket(a.1,a.2));
true
gap> DecompositionOfFRElement(LieBracket(a.1,a.2))=DiagonalMat([a.2,a.2]);
true
</pre></td></tr></table>
<p><a id="X7D015CA5829FAA2A" name="X7D015CA5829FAA2A"></a></p>
<h5>10.3-2 GrigorchukThinnedAlgebra</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>). !!!</p>
<table class="example">
<tr><td><pre>
gap> !!!
</pre></td></tr></table>
<p><a id="X7B66ED537D0A43AF" name="X7B66ED537D0A43AF"></a></p>
<h5>10.3-3 GuptaSidkiThinnedAlgebra</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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="chap10.html#X83E59288860EF661"><b>10.1-18</b></a>). !!!</p>
<table class="example">
<tr><td><pre>
gap> !!!
</pre></td></tr></table>
<p><a id="X7B0B5B09878C7CEA" name="X7B0B5B09878C7CEA"></a></p>
<h5>10.3-4 SidkiFreeAlgebra</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SidkiFreeAlgebra</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>!!!</p>
<table class="example">
<tr><td><pre>
gap> !!!
</pre></td></tr></table>
<p><a id="X7989134C83AF38AE" name="X7989134C83AF38AE"></a></p>
<h4>10.4 <span class="Heading">Bacher's determinant identities</span></h4>
<p>In his paper <a href="chapBib.html#biBbacher">[Bac07]</a>, Roland Bacher exhibits striking formulas for determinants of matrices obtained from binomial coefficients.</p>
<p>The general construction is as follows: let P be an infinite matrix, and let P(n) be its upper nx n corner. To evaluate det P(n), decompose P=LDR where L,D,R are respectively lower triangular, diagonal, and upper triangular, with 1's on the diagonals of L and R. Then that determinant is the product of the first n entries of D.</p>
<p>Bacher considers some natural examples of matrices arising from binomial coefficients, and notes that the matrix P is the limit of a convergent vector element (see <code class="func">IsConvergent</code> (<a href="chap6.html#X7EF5B7417AE6B3F8"><b>6.1-8</b></a>)). He also notes that the decomposition P=LDR may be achieved within vector elements.</p>
<p>As a first example, consider the nx n matrix P(n) with coefficients P_s,t=s+t choose smod 2. Here and below, indices start at 0. Let also ds(n) denote the digit-sum of the integer n. Then</p>
<p class="pcenter">\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 P 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 P within FR vector elements, following Bacher:</p>
<table class="example">
<tr><td><pre>
gap> AssignGeneratorVariables(FRAlgebra(Rationals,
"P=[[P,P],[P,0]]","L=[[L,0],[L,L]]","D=[[D,0],[0,-D]]"));
gap> L*D*TransposedFRElement(L)=P;
true
</pre></td></tr></table>
<p>and to analyse the elements of the diagonal matrix D.</p>
<p>For a more complicated example, let v_2 denote 2-valuation of a rational, and construct the nx n matrix V(n) with coefficients V_s,t=i^v_2(s+t choose s). Then</p>
<p class="pcenter">\det(V(n))=\det(P(n))\prod_{k=1}^{n-1}(1-f(k)i),</p>
<p>where f(k) is the regular paper-folding sequence defined by f(2^n)=1 and f(2^n+a)=-f(2^n-a) for 1le a<2^n.</p>
<p>This is again proved by noticing that V is a corner in a self-similar element, namely</p>
<table class="example">
<tr><td><pre>
gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
"V1=[[V1,V2],[V2,E(4)*V1]]",
"V2=[[V1,-E(4)*V1+(1+E(4))*V2],[-E(4)*V1+(1+E(4))*V2,-V1]]"));
gap> Activity(V1,3)=
List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));
true
</pre></td></tr></table>
<p>The LR decomposition of V=V1 can be checked as follows:</p>
<table class="example">
<tr><td><pre>
gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
"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)"));
gap> L1*D1*TransposedFRElement(L1)=V1;
true
</pre></td></tr></table>
<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.html#X796B736286CACF85"><b>6.1-10</b></a>). This approach will be followed below.</p>
<p>For the next example, consider "Beeblebrox reduction" beta(4kpm1)=pm1,beta(2k)=0, and construct the nx n matrix Z(n) (named after Zaphod Beeblebrox) with coefficients Z_s,t=beta(s+t choose s). Then</p>
<p class="pcenter">\det(Z(n))=\prod_{k=1}^{n-1}g(k),</p>
<p>where g(sum a_i2^i)=(-1)^a_03^#{i:a_i=a_i+1=1}-#{i:a_i<> a_i+1=1} with all a_iin{0,1}.</p>
<p>This is again proved by noticing that Z is a corner in a self-similar element, namely</p>
<table class="example">
<tr><td><pre>
gap> beta := n->Jacobi(-1,n)*(n mod 2);;
gap> Zaphod := GuessVectorElement(List([0..7],i->List([0..7],j->beta(Binomial(i+j,j)))));
<Linear element on alphabet Rationals^2 with 3-dimensional stateset>
gap> Display(Zaphod);
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
gap> LDUDecompositionFRElement(guessZ);
[ <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> ]
gap> Display(last[2]);
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></td></tr></table>
<p>and now the recursion read on this diagonal self-similar matrix gives immediately Bacher's recursion for det(Z(n)).</p>
<p>Bacher notes that the group generated by a=L_1,b=L_2/2,c=L_3,d=L_4 in the last example may be of interest. A quick check produces the following relations (slightly rewritten):</p>
<table class="example">
<tr><td><pre>
gap> AssignGeneratorVariables(FRAlgebra(Rationals,
"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]]"));
gap> g := Group(List([a,b,c,d], x->Activity(x,3)));
<matrix group with 4 generators>
gap> FindShortGroupRelations(g,10);
[ 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></td></tr></table>
<p>Consider next the "triangular Beeblebrox matrix" with entries L_s,t=beta(s choose t). The recurrence is now given by</p>
<table class="example">
<tr><td><pre>
gap> A := FRAlgebra(Rationals,
"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></td></tr></table>
<p>and it is striking that A is a graded algebra, with L_1,L_2,L_3 homogeneous of degree 1, and each homogeneous component is 3-dimensional; all of L_1,L_2,L_3 are invertible (with inverses have degree -1), and generate a group that admits a faithful 3x 3 linear representation. As a final example, Bacher considers the "Jacobi character" chi(8ℤpm1)=1,chi(8ℤpm3)=-1,chi(2ℤ)=0, and the associated matrix J_s,t=chi(s+t choose s). He gives an easily-computed, but complicated formula for det(J(n)). We can recover this formula, as before, by "guessing" an LR decomposition for J, which is self-similar and convergent:</p>
<table class="example">
<tr><td><pre>
gap> chi := function(x)
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;;
gap> m := List([0..63],i->List([0..63],j->chi(Binomial(i+j,j))));;
gap> J := GuessVectorElement(m,2);
<Linear element on alphabet Rationals^2 with 9-dimensional stateset>
gap> LDUDecompositionFRElement(J);
[ <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> ]
gap> time;
26869
gap> Display(last2[2]);
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></td></tr></table>
<p><a id="X7C4A51947E1609A8" name="X7C4A51947E1609A8"></a></p>
<h4>10.5 <span class="Heading">VH groups</span></h4>
<p>[!!! introduction to do]</p>
<p><a id="X7E0071D4838B239D" name="X7E0071D4838B239D"></a></p>
<h5>10.5-1 VHStructure</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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">> IsVHGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p><b>Returns: </b>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 V,H such that every relator of <var class="Arg">g</var> is of the form vhv'h', and such that for all vin V,hin H there exist unique v'in V,h'in H such that vhv'h'=1.</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>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<p><a id="X7F852A357D7E2E76" name="X7F852A357D7E2E76"></a></p>
<h5>10.5-2 VerticalAction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> 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">> HorizontalAction</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A homomorphism to an FR group.</p>
<p>A group with VH structure admits a <em>vertical action</em> of its subgroup < V>; this is the group generated by the automaton <code class="code">MealyMachine(trans,out)</code>. The function returns the group homomorphism from the subgroup < V> to that FR group.</p>
<p>The horizontal action is that of the dual automaton (see <code class="func">DualMachine</code> (<a href="chap5.html#X809F069B798ED985"><b>5.2-3</b></a>)).</p>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<p><a id="X86B1C2F079FE8D82" name="X86B1C2F079FE8D82"></a></p>
<h5>10.5-3 VHGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VHGroup</code>( <var class="Arg">l1, l2, ...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>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>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<p><a id="X7D1FCB877D1B96EA" name="X7D1FCB877D1B96EA"></a></p>
<h5>10.5-4 IsIrreducibleVHGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsIrreducibleVHGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b>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>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<p><a id="X84DB7FA4846075A7" name="X84DB7FA4846075A7"></a></p>
<h5>10.5-5 MaximalSimpleSubgroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MaximalSimpleSubgroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b>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.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>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap9.html">Previous Chapter</a> <a href="chap11.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1150
