<?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 9: Iterated monodromy groups</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="chap8.html">Previous Chapter</a> <a href="chap10.html">Next Chapter</a> </div>
<p><a id="X798DE1297EC58F59" name="X798DE1297EC58F59"></a></p>
<div class="ChapSects"><a href="chap9.html#X798DE1297EC58F59">9 <span class="Heading">Iterated monodromy groups</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap9.html#X7CA23C95828C2A3E">9.1 <span class="Heading">Creators and operations for IMG FR machines</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X79C411167D97F0F9">9.1-1 IMGFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7BCE03F2827DAA0A">9.1-2 IMGRelator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7AB029AE8590964E">9.1-3 Mating</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7D71EBDA7D7C3474">9.1-4 PolynomialFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X82F0B23486F2E3AC">9.1-5 DBRationalIMGGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7A32EC907B726CF7">9.1-6 ValueRational</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X789111E786DF284D">9.1-7 CriticalValuesQuadraticRational</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7EA768B886A5C7F2">9.1-8 CanonicalQuadraticRational</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X8365719F7E03B7C3">9.1-9 PostCriticalMachine</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap9.html#X7C73C74D87428A33">9.2 <span class="Heading">Spiders</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7CC0BBAD807D1A45">9.2-1 RationalFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap9.html#X7ED04E0884385D54">9.2-2 IMGFRMachine</a></span>
</div>
</div>
<h3>9 <span class="Heading">Iterated monodromy groups</span></h3>
<p>Iterated monodromy machines are a special class of group FR machines (see Section <a href="chap3.html#X7D65CA8B876E514C"><b>3</b></a>) with attribute <code class="func">IMGRelator</code> (<a href="chap9.html#X7BCE03F2827DAA0A"><b>9.1-2</b></a>). This attribute records a cyclic ordering of the generators of the machine whose product is trivial.</p>
<p>The interpretation is the following: the machine encodes a <em>Thurston map</em>, i.e. a post-critically finite topological branched self-covering of the sphere S^2. Generators of the machine correspond to loops in the fundamental group of the sphere (punctured at post-critical points), that circle once counter-clockwise around a post-critical point. For more details on the connection between self-similar groups and Thurston maps, see <a href="chapBib.html#biBMR2162164">[Nek05]</a>.</p>
<p>IMG FR elements are a bit different from group FR elements: while we said a group FR element is trivial if and only if its action on sequences is trivial, we say that an IMG FR element g is trivial if there exists an integer N such that unfolding N times the recursion for g yields only trivial states (as elements of the underlying free group).</p>
<p><a id="X7CA23C95828C2A3E" name="X7CA23C95828C2A3E"></a></p>
<h4>9.1 <span class="Heading">Creators and operations for IMG FR machines</span></h4>
<p><a id="X79C411167D97F0F9" name="X79C411167D97F0F9"></a></p>
<h5>9.1-1 IMGFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IMGFRMachine</code>( <var class="Arg">m[, w]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An IMG FR machine.</p>
<p>This function creates a new IMG FR machine, starting from a group FR machine <var class="Arg">m</var>. If a state <var class="Arg">w</var> is specified, it is used as IMG relator; otherwise, if some ordering of the generators is trivial, it is used as a relator; in other cases, an additional generator is added to the machine in such a way that a product of generators is trivial.</p>
<p>A standard FR machine can be recovered from an IMG FR machine by <code class="func">AsGroupFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>), <code class="func">AsMonoidFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>), and <code class="func">AsSemigroupFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>).</p>
<table class="example">
<tr><td><pre>
!!!
</pre></td></tr></table>
<p><a id="X7BCE03F2827DAA0A" name="X7BCE03F2827DAA0A"></a></p>
<h5>9.1-2 IMGRelator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IMGRelator</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The relator of the IMG FR machine.</p>
<p>This attribute stores the product of generators that is trivial. In essence, it records an ordering of the generators whose product is trivial in the punctured sphere's fundamental group.</p>
<p><a id="X7AB029AE8590964E" name="X7AB029AE8590964E"></a></p>
<h5>9.1-3 Mating</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Mating</code>( <var class="Arg">m1, m2[, w1, w2]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An IMG FR machine.</p>
<p>This function mates two IMG FR machines. The arguments <var class="Arg">w1,w2</var> are IMG FR elements that represent adding elements; they may be omitted if <var class="Arg">m1,m2</var> contain pre-specified adding machines (through the attribute <code class="func">AddingElement</code> (<a href="chap10.html#X85F4FDF787173863"><b>10.1-4</b></a>)). The elements <var class="Arg">w1</var> and <var class="Arg">w2</var> must satisfy the same recursion.</p>
<p>The mating is defined as follows: one removes a disc around the adding machine in <var class="Arg">m1</var> and <var class="Arg">m2</var>; one applies complex conjugation to <var class="Arg">m2</var>; and one glues the hollowed spheres along their boundary circle.</p>
<table class="example">
<tr><td><pre>
!!!
</pre></td></tr></table>
<p><a id="X7D71EBDA7D7C3474" name="X7D71EBDA7D7C3474"></a></p>
<h5>9.1-4 PolynomialFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PolynomialFRMachine</code>( <var class="Arg">d, per, pre</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">> PolynomialIMGMachine</code>( <var class="Arg">d, per, pre</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">> PolynomialMealyMachine</code>( <var class="Arg">d, per, pre</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An IMG FR machine.</p>
<p>This function creates a group, IMG or Mealy machine that describes a topological polynomial. The polynomial is described symbolically in the language of <em>external angles</em>. For more details, see <a href="chapBib.html#biBMR762431">[DH84]</a> and <a href="chapBib.html#biBMR812271">[DH85]</a> (in the quadratic case), <a href="chapBib.html#biBMR1149891">[BFH92]</a> (in the preperiodic case), and <a href="chapBib.html#biBmath.DS/9305207">[Poi]</a> (in the general case).</p>
<p><var class="Arg">d</var> is the degree of the polynomial. <var class="Arg">per</var> and <var class="Arg">pre</var> are lists of angles or preangles. In what follows, angles are rational numbers, considered modulo 1. Each entry in <var class="Arg">per</var> or <var class="Arg">pre</var> is either a rational (interpreted as an angle), or a list of angles [a_1,dots,a_i] such that da_1=dots=da_i.</p>
<table class="example">
<tr><td><pre>
gap> PolynomialIMGMachine(2,[0],[]); # the adding machine
<FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )/[ f2*f1 ]>
gap> Display(last);
G | 1 2
----+--------+--------+
f1 | <id>,2 f1,1
f2 | f2,2 <id>,1
----+--------+--------+
Relator: f2*f1
gap> Display(PolynomialIMGMachine(2,[1/3],[])); # the Basilica
G | 1 2
----+---------+---------+
f1 | f1^-1,2 f2*f1,1
f2 | f1,1 <id>,2
f3 | f3,2 <id>,1
----+---------+---------+
Relator: f3*f2*f1
gap> Display(PolynomialIMGMachine(2,[],[1/6])); # z^2+I
G | 1 2
----+---------------+---------+
f1 | f1^-1*f2^-1,2 f2*f1,1
f2 | f1,1 f3,2
f3 | f2,1 <id>,2
f4 | f4,2 <id>,1
----+---------------+---------+
Relator: f4*f3*f2*f1
gap> PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>
gap> PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>
</pre></td></tr></table>
<p>The following construct the examples in Poirier's paper:</p>
<table class="example">
<tr><td><pre>
PoirierExamples := function(arg)
if arg=[1] then
return PolynomialIMGMachine(2,[1/7],[]);
elif arg=[2] then
return PolynomialIMGMachine(2,[],[1/2]);
elif arg=[3,1] then
return PolynomialIMGMachine(2,[],[5/12]);
elif arg=[3,2] then
return PolynomialIMGMachine(2,[],[7/12]);
elif arg=[4,1] then
return PolynomialIMGMachine(3,[[3/4,1/12],[1/4,7/12]],[]);
elif arg=[4,2] then
return PolynomialIMGMachine(3,[[7/8,5/24],[5/8,7/24]],[]);
elif arg=[4,3] then
return PolynomialIMGMachine(3,[[1/8,19/24],[3/8,17/24]],[]);
elif arg=[5] then
return PolynomialIMGMachine(3,[[3/4,1/12],[3/8,17/24]],[]);
elif arg=[6,1] then
return PolynomialIMGMachine(4,[],[[1/4,3/4],[1/16,13/16],[5/16,9/16]]);
elif arg=[6,2] then
return PolynomialIMGMachine(4,[],[[1/4,3/4],[3/16,15/16],[7/16,11/16]]);
elif arg=[7] then
return PolynomialIMGMachine(5,[[0,4/5],[1/5,2/5,3/5]],[[1/5,4/5]]);
elif arg=[9,1] then
return PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);
elif arg=[9,2] then
return PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);
fi;
end;
</pre></td></tr></table>
<p><a id="X82F0B23486F2E3AC" name="X82F0B23486F2E3AC"></a></p>
<h5>9.1-5 DBRationalIMGGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DBRationalIMGGroup</code>( <var class="Arg">sequence, or, rational, map</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>An IMG group from Dau's database.</p>
<p>This function returns the iterated monodromy group from a database of groups associated to quadratic rational maps. This database has been compiled by Dau Truong Tan <a href="chapBib.html#biBtan:database">[Tan02]</a>.</p>
<p>When called with no arguments, this command returns the database contents in raw form.</p>
<p>The argments can be a sequence; the first integer is the size of the postcritical set, the second argument is an index for the postcritical graph, and sometimes a third argument distinguishes between maps with same post-critical graph.</p>
<p>If the argument is a rational map, the command returns the IMG group of that map, assuming its <code class="func">CanonicalQuadraticRational</code> (<a href="chap9.html#X7EA768B886A5C7F2"><b>9.1-8</b></a>) form exists in the database.</p>
<table class="example">
<tr><td><pre>
gap> DBRationalIMGGroup(z^2-1);
IMG((z-1)^2)
gap> DBRationalIMGGroup(z^2+1); # not post-critically finite
fail
gap> DBRationalIMGGroup(4,1,1);
IMG((z/h+1)^2|2h^3+2h^2+2h+1=0,h~-0.64)
</pre></td></tr></table>
<p><a id="X7A32EC907B726CF7" name="X7A32EC907B726CF7"></a></p>
<h5>9.1-6 ValueRational</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ValueRational</code>( <var class="Arg">f, x</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The value of <var class="Arg">f</var> at <var class="Arg">x</var>.</p>
<p>This function is almost identical to <code class="code">Value(f,x)</code>. It accepts <code class="keyw">infinity</code> as an argument, and may return <code class="keyw">infinity</code> as a value.</p>
<table class="example">
<tr><td><pre>
gap> z := Indeterminate(Rationals,"z");;
gap> ValueRational(1/z,infinity);
0
gap> ValueRational(1/z,0);
infinity
gap> ValueRational(1/z,1/2);
2
</pre></td></tr></table>
<p><a id="X789111E786DF284D" name="X789111E786DF284D"></a></p>
<h5>9.1-7 CriticalValuesQuadraticRational</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CriticalValuesQuadraticRational</code>( <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The critical values of <var class="Arg">f</var>.</p>
<p>This function returns, as a list, the values of <var class="Arg">f</var> at places where the derivative of <var class="Arg">f</var> vanishes.</p>
<table class="example">
<tr><td><pre>
gap> z := Indeterminate(Rationals,"z");;
gap> CriticalValuesQuadraticRational(z^2);
[ 0, infinity ]
gap> CriticalValuesQuadraticRational(z^2+1);
[ 1, infinity ]
gap> CriticalValuesQuadraticRational((z^2+1)/(z^2-1));
[ -1, 1 ]
gap> CriticalValuesQuadraticRational((z^2+1)/(z^2-z-1));
[ 2/5*E(5)-2/5*E(5)^2-2/5*E(5)^3+2/5*E(5)^4, -2/5*E(5)+2/5*E(5)^2+2/5*E(5)^3-2/5*E(5)^4 ]
</pre></td></tr></table>
<p><a id="X7EA768B886A5C7F2" name="X7EA768B886A5C7F2"></a></p>
<h5>9.1-8 CanonicalQuadraticRational</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CanonicalQuadraticRational</code>( <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The canonical forms of the quadratic rational map <var class="Arg">f</var>.</p>
<p>This function puts the quadratic rational map <var class="Arg">f</var> in canonical form, that is, in form ((az+b)/(cz+d))^2, such that its critical values are <code class="keyw">0</code> and <code class="keyw">infinity</code>. Furthermore, it attempts to make <code class="code">f(infinity)=1</code>, and if this is impossible to make <code class="code">f(0)=1</code>.</p>
<p>The command returns the set of all maps with these properties.</p>
<table class="example">
<tr><td><pre>
gap> z := Indeterminate(Rationals,"z");;
gap> CanonicalQuadraticRational(z^2);
[ z^2 ]
gap> CanonicalQuadraticRational(z^2+1);
[ (z^2)/(z^2+2*z+1), z^2+2*z+1 ]
gap> CanonicalQuadraticRational((z^2+1)/(z^2-1));
[ (1/2*z^2+z+1/2)/(1/2*z^2-z+1/2), (-1/2*z^2+z-1/2)/(-1/2*z^2-z-1/2) ]
</pre></td></tr></table>
<p><a id="X8365719F7E03B7C3" name="X8365719F7E03B7C3"></a></p>
<h5>9.1-9 PostCriticalMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PostCriticalMachine</code>( <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>The Mealy machine of <var class="Arg">f</var>'s post-critical orbit.</p>
<p>This function constructs a Mealy machine <code class="code">P</code> on the alphabet <code class="code">[1]</code>, which describes the post-critical set of <var class="Arg">f</var>. It is in fact an oriented graph with constant out-degree 1. It is most conveniently passed to <code class="func">Draw</code> (<a href="chap5.html#X7DF9F3AD86602DFC"><b>5.2-1</b></a>).</p>
<p>The attribute <code class="code">Correspondence(P)</code> is the list of values associated with the stateset of <code class="code">P</code>.</p>
<table class="example">
<tr><td><pre>
gap> z := Indeterminate(Rationals,"z");;
gap> m := PostCriticalMachine(z^2);
<Mealy machine on alphabet [ 1 ] with 2 states>
gap> Display(m);
| 1
---+-----+
a | a,1
b | b,1
---+-----+
gap> Correspondence(m);
[ 0, infinity ]
gap> m := PostCriticalMachine(z^2-1);; Display(m); Correspondence(m);
| 1
---+-----+
a | c,1
b | b,1
c | a,1
---+-----+
[ -1, infinity, 0 ]
</pre></td></tr></table>
<p><a id="X7C73C74D87428A33" name="X7C73C74D87428A33"></a></p>
<h4>9.2 <span class="Heading">Spiders</span></h4>
<p><a id="X7CC0BBAD807D1A45" name="X7CC0BBAD807D1A45"></a></p>
<h5>9.2-1 RationalFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RationalFunction</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A rational function.</p>
<p>!!!</p>
<table class="example">
<tr><td><pre>
!!!
</pre></td></tr></table>
<p><a id="X7ED04E0884385D54" name="X7ED04E0884385D54"></a></p>
<h5>9.2-2 IMGFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IMGFRMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An IMG FR machine.</p>
<p>!!!</p>
<table class="example">
<tr><td><pre>
!!!
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap8.html">Previous Chapter</a> <a href="chap10.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
>
1170
