<?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 7: Self-similar groups, monoids and semigroups</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="chap6.html">Previous Chapter</a> <a href="chap8.html">Next Chapter</a> </div>
<p><a id="X86C0E6F083DCCDC8" name="X86C0E6F083DCCDC8"></a></p>
<div class="ChapSects"><a href="chap7.html#X86C0E6F083DCCDC8">7 <span class="Heading">Self-similar groups, monoids and semigroups</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X80A26BAA7B53C1BD">7.1 <span class="Heading">Creators for FR semigroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7AE8F92383272329">7.1-1 FRGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X853E3F0680C76F56">7.1-2 SCGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F15D57A7959FEF6">7.1-3 Correspondence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D0B8334786E2802">7.1-4 FullSCGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7DB92C34827D513F">7.1-5 FRMachineFRGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7BF4AC9F830A8E1A">7.1-6 IsomorphismFRGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7DE1CAE981F2825B">7.1-7 IsomorphismMealyGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7BB8DDEA83946C73">7.1-8 FRGroupByVirtualEndomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79D75A7D80DD9AD1">7.1-9 TreeWreathProduct</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85840A047C04BFC6">7.1-10 WeaklyBranchedEmbedding</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X84E20571841DE1E4">7.2 <span class="Heading">Operations for FR semigroups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C6D7BA0818A3A3D">7.2-1 PermGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8620BEAF7957FA4D">7.2-2 PcGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79B8CFEA79987E12">7.2-3 TransMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82BF1F2579A02C5E">7.2-4 TransSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7BDC634086437315">7.2-5 EpimorphismGermGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87378D53791D0B70">7.2-6 StabilizerImage</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B4CD9CA872BA368">7.2-7 LevelStabilizer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F65F07F85034B3B">7.2-8 IsStateClosedFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79246DB482BEAF2D">7.2-9 StateClosure</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E2F34417EBB7673">7.2-10 IsRecurrentFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FBF56737D9063F4">7.2-11 IsLevelTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D95219481AEDD20">7.2-12 IsInfinitelyTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A6CB30181662C77">7.2-13 IsFinitaryFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X791BCD9D782C6237">7.2-14 Degree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FA67E4387C91BD8">7.2-15 HasOpenSetConditionFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7EAB4B5B843C0EC5">7.2-16 IsContracting</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7CA062A67C1554BB">7.2-17 NucleusOfFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8443D711796F06E4">7.2-18 NucleusMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A874A107D4944E1">7.2-19 BranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X78ADACCD8586D3C7">7.2-20 FindBranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X832D98E47ACA099C">7.2-21 IsBranched</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A905CE87B49213F">7.2-22 IsBranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8749E0797A99F531">7.2-23 TopVertexTransformations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C56C90086070A2E">7.2-24 VertexTransformations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7DF2D9838625CDED">7.2-25 VirtualEndomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C81CB1C7F0D7A90">7.2-26 EpimorphismFromFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8740656382656D63">7.2-27 IsomorphismSubgroupFpGroup</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7E8485A081EBB3AA">7.3 <span class="Heading">Properties for infinite groups</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X840ED7D279ECAB7F">7.3-1 IsTorsionGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7914F2D68077F503">7.3-2 IsTorsionFreeGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87E93FFC820ED40E">7.3-3 IsAmenableGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X873C0A7C8422C0C9">7.3-4 IsVirtuallySimpleGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79A3A0CF82B6F089">7.3-5 IsResiduallyFinite</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X86E1182E7EEFAADB">7.3-6 IsSQUniversal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FDAEAFF78A5E7D2">7.3-7 IsJustInfinite</a></span>
</div>
</div>
<h3>7 <span class="Heading">Self-similar groups, monoids and semigroups</span></h3>
<p>Self-similar groups, monoids and semigroups (below <em>FR semigroups</em>) are simply groups, monoids and semigroups whose elements are FR machines. They naturally act on the alphabet of their elements, and on sequences over that alphabet.</p>
<p>Most non-trivial calculations in FR groups are performed as follows: <strong class="pkg">GAP</strong> searches through words of short length in the generating set of a FR group to find a solution to a group-theoretic question, and at the same time searches through the finite quotients to prove the inexistence of a solution. Usually the calculation ends with the answer <code class="keyw">maybe</code>, which means that no definite answer, neither positive nor negative, could be found; however, the cases where the calculation actually terminates have been most useful.</p>
<p>The maximal length of words to consider in the search is controlled by the variable <code class="code">FR_SEARCH.radius</code> (initially 10), and the maximal depth of the tree in which to search is controlled by the variable <code class="code">FR_SEARCH.depth</code> (initially 6). These limits can be modified in any function call using <strong class="pkg">GAP</strong>'s options mechanism, e.g. in <code class="code">Index(G,H:FRdepth:=5,FRradius:=5)</code>.</p>
<p><a id="X80A26BAA7B53C1BD" name="X80A26BAA7B53C1BD"></a></p>
<h4>7.1 <span class="Heading">Creators for FR semigroups</span></h4>
<p>The most straightforward creation method for FR groups is <code class="code">Group()</code>, applied with FR elements as arguments. There are shortcuts to this somewhat tedious method:</p>
<p><a id="X7AE8F92383272329" name="X7AE8F92383272329"></a></p>
<h5>7.1-1 FRGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRGroup</code>( <var class="Arg">{definition, }</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">> FRMonoid</code>( <var class="Arg">{definition, }</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">> FRSemigroup</code>( <var class="Arg">{definition, }</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new self-similar group/monoid/semigroup.</p>
<p>This function constructs a new FR group/monoid/semigroup, generated by group FR elements. It receives as argument any number of strings, each of which represents a generator of the object to be constructed.</p>
<p>Each <var class="Arg">definition</var> is of the form <code class="code">"name=projtrans"</code>, where each of <code class="code">proj</code> and <code class="code">trans</code> is optional. <code class="code">proj</code> is of the form <code class="code"><w1,...,wd></code>, where each <code class="code">wi</code> is a (possibly empty) word in the <code class="code">name</code>s or is 1. <code class="code">trans</code> is either a permutation in disjoint cycle notation, or a list, representing the images of a permutation.</p>
<p>The option <code class="code">IsMealyElement</code>, passed e.g. as in <code class="code">FRGroup("a=(1,2)":IsMealyElement)</code>, asks for the resulting group to be generated by Mealy elements. The generators must of course be finite-state. Their names ("a",...) are not remembered in the constructing group (but can be set using <code class="func">SetName</code> (<a href="/usr/local/src/4.0/doc/ref/chap12.html#s8ss1"><b>Reference: SetName</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> FRGroup("a=(1,2)","b=(1,2,3,4,5)"); Size(last);
<self-similar group over [ 1 .. 5 ] with 2 generators>
120
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(Dinfinity);
#I Assigned the global variables [ a, b ]
gap> Order(a); Order(b); Order(a*b);
2
2
infinity
gap> ZZ := FRGroup("t=<,t>[2,1]");
<self-similar group over [ 1 .. 2 ] with 1 generator>
tau := FRElement([[[b,1],[1]]],[()],[1]);
<2|f3>
gap> IsSubgroup(Dinfinity,ZZ);
false
gap> IsSubgroup(Dinfinity^tau,ZZ);
true
gap> Index(Dinfinity^tau,ZZ);
2
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");
<self-similar monoid over [ 1 .. 2 ] with 2 generators>
gap> f := GeneratorsOfMonoid(i4){[1,2]};;
gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
gap> f[1]^2=One(m);
true
gap> f[2]^3=f[2];
true
gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
true
gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
true
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> i2 := FRSemigroup("f0=<f0,f0>(1,2)","f1=<f1,f0>[2,2]");
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(i2);
#I Assigned the global variables [ "f0", "f1" ]
gap> f0^2=One(i2);
true
gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
true
</pre></td></tr></table>
<p><a id="X853E3F0680C76F56" name="X853E3F0680C76F56"></a></p>
<h5>7.1-2 SCGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SCGroup</code>( <var class="Arg">m</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">> SCGroupNC</code>( <var class="Arg">m</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">> SCMonoid</code>( <var class="Arg">m</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">> SCMonoidNC</code>( <var class="Arg">m</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">> SCSemigroup</code>( <var class="Arg">m</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">> SCSemigroupNC</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The state-closed group/monoid/semigroup generated by the machine <var class="Arg">m</var>.</p>
<p>This function constructs a new FR group/monoid/semigroup <code class="code">g</code>, generated by all the states of the FR machine <var class="Arg">m</var>. There is a bijective correspondence between <code class="code">GeneratorsOfFRMachine(m)</code> and the generators of <code class="code">g</code>, which is accessible via <code class="code">Correspondence(g)</code> (See <code class="func">Correspondence</code> (<a href="chap7.html#X7F15D57A7959FEF6"><b>7.1-3</b></a>)); it is a homomorphism from the stateset of <var class="Arg">m</var> to <code class="code">g</code>, or a list indicating for each state of <var class="Arg">m</var> a corresponding generator index in the generators of <code class="code">g</code> (with negatives for inverses, and 0 for identity).</p>
<p>In the non-<code class="code">NC</code> forms, redundant (equal, trivial or mutually inverse) states are removed from the generating set of <code class="code">g</code>.</p>
<table class="example">
<tr><td><pre>
gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);; g := SCGroupNC(b);
<self-similar group over [ 1 .. 2 ] with 3 generators>
gap> Size(g);
infinity
gap> IsOne(Comm(g.2,g.2^g.1));
true
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> i4machine := MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> IsInvertible(i4machine);
false
gap> i4 := SCMonoidNC(i4machine);
<self-similar monoid over [ 1 .. 2 ] with 3 generators>
gap> f := GeneratorsOfMonoid(i4){[1,2]};;
gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
gap> f[1]^2=One(m);
true
gap> f[2]^3=f[2];
true
gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
true
gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
true
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> i2machine := MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]);
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
gap> i2 := SCSemigroupNC(i2machine);
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
gap> f0^2=One(i2);
true
gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
true
</pre></td></tr></table>
<p><a id="X7F15D57A7959FEF6" name="X7F15D57A7959FEF6"></a></p>
<h5>7.1-3 Correspondence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Correspondence</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A correspondence between the generators of the underlying FR machine of <var class="Arg">g</var> and <var class="Arg">g</var>.</p>
<p>If <var class="Arg">g</var> was created as the state closure of an FR machine <code class="code">m</code>, this attribute records the correspondence between <code class="code">m</code> and <var class="Arg">g</var>.</p>
<p>If <code class="code">m</code> is a group/monoid/semigroup/algebra FR machine, then <code class="code">Correspondence(g)</code> is a homomorphism from the stateset of <code class="code">m</code> to <var class="Arg">g</var>.</p>
<p>If <code class="code">m</code> is a Mealy or vector machine, then <code class="code">Correspondence(g)</code> is a list, with in position i the index in the generating set of <var class="Arg">g</var> of state number i. This index is 0 if there is no corresponding generator because the state is trivial, and is negative if there is no corresponding generator because the inverse of state number i is a generator.</p>
<p>See <code class="func">SCGroupNC</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCGroup</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCMonoidNC</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCMonoid</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCSemigroupNC</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCSemigroup</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>), <code class="func">SCAlgebraNC</code> (<a href="chap8.html#X844B890F7BF56236"><b>8.1-2</b></a>), <code class="func">SCAlgebra</code> (<a href="chap8.html#X844B890F7BF56236"><b>8.1-2</b></a>), <code class="func">SCAlgebraWithOneNC</code> (<a href="chap8.html#X844B890F7BF56236"><b>8.1-2</b></a>), and <code class="func">SCAlgebraWithOne</code> (<a href="chap8.html#X844B890F7BF56236"><b>8.1-2</b></a>) for examples.</p>
<p><a id="X7D0B8334786E2802" name="X7D0B8334786E2802"></a></p>
<h5>7.1-4 FullSCGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FullSCGroup</code>( <var class="Arg">...</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">> FullSCMonoid</code>( <var class="Arg">...</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">> FullSCSemigroup</code>( <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>A maximal state-closed group/monoid/semigroup on the alphabet <var class="Arg">a</var>.</p>
<p>This function constructs a new FR group, monoid or semigroup, which contains all transformations with given properties of the tree with given alphabet.</p>
<p>The arguments can be, in any order: a semigroup, specifying which vertex actions are allowed; a set or domain, specifying the alphabet of the tree; an integer, specifying the maximal depth of elements; and a filter among <code class="func">IsFinitaryFRElement</code> (<a href="chap5.html#X793C427084F830CE"><b>5.2-10</b></a>), <code class="func">IsBoundedFRElement</code> (<a href="chap5.html#X82F4410E85C54C7E"><b>5.2-12</b></a>), <code class="func">IsPolynomialGrowthFRElement</code> (<a href="chap5.html#X81D4A3F27C5FAD96"><b>5.2-13</b></a>) and <code class="func">IsFiniteStateFRElement</code> (<a href="chap4.html#X7C4076707CBBE945"><b>4.2-11</b></a>).</p>
<p>This object serves as a container for all FR elements with alphabet <var class="Arg">a</var>. Random elements can be drawn from it; they are Mealy elements with a random number of states, and with the required properties.</p>
<table class="example">
<tr><td><pre>
gap> g := FullSCGroup([1..3]);
FullSCGroup([ 1 .. 3 ]);
gap> IsSubgroup(g,GuptaSidkiGroup);
true
gap> g := FullSCGroup([1..3],Group((1,2,3)));
FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ))
gap> IsSubgroup(g,GuptaSidkiGroup);
true
gap> IsSubgroup(g,GrigorchukGroup);
false
gap> Random(g);
<Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>
gap> Size(FullSCGroup([1,2],3));
128
gap> g := FullSCMonoid([1..2]);
FullSCMonoid([ 1 .. 2 ])
gap> IsSubset(g,AsTrans(FullSCGroup([1..2])));
true
gap> IsSubset(g,AsTrans(GrigorchukGroup));
true
gap> g := FullSCSemigroup([1..3]);
FullSCSemigroup([ 1 .. 3 ])
gap> h := FullSCSemigroup([1..3],Semigroup(Trans([1,1,1])));
FullSCSemigroup([ 1 .. 3 ], Semigroup( [ Trans( [ 1, 1, 1 ] ) ] ))
gap> Size(h);
1
gap> IsSubset(g,h);
true
gap> g=FullSCMonoid([1..3]);
true
</pre></td></tr></table>
<p><a id="X7DB92C34827D513F" name="X7DB92C34827D513F"></a></p>
<h5>7.1-5 FRMachineFRGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRMachineFRGroup</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">> FRMachineFRMonoid</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">> FRMachineFRSemigroup</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">> MealyMachineFRGroup</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">> MealyMachineFRMonoid</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">> MealyMachineFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A machine describing all generators of <var class="Arg">g</var>.</p>
<p>This function constructs a new group/monoid/semigroup/Mealy FR machine, with (at least) one generator per generator of <var class="Arg">g</var>. This is done by adding all machines of all generators of <var class="Arg">g</var>, and minimizing.</p>
<p>In particular, if <var class="Arg">g</var> is state-closed, then <code class="code">SCGroup(FRMachineFRGroup(g))</code> gives a group isomorphic to <var class="Arg">g</var>, and similarly for monoids and semigroups.</p>
<table class="example">
<tr><td><pre>
gap> FRMachineFRGroup(GuptaSidkiGroup);
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f11, f12 ] )>
gap> Display(last);
G | 1 2 3
-----+--------+----------+--------+
f11 | <id>,2 <id>,3 <id>,1
f12 | f11,1 f11^-1,2 f12,3
-----+--------+----------+--------+
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> FRMachineFRMonoid(I4Monoid);
<FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m11, m12 ], ... )>
gap> Display(last);
M | 1 2
-----+--------+--------+
m11 | <id>,2 <id>,1
m12 | m11,1 m12,1
-----+--------+--------+
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> FRMachineFRSemigroup(I2Monoid);
<FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s11, s12, s1 ] )>
gap> Display(last);
S | 1 2
-----+-------+-------+
s11 | s11,1 s11,2
s12 | s12,2 s12,1
s1 | s1,2 s12,2
-----+-------+-------+
</pre></td></tr></table>
<p><a id="X7BF4AC9F830A8E1A" name="X7BF4AC9F830A8E1A"></a></p>
<h5>7.1-6 IsomorphismFRGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsomorphismFRGroup</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">> IsomorphismFRMonoid</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">> IsomorphismFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An isomorphism towards a group/monoid/semigroup on a single FR machine.</p>
<p>This function constructs a new FR group/monoid/semigroup, such that all elements of the resulting object have the same underlying group/monoid/semigroup FR machine.</p>
<table class="example">
<tr><td><pre>
gap> phi := IsomorphismFRGroup(GuptaSidkiGroup);
[ <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>,
<Mealy element on alphabet [ 1, 2, 3 ] with 4 states, initial state 1> ] ->
[ <3|identity ...>, <3|f1>, <3|f1^-1>, <3|f2> ]
gap> Display(GuptaSidkiGroup.2);
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 a,1
c | a,3 a,1 a,2
d | b,1 c,2 d,3
---+-----+-----+-----+
Initial state: d
gap> Display(GuptaSidkiGroup.2^phi);
| 1 2 3
----+--------+---------+--------+
f1 | <id>,2 <id>,3 <id>,1
f2 | f1,1 f1^-1,2 f2,3
----+--------+---------+--------+
Initial state: f2
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> phi := IsomorphismFRSemigroup(I2Monoid);
MappingByFunction( I2, <self-similar semigroup over [ 1 .. 2 ] with
3 generators>, <Operation "AsSemigroupFRElement"> )
gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]);
| 1 2
---+-----+-----+
a | a,2 b,2
b | b,2 b,1
---+-----+-----+
Initial state: a
gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]^phi);
S | 1 2
----+------+------+
s1 | s1,2 s2,2
s2 | s2,2 s2,1
----+------+------+
Initial state: s1
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> phi := IsomorphismFRMonoid(I4Monoid);
MappingByFunction( I4, <self-similar monoid over [ 1 .. 2 ] with
2 generators>, <Operation "AsMonoidFRElement"> )
gap> Display(GeneratorsOfMonoid(I4Monoid)[1]);
| 1 2
---+-----+-----+
a | b,2 b,1
b | b,1 b,2
---+-----+-----+
Initial state: a
gap> Display(GeneratorsOfMonoid(I4Monoid)[1]^phi);
M | 1 2
----+--------+--------+
m1 | <id>,2 <id>,1
----+--------+--------+
Initial state: m1
</pre></td></tr></table>
<p><a id="X7DE1CAE981F2825B" name="X7DE1CAE981F2825B"></a></p>
<h5>7.1-7 IsomorphismMealyGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsomorphismMealyGroup</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">> IsomorphismMealyMonoid</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">> IsomorphismMealySemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An isomorphism towards a group/monoid/semigroup all of whose elements are Mealy machines.</p>
<p>This function constructs a new FR group/monoid/semigroup, such that all elements of the resulting object are Mealy machines.</p>
<table class="example">
<tr><td><pre>
gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
<self-similar group over [ 1 .. 2 ] with 3 generators>
gap> phi := IsomorphismMealyGroup(G);
[ <2|a>, <2|b>, <2|c> ] ->
[ <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>,
<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>,
<Mealy element on alphabet [ 1, 2 ] with 4 states, initial state 1> ]
gap> Display(G.3);
| 1 2
---+--------+--------+
a | <id>,2 <id>,1
b | a,1 b,2
c | c,1 b,2
---+--------+--------+
Initial state: c
gap> Display(G.3^phi);
| 1 2
---+-----+-----+
a | a,1 b,2
b | c,1 b,2
c | d,2 d,1
d | d,1 d,2
---+-----+-----+
Initial state: a
</pre></td></tr></table>
<p><a id="X7BB8DDEA83946C73" name="X7BB8DDEA83946C73"></a></p>
<h5>7.1-8 FRGroupByVirtualEndomorphism</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRGroupByVirtualEndomorphism</code>( <var class="Arg">hom[, transversal]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new self-similar group.</p>
<p>This function constructs a new FR group <code class="code">P</code>, generated by group FR elements. Its first argument is a virtual endomorphism of a group <code class="code">G</code>, i.e. a homomorphism from a subgroup <code class="code">H</code> to <code class="code">G</code>. The constructed FR group acts on a tree with alphabet a transversal of <code class="code">H</code> in <code class="code">G</code> (represented as <code class="code">[1..d]</code>), and is a homomorphic image of <code class="code">G</code>. The stabilizer of the first-level vertex corresponding to the trivial coset is the image of <code class="code">H</code>. This function is loosely speaking an inverse of <code class="func">VirtualEndomorphism</code> (<a href="chap7.html#X7DF2D9838625CDED"><b>7.2-25</b></a>).</p>
<p>The optional second argument is a transversal of <code class="code">H</code> in <code class="code">G</code>, either of type <code class="code">IsRightTransversal</code> or a list.</p>
<p>Furthermore, an option "MealyElement" can be passed to the function, as <code class="code">FRGroupByVirtualEndomorphism(f:MealyElement)</code>, to require the resulting group to be generated by Mealy elements and not FR elements. The call will succeed, of course, only if the representation of <code class="code">G</code> is finite-state.</p>
<p>The resulting FR group has an attribute <code class="code">Correspondence(P)</code> that records a homomorphism from <code class="code">G</code> to <code class="code">P</code>.</p>
<p>The example below constructs the binary adding machine, and a non-standard representation of it.</p>
<table class="example">
<tr><td><pre>
gap> G := FreeGroup(1);
<free group on the generators [ f1 ]>
gap> f := GroupHomomorphismByImages(Group(G.1^2),G,[G.1^2],[G.1]);
[ f1^2 ] -> [ f1 ]
gap> H := FRGroupByVirtualEndomorphism(f);
<self-similar group over [ 1 .. 2 ] with 1 generator>
gap> Display(H.1);
| 1 2
----+--------+------+
x1 | <id>,2 x1,1
----+--------+------+
Initial state: x1
gap> Correspondence(H);
[ f1 ] -> [ <2|x1> ]
gap> H := FRGroupByVirtualEndomorphism(f,[G.1^0,G.1^3]);;
gap> Display(H.1);
| 1 2
----+---------+--------+
x1 | x1^-1,2 x1^2,1
----+---------+--------+
Initial state: x1
gap> H := FRGroupByVirtualEndomorphism(f:MealyElement);
<self-similar group over [ 1 .. 2 ] with 1 generator>
gap> Display(H.1);
| 1 2
---+-----+-----+
a | b,2 a,1
b | b,1 b,2
---+-----+-----+
Initial state: a
</pre></td></tr></table>
<p><a id="X79D75A7D80DD9AD1" name="X79D75A7D80DD9AD1"></a></p>
<h5>7.1-9 TreeWreathProduct</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TreeWreathProduct</code>( <var class="Arg">g, h, x0, y0</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The tree-wreath product of groups <var class="Arg">g,h</var>.</p>
<p>The tree-wreath product of two FR groups is a group generated by a copy of <var class="Arg">g</var> and of <var class="Arg">h</var>, in such a way that many conjugates of <var class="Arg">g</var> commute.</p>
<p>More formally, assume without loss of generality that all generators of <var class="Arg">g</var> are states of a machine <code class="code">m</code>, and that all generators of <var class="Arg">h</var> are states of a machine <code class="code">n</code>. Then the tree-wreath product is generated by the images of generators of <var class="Arg">g,h</var> in <code class="code">TreeWreathProduct(m,n,x0,y0)</code>.</p>
<p>For the operation on FR machines see <code class="func">TreeWreathProduct</code> (<a href="chap3.html#X7A0858097AA3FBDA"><b>3.5-8</b></a>)). It is described (with small variations, and in lesser generality) in <a href="chapBib.html#biBMR2197828">[Sid05]</a>. For example, in</p>
<table class="example">
<tr><td><pre>
gap> w := TreeWreathProduct(AddingGroup(2),AddingGroup(2),1,1);
<recursive group over [ 1 .. 4 ] with 2 generators>
gap> a := w.1; b := w.2;
<Mealy element on alphabet [ 1 .. 4 ] with 3 states>
<Mealy element on alphabet [ 1 .. 4 ] with 2 states>
gap> Order(a); Order(b);
infinity
infinity
gap> ForAll([-100..100],i->IsOne(Comm(a,a^(b^i))));
true
</pre></td></tr></table>
<p>the group <code class="code">w</code> is the wreath product Zwr Z.</p>
<p><a id="X85840A047C04BFC6" name="X85840A047C04BFC6"></a></p>
<h5>7.1-10 WeaklyBranchedEmbedding</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeaklyBranchedEmbedding</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A embedding of <var class="Arg">g</var> in a weakly branched group.</p>
<p>This function constructs a new FR group, on alphabet the square of the alphabet of <var class="Arg">g</var>. It is generated by the canonical copy of <var class="Arg">g</var> and by the tree-wreath product of <var class="Arg">g</var> with an adding machine on the same alphabet as <var class="Arg">g</var> (see <code class="func">TreeWreathProduct</code> (<a href="chap7.html#X79D75A7D80DD9AD1"><b>7.1-9</b></a>)). The function returns a group homomorphism into this new FR group.</p>
<p>The main result of <a href="chapBib.html#biBMR1995624">[SW03]</a> is that the resulting group h is weakly branched. More precisely, h' contains |X|^2 copies of itself. <code class="code"> gap> f := WeaklyBranchedEmbedding(BabyAleshinGroup);; gap> Range(f); <recursive group over [ 1 .. 4 ] with 8 generators> </code> constructs a finitely generated branched group containing a free subgroup.</p>
<p><a id="X84E20571841DE1E4" name="X84E20571841DE1E4"></a></p>
<h4>7.2 <span class="Heading">Operations for FR semigroups</span></h4>
<p><a id="X7C6D7BA0818A3A3D" name="X7C6D7BA0818A3A3D"></a></p>
<h5>7.2-1 PermGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PermGroup</code>( <var class="Arg">g, l</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">> EpimorphismPermGroup</code>( <var class="Arg">g, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>[An epimorphism to] the permutation group of <var class="Arg">g</var>'s action on level <var class="Arg">l</var>.</p>
<p>The first function returns a permutation group on d^l points, where d is the size of <var class="Arg">g</var>'s alphabet. It has as many generators as <var class="Arg">g</var>, and represents the action of <var class="Arg">g</var> on the <var class="Arg">l</var>th layer of the tree.</p>
<p>The second function returns a homomorphism from <var class="Arg">g</var> to this permutation group.</p>
<table class="example">
<tr><td><pre>
gap> g := FRGroup("a=(1,2)","b=<a,>"); Size(g);
<self-similar group over [ 1 .. 2 ] with 2 generators>
8
gap> PermGroup(g,2);
Group([ (1,3)(2,4), (1,2) ])
gap> PermGroup(g,3);
Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4) ])
gap> List([1..6],i->LogInt(Size(PermGroup(GrigorchukGroup,i)),2));
[ 1, 3, 7, 12, 22, 42 ]
gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
<self-similar group over [ 1 .. 2 ] with 1 generator>
infinity
gap> pi := EpimorphismPermGroup(g,5);
MappingByFunction( <self-similar group over [ 1 .. 2 ] with 1 generator,
of size infinity>, Group([ (1,17,9,25,5,21,13,29,3,19,11,27,7,23,15,31,
2,18,10,26,6,22,14,30,4,20,12,28,8,24,16,32) ]), function( w ) ... end )
gap> Order(g.1);
infinity
gap> Order(g.1^pi);
32
</pre></td></tr></table>
<p><a id="X8620BEAF7957FA4D" name="X8620BEAF7957FA4D"></a></p>
<h5>7.2-2 PcGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PcGroup</code>( <var class="Arg">g, l</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">> EpimorphismPcGroup</code>( <var class="Arg">g, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>[An epimorphism to] the pc group of <var class="Arg">g</var>'s action on level <var class="Arg">l</var>.</p>
<p>The first function returns a polycyclic group representing the action of <var class="Arg">g</var> on the <var class="Arg">l</var>th layer of the tree. It converts the permutation group <code class="code">PermGroup(g,l)</code> to a Pc group, in which computations are often faster.</p>
<p>The second function returns a homomorphism from <var class="Arg">g</var> to this pc group.</p>
<table class="example">
<tr><td><pre>
gap> g := PcGroup(GrigorchukGroup,7); time;
<pc group with 5 generators>
3370
gap> NormalClosure(g,Group(g.3)); time;
<pc group with 79 generators>
240
gap> g := PermGroup(GrigorchukGroup,7); time;
<permutation group with 5 generators>
3
gap> NormalClosure(g,Group(g.3)); time;
<permutation group with 5 generators>
5344
gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
<self-similar group over [ 1 .. 2 ] with 1 generator>
infinity
gap> pi := EpimorphismPcGroup(g,5);
MappingByFunction( <self-similar group over [ 1 .. 2 ] with
1 generator, of size infinity>, Group([ f1, f2, f3, f4, f5 ]), function( w ) ... end )
gap> Order(g.1);
infinity
gap> Order(g.1^pi);
32
</pre></td></tr></table>
<p><a id="X79B8CFEA79987E12" name="X79B8CFEA79987E12"></a></p>
<h5>7.2-3 TransMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TransMonoid</code>( <var class="Arg">g, l</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">> TransformationMonoid</code>( <var class="Arg">g, l</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">> EpimorphismTransMonoid</code>( <var class="Arg">g, l</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">> EpimorphismTransformationMonoid</code>( <var class="Arg">g, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>[An epimorphism to] the transformation monoid of <var class="Arg">g</var>'s action on level <var class="Arg">l</var>.</p>
<p>The first function returns a transformation monoid on d^l points, where d is the size of <var class="Arg">g</var>'s alphabet. It has as many generators as <var class="Arg">g</var>, and represents the action of <var class="Arg">g</var> on the <var class="Arg">l</var>th layer of the tree.</p>
<p>The second function returns a homomorphism from <var class="Arg">g</var> to this transformation monoid.</p>
<table class="example">
<tr><td><pre>
gap> i4 := SCMonoid(MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]));
<self-similar monoid over [ 1 .. 2 ] with 3 generators>
gap> g := TransMonoid(i4,6);
<monoid with 3 generators>
gap> List([1..6],i->Size(TransMonoid(i4,i)));
[ 4, 14, 50, 170, 570, 1882 ]
gap> Collected(List(g,RankOfTrans));
[ [ 1, 64 ], [ 2, 1280 ], [ 4, 384 ], [ 8, 112 ], [ 16, 32 ], [ 32, 8 ], [ 64, 2 ] ]
gap> pi := EpimorphismTransMonoid(i4,9);
MappingByFunction( <self-similar monoid over [ 1 .. 2 ] with 3 generators>,
<monoid with 3 generators>, function( w ) ... end )
gap> f := GeneratorsOfMonoid(i4){[1,2]};;
gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
gap> Product(f{[3,5,7,9,11]})=f[11]*f[10];
false
gap> Product(f{[3,5,7,9,11]})^pi=(f[11]*f[10])^pi;
true
</pre></td></tr></table>
<p><a id="X82BF1F2579A02C5E" name="X82BF1F2579A02C5E"></a></p>
<h5>7.2-4 TransSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TransSemigroup</code>( <var class="Arg">g, l</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">> TransformationSemigroup</code>( <var class="Arg">g, l</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">> EpimorphismTransSemigroup</code>( <var class="Arg">g, l</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">> EpimorphismTransformationSemigroup</code>( <var class="Arg">g, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>[An epimorphism to] the transformation semigroup of <var class="Arg">g</var>'s action on level <var class="Arg">l</var>.</p>
<p>The first function returns a transformation semigroup on d^l points, where d is the size of <var class="Arg">g</var>'s alphabet. It has as many generators as <var class="Arg">g</var>, and represents the action of <var class="Arg">g</var> on the <var class="Arg">l</var>th layer of the tree.</p>
<p>The second function returns a homomorphism from <var class="Arg">g</var> to this transformation semigroup.</p>
<table class="example">
<tr><td><pre>
gap> i2 := SCSemigroup(MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]));
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
gap> g := TransSemigroup(i2,6);
<semigroup with 2 generators>
gap> List([1..6],i->Size(TransSemigroup(i2,i)));
[ 4, 14, 42, 114, 290, 706 ]
gap> Collected(List(g,RankOfTrans));
[ [ 1, 64 ], [ 2, 384 ], [ 4, 160 ], [ 8, 64 ], [ 16, 24 ], [ 32, 8 ], [ 64, 2 ] ]
gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
gap> pi := EpimorphismTransSemigroup(i2,10);
MappingByFunction( <self-similar semigroup over [ 1 .. 2 ] with
2 generators>, <semigroup with 2 generators>, function( w ) ... end )
gap> (f1*(f1*f0)^10)=((f1*f0)^10);
false
gap> (f1*(f1*f0)^10)^pi=((f1*f0)^10)^pi;
true
</pre></td></tr></table>
<p><a id="X7BDC634086437315" name="X7BDC634086437315"></a></p>
<h5>7.2-5 EpimorphismGermGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> EpimorphismGermGroup</code>( <var class="Arg">g, l</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">> EpimorphismGermGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A homomorphism to a polycyclic group.</p>
<p>This function returns an epimorphism to a polycyclic group, encoding the action on the first <var class="Arg">l</var> levels of the tree and on the germs below. If <var class="Arg">l</var> is omitted, it is assumed to be 0.</p>
<p>Since the elements of <var class="Arg">g</var> are finite automata, they map periodic sequences to periodic sequences. The action on the periods, and in the immediate vicinity of them, is called the <em>germ action</em> of <var class="Arg">g</var>. This function returns the natural homomorphism from <var class="Arg">g</var> to the wreath product of this germ group with the quotient of <var class="Arg">g</var> acting on the <var class="Arg">l</var>th layer of the tree.</p>
<p>The germ group, by default, is abelian. If it is finite, this function returns a homomorphism to a Pc group; otherwise, a homomorphism to a polycyclic group.</p>
<p>The <code class="func">GrigorchukEvilTwin</code> (<a href="chap10.html#X7C58F33D825A473A"><b>10.1-11</b></a>) is, for now, the only example with a hand-coded, non-abelian germ group.</p>
<table class="example">
<tr><td><pre>
gap> EpimorphismGermGroup(GrigorchukGroup,0);
MappingByFunction( GrigorchukGroup, <pc group of size 4 with 2 generators>,
function( g ) ... end )
gap> List(GeneratorsOfGroup(GrigorchukGroup),x->x^last);
[ <identity> of ..., f1, f1*f2, f2 ]
gap> StructureDescription(Image(last2));
"C2 x C2"
gap> g := FRGroup("t=<,t>(1,2)","m=<,m^-1>(1,2)");;
gap> EpimorphismGermGroup(g,0);
MappingByFunction( <state-closed, bounded group over [ 1, 2 ] with 2
generators>, Pcp-group with orders [ 0, 0 ], function( x ) ... end )
gap> EpimorphismGermGroup(g,1);; Range(last); Image(last2);
Pcp-group with orders [ 2, 0, 0, 0, 0 ]
Pcp-group with orders [ 2, 0, 0, 0 ]
</pre></td></tr></table>
<p><a id="X87378D53791D0B70" name="X87378D53791D0B70"></a></p>
<h5>7.2-6 StabilizerImage</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StabilizerImage</code>( <var class="Arg">g, v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The group of all states at <var class="Arg">v</var> of elements of <var class="Arg">g</var>.</p>
<p>This function constructs a new FR group, containing all states at vertex <var class="Arg">v</var> (which can be an integer or a list) of elements of <var class="Arg">g</var>.</p>
<p>The result is <var class="Arg">g</var> itself precisely if <var class="Arg">g</var> is recurrent (see <code class="func">IsRecurrentFRSemigroup</code> (<a href="chap7.html#X7E2F34417EBB7673"><b>7.2-10</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> G := FRGroup("t=<,t>(1,2)","u=<,u^-1>(1,2)","b=<u,t>");
<self-similar group over [ 1 .. 2 ] with 3 generators>
gap> Stabilizer(G,1);
<self-similar group over [ 1 .. 2 ] with 5 generators>
gap> GeneratorsOfGroup(last);
[ <2|u*t^-1>, <2|b>, <2|t^2>, <2|t*u>, <2|t*b*t^-1> ]
gap> StabilizerImage(G,1);
<self-similar group over [ 1 .. 2 ] with 5 generators>
gap> GeneratorsOfGroup(last);
[ <2|identity ...>, <2|u>, <2|t>, <2|u^-1>, <2|t> ]
</pre></td></tr></table>
<p><a id="X7B4CD9CA872BA368" name="X7B4CD9CA872BA368"></a></p>
<h5>7.2-7 LevelStabilizer</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LevelStabilizer</code>( <var class="Arg">g, n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The fixator of the <var class="Arg">n</var>th level of the tree.</p>
<p>This function constructs the normal subgroup of <var class="Arg">g</var> that fixes the <var class="Arg">n</var>th level of the tree.</p>
<table class="example">
<tr><td><pre>
gap> G := FRGroup("t=<,t>(1,2)","a=(1,2)");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> LevelStabilizer(G,2);
<self-similar group over [ 1 .. 2 ] with 9 generators>
gap> Index(G,last);
8
gap> IsNormal(G,last2);
true
</pre></td></tr></table>
<p><a id="X7F65F07F85034B3B" name="X7F65F07F85034B3B"></a></p>
<h5>7.2-8 IsStateClosedFRSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsStateClosedFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if all states of elements of <var class="Arg">g</var> belong to <var class="Arg">g</var>.</p>
<p>This function tests whether <var class="Arg">g</var> is a <em>state-closed</em> group, i.e. a group such that all states of all elements of <var class="Arg">g</var> belong to <var class="Arg">g</var>.</p>
<p>The smallest state-closed group containing <var class="Arg">g</var> is computed with <code class="func">StateClosure</code> (<a href="chap7.html#X79246DB482BEAF2D"><b>7.2-9</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(Dinfinity);
#I Assigned the global variables [ a, b ]
gap> IsStateClosedFRSemigroup(Group(a));
IsStateClosedFRSemigroup(Group(b));
IsStateClosedFRSemigroup(Dinfinity);
true
false
true
</pre></td></tr></table>
<p><a id="X79246DB482BEAF2D" name="X79246DB482BEAF2D"></a></p>
<h5>7.2-9 StateClosure</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StateClosure</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The smallest state-closed group containing <var class="Arg">g</var>.</p>
<p>This function computes the smallest group containing all states of all elements of <var class="Arg">g</var>, i.e. the smallest group containing <var class="Arg">g</var> and for which <code class="func">IsStateClosedFRSemigroup</code> (<a href="chap7.html#X7F65F07F85034B3B"><b>7.2-8</b></a>) returns <code class="keyw">true</code>.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(Dinfinity);
#I Assigned the global variables [ a, b ]
gap> StateStateClosure(Group(a))=Dinfinity; StateClosure(Group(b))=Dinfinity;
false
true
</pre></td></tr></table>
<p><a id="X7E2F34417EBB7673" name="X7E2F34417EBB7673"></a></p>
<h5>7.2-10 IsRecurrentFRSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRecurrentFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is a recurrent group.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is a <em>recurrent</em> group, i.e. if, for every vertex <code class="code">v</code>, all elements of <var class="Arg">g</var> appear as states at <code class="code">v</code> of elements fixing <code class="code">v</code>.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(Dinfinity);
#I Assigned the global variables [ a, b ]
gap> IsRecurrentFRSemigroup(Group(a)); IsRecurrentFRSemigroup(Group(b));
false
false
gap> IsRecurrentFRSemigroup(Dinfinity);
true
</pre></td></tr></table>
<p><a id="X7FBF56737D9063F4" name="X7FBF56737D9063F4"></a></p>
<h5>7.2-11 IsLevelTransitive</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsLevelTransitive</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is a level-transitive group.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is a <em>level-transitive</em> group, i.e. if the action of <var class="Arg">g</var> is transitive at every level of the tree on which it acts.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(Dinfinity);
#I Assigned the global variables [ a, b ]
gap> IsLevelTransitive(Group(a)); IsLevelTransitive(Group(b));
IsLevelTransitive(Dinfinity);
false
false
true
</pre></td></tr></table>
<p><a id="X7D95219481AEDD20" name="X7D95219481AEDD20"></a></p>
<h5>7.2-12 IsInfinitelyTransitive</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsInfinitelyTransitive</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is infinitely transitive.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is an <em>infinitely transitive</em> group. This means that <var class="Arg">g</var> is the state-closed group of a bireversible Mealy machine (see <code class="func">IsBireversible</code> (<a href="chap5.html#X80D2545D7D0990A2"><b>5.2-7</b></a>)), that this Mealy machine has an involution on its alphabet (see <code class="func">AlphabetInvolution</code> (<a href="chap5.html#X7CCB79B981912CCC"><b>5.2-6</b></a>)), and that the action of the set of reduced words of any given length over the alphabet (where "reduced" means no successive letters related by the involution) is transitive.</p>
<p>This notion is of fundamental importance for the study of lattices in a product of trees.</p>
<table class="example">
<tr><td><pre>
gap> !!!
</pre></td></tr></table>
<p><a id="X7A6CB30181662C77" name="X7A6CB30181662C77"></a></p>
<h5>7.2-13 IsFinitaryFRSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFinitaryFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsWeaklyFinitaryFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsBoundedFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsPolynomialGrowthFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFiniteStateFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if all elements of <var class="Arg">g</var> have the required property.</p>
<p>This function returns <code class="keyw">true</code> if all elements of <var class="Arg">g</var> have the required property, as FR elements; see <code class="func">IsFinitaryFRElement</code> (<a href="chap5.html#X793C427084F830CE"><b>5.2-10</b></a>), <code class="func">IsWeaklyFinitaryFRElement</code> (<a href="chap5.html#X7A87ED9D789245E4"><b>5.2-23</b></a>), <code class="func">IsBoundedFRElement</code> (<a href="chap5.html#X82F4410E85C54C7E"><b>5.2-12</b></a>), <code class="func">IsPolynomialGrowthFRElement</code> (<a href="chap5.html#X81D4A3F27C5FAD96"><b>5.2-13</b></a>) and <code class="func">IsFiniteStateFRElement</code> (<a href="chap4.html#X7C4076707CBBE945"><b>4.2-11</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>","d=<d,d>(1,2)");
<self-similar group over [ 1 .. 2 ] with 4 generators>
gap> L := [Group(G.1),Group(G.1,G.2),Group(G.1,G.2,G.3),G];;
gap> List(L,IsFinitaryFRSemigroup);
[ true, false, false, false ]
gap> List(L,IsBoundedFRSemigroup);
[ true, true, false, false ]
gap> List(L,IsPolynomialGrowthFRSemigroup);
[ true, true, true, false ]
gap> List(L,IsFiniteStateFRSemigroup);
[ true, true, true, true ]
</pre></td></tr></table>
<p><a id="X791BCD9D782C6237" name="X791BCD9D782C6237"></a></p>
<h5>7.2-14 Degree</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Degree</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">> DegreeOfFRSemigroup</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">> Depth</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">> DepthOfFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The maximal degree/depth of elements of <var class="Arg">g</var>.</p>
<p>This function returns the maximal degree/depth of elements of <var class="Arg">g</var>; see <code class="func">Degree</code> (<a href="chap5.html#X84BE780A81CAC69C"><b>5.2-9</b></a>) and <code class="func">Depth</code> (<a href="chap5.html#X7E5E8B2C79688DC0"><b>5.2-11</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> Degree(Group(G.1)); Degree(Group(G.1,G.2)); Degree(G);
0
1
2
gap> Depth(Group(G.1)); Depth(Group(G.1,G.2)); Depth(G);
1
infinity
infinity
</pre></td></tr></table>
<p><a id="X7FA67E4387C91BD8" name="X7FA67E4387C91BD8"></a></p>
<h5>7.2-15 HasOpenSetConditionFRSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HasOpenSetConditionFRSemigroup</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> has the open set condition.</p>
<p>This function returns <code class="keyw">true</code> if all elements of <var class="Arg">g</var> have the <em>open set condition</em>, see <code class="func">HasOpenSetConditionFRElement</code> (<a href="chap5.html#X7F76AF2D7C0279F9"><b>5.2-25</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> HasOpenSetConditionFRSemigroup(GrigorchukGroup);
false
gap> HasOpenSetConditionFRSemigroup(BinaryAddingGroup);
true
</pre></td></tr></table>
<p><a id="X7EAB4B5B843C0EC5" name="X7EAB4B5B843C0EC5"></a></p>
<h5>7.2-16 IsContracting</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsContracting</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is a contracting semigroup.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is a <em>contracting</em> semigroup, i.e. if there exists a finite subset <code class="code">n</code> of <var class="Arg">g</var> such that the <code class="func">LimitStates</code> (<a href="chap4.html#X8303B36C83371FB3"><b>4.2-10</b></a>) of every element of <var class="Arg">g</var> belong to <var class="Arg">n</var>.</p>
<p>The minimal such <code class="code">n</code> can be computed with <code class="func">NucleusOfFRSemigroup</code> (<a href="chap7.html#X7CA062A67C1554BB"><b>7.2-17</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> IsContracting(Dinfinity);
true
</pre></td></tr></table>
<p><a id="X7CA062A67C1554BB" name="X7CA062A67C1554BB"></a></p>
<h5>7.2-17 NucleusOfFRSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NucleusOfFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The nucleus of the contracting semigroup <var class="Arg">g</var>.</p>
<p>This function returns the <em>nucleus</em> of the contracting semigroup <var class="Arg">g</var>, i.e. the smallest subset <code class="code">n</code> of <var class="Arg">g</var> such that the <code class="func">LimitStates</code> (<a href="chap4.html#X8303B36C83371FB3"><b>4.2-10</b></a>) of every element of <var class="Arg">g</var> belong to <code class="code">n</code>.</p>
<p>This function returns <code class="keyw">fail</code> if no such <code class="code">n</code> exists. Usually, it loops forever without being able to decide whether <code class="code">n</code> is finite or infinite. It succeeds precisely when <code class="code">IsContracting(g)</code> succeeds.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> NucleusOfFRSemigroup(Dinfinity);
[ <2|identity ...>, <2|b>, <2|a> ]
</pre></td></tr></table>
<p><a id="X8443D711796F06E4" name="X8443D711796F06E4"></a></p>
<h5>7.2-18 NucleusMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NucleusMachine</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The nucleus machine of the contracting semigroup <var class="Arg">g</var>.</p>
<p>This function returns the <em>nucleus</em> of the contracting semigroup <var class="Arg">g</var>, see <code class="func">NucleusOfFRSemigroup</code> (<a href="chap7.html#X7CA062A67C1554BB"><b>7.2-17</b></a>), in the form of a Mealy machine.</p>
<p>Since all states of the nucleus are elements of the nucleus, the transition and output function may be restricted to the nucleus, defining a Mealy machine. Finitely generated recurrent groups are generated by their nucleus machine.</p>
<p>This function returns <code class="keyw">fail</code> if no such <code class="code">n</code> exists. Usually, it loops forever without being able to decide whether <code class="code">n</code> is finite or infinite. It succeeds precisely when <code class="code">IsContracting(g)</code> succeeds.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> M := NucleusMachine(Dinfinity);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> Display(M);
| 1 2
---+-----+-----+
a | a,1 a,2
b | c,1 b,2
c | a,2 a,1
---+-----+-----+
gap> Dinfinity=SCGroup(M);
true
</pre></td></tr></table>
<p><a id="X7A874A107D4944E1" name="X7A874A107D4944E1"></a></p>
<h5>7.2-19 BranchingSubgroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BranchingSubgroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A branching subgroup of <var class="Arg">g</var>.</p>
<p>This function searches for a subgroup k of <var class="Arg">g</var>, such that k contains k x cdots x k.</p>
<p>It searches for elements in larger and larger balls in <var class="Arg">g</var>, calling <code class="func">FindBranchingSubgroup</code> (<a href="chap7.html#X78ADACCD8586D3C7"><b>7.2-20</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> K := BranchingSubgroup(GrigorchukGroup);
<self-similar group over [ 1 .. 2 ] with 9 generators>
gap> IsBranchingSubgroup(K);
true
gap> IsBranched(GrigorchukGroup);
true
gap> Index(GrigorchukGroup,K);
16
</pre></td></tr></table>
<p><a id="X78ADACCD8586D3C7" name="X78ADACCD8586D3C7"></a></p>
<h5>7.2-20 FindBranchingSubgroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FindBranchingSubgroup</code>( <var class="Arg">g, l, r</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A branching subgroup of <var class="Arg">g</var>.</p>
<p>This function searches for a subgroup k of <var class="Arg">g</var>, such that k contains k x cdots x k.</p>
<p>The second argument <var class="Arg">l</var> specifies the level at which branching must occur; i.e. asks to search for a subgroup k such that <var class="Arg">g</var> contains k^d^l where d is the size of the alphabet. If <code class="code">l=infinity</code>, the resulting k will be a regularly branched subgroup.</p>
<p>The third argument <var class="Arg">r</var> specifies the radius to explore in <var class="Arg">g</var> and all branching subgroups at levels smaller than <var class="Arg">l</var> for elements with all level-1 states trivial except one.</p>
<table class="example">
<tr><td><pre>
gap> FindBranchingSubgroup(GrigorchukGroup,1,4);
<self-similar group over [ 1 .. 2 ] with 8 generators>
gap> Index(GrigorchukGroup,last);
8
gap> FindBranchingSubgroup(GrigorchukGroup,2,4);
<self-similar group over [ 1 .. 2 ] with 6 generators>
gap> Index(GrigorchukGroup,last);
16
gap> FindBranchingSubgroup(GrigorchukGroup,3,4);
<self-similar group over [ 1 .. 2 ] with 9 generators>
gap> Index(GrigorchukGroup,last);
16
</pre></td></tr></table>
<p><a id="X832D98E47ACA099C" name="X832D98E47ACA099C"></a></p>
<h5>7.2-21 IsBranched</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsBranched</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> has a finite-index branching subgroup.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> has a finite-index subgroup k, such that k contains k x cdots x k.</p>
<table class="example">
<tr><td><pre>
<Example><![CDATA[
gap> K := BranchingSubgroup(GrigorchukGroup);
<self-similar group over [ 1 .. 2 ] with 9 generators>
gap> IsBranchingSubgroup(K);
true
gap> IsBranched(GrigorchukGroup);
true
gap> Index(GrigorchukGroup,K);
16
</pre></td></tr></table>
<p><a id="X7A905CE87B49213F" name="X7A905CE87B49213F"></a></p>
<h5>7.2-22 IsBranchingSubgroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsBranchingSubgroup</code>( <var class="Arg">k</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">k</var> is a branching subgroup.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">k</var> contains k x cdots x k.</p>
<table class="example">
<tr><td><pre>
gap> K := BranchingSubgroup(GrigorchukGroup);
<self-similar group over [ 1 .. 2 ] with 9 generators>
gap> IsBranchingSubgroup(K);
true
gap> IsBranched(GrigorchukGroup);
true
gap> Index(GrigorchukGroup,K);
16
</pre></td></tr></table>
<p><a id="X8749E0797A99F531" name="X8749E0797A99F531"></a></p>
<h5>7.2-23 TopVertexTransformations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TopVertexTransformations</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The transformations at the root under the action of <var class="Arg">g</var>.</p>
<p>This function returns the permutation group, or the transformation group/semigroup/monoid, of all activities of all elements under the root vertex of the tree on which <var class="Arg">g</var> acts.</p>
<p>It is a synonym for <code class="code">PermGroup(g,1)</code> or <code class="code">TransMonoid(g,1)</code> or <code class="code">TransSemigroup(g,1)</code>.</p>
<table class="example">
<tr><td><pre>
gap> TopVertexTransformations(GrigorchukGroup);
Group([ (), (1,2) ])
gap> IsTransitive(last,AlphabetOfFRSemigroup(GrigorchukGroup));
true
gap> TopVertexTransformations(FullSCMonoid([1..3]));
<monoid with 3 generators>
gap> Size(last);
27
</pre></td></tr></table>
<p><a id="X7C56C90086070A2E" name="X7C56C90086070A2E"></a></p>
<h5>7.2-24 VertexTransformations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VertexTransformations</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The transformations at all vertices under the action of <var class="Arg">g</var>.</p>
<p>This function returns the permutation group, or the transformation group/monoid/semigroup, of all activities of all elements under all vertices of the tree on which <var class="Arg">g</var> acts.</p>
<p>This is the smallest group/monoid/semigroup <code class="code">P</code> such that <var class="Arg">g</var> is a subset of <code class="code">FullSCGroup(AlphabetOfFRSemigroup(g),P)</code> or <code class="code">FullSCMonoid(AlphabetOfFRSemigroup(g),P)</code> or <code class="code">FullSCSemigroup(AlphabetOfFRSemigroup(g),P)</code>.</p>
<table class="example">
<tr><td><pre>
gap> VertexTransformations(GuptaSidkiGroup);
Group([ (), (1,2,3), (1,3,2) ])
gap> TopVertexTransformations(Group(GuptaSidkiGroup.2));
Group(())
gap> VertexTransformations(Group(GuptaSidkiGroup.2));
Group([ (), (1,2,3), (1,3,2) ])
</pre></td></tr></table>
<p><a id="X7DF2D9838625CDED" name="X7DF2D9838625CDED"></a></p>
<h5>7.2-25 VirtualEndomorphism</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VirtualEndomorphism</code>( <var class="Arg">g, v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The virtual endomorphism at vertex <var class="Arg">v</var>.</p>
<p>This function returns the homomorphism from <code class="code">Stabilizer(g,v)</code> to <var class="Arg">g</var>, defined by computing the state at <var class="Arg">v</var>. It is loosely speaking an inverse of <code class="func">FRGroupByVirtualEndomorphism</code> (<a href="chap7.html#X7BB8DDEA83946C73"><b>7.1-8</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> A := SCGroup(MealyMachine([[2,1],[2,2]],[(1,2),()]));
<self-similar group over [ 1 .. 2 ] with 1 generator>
gap> f := VirtualEndomorphism(A,1);
MappingByFunction( <self-similar group over [ 1 .. 2 ] with
1 generator>, <self-similar group over [ 1 .. 2 ] with
1 generator>, function( g ) ... end )
gap> ((A.1)^2)^f=A.1;
true
gap> B := FRGroupByVirtualEndomorphism(f);
<self-similar group over [ 1 .. 2 ] with 1 generator>
gap> A=B;
true
</pre></td></tr></table>
<p><a id="X7C81CB1C7F0D7A90" name="X7C81CB1C7F0D7A90"></a></p>
<h5>7.2-26 EpimorphismFromFpGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> EpimorphismFromFpGroup</code>( <var class="Arg">g, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An epimorphism from a finitely presented group to <var class="Arg">g</var>.</p>
<p>For some examples of self-similar groups, a recursive presentation of the group is coded into <strong class="pkg">FR</strong>, and an approximate presentation is returned by this command, together with a map onto the group <var class="Arg">g</var>. The argument <var class="Arg">l</var> roughly means the number of iterates of an endomorphism were applied to a finite set of relators. An isomorphic group would be obtained by setting <code class="code">l=infinity</code>; for that purpose, see <code class="func">IsomorphismSubgroupFpGroup</code> (<a href="chap7.html#X8740656382656D63"><b>7.2-27</b></a>).</p>
<p>Preimages can be computed, with <code class="code">PreImagesRepresentative</code>. They are usually reasonably short words, though by no means guaranteed to be of minimal length.</p>
<p>Currently this command is implemented through an ad hoc method for <code class="func">BinaryKneadingGroup</code> (<a href="chap10.html#X813F53C57F41F5F5"><b>10.1-2</b></a>), <code class="func">GrigorchukGroup</code> (<a href="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>) and <code class="func">GrigorchukOverGroup</code> (<a href="chap10.html#X800640597E9C707D"><b>10.1-10</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> f := EpimorphismFromFpGroup(GrigorchukGroup,1);
MappingByFunction( <fp group on the generators
[ a, b, c, d ]>, GrigorchukGroup, function( w ) ... end )
4 gap> RelatorsOfFpGroup(Source(f));
[ a^2, b^2, c^2, d^2, b*c*d, a*d*a*d*a*d*a*d, a^-1*c*a*c*a^-1*c*a*c*a^-1*c*a*c*a^
-1*c*a*c, a^-1*c^-1*a*b*a^-1*c*a*b*a^-1*c^-1*a*b*a^-1*c*a*b*a^-1*c^-1*a*b*a^-1*
c*a*b*a^-1*c^-1*a*b*a^-1*c*a*b, a*d*a*c*a*c*a*d*a*c*a*c*a*d*a*c*a*c*a*d*a*c*a*c,
a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^
-1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b ]
gap> PreImagesRepresentative(f,Comm(GrigorchukGroup.1,GrigorchukGroup.2));
a*c*a*d*a*d*a*c
gap> Source(f).4^f=GrigorchukGroup.4;
true
</pre></td></tr></table>
<p><a id="X8740656382656D63" name="X8740656382656D63"></a></p>
<h5>7.2-27 IsomorphismSubgroupFpGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsomorphismSubgroupFpGroup</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">> AsSubgroupFpGroup</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">> IsomorphismLpGroup</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">> AsLpGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An isomorphism to a subgroup of a finitely presented group, or an L-presented group.</p>
<p>For some examples of self-similar groups, a recursive presentation of the group is coded into <strong class="pkg">FR</strong>, and is returned by this command. The group <var class="Arg">g</var> itself sits as a subgroup of a finitely presented group. To obtain a finitely presented group approximating <var class="Arg">g</var>, see <code class="func">EpimorphismFromFpGroup</code> (<a href="chap7.html#X7C81CB1C7F0D7A90"><b>7.2-26</b></a>). PreImages can also be computed; it is usually better to use <code class="code">PreImageElm</code>, since the word problem may not be solvable by <strong class="pkg">GAP</strong> in the f.p. group.</p>
<p>Currently this command is implemented through an ad hoc method for <code class="func">BinaryKneadingGroup</code> (<a href="chap10.html#X813F53C57F41F5F5"><b>10.1-2</b></a>), <code class="func">GrigorchukGroup</code> (<a href="chap10.html#X85BAE48780E665A4"><b>10.1-9</b></a>), <code class="func">GrigorchukOverGroup</code> (<a href="chap10.html#X800640597E9C707D"><b>10.1-10</b></a>), generalized <code class="func">GuptaSidkiGroups</code> (<a href="chap10.html#X82D3CB6A7C189C78"><b>10.1-17</b></a>) and generalized <code class="func">FabrykowskiGuptaGroups</code> (<a href="chap10.html#X878D1C7080EA9797"><b>10.1-20</b></a>).</p>
<p>The second form returns an isomorphism to an L-presented group (see <a href="chapBib.html#biBMR2009317">[Bar03b]</a> and <a href="chapBib.html#biBeick-hartung">[EH07]</a>. It requires the package <strong class="pkg">NQL</strong>.</p>
<table class="example">
<tr><td><pre>
gap> f := IsomorphismSubgroupFpGroup(BasilicaGroup);
MappingByFunction( BasilicaGroup, Group([ a^-1, a*t^-1*a^-1*t*a^-1
]), function( g ) ... end, function( w ) ... end )
gap> Range(f);
Group([ a^-1, a*t^-1*a^-1*t*a^-1 ])
gap> c := Comm(BasilicaGroup.1,BasilicaGroup.2);
<Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
gap> c^f;
t^-2*a*t^-1*a*t*a^-2*t*a*t^-2*a*t^-1*a*t*a^-1*t*a*t^-1*a*t^-2*
a^-1*t*a*t^-1*a*t^-1*a^-1*t*a^-1*t^5*a*t^-1*a^-1*t*a^-1
gap> PreImageElm(f,last);
<Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
gap> last=c;
true
</pre></td></tr></table>
<p><a id="X7E8485A081EBB3AA" name="X7E8485A081EBB3AA"></a></p>
<h4>7.3 <span class="Heading">Properties for infinite groups</span></h4>
<p><a id="X840ED7D279ECAB7F" name="X840ED7D279ECAB7F"></a></p>
<h5>7.3-1 IsTorsionGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsTorsionGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is a torsion group.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is a torsion group, i.e. if every element in <var class="Arg">g</var> has finite order; and <code class="keyw">false</code> if <var class="Arg">g</var> contains an element of infinite order.</p>
<p>This method is quite rudimentary, and is not guaranteed to terminate. At the minimum, <var class="Arg">g</var> should be a group in which <code class="code">Order()</code> succeeds in computing element orders; e.g. a bounded group in Mealy machine format.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> IsTorsionGroup(Dinfinity);
false
gap> IsTorsionGroup(GrigorchukGroup); IsTorsionGroup(GuptaSidkiGroup);
true
true
gap> IsTorsionGroup(FabrykowskiGuptaGroup);
false
</pre></td></tr></table>
<p><a id="X7914F2D68077F503" name="X7914F2D68077F503"></a></p>
<h5>7.3-2 IsTorsionFreeGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsTorsionFreeGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is a torsion-free group.</p>
<p>This function returns <code class="keyw">true</code> if <var class="Arg">g</var> is a torsion-free group, i.e. if no element in <var class="Arg">g</var> has finite order; and <code class="keyw">false</code> if <var class="Arg">g</var> contains an element of finite order.</p>
<p>This method is quite rudimentary, and is not guaranteed to terminate. At the minimum, <var class="Arg">g</var> should be a group in which <code class="code">Order()</code> succeeds in computing element orders; e.g. a bounded group in Mealy machine format.</p>
<table class="example">
<tr><td><pre>
gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> IsTorsionFreeGroup(Dinfinity);
false
gap> IsTorsionFreeGroup(BasilicaGroup);
true
</pre></td></tr></table>
<p><a id="X87E93FFC820ED40E" name="X87E93FFC820ED40E"></a></p>
<h5>7.3-3 IsAmenableGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsAmenableGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> is an amenable group.</p>
<p>Amenable groups, introduced by von Neumann <a href="chapBib.html#biBvneumann">[vN29]</a>, are those groups that admit a finitely additive, translation-invariant measure.</p>
<table class="example">
<tr><td><pre>
gap> IsAmenableGroup(FreeGroup(2));
false
gap> IsAmenableGroup(BasilicaGroup);
true
</pre></td></tr></table>
<p><a id="X873C0A7C8422C0C9" name="X873C0A7C8422C0C9"></a></p>
<h5>7.3-4 IsVirtuallySimpleGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsVirtuallySimpleGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">g</var> admits a finite-index simple subgroup.</p>
<table class="example">
<tr><td><pre>
true
</pre></td></tr></table>
<p><a id="X79A3A0CF82B6F089" name="X79A3A0CF82B6F089"></a></p>
<h5>7.3-5 IsResiduallyFinite</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsResiduallyFinite</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">obj</var> is residually finite.</p>
<p>A object is <em>residually finite</em> if it can be approximated arbitrarily well by finite quotients; i.e. if for every g<> hin X there exists a finite quotient pi:X-> Q such that g^pi<> h^pi.</p>
<table class="example">
<tr><td><pre>
gap> IsResiduallyFinite(FreeGroup(2));
true
gap> IsResiduallyFinite(BasilicaGroup);
true
</pre></td></tr></table>
<p><a id="X86E1182E7EEFAADB" name="X86E1182E7EEFAADB"></a></p>
<h5>7.3-6 IsSQUniversal</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsSQUniversal</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">obj</var> is SQ-universal.</p>
<p>An object <var class="Arg">obj</var> is <em>SQ-universal</em> if every countable object of the same category as <var class="Arg">obj</var> is a subobject of a quotient of <var class="Arg">obj</var>.</p>
<table class="example">
<tr><td><pre>
gap> IsSQUniversal(FreeGroup(2));
true
</pre></td></tr></table>
<p><a id="X7FDAEAFF78A5E7D2" name="X7FDAEAFF78A5E7D2"></a></p>
<h5>7.3-7 IsJustInfinite</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsJustInfinite</code>( <var class="Arg">obj</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">obj</var> is just-infinite.</p>
<p>An object <var class="Arg">obj</var> is <em>just-infinite</em> if <var class="Arg">obj</var> is infinite, but every quotient of <var class="Arg">obj</var> is finite.</p>
<table class="example">
<tr><td><pre>
gap> IsJustInfinite(FreeGroup(2));
false
gap> IsJustInfinite(FreeGroup(1));
true
gap> IsJustInfinite(GrigorchukGroup); time
true
8284
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap6.html">Previous Chapter</a> <a href="chap8.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
>
1166
