GAP (FR) - Chapter 9: Iterated monodromy groups

Iterated monodromy machines are a special class of group FR machines (see Section 3) with attribute IMGRelator (9.1-4). This attribute records a cyclic ordering of the generators of the machine whose product is trivial.

The interpretation is the following: the machine encodes a Thurston map, 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 [Nek05].

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

9.1 Creators and operations for IMG machines

9.1-1 IsIMGMachine

The categories of IMG and polynomial machines. IMG machines are group FR machines with an additional element, their attribute IMGRelator (9.1-4); see AsIMGMachine (9.1-3).

A polynomial machine is a group FR machine with a distinguished state (which must be a generator of the stateset), stored as the attribute AddingElement (10.1-6); see AsPolynomialFRMachine (9.1-9). If it is normalized, in the sense that the wreath recursion of the adding element a is [[a,1,...,1],[d,1,...,d-1]], then the basepoint is assumed to be at +∞; the element a describes a clockwise loop around infinity; the kth preimage of the basepoint is at exp(2iπ(k-1)/d)∞, for k=1,dots,d; and there is a direct connection from basepoint k to k+1 for all k=1,dots,d-1.

9.1-2 IMGMachineNC

This function creates, without checking its arguments, a new IMG machine in family fam, stateset group, with transitions and output trans,out, and IMG relator rel.

9.1-3 AsIMGMachine

This function creates a new IMG FR machine, starting from a group FR machine m. If a state w is specified, and that state defines the trivial FR element, then it is used as IMGRelator (9.1-4); if the state w is non-trivial, then a new generator f is added to m, equal to the inverse of w; and the IMG relator is chosen to be w*f. Finally, if no relator is specified, and the product (in some ordering) of the generators is trivial, then that product is used as IMG relator. In other cases, the method returns fail.

Note that IMG elements and FR elements are compared differently (see the example below); namely, an FR element is trivial precisely when it acts trivially on sequences. An IMG element is trivial precisely when a finite number of applications of free cancellation, the IMG relator, and the decomposition map, result in trivial elements of the underlying free group.

A standard FR machine can be recovered from an IMG FR machine by AsGroupFRMachine (3.3-4), AsMonoidFRMachine (3.3-4), and AsSemigroupFRMachine (3.3-4).

gap> m := UnderlyingFRMachine(BasilicaGroup);
<Mealy machine on alphabet [ 1 .. 2 ] with 3 states>
gap> g := AsGroupFRMachine(m);
<FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )>
gap> AsIMGMachine(g,Product(GeneratorsOfFRMachine(g)));
<FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2, t ] )/[ f1*f2*t ]>
gap> Display(last);
 G  |              1         2
----+-----------------+---------+
 f1 |          <id>,2      f2,1
 f2 |          <id>,1      f1,2
  t | f2^-1*f1*f2*t,2   f1^-1,1
----+-----------------+---------+
Relator: f1*f2*t
gap> g := AsGroupFRMachine(GuptaSidkiMachine);
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2 ] )>
gap> m := AsIMGMachine(g,GeneratorsOfFRMachine(g)[1]);
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, t ] )/[ f1*t ]>
gap> x := FRElement(g,2)^3; IsOne(x);
<3|identity ...>
true
gap> x := FRElement(m,2)^3; IsOne(x);
<3#f2^3>
false

9.1-4 IMGRelator

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.

9.1-5 CleanedIMGMachine

This command attempts to shorten the length of the transitions in m, and ensure (if possible) that the product along every cycle of the states of a generator is a conjugate of a generator. It returns the new machine.

9.1-6 NewSemigroupFRMachine

This command constructs a new FR or IMG machine, in a format similar to FRGroup (7.1-1); namely, the arguments are strings of the form "gen=<word-1,...,word-d>perm"; each word-i is a word in the generators; and perm is a transformation, either written in disjoint cycle or in images notation.

Except in the semigroup case, word-i is allowed to be the empty string; and the "<...>" may be skipped altogether. In the group or IMG case, each word-i may also contain inverses.

In the IMG case, an extra final argument is allowed, which is a word in the generators, and describes the IMG relation. If absent, FR will attempt to find such a relation.

The following examples construct realizable foldings of the polynomial z^3+i, following Cui's arguments.

gap> fold1 := NewIMGMachine("a=<,,b,,,B>(1,2,3)(4,5,6)","b=<,,b*a/b,,,B*A/B>",
     "A=<,,b*a,,,B*A>(3,6)","B=(1,6,5,4,3,2)");
gap> <FR machine with alphabet [ 1, 2, 3, 4, 5, 6 ] on Group( [ a, b, A, B ] )/[ a*B*A*b ]>                                
gap> fold2 := NewIMGMachine("a=<,,b,,,B>(1,2,3)(4,5,6)","b=<,,b*a/b,,,B*A/B>",
     "A=(1,6)(2,5)(3,4)","B=<B*A,,,b*a,,>(1,4)(2,6)(3,5)");;
gap> RationalFunction(fold1); RationalFunction(fold2);
...

9.1-7 AsIMGElement

The category of IMG elements, namely FR elements of an IMG machine. See AsIMGMachine (9.1-3) for details.

9.1-8 IsKneadingMachine

A kneading machine is a special kind of Mealy machine, used to describe postcritically finite complex polynomials. It is a machine such that its set of permutations is "treelike" (see [Nek05, §6.7]) and such that each non-trivial state occurs exactly once among the outputs.

Furthermore, this set of permutations is treelike if there exists an ordering of the states that their product in that order t is an adding machine; i.e. such that t's activity is a full cycle, and the product of its states along that cycle is conjugate to t. This element t represents the Carathéodory loop around infinity.

gap> M := BinaryKneadingMachine("0");
BinaryKneadingMachine("0*")
gap> Display(M);
   |  1     2
---+-----+-----+
 a | c,2   b,1
 b | a,1   c,2
 c | c,1   c,2
---+-----+-----+
gap> IsPlanarKneadingMachine(M);
true
gap> IsPlanarKneadingMachine(GrigorchukMachine);
false

9.1-9 AsPolynomialFRMachine

The first function creates a new polynomial FR machine, starting from a group or Mealy machine. A polynomial machine is one that has a distinguished adding element, AddingElement (10.1-6).

If the argument is a Mealy machine, it must be planar (see IsPlanarKneadingMachine (9.1-8)). If the argument is a group machine, its permutations must be treelike, and its outputs must be such that, up to conjugation, each non-trivial state appears exactly once as the product along all cycles of all states.

If a second argument adder is supplied, it is checked to represent an adding element, and is used as such.

The second function creates a new polynomial IMG machine, i.e. a polynomial FR machine with an extra relation among the generators. the optional second argument may be an adder (if m is an IMG machine) or a relator (if m is a polynomial FR machine). Finally, if m is a group FR machine, two arguments, an adder and a relator, may be specified.

A machine without the extra polynomial / IMG information may be recovered using AsGroupFRMachine (3.3-4).

gap> M := PolynomialIMGMachine(2,[1/7],[]);; SetName(StateSet(M),"F"); M;
<FR machine with alphabet [ 1, 2 ] and adder f4 on F/[ f4*f3*f2*f1 ]>
gap> Mi := AsIMGMachine(M);
<FR machine with alphabet [ 1, 2 ] on F/[ f4*f3*f2*f1 ]>
gap> Mp := AsPolynomialFRMachine(M);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F>
gap> Mg := AsGroupFRMachine(M);
<FR machine with alphabet [ 1, 2 ] on F>
gap>
gap> AsPolynomialIMGMachine(Mg);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F/[ f4*f3*f2*f1 ]>
gap> AsPolynomialIMGMachine(Mi);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F/[ f4*f3*f2*f1 ]>
gap> AsPolynomialIMGMachine(Mp);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F/[ f4*f3*f2*f1 ]>
gap> AsIMGMachine(Mg);
<FR machine with alphabet [ 1, 2 ] on F4/[ f1*f4*f3*f2 ]>
gap> AsPolynomialFRMachine(Mg);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F4>

9.1-10 AddingElement

This attribute stores the product of generators that is an adding machine. In essence, it records an ordering of the generators whose product corresponds to the Carathéodory loop around infinity.

The following example illustrates Wittner's shared mating of the airplane and the rabbit. In the machine m, an airplane is represented by Group(a,b,c) and a rabbit is represented by Group(x,y,z); in the machine newm, it is the other way round. The effect of CleanedIMGMachine was to remove unnecessary instances of the IMG relator from newm's recursion.

gap> f := FreeGroup("a","b","c","x","y","z");;
gap> AssignGeneratorVariables(f);
gap> m := AsIMGMachine(FRMachine(f,[[a^-1,b*a],[One(f),c],[a,One(f)],[z*y*x,
       x^-1*y^-1],[One(f),x],[One(f),y]],[(1,2),(),(),(1,2),(),()]));;
gap> Display(m);
 G |      1             2   
---+---------+-------------+
 a |  a^-1,2         b*a,1  
 b |  <id>,1           c,2  
 c |     a,1        <id>,2  
 x | z*y*x,2   x^-1*y^-1,1  
 y |  <id>,1           x,2  
 z |  <id>,1           y,2  
---+---------+-------------+
Relator: z*y*x*c*b*a
gap> iso := GroupHomomorphismByImages(f,f,[a,b^(y^-1),c^(x^-1*y^-1*a^-1),x^(b*a*z*a^-1),y,z^(a^-1)],[a,b,c,x,y,z]);;
gap> newm := CleanedIMGMachine(ChangeFRMachineBasis(m^iso,[a^-1*y^-1,y^-1*a^-1*c^-1]));;
gap> Display(newm);
 G |          1         2   
---+-------------+---------+
 a | a^-1*c^-1,2   c*a*b,1  
 b |      <id>,1       c,2  
 c |         a,1    <id>,2  
 x |       z*x,2    x^-1,1  
 y |      <id>,1       x,2  
 z |         y,1    <id>,2  
---+-------------+---------+
Relator: c*a*b*y*z*x

9.1-11 PolynomialFRMachine

This function creates a group, IMG or Mealy machine that describes a topological polynomial. The polynomial is described symbolically in the language of external angles. For more details, see [DH84] and [DH85] (in the quadratic case), [BFH92] (in the preperiodic case), and [Poi] (in the general case).

d is the degree of the polynomial. per and pre are lists of angles or preangles. In what follows, angles are rational numbers, considered modulo 1. Each entry in per or pre is either a rational (interpreted as an angle), or a list of angles [a_1,...,a_i] such that da_1=...=da_i. The angles in per are angles landing at the root of a Fatou component, and the angles in pre land on the Julia set.

Note that, for IMG machines, the last generator of the machine produced is an adding machine, representing a loop going counterclockwise around infinity (in the compactification of C by a disk, this loop goes clockwise around that disk).

In constructing a polynomial IMG machine, one may specify a boolean flag formal, which defaults to true. In a formal recursion, distinct angles give distinct generators; while in a non-formal recursion, distinct angles, which land at the same point in the Julia set, give a single generator. The simplest example where this occurs is angle 5/12 in the quadratic family, in which angles 1/3 and 2/3 land at the same point -- see the example below.

The attribute Correspondence(m) records the angles landing on the generators: Correspondence(m)[i] is a list [a,s] where a is an angle landing on generator i and s is "Julia" or "Fatou".

If only one list of angles is supplied, then FR guesses that all angles with denominator coprime to n are Fatou, and all the others are Julia.

The inverse operation, reconstructing the angles from the IMG machine, is SupportingRays (9.1-12).

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(2,[],[5/12]);
gap> PolynomialIMGMachine(2,[],[5/12]);
<FR machine with alphabet [ 1, 2 ] and adder f5 on Group( [ f1, f2, f3, f4, f5 ] )/[ f5*f4*f3*f2*f1 ]>
gap> Correspondence(last);
[ [ 1/3, "Julia" ], [ 5/12, "Julia" ], [ 2/3, "Julia" ], [ 5/6, "Julia" ] ]
gap> PolynomialIMGMachine(2,[],[5/12],false);
<FR machine with alphabet [ 1, 2 ] and adder f4 on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>
gap> Correspondence(last);
[ [ [ 1/3, 2/3 ], "Julia" ], [ [ 5/12 ], "Julia" ], [ [ 5/6 ], "Julia" ] ]

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]]);
    else
        Error("Unknown Poirier example ",arg);
    fi;
end;

9.1-12 SupportingRays

This operation is the inverse of PolynomialIMGMachine (9.1-11): it computes a choice of angles, describing landing rays on Fatou/Julia critical points.

If there does not exist a complex realization, namely if the machine is obstructed, then this command returns an obstruction, as a record. The field minimal is set to false, and a proper sub-machine is set as the field submachine. The field homomorphism gives an embedding of the stateset of submachine into the original machine, and relation is the equivalence relation on the set of generators of m that describes the pinching.

gap> r := PolynomialIMGMachine(2,[1/7],[]);
<FR machine with alphabet [ 1, 2 ] and adder f4 on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>
gap> F := StateSet(r);; SetName(F,"F");
gap> SupportingRays(r);
[ 2, [ [ 1/7, 9/14 ] ], [  ] ] # actually returns the angle 2/7
gap> # now CallFuncList(PolynomialIMGMachine,last) would return the machine r
gap> twist := GroupHomomorphismByImages(F,F,GeneratorsOfGroup(F),[F.1^(F.2*F.1),F.2^F.1,F.3,F.4])^-1;
[ f1, f2, f3, f4 ] -> [ f1*f2*f1^-1, f2*f1*f2*f1^-1*f2^-1, f3, f4 ]
gap> List([-5..5],i->2*SupportingRays(r*twist^i)[2][1][1]);
[ 4/7, 5/7, 4/7, 4/7, 5/7, 2/7, 4/7, 4/7, 2/7, 4/7, 4/7 ]
gap> r := PolynomialIMGMachine(2,[],[1/6]);;
gap> F := StateSet(r);;
gap> twist := GroupHomomorphismByImages(F,F,GeneratorsOfGroup(F),[F.1,F.2^(F.3*F.2),F.3^F.2,F.4]);;
gap> SupportingRays(r);
[ 2, [  ], [ [ 1/12, 7/12 ] ] ]
gap> SupportingRays(r*twist);
[ 2, [  ], [ [ 5/12, 11/12 ] ] ]
gap> SupportingRays(r*twist^2);
rec(
  transformation := [ [ f1, f2^-1*f3^-1*f2^-1*f3^-1*f2*f3*f2*f3*f2, f2^-1*f3^-1*f2^-1*f3*f2*f3*f2,
          f4 ] -> [ f1, f2, f3, f4 ],
      [ f1^-1*f2^-1*f1^-1*f2^-1*f1*f2*f1*f2*f1, f1^-1*f2^-1*f1^-1*f2*f1*f2*f1, f3, f4 ] ->
        [ f1, f2, f3, f4 ],
      [ f1^-1*f2^-1*f3^-1*f2*f1*f2^-1*f3*f2*f1, f2, f2*f1^-1*f2^-1*f3*f2*f1*f2^-1, f4 ] ->
        [ f1, f2, f3, f4 ], [ f1, f3*f2*f3^-1, f3, f4 ] -> [ f1, f2, f3, f4 ],
      [ f1, f2, f2*f3*f2^-1, f4 ] -> [ f1, f2, f3, f4 ],
      [ f1, f3*f2*f3^-1, f3, f4 ] -> [ f1, f2, f3, f4 ],
      [ f1, f2, f2*f3*f2^-1, f4 ] -> [ f1, f2, f3, f4 ],
      [ f1, f3*f2*f3^-1, f3, f4 ] -> [ f1, f2, f3, f4 ] ], machine := <FR machine with alphabet
    [ 1, 2 ] and adder f4 on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>, minimal := false,
  submachine := <FR machine with alphabet [ 1, 2 ] and adder f3 on Group( [ f1, f2, f3 ] )>,
  homomorphism := [ f1, f2, f3 ] -> [ f1, f2*f3, f4 ],
  relation := <equivalence relation on <object> >, niter := 8 )

9.1-13 AsGroupFRMachine

This function creates an FR machine on a 1-letter alphabet, that represents the endomorphism f. It is specially useful when combined with products of machines; indeed the usual product of machines corresponds to composition of endomorphisms.

gap> f := FreeGroup(2);;
gap> h := GroupHomomorphismByImages(f,f,[f.1,f.2],[f.2,f.1*f.2]);
[ f1, f2 ] -> [ f2, f1*f2 ]
gap> m := AsGroupFRMachine(h);
<FR machine with alphabet [ 1 ] on Group( [ f1, f2 ] )>
gap> mm := TensorProduct(m,m);
<FR machine with alphabet [ 1 ] on Group( [ f1, f2 ] )>
gap> Display(mm);
 G  |         1
----+------------+
 f1 |    f1*f2,1
 f2 | f2*f1*f2,1
----+------------+

9.1-14 NormalizedPolynomialFRMachine

This function returns a new FR machine, in which the adding element has been put into a standard form t=[t,1,dots,1]s, where s is the long cycle i↦ i-1.

For the first command, the machine returned is an FR machine; for the second, it is an IMG machine.

9.1-15 SimplifiedIMGMachine

This function returns a new IMG machine, with hopefully simpler transitions. The simplified machine is obtained by applying automorphisms to the stateset. The sequence of automorphisms (in increasing order) is stored as a correspondence; namely, if n=SimplifiedIMGMachine(m), then m^Product(Correspondence(n))=n.

gap> r := PolynomialIMGMachine(2,[1/7],[]);;
gap> F := StateSet(r);; SetName(F,"F");
gap> twist := GroupHomomorphismByImages(F,F,GeneratorsOfGroup(F),[F.1^(F.2*F.1),F.2^F.1,F.3,F.4]);;
gap> m := r*twist;; Display(m);
 G  |                     1            2
----+------------------------+------------+
 f1 |          f1^-1*f2^-1,2   f3*f2*f1,1
 f2 | f1^-1*f2^-1*f1*f2*f1,1       <id>,2
 f3 |          f1^-1*f2*f1,1       <id>,2
 f4 |                   f4,2       <id>,1
----+------------------------+------------+
Adding element: f4
Relator: f4*f3*f2*f1
gap> n := SimplifiedIMGMachine(m);
<FR machine with alphabet [ 1, 2 ] and adder f4 on F>
gap> Display(n);
 G  |            1            2
----+---------------+------------+
 f1 | f2^-1*f1^-1,2   f1*f2*f3,1
 f2 |        <id>,1         f1,2
 f3 |        <id>,1         f2,2
 f4 |          f4,2       <id>,1
----+---------------+------------+
Adding element: f4
Relator: f4*f1*f2*f3
gap> n = m^Product(Correspondence(n));
true

9.1-16 Mating

The mating is defined as follows: one removes a disc around the adding machine in m1 and m2; one applies complex conjugation to m2; and one glues the hollowed spheres along their boundary circle.

The optional argument formal, which defaults to true, specifies whether a formal mating should be done; in a non-formal mating, generators of m1 and m2 which have identical angle should be treated as a single generator. A non-formal mating is of course possible only if the machines are realizable -- see SupportingRays (9.1-12).

The attribute Correspondence is a pair of homomorphisms, from the statesets of m1,m2 respectively to the stateset of the mating.

gap> # the Tan-Shishikura examples
gap> z := Indeterminate(MPC_PSEUDOFIELD);;
gap> a := RootsFloat((z-1)*(3*z^2-2*z^3)+1);;
gap> c := RootsFloat((z^3+z)^3+z);;
gap> am := List(a,a->IMGMachine((a-1)*(3*z^2-2*z^3)+1));;
gap> cm := List(c,c->IMGMachine(z^3+c));;
gap> m := ListX(am,cm,Mating);;
gap> # m[2] is realizable
gap> RationalFunction(m[2]);
((1.66408+I*0.668485)*z^3+(-2.59772+I*0.627498)*z^2+(-1.80694-I*0.833718)*z
  +(1.14397-I*1.38991))/((-1.52357-I*1.27895)*z^3+(2.95502+I*0.234926)*z^2
  +(1.61715+I*1.50244)*z+1)
gap> # m[6] is obstructed
gap> RationalFunction(m[6]);
rec( matrix := [ [ 1/2, 1 ], [ 1/2, 0 ] ], machine := <FR machine with alphabet
    [ 1, 2, 3 ] on Group( [ f1, f2, f3, g1, g2, g3 ] )/[ f2*f3*f1*g1*g3*g2 ]>,
  obstruction := [ f1^-1*f3^-1*f2^-1*f1*f2*f3*f1*g2^-1*g3^-1*f1^-1*f3^-1*f2^-1,
      f2*f3*f1*f2*f3*f1*g2*f1^-1*f3^-1*f2^-1*f1^-1*f3^-1 ],
  spider := <spider on <triangulation with 8 vertices, 36 edges and
    12 faces> marked by GroupHomomorphismByImages( Group( [ f1, f2, f3, g1, g2, g3
     ] ), Group( [ f1, f2, f3, f4, f5 ] ), [ f1, f2, f3, g1, g2, g3 ],
    [ f1*f4*f2^-1*f1*f4^-1*f1^-1, f1*f4*f2^-1*f1*f4*f5^-1*f1^-1*f2*f4^-1*f1^-1,
      f1*f4*f2^-1*f1*f5*f1^-1*f2*f4^-1*f1^-1, f2*f4^-1*f1^-1*f2*f1*f4*f2^-1,
      f2*f4^-1*f3*f2^-1, f2*f4^-1*f1^-1*f3^-1*f4*f2^-1 ] )> )

9.1-17 AutomorphismVirtualEndomorphism

Let m be an IMG machine, thought of as a biset for the fundamental group G of a punctured sphere. Let M denote the automorphism of the surface, seen as a group of outer automorphisms of G that fixes the conjugacy classes of punctures.

Choose an alphabet letter a, and consider the virtual endomorphism v:G_a-> G. Let H denote the subgroup of M that fixes all conjugacy classes of G_a. then there is an induced virtual endomorphism α:H-> M, defined by t^α=v^-1tv. This is the homomorphism computed by the first command. Its source and range are in fact groups of automorphisms of range of v.

The second command constructs an FR machine associated with \alpha. Its stateset is a free group generated by elementary Dehn twists of the generators of G.

gap> z := Indeterminate(COMPLEX_FIELD);;
gap> # a Sierpinski carpet map without multicurves
gap> m := IMGMachine((z^2-z^-2)/2/COMPLEX_I);
<FR machine with alphabet [ 1, 2, 3, 4 ] on Group( [ f1, f2, f3, f4 ] )/[ f3*f2*f1*f4 ]>
gap> AutomorphismIMGMachine(i);
<FR machine with alphabet [ 1, 2 ] on Group( [ x1, x2, x3, x4, x5, x6 ] )>
gap> Display(last);
 G  |     1        2
----+--------+--------+
 x1 | <id>,2   <id>,1  
 x2 | <id>,1   <id>,2  
 x3 | <id>,2   <id>,1  
 x4 | <id>,2   <id>,1  
 x5 | <id>,1   <id>,2  
 x6 | <id>,2   <id>,1  
----+--------+--------+
gap> # the original rabbit problem
gap> m := PolynomialIMGMachine(2,[1/7],[]);;
gap> v := VirtualEndomorphism(m,1);;
gap> a := AutomorphismVirtualEndomorphism(v);
MappingByFunction( <group with 20 generators>, <group with 6 generators>, function( a ) ... end )
gap> Source(a).1;
[ f1, f2, f3, f4 ] -> [ f3*f2*f1*f2^-1*f3^-1, f2, f3, f3*f2*f1^-1*f2^-1*f3^-1*f2^-1*f3^-1 ]
gap> Image(a,last);
[ f1, f2, f3, f4 ] -> [ f1, f2, f2*f1*f3*f1^-1*f2^-1, f3^-1*f1^-1*f2^-1 ]
gap> # so last2*m is equivalent to m*last

9.1-18 DBRationalIMGGroup

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 [Tan02].

When called with no arguments, this command returns the database contents in raw form.

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.

If the argument is a rational map, the command returns the IMG group of that map, assuming its canonical quadratic rational form form exists in the database.

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)

9.1-19 PostCriticalMachine

This function constructs a Mealy machine P on the alphabet [1], which describes the post-critical set of f. It is in fact an oriented graph with constant out-degree 1. It is most conveniently passed to Draw (5.2-1).

The attribute Correspondence(P) is the list of values associated with the stateset of P.

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 ]

9.1-20 Mandel

This function starts the external program mandel, by Wolf Jung. The program is searched for along the standard PATH; alternatively, its location can be set in the string variable EXEC@FR.mandel.

When called with no arguments, this command returns starts mandel in its default mode. With a rational map as argument, it starts mandel pointing at that rational map.

9.2 Spiders

FR contains an implementation of the Thurston-Hubbard-Schleicher "spider algorithm" [HS94] that constructs a rational map from an IMG recursion. This implementation does not give rigourous results, but relies of floating-point approximation. In particular, various floating-point parameters control the proper functioning of the algorithm. They are stored in a record, EPS@fr. Their meaning and default values are:

9.2-1 DelaunayTriangulation

If points is a list of points on the unit sphere, represented by their 3D coordinates, this function creates a triangulation of the sphere with these points as vertices. This triangulation is such that the angles are as equilateral as possible.

This triangulation is a recursive collection of records, one for each vertex, oriented edge or face. Each such object has a pos component giving its coordinates; and an index component identifying it uniquely. Additionally, vertices and faces have a n component which lists their neighbours in CCW order, and edges have from,to,left,right,reverse components.

If all points are aligned on a great circle, or if all points are in a hemisphere, some points are added so as to make the triangulation simplicial with all edges of length <π. These vertices additionally have a fake component set to true.

A triangulation may be plotted with Draw; this requires appletviewer to be installed. The command Draw(t:detach) detaches the subprocess after it is started. The extra arguments Draw(t:lower) or Draw(t:upper) stretch the triangulation to the lower, respectively upper, hemisphere.

If the second argument quality, which must be a floatean, is present, then all triangles in the resulting triangulation are guaranteed to have circumcircle ratio / minimal edge length at most quality. Of course, additional vertices may need to be added to ensure that.

gap> octagon := Concatenation(IdentityMat(3),-IdentityMat(3))*1.0;
gap> dt := DelaunayTriangulation(octagon);
<triangulation with 6 vertices, 24 edges and 8 faces>
gap> dt!.v;
[ <vertex 1>, <vertex 2>, <vertex 3>, <vertex 4>, <vertex 5>, <vertex 6> ]
gap> last[1].n;
[ <edge 17>, <edge 1>, <edge 2>, <edge 11> ]
gap> last[1].from;
<vertex 1>

9.2-2 LocateInTriangulation

This command locates the face in t that contains point; or, if point lies on an edge or a vertex, it returns that edge or vertex.

The optional second argument specifies a starting vertex, edge, face, or vertex index from which to start the search. Its only effect is to speed up the algorithm.

gap> cube := Tuples([-1,1],3)/Sqrt(3.0);;
gap> dt := DelaunayTriangulation(cube);
<triangulation with 8 vertices, 36 edges and 12 faces>
gap> LocateInTriangulation(dt,dt!.v[1].pos);
<vertex 1>
gap> LocateInTriangulation(dt,[3/5,0,4/5]*1.0);
<face 9>

9.2-3 IsSphereTriangulation

The category of triangulated spheres (points in Moduli space), or of marked, triangulated spheres (points in Teichmüller space).

Various commands have an attribudte Spider, which records this point in Teichmüller space.

9.2-4 RationalFunction

This command runs a modification of Hubbard and Schleicher's "spider algorithm" [HS94] on the IMG FR machine m. It either returns a rational function f whose associated machine is m; or a record describing the Thurston obstruction to realizability of f.

This obstruction record r contains a list r.multicurve of conjugacy classes in StateSet(m), which represent short multicurves; a matrix r.mat, and a spider r.spider on which the obstruction was discovered.

If a rational function is returned, it has preset attributes Spider(f) and IMGMachine(f) which is a simplified version of m. This rational function is also normalized so that its post-critical points have barycenter=0 and has two post-critical points at infinity and on the positive real axis. Furthermore, if m is polynomial-like, then the returned map is a polynomial.

The command accepts the following options, to return a map in a given normalization:

gap> m := PolynomialIMGMachine(2,[1/3],[]);
<FR machine with alphabet [ 1, 2 ] on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>
gap> RationalFunction(m);
0.866025*z^2+(-1)*z+(-0.288675)

9.2-5 Draw

This command plots the spider s in a separate X window. It displays the complex sphere, big dots at the post-critical set (feet of the spider), and the arcs and dual arcs of the triangulation connecting the feet.

If the option julia:=<gridsize> (if no grid size is specified, it is 500 by default), then the Julia set of the map associated with the spider is also displayed. Points attracted to attracting cycles are coloured in pastel tones, and unattracted points are coloured black.

If the option noarcs is specified, the printing of the arcs and dual arcs is disabled.

9.2-6 FRMachine

This function computes a triangulation of the sphere, on the post-critical set of f, and lifts it through the map f. the action of the fundamental group of the punctured sphere is then read into an IMG fr machine m, which is returned.

An approximation of the Julia set of f can be computed, and plotted on the spider, with the form IMGMachine(f:julia) or IMGMachine(f:julia:=gridsize).

gap> z := Indeterminate(COMPLEX_FIELD);;
gap> IMGMachine(z^2-1);
<FR machine with alphabet [ 1, 2 ] on Group( [ f1, f2, f3 ] )/[ f2*f1*f3 ]>
gap> Display(last);
 G  |            1        2
----+---------------+--------+
 f1 |          f2,2   <id>,1
 f2 | f3^-1*f1*f3,1   <id>,2
 f3 |        <id>,2     f3,1
----+---------------+--------+
Relator: f2*f1*f3

9.2-7 FindThurstonObstruction

This method accepts a list of IMG elements on the same underlying machine, and treats these as representatives of conjugacy classes defining (part of) a multicurve. It computes whether these curves, when supplemented with their lifts under the recursion, constitute a Thurston obstruction, by computing its transition matrix.

The method either returns fail, if there is no obstruction, or a record with as fields matrix,machine,obstruction giving respectively the transition matrix, a simplified machine, and the curves that constitute a minimal obstruction.

gap> r := PolynomialIMGMachine(2,[],[1/6]);;
gap> F := StateSet(r);;
gap> twist := GroupHomomorphismByImages(F,F,GeneratorsOfGroup(F),[F.1,F.2^(F.3*F.2),F.3^F.2,F.4]);;
gap> SupportingRays(r*twist^-1);
rec( machine := <FR machine with alphabet [ 1, 2 ] on F/[ f4*f1*f2*f3 ]>,
     twist := [ f1, f2, f3, f4 ] -> [ f1, f3^-1*f2*f3, f3^-1*f2^-1*f3*f2*f3, f4 ],
     obstruction := "Dehn twist" )
gap> FindThurstonObstruction([FRElement(last.machine,[2,3])]);
rec( matrix := [ [ 1 ] ], machine := <FR machine with alphabet [ 1, 2 ] on F/[ f4*f1*f2*f3 ]>, obstruction := [ f1^-1*f4^-1 ] )

9.2-8 KneadingSequence

This function converts a rational angle to a kneading sequence, to describe a quadratic polynomial.

If angle is in [1/7,2/7] and the option marked is set, the kneading sequence is decorated with markings in A,B,C.

gap> KneadingSequence(1/7);
[ 1, 1 ]
gap> KneadingSequence(1/5:marked);
[ "A1", "B1", "B0" ]

9.2-9 AllInternalAddresses

This function returns internal addresses for all periodic points of period up to n under angle doubling. These internal addresses describe the prominent hyperbolic components along the path from the landing point to the main cardioid in the Mandelbrot set; this is a list of length 3k, with at position 3i+1,3i+2 the left and right angles, respectively, and at position 3i+3 the period of that component. For example, [ 3/7, 4/7, 3, 1/3, 2/3, 2 ] describes the airplane: a polynomial with landing angles [3/7,4/7] of period 3; and such that there is a polynomial with landing angles [1/3,2/3] and period 2.

gap> AllInternalAddresses(3);
[ [  ], [ [ 1/3, 2/3, 2 ] ], 
[ [ 1/7, 2/7, 3 ], [ 3/7, 4/7, 3, 1/3, 2/3, 2 ], [ 5/7, 6/7, 3 ] ] ]

9.2-10 ExternalAnglesRelation

This function returns the equivalence relation on Rationals identifying all pairs of external angles that land at a common point of period up to n under angle multiplication by by degree.

gap> ExternalAnglesRelation(2,3);
<equivalence relation on Rationals >
gap> EquivalenceRelationPartition(last);
[ [ 1/7, 2/7 ], [ 1/3, 2/3 ], [ 3/7, 4/7 ], [ 5/7, 6/7 ] ]

9.2-11 ExternalAngle

In case machine is the IMG machine of a unicritical polynomial, this function computes the external angle landing at the critical value. More precisely, it computes the equivalence class of that external angle under ExternalAnglesRelation (9.2-10).

9 Iterated monodromy groups