Quelle chap2_mj.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/fr/doc/chap2_mj.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap2" onload="jscontent()">

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

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

<a href="chap2.html">[MathJax off]</a>
<a id="X7ADCE68284FB4ACF" name="X7ADCE68284FB4ACF"></a>
<div class="ChapSects"><a href="chap2_mj.html#X7ADCE68284FB4ACF">2 FR package</a>
<div class="ContSect"> <a href="chap2_mj.html#X80C332C686212786">2.1 A brief mathematical introduction</a>

</div>
<div class="ContSect"> <a href="chap2_mj.html#X78DF4DE18260BD80">2.2 An example session</a>

</div>
</div>

<h3>2 FR package</h3>

<a id="X80C332C686212786" name="X80C332C686212786"></a>

<h4>2.1 A brief mathematical introduction</h4>

This chapter assumes that you have no familiarity with groups generated by automata. If you do, and wish to see their usage within GAP through a sample session, please skip to Section <a href="chap2_mj.html#X78DF4DE18260BD80">2.2</a>. For a more thourough introduction on self-similar groups see <a href="chapBib_mj.html#biBMR2091700">[BGN03]</a> or <a href="chapBib_mj.html#biBMR2035113">[BG{Š}03]</a>.

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.

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 activity of \(a\). We may also obtain, for all \(x\in X\), a tree automorphism \(a_x \in W\), called the state of \(a\) at \(x\), by the formula

\[(v){a_x} = w \quad\textrm{if}\quad (xv)a = x^{\pi_a}w.\]

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

\[\phi: W \to W\wr \mathop{Sym}(X),\]

called the Wreath recursion. The image of \(\phi\) is the permutational wreath product \(W^X \rtimes \mathop{Sym}(X)\).

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^*\).

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\).

This graph may be conveniently encoded in what is called a Moore machine: it consists of a set \(Q\), the vertex set of the graph; an alphabet, \(X\); a `transition' function \(\phi:Q\times X\to Q\), where \(\phi(q,x)\) is the endpoint of the edge starting at \(q\) and labeled \(x\); and a labeling \(\pi\) of \(X\) by the symmetric group on \(X\). We will use the equivalent Mealy machines, given by a `transition' function \(\phi:Q\times X\to X\times Q\), encoding both \(\phi\) and \(\pi\) together.

Of particular interest are finite-state automorphisms: these are automorphisms whose Mealy machine has finitely many states. The product and inverse of finite-state automorphisms is again finite-state.

A subgroup \(G \le W\) is self-similar if \(G^\phi \subset G\wr\mathop{Sym}(X)\). This is equivalent to asking, for every \(a \in G\), that all of its states \(a_x\) also belong to \(G\).

The following important properties have also been considered. A subgroup \(G \le W\) is level-transitive if its action is transitive on all the \(G\)-subsets \(X^n\). It is weakly branched if it is level-transitive, and for every \(v\in X^*\) there is a non-trivial \(a_v\in G\) that fixes \(X^* \setminus vX^*\). It is branched if furthermore for each \(n \in \mathbb N\) the group generated by all such \(a_v\) for all \(v\) of length \(n\) has finite index in \(G\).

A self-similar finitely generated group \(G \le W\) is contracting if there are constants \(K,n \in \mathbb N\) and \(\lambda<1\) such that \(|a_v|\le\lambda|a|+K\) for all \(a\in G\) and \(v\in X^n\); here \(|a|\) denotes the minimal number of generators needed to express \(a\). It then follows that there exists a finite set \(N\subset G\) such that for all \(a\in G\), all but finitely many of the states of \(a\) belong to \(N\). The minimal such \(N\) is called the nucleus 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 group generated by the machine.

In this package, we are mainly interested in self-similar groups of finite-state automorphisms. The reason is historical: Aleshin <a href="chapBib_mj.html#biBMR713968">[Ale83]</a>, and later Grigorchuk <a href="chapBib_mj.html#biBMR565099">[Gri80]</a> and Gupta and Sidki <a href="chapBib_mj.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.

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.

<a id="X78DF4DE18260BD80" name="X78DF4DE18260BD80"></a>

<h4>2.2 An example session</h4>

This is a brief introduction describing some of the simpler features of the FR 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_mj.html#X80C332C686212786">2.1</a>. We show here and comment a typical use of the package.

The package is installed by unpacking the archive in the <code class="file">pkg/</code> directory of your GAP 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.

<div class="example"><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></div>

Many FR groups are predefined by FR, see Chapter <a href="chap9_mj.html#X7A489A5D79DA9E5C">9</a>. We consider here the Basilica group, considered in <a href="chapBib_mj.html#biBMR1902367">[G{\.Z}02]</a> and <a href="chapBib_mj.html#biBMR2176547">[BV05]</a>.

We may start by defining a group: it has two generators \(a\) and \(b\), satisfying the specified recursions.

<div class="example"><pre>
gap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>",IsFRMealyElement);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(B);
#I Assigned the global variables [ a, b ]
</pre></div>

We have just created the group \(B=\langle a,b\rangle\).

Note that this group is predefined as <code class="code">BasilicaGroup</code>. We now compute the decompositions of the generators:

<div class="example"><pre>
gap> DecompositionOfFRElement(a); DecompositionOfFRElement(b);
[ [ <2|identity ...>, <2|b> ], [ 2, 1 ] ]
[ [ <2|identity ...>, <2|a> ], [ 1, 2 ] ]
</pre></div>

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.

The optional argument <code class="func">IsFRElement</code> (<a href="chap10_mj.html#X7966F9B982B1DFE1">10.2-11</a>) tells FR 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="chap10_mj.html#X7C86614187606A4C">10.2-4</a>) forces FR to use a more efficient representation, which in some cases may take an infinite time to set up. With no extra argument, FR does what it thinks is best. The advantages of both representations are sometimes obtained by the argument <code class="func">IsFRMealyElement</code> (<a href="chap10_mj.html#X847A4BBE82C736B6">10.2-12</a>), which stores both representations.

Elements act on sequences over \(\{1,2\}\). The action is computed in the standard manner:

<div class="example"><pre>
gap> 1^a; [1]^a; [1,1]^a;
2
[ 2 ]
[ 2, 1 ]
</pre></div>

Periodic sequences are also implemented in FR; they are constructed by giving the period and preperiod. The period is printed by preceding it with a "/":

<div class="example"><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></div>

Most computations are much more efficient if \(B\)'s elements are converted to Mealy representation,

<div class="example"><pre>
gap> Bm := Image(IsomorphismMealyGroup(B));
<recursive group over [ 1 .. 2 ] with 2 generators>
gap> a := Bm.1; b := Bm.2;
<Mealy element on alphabet [ 1, 2 ] with 3 states>
<Mealy element on alphabet [ 1, 2 ] with 3 states>
</pre></div>

This could have been done automatically by specifying <code class="code">IsMealyElement</code> as last argument in the call to <code class="code">FRGroup</code>.

The group \(B\) is torsion-free, and its elements are bounded automata. Although torsion-freeness is difficult to check for FR, it can be checked on individual elements:

<div class="example"><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></div>

The group \(B\) is weakly branched; more precisely, the derived subgroup \(B'\) contains \(B' \times B'\). To prove that, it suffices to check \([a,b] \times 1\in B'\) and \(1 \times [a,b]\in B'\). These elements are constructed using VertexElement (4.1-5):

<div class="example"><pre>
gap> c := Comm(a,b);
<Mealy element on alphabet [ 1, 2 ] with 9 states>
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)],[1,2]];
true
gap> VertexElement(2,c)=Comm(b,a^2);
true
</pre></div>

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 GAP using <code class="func">ShortGroupWordInSet</code> (<a href="chap11_mj.html#X7B9942AA84B0753E">11.4-2</a>).

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\):

<div class="example"><pre>
gap> ForAll([0..10],i->IsOne(Comm(b^(2^i),(b^(2^i))^((a^(2^i)))))); time;
true
1361
</pre></div>

Since the group \(B\) is bounded, it is contracting. We compute its nucleus:

<div class="example"><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></div>

We then compute the Mealy machine with stateset this nucleus, and draw it graphically (this requires the external programs graphviz and imagemagick):

<div class="example"><pre>
gap> N := NucleusMachine(B);
<Mealy machine on alphabet [ 1, 2 ] with 7 states>
gap> Draw(N);
</pre></div>

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:

<div class="example"><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></div>

These Schreier graphs are orbits of the group; they can be displayed as follows:

<div class="example"><pre>
gap> WordGrowth(B:point:=[1,1,1,1],draw);
</pre></div>

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:

<div class="example"><pre>
gap> G := PermGroup(B,7);
<permutation group with 2 generators>
gap> Size(G); LogInt(last,2);
309485009821345068724781056
88
</pre></div>

We may "guess" the structure of the Lie algebra of \(B\) by examining the ranks of the successive quotients along its Jennings series:

<div class="example"><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></div>

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\).

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

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

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

quality100%

¤ Dauer der Verarbeitung: 0.22 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.