<?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 2: FR package</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="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X7ADCE68284FB4ACF" name="X7ADCE68284FB4ACF"></a></p>
<div class="ChapSects"><a href="chap2.html#X7ADCE68284FB4ACF">2 <span class="Heading">FR package</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X80C332C686212786">2.1 <span class="Heading">A brief mathematical introduction</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X78DF4DE18260BD80">2.2 <span class="Heading">An example session</span></a>
</div>
</div>
<h3>2 <span class="Heading">FR package</span></h3>
<p><a id="X80C332C686212786" name="X80C332C686212786"></a></p>
<h4>2.1 <span class="Heading">A brief mathematical introduction</span></h4>
<p>This chapter assumes that you have no familiarity with groups generated by automata. If you do, and wish to see their usage within <strong class="pkg">GAP</strong> through a sample session, please skip to Section <a href="chap2.html#X78DF4DE18260BD80"><b>2.2</b></a>. For a more thourough introduction on self-similar groups see <a href="chapBib.html#biBMR2091700">[BGN03]</a> or <a href="chapBib.html#biBMR2035113">[BGŠ03]</a>.</p>
<p>We shall here be interested in groups G defined by their action on a regular rooted tree. Let X be a finite set; and let X^* denote the set of words (free monoid) over X. Then X^* naturally has the structure of a regular rooted tree: the root is the empty word, and vertex v in X^* is connected to vertex vx for all choices of x in X. Each vertex except the root therefore has #X+1 neighbours.</p>
<p>Let W denote the automorphism group of the graph X^*. Given a in W, we may restrict its action to X subset X^*, and obtain a permutation pi_a on X, called the <em>activity</em> of a. We may also obtain, for all xin X, a tree automorphism a_x in W, called the <em>state of a at x</em>, by the formula</p>
<p class="pcenter">(v){a_x} = w \quad\textrm{if}\quad (xv)a = x^{\pi_a}w.</p>
<p>The data (a_x,pi_a) determine uniquely the automorphism a, and any choice of a_x and pi_a defines a tree isometry. We therefore have a group isomorphism</p>
<p class="pcenter">\phi: W \to W\wr \mathop{Sym}(X),</p>
<p>called the <em>Wreath recursion</em>. The image of phi is the permutational wreath product W^X rtimes Sym(X).</p>
<p>The state a_x should be interpreted as the restriction of the action of a on the subtree xX^*; the automorphism a is defined by acting first on each of the subtrees of the form xX^* by its respective state, and then permuting these subtrees according to pi_a. The wreath recursion can be iterated on the states of a, to define states a_v for any v in X^*.</p>
<p>The automorphism a in W may be represented by a graph, as follows. There is one vertex for each state a_v of a, labeled pi_a_v; and for each x in X there is one edge from state a_v to state a_vx, labeled x. This graph is nothing but a quotient of the regular rooted tree X^*, where vertices v and w are identified if a_v=a_w. Again, this graph, with a choice of initial vertex, determines uniquely the automorphism a. It is called the <em>Mealy machine</em> associated with a.</p>
<p>Of particular interest are <em>finite-state automorphisms</em>: these are automorphisms whose Mealy machine has finitely many states. The product and inverse of finite-state automorphisms is again finite-state.</p>
<p>A subgroup G le W is <em>self-similar</em> if G^phi subset GwrSym(X). This is equivalent to asking, for every a in G, that all of its states a_x also belong to G.</p>
<p>The following important properties have also been considered. A subgroup G le W is <em>level-transitive</em> if its action is transitive on all the G-subsets X^n. It is <em>weakly branched</em> if it is level-transitive, and for every vin X^* there is a non-trivial a_vin G that fixes X^* \ vX^*. It is <em>branched</em> if furthermore for each n in N the group generated by all such a_v for all v of length n has finite index in G.</p>
<p>A self-similar finitely generated group G le is <em>contracting</em> if there are constants K,n in N and lambda<1 such that |a_v|lelambda|a|+K for all ain G and vin X^n; here |a| denotes the minimal number of generators needed to express a. It then follows that there exists a finite set Nsubset G such that for all ain G, all but finitely many of the states of a belong to N. The minimal such N is called the <em>nucleus</em> of G. Since the states of elements of the nucleus are again in the nucleus, we see that the nucleus is naturally a Mealy machine. By considering all elements of W obtained from this Mealy machine by choosing all possible initial states, we obtain a generating set for G made of all states of a single machine; this is the <em>group generated</em> by the machine.</p>
<p>In this package, we are mainly interested in self-similar groups of finite-state automorphisms. The reason is historical: Aleshin <a href="chapBib.html#biBMR713968">[Ale83]</a>, and later Grigorchuk <a href="chapBib.html#biBMR565099">[Gri80]</a> and Gupta and Sidki <a href="chapBib.html#biBMR696534">[GS83]</a> constructed peculiar examples of groups using self-similar finite-state automorphisms. All these groups can be defined by drawing a small machine (at most five vertices) and considering the group that they generate.</p>
<p>We assumed for simplicity that the elements a were invertible. Actually, in the definition of Mealy machines it makes sense to accept arbitrary maps, and not necessarily bijections of X as a label at each vertex. One may in this way define peculiar semigroups.</p>
<p><a id="X78DF4DE18260BD80" name="X78DF4DE18260BD80"></a></p>
<h4>2.2 <span class="Heading">An example session</span></h4>
<p>This is a brief introduction describing some of the simpler features of the <strong class="pkg">FR</strong> package. It assumes you have some familiarity with the theory of groups defined by automata; if not, a brief mathematical introduction may be found in Section <a href="chap2.html#X80C332C686212786"><b>2.1</b></a>. We show here and comment a typical use of the package.</p>
<p>The package is installed by unpacking the archive in the <code class="file">pkg/</code> directory of your <strong class="pkg">GAP</strong> installation. It can also be placed in a local directory, which must be added to the load-path by invoking <code class="code">gap</code> with the <code class="code">-l</code> option.</p>
<table class="example">
<tr><td><pre>
gap> LoadPackage("fr");
----------------------------------------------------------------
Loading FR 0.857142p5 (Functionally recursive and automata groups)
by Laurent Bartholdi (http://www.uni-math.gwdg.de/laurent)
----------------------------------------------------------------
true
</pre></td></tr></table>
<p>Many FR groups are predefined by <strong class="pkg">FR</strong>, see Chapter <a href="chap10.html#X7A489A5D79DA9E5C"><b>10</b></a>. We consider here the <em>Basilica group</em>, considered in <a href="chapBib.html#biBMR1902367">[GŻ02a]</a> and <a href="chapBib.html#biBMR2176547">[BV05]</a>.</p>
<p>We may start by defining a group: it has two generators a and b, satisfying the specified recursions.</p>
<table class="example">
<tr><td><pre>
gap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>":IsFRElement);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(B);
#I Assigned the global variables [ a, b ]
</pre></td></tr></table>
<p>We have just created the group B=< a,b>.</p>
<p>Note that this group is predefined as <code class="code">BasilicaGroup</code>. We now compute the decompositions of the generators:</p>
<table class="example">
<tr><td><pre>
gap> DecompositionOfFRElement(a); DecompositionOfFRElement(b);
[ [ <2|identity ...>, <2|b> ], (1,2) ]
[ [ <2|identity ...>, <2|a> ], () ]
</pre></td></tr></table>
<p>Elements are described as words in the generators; they are printed as <code class="code"><2|a></code>, where the 2 reminds of the degree of the tree on which a acts.</p>
<p>The optional argument <code class="func">IsFRElement</code> (<a href="chap11.html#X7966F9B982B1DFE1"><b>11.2-11</b></a>) tells <strong class="pkg">FR</strong> to store elements in this way. This representation is always possible, but it is usually inefficient for calculations. The argument <code class="func">IsMealyElement</code> (<a href="chap11.html#X7C86614187606A4C"><b>11.2-4</b></a>) forces <strong class="pkg">FR</strong> to use a more efficient representation, which in some cases may take an infinite time to set up. With no extra argument, <strong class="pkg">FR</strong> does what it thinks is best.</p>
<p>Elements act on sequences over {1,2}. The action is computed in the standard manner:</p>
<table class="example">
<tr><td><pre>
gap> 1^a; [1]^a; [1,1]^a;
2
[ 2 ]
[ 2, 1 ]
</pre></td></tr></table>
<p>Periodic sequences are also implemented in <strong class="pkg">FR</strong>; they are constructed by giving the period and preperiod. The period is printed by preceding it with a "/":</p>
<table class="example">
<tr><td><pre>
gap> v := PeriodicList([1],[2]);
[ 1, / 2 ]
gap> v^a; v^(a^2);
[/ 2 ]
[/ 1, 2 ]
gap> last{[1..10]};
[ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ]
</pre></td></tr></table>
<p>Most computations are much more efficient if B's elements are converted to <em>Mealy representation</em>,</p>
<table class="example">
<tr><td><pre>
gap> Bm := Image(IsomorphismMealyGroup(B));
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> a := Bm.1; b := Bm.2;
<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
</pre></td></tr></table>
<p>This could have been done automatically by specifying <code class="code">:IsMealyElement</code> as an option in the call to <code class="code">FRGroup</code>.</p>
<p>The group B is torsion-free, and its elements are bounded automata. Although torsion-freeness is difficult to check for <strong class="pkg">FR</strong>, it can be checked on individual elements:</p>
<table class="example">
<tr><td><pre>
gap> IsBoundedFRSemigroup(Bm);
true
gap> Order(a); Order(b);
infinity
infinity
gap> g := PseudoRandom(B);; Length(InitialState(g));
4679
gap> Order(g); time;
infinity
2599
</pre></td></tr></table>
<p>The group B is weakly branched; more precisely, the derived subgroup B' contains B' x B'. To prove that, it suffices to check [a,b] x 1in B' and 1 x [a,b]in B'. These elements are constructed using <code class="func">VertexElement</code> (<a href="chap4.html#X7CE388057DAB4802"><b>4.1-5</b></a>):</p>
<table class="example">
<tr><td><pre>
gap> c := Comm(a,b);
<Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
gap> K := NormalClosure(Bm,Group(c));
<self-similar group over [ 1 .. 2 ] with 3 generators>
gap> VertexElement(1,c) in K; VertexElement(1,c) in K;
true
true
gap> DecompositionOfFRElement(VertexElement(1,c)=[[c,One(Bm)],()];
true
gap> VertexElement(2,c)=Comm(b,a^2);
true
</pre></td></tr></table>
<p>Note that we had to guess the form of the element <code class="code">VertexElement(2,c)</code> above. This could have been found out by <strong class="pkg">GAP</strong> using <code class="func">ShortGroupWordInSet</code> (<a href="chap12.html#X7B9942AA84B0753E"><b>12.1-13</b></a>).</p>
<p>We may also check the relations [b^p,(b^p)^a^p]=1 and [a^2p,(a^2p)^b^p] for p any power of 2:</p>
<table class="example">
<tr><td><pre>
gap> ForAll([0..10],i->IsOne(Comm(b^(2^i),(b^(2^i))^((a^(2^i)))))); time;
true
1361
</pre></td></tr></table>
<p>Since the group B is bounded, it is contracting. We compute its nucleus:</p>
<table class="example">
<tr><td><pre>
gap> NucleusOfFRSemigroup(B);
[ <2|identity ...>, <2|b>, <2|b^-1>, <2|a>, <2|a^-1>, <2|b^-1*a>, <2|a^-1*b> ]
</pre></td></tr></table>
<p>We then compute the Mealy machine with stateset this nucleus, and draw it graphically (this requires the external programs <strong class="pkg">graphviz</strong> and <strong class="pkg">imagemagick</strong>):</p>
<table class="example">
<tr><td><pre>
gap> N := NucleusMachine(B);
<Mealy machine on alphabet [ 1, 2 ] with 7 states>
gap> Draw(N);
</pre></td></tr></table>
<p>We may also draw powers of the dual automaton: these are approximations to the Schreier graph of B. However, we also construct a smaller Mealy machine with states only a and b, which give better images:</p>
<table class="example">
<tr><td><pre>
gap> Draw(DualMachine(N)^3);
gap> M := AsMealyMachine(FRMachine(a))[1];
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> Draw(DualMachine(M)^4);
</pre></td></tr></table>
<p>These Schreier graphs are orbits of the group; they can be displayed as follows:</p>
<table class="example">
<tr><td><pre>
gap> WordGrowth(B:point:=[1,1,1,1],draw);
</pre></td></tr></table>
<p>More properties of B can be checked, or experimented with, on its finite quotients obtained by truncating the tree on which B acts at a given length. <code class="code">PermGroup(B,n)</code> constructs a permutation group which is the natural quotient of B acting on 2^n points:</p>
<table class="example">
<tr><td><pre>
gap> G := PermGroup(B,7);
<permutation group with 2 generators>
gap> Size(G); LogInt(last,2);
309485009821345068724781056
88
</pre></td></tr></table>
<p>We may "guess" the structure of the Lie algebra of B by examining the ranks of the successive quotients along its Jennings series:</p>
<table class="example">
<tr><td><pre>
gap> J := JenningsLieAlgebra(G); time;
<Lie algebra of dimension 88 over GF(2)>
18035
gap> List([1..15],i->Dimension(Grading(J).hom_components(i)));
[ 2, 3, 1, 4, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 ]
</pre></td></tr></table>
<p>The "4" in position 8 of that list should really be a "5"; computations on finite quotients of B usually give lower bounds for invariants of B. In that case, we guess that the ranks behave like a "ruler" function, i.e. that the rank of the homogeneous component of degree i is 2+nu_2(i) if i is a power of 2 and is 1+nu_2(i) otherwise; here nu_2(i) is the number of times 2 divides i.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.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
>
1156
