Goto Chapter: Top 1 2 3 4 5 6 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 Sphere groups and machines
 3.1 Sphere groups
 3.2 Sphere machines
 3.3 Polynomial sphere machines
 3.4 Automorphisms of sphere machines

3 Sphere groups and machines

3.1 Sphere groups

Fundamental groups of punctured spheres, and of sphere orbifolds, are defined in IMG as a special class of finitely presented groups. The generators of the group represent the punctures of the sphere, or more generally its orbispace points.

3.1-1 IsSphereGroup
‣ IsSphereGroup( filter )

A sphere group is a special kind of finitely presented group, in which exactly one relation is a product, in some order, of all the generators, and all the other relations (possibly none) are powers of generators.

Sphere groups are used to represent the fundamental groups of punctured spheres, or more generally orbifolds whose underlying space is a sphere.

3.1-2 IsomorphismSphereGroup
‣ IsomorphismSphereGroup( g )( attribute )
‣ AsSphereGroup( g )( attribute )

These functions compute an isomorphism from g to a sphere group; the first form returns the isomorphism, while the second one returns its image.

3.1-3 EulerCharacteristic
‣ EulerCharacteristic( g )( attribute )

Returns: The Euler characteristic of g.

The Euler characteristic of a free group of rank n is 1-n; and it multiplies by the index on subgroups. A sphere group is finite if and only if its Euler characteristic is positive, and is virtually abelian if and only if its Euler characteristic is 0.

3.1-4 RankOfSphereGroup
‣ RankOfSphereGroup( g )( attribute )

Returns: The number of generators of g.

3.1-5 OrderingOfSphereGroup
‣ OrderingOfSphereGroup( g )( attribute )

Returns: The list of the orders of the generators.

This attribute has the property that Product(GeneratorsOfGroup(g){OrderingOfSphereGroup(g)}) is the identity.

3.1-6 ExponentsOfSphereGroup
‣ ExponentsOfSphereGroup( g )( attribute )

Returns: The list of exponents of the generators.

This attribute has the property that GeneratorsOfGroup(g)[i]^ExponentsOfSphereGroup(g)[i] is the identity for all i. If an element has infinite order, the value stored is 0.

3.1-7 IsomorphismFreeGroup
‣ IsomorphismFreeGroup( g )( attribute )

Returns: An isomorphism to a free group, if it exists.

If g was created as a sphere group with all exponents infinity, then g is isomorphic to a free group on all the generators but one; this attribute stores such an isomorphism.

3.1-8 SphereGroup
‣ SphereGroup( ordering[, exponent] )( function )

Returns: A new sphere group.

ordering is either a list of integers, describing the order of the generators that is to be trivial; or an integer m, in which case the ordering is [m,m-1,..,1].

The optional second argument exponent is a list of integers describing the exponents of the generators. The value 0 specifies a generator of infinite order.

3.1-9 IsSphereConjugacyClass
‣ IsSphereConjugacyClass( filter )

Elements of a sphere group represent based loops on a punctured sphere. Loops (without specified basepoint) are represented by conjugacy classes. A multicurve is a collection of non-intersecting loops.

Conjugacy classes may be raised to integer powers; the nth power of a conjugacy class is the conjugacy class of the nth power of an element.

3.1-10 IsPeripheral
‣ IsPeripheral( c )( property )

Returns: Whether the conjugacy class c is peripheral.

A conjugacy class is peripheral if it contains a generator of the sphere group.

3.1-11 PeripheralClasses
‣ PeripheralClasses( g )( attribute )

Returns: The peripheral conjugacy classes of g.

3.1-12 IntersectionNumber
‣ IntersectionNumber( c, d )( attribute )

Returns: The intersection number of the conjugacy classes c and d.

The geometric intersection number of two loops is the minimal number of intersections they may have. The self-intersection number of a loop is the intersection number of the loop with a small translate.

3.1-13 AutomorphismGroup
‣ AutomorphismGroup( g )( attribute )
‣ EpimorphismToOut( a )( attribute )

This function computes the pure automorphism group of the sphere group g, namely the group of automorphisms that preserves all the peripheral conjugacy classes (conjugacy classes of generators).

The attribute EpimorphismToOut stores an epimorphism from the automorphism group to the group of outer automorphisms.

3.1-14 AmalgamateFreeProduct
‣ AmalgamateFreeProduct( g, h, x, y )( operation )

This function computes the amalgamated free product of two sphere groups g and h, along the cyclic subgroups ⟨ x⟩ of g and ⟨ y⟩ of h.

The attribute EmbeddingsOfAmalgamatedFreeProduct is a list of length two, storing the embeddings of g and h respectively into the amalgam.

3.2 Sphere machines

Sphere machines are simply group FR machines (see Section fr: FRMachine [list,]list,list) whose underlying StateSet (fr: StateSet fr machine) is a sphere group. DeclareProperty("IsSphereMachine", IsGroupFRMachine); InstallImmediateMethod(IsSphereMachine,IsFRMachine,0, function(m) local g; g := StateSet(m); return HasIsSphereGroup(g) and IsSphereGroup(g); end);

3.2-1 IsSphereMachine
‣ IsSphereMachine( m )( filter )
‣ IsPolynomialSphereMachine( m )( filter )

The categories of Sphere and polynomial machines. Sphere machines are group FR machines whose underlying group is a sphere group, see SphereGroup (3.1-8).

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 (3.3-7); see AsPolynomialSphereMachine (3.3-8). 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.

The last category is the intersection of the first two.

DeclareAttribute("AsSphereMachine", IsGroupFRMachine); DeclareOperation("AsSphereMachine", [IsGroupFRMachine, IsWord]); DeclareOperation("AsSphereMachine", [IsGroupFRMachine, IsSphereGroup]);

3.2-2 AsSphereMachine
‣ AsSphereMachine( m[, w] )( operation )

Returns: A sphere machine.

This function creates a new sphere 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 relator; if w is a sphere group, then it is used as the new stateset. Finally, if no relator and no group is specified, and the product (in some ordering) of the generators is trivial, then that product is used as relator. In other cases, the method returns fail.

A standard FR machine can be recovered from a sphere machine by AsGroupFRMachine (fr: AsGroupFRMachine), AsMonoidFRMachine (fr: AsMonoidFRMachine), and AsSemigroupFRMachine (fr: AsSemigroupFRMachine).

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> AsSphereMachine(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

DeclareGlobalFunction("NewSphereMachine");

3.2-3 NewSphereMachine
‣ NewSphereMachine( ... )( attribute )

Returns: A new sphere machine, based on string descriptions.

This command constructs a new sphere machine, in a format similar to FRGroup (fr: FRGroup); 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. The underlying group of the machine is a sphere group.

word-i is allowed to be the empty string; and the "<...>" may be skipped altogether. Each word-i may also contain inverses.

The extra final arguments describe relations in the underlying sphere group; at least one relation is required, the product of the generators in an appropriate order.

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

gap> fold1 := NewSphereMachine("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)","a*B*A*b");
gap> <FR machine with alphabet [ 1, 2, 3, 4, 5, 6 ] on Group( [ a, b, A, B ] )/[ a*B*A*b ]>                                
gap> fold2 := NewSphereMachine("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)","a*B*A*b");;
gap> P1MapBySphereMachine(fold1); P1MapBySphereMachine(fold2);
...

3.3 Polynomial sphere machines

Polynomial sphere machines have a special extra attribute, an AddingElement (3.3-7). This is an element of the underlying FR group, which acts as an adding element on the machine's alphabet. It represents a fixed point of a Thurston map of maximal ramification; typically, the point of a polynomial. DeclareOperation("PolynomialMealyMachine",[IsPosInt,IsList,IsList]); DeclareOperation("PolynomialMealyMachine",[IsPosInt,IsList]); DeclareOperation("PolynomialSphereMachine",[IsPosInt,IsList,IsList,IsRecord]); DeclareOperation("PolynomialSphereMachine",[IsPosInt,IsList,IsList]); DeclareOperation("PolynomialSphereMachine",[IsPosInt,IsList,IsRecord]); DeclareOperation("PolynomialSphereMachine",[IsPosInt,IsList]);

3.3-1 PolynomialSphereMachine
‣ PolynomialSphereMachine( d, per[, pre][, options] )( operation )
‣ PolynomialMealyMachine( d, per[, pre] )( operation )

Returns: A sphere or Mealy machine.

This function creates a sphere 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 sphere 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 sphere machine, one may specify a record options, which may contain the following fields: mealy (boolean, default false) specifies if a formal construction is required; adding specifying that the adding machine should have the most compact representation; and orbispace (boolean, default false) asking the constructed group to have orbispace points of minimal degree.

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 IMG 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 sphere machine, is SupportingRays (3.3-2).

gap> PolynomialSphereMachine(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(PolynomialSphereMachine(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(PolynomialSphereMachine(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> PolynomialSphereMachine(2,[],[5/12]);
<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" ] ]
gap> PolynomialSphereMachine(2,[],[5/12],rec(formal:=true));
<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" ] ]

The following construct the examples in Poirier's paper:

PoirierExamples := function(arg)
    if arg=[1] then
        return PolynomialSphereMachine(2,[1/7],[]);
    elif arg=[2] then
        return PolynomialSphereMachine(2,[],[1/2]);
    elif arg=[3,1] then
        return PolynomialSphereMachine(2,[],[5/12]);
    elif arg=[3,2] then
        return PolynomialSphereMachine(2,[],[7/12]);
    elif arg=[4,1] then
        return PolynomialSphereMachine(3,[[3/4,1/12],[1/4,7/12]],[]);
    elif arg=[4,2] then
        return PolynomialSphereMachine(3,[[7/8,5/24],[5/8,7/24]],[]);
    elif arg=[4,3] then
        return PolynomialSphereMachine(3,[[1/8,19/24],[3/8,17/24]],[]);
    elif arg=[5] then
        return PolynomialSphereMachine(3,[[3/4,1/12],[3/8,17/24]],[]);
    elif arg=[6,1] then
        return PolynomialSphereMachine(4,[],[[1/4,3/4],[1/16,13/16],[5/16,9/16]]);
    elif arg=[6,2] then
        return PolynomialSphereMachine(4,[],[[1/4,3/4],[3/16,15/16],[7/16,11/16]]);
    elif arg=[7] then
        return PolynomialSphereMachine(5,[[0,4/5],[1/5,2/5,3/5]],[[1/5,4/5]]);
    elif arg=[9,1] then
        return PolynomialSphereMachine(3,[[0,1/3],[5/9,8/9]],[]);
    elif arg=[9,2] then
        return PolynomialSphereMachine(3,[[0,1/3]],[[5/9,8/9]]);
    else
        Error("Unknown Poirier example ",arg);
    fi;
end;

DeclareAttribute("SupportingRays",IsFRMachine);

3.3-2 SupportingRays
‣ SupportingRays( m )( attribute )

Returns: A [degree,fatou,julia] description of m.

This operation is the inverse of PolynomialSphereMachine (3.3-1): 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 := PolynomialSphereMachine(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(PolynomialSphereMachine,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 := PolynomialSphereMachine(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 )

DeclareAttribute("FRMachineWithNormalizedAdder",IsGroupFRMachine); DeclareOperation("FRMachineWithNormalizedAdder",[IsGroupFRMachine,IsAssocWord]);

3.3-3 FRMachineWithNormalizedAdder
‣ FRMachineWithNormalizedAdder( m[, adder] )( attribute )

Returns: A sphere machine.

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. If the adding element adder is not specified, then m should be a polynomial sphere machine, and adder is its AddingElement.

DeclareAttribute("SimplifiedSphereMachine",IsSphereMachine);

3.3-4 SimplifiedSphereMachine
‣ SimplifiedSphereMachine( m )( attribute )

Returns: A simpler sphere machine.

This function returns a new sphere 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=SimplifiedSphereMachine(m), then m^Product(Correspondence(n))=n.

gap> r := PolynomialSphereMachine(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 := SimplifiedSphereMachine(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

DeclareOperation("Mating",[IsPolynomialSphereMachine,IsPolynomialSphereMachine]); DeclareOperation("Mating",[IsPolynomialSphereMachine,IsPolynomialSphereMachine,IsBool]); DeclareAttribute("EquatorElement",IsSphereMachine); DeclareAttribute("EquatorTwist",IsSphereMachine);

3.3-5 Mating
‣ Mating( m1, m2[, formal] )( operation )
‣ EquatorElement( m )( attribute )
‣ EquatorTwist( m )( attribute )

Returns: A sphere machine.

This function "mates" two polynomial sphere machines.

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 (3.3-2).

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

The attribute EquatorElement is set, and records the original adding elements of m1,m2, which have become the equator of the mating.

Note that there are d-1 different matings between polynomials of degree d: each has d-1 fixed rays at angles 2π ik/(d-1). This command constructs the mating in which rays at angle 0 are matched to each other. To obtain the other matings, multiply the machine by a power of its EquatorTwist.

gap> # the Tan-Shishikura examples
gap> SetP1Points(PMCOMPLEX);
gap> z := Indeterminate(@IMG.field);;
gap> a := RootsFloat((z-1)*(3*z^2-2*z^3)+1);;
gap> c := RootsFloat((z^2+1)^3*z^2+1);;
gap> am := List(a,a->SphereMachine((a-1)*(3*P1z^2-2*P1z^3)+1));;
gap> cm := List(c,c->SphereMachine(P1z^3+c));;
gap> m := ListX(am,cm,Mating);;
gap> # m[1] is realizable
gap> P1MapBySphereMachine(m[1]);
((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[29] is obstructed, and has a Levy cycle
gap> P1MapBySphereMachine(m[29]);
rec(
  machine := <sphere machine with alphabet [ 1, 2, 3 ] on Group( [ f1, f2, f3, g1, g2,\
 g3 ] ) / [ f3*f2*f1*g3*g2*g1 ]>, matrix := [ [ 1, 1/2 ], [ 1, 0 ] ],
  multicurve := [ (f1*f3*f2)^2*f1*g1^-1*(g3*g2*g1)^3*f2^-1*f3*f2^G,
      f1^-1*f2^-1*(f3*f2*f1)^4*g2*(g3*g2*g1)^3^G ] )
gap> but the other mating of the same polynomials is not obstructed:
gap> P1MapBySphereMatrix(m[29]*EquatorTwist(m[29]));
<((-1.4495156808145406+0.44648102591936722i_z)*z^3+
(-1.1286550578708263-0.40162285610021786i_z)*z^2+
(1.0326873942952213-0.11770300021984977i_z)*z+
(1.0940864612174037+0.24650956710141259i_z))/
((0.85917327990384307-0.8755042485587835i_z)*z^3+
(0.9573881709899621-0.14875521653926685i_z)*z^2+
(-0.68923589444039035+0.48120812618585479i_z)*z+1._z)>
gap> # m[14] is the original Tan Lei-Shishikura example
gap> ThurstonAlgorithm(m[14]);
rec(
  machine := <sphere machine with alphabet [ 1, 2, 3 ] on Group( [ f1, f2, f3, g1, g2, g3 ] ) / [ f\
3*f2*f1*g3*g2*g1 ]>, matrix := [ [ 1/2, 1 ], [ 1/2, 0 ] ],
  multicurve := [ f1^-1*f3*f2*f1*f3*f2*f1*g1^-1*g3*g2*g1*g3*g2*g1^G,
                  f1^-1*f2*f1*f3*f2*f1*f3*f2*f1*g2*g3*g2*g1*g3*g2*g1^G ] )

DeclareProperty("IsKneadingMachine",IsFRMachine); DeclareAttribute("PlanarEmbeddingOfKneadingMachine",IsFRMachine); DeclareAttribute("PlanarEmbeddingsOfKneadingMachine",IsFRMachine); DeclareSynonym("IsPlanarKneadingMachine",HasPlanarEmbeddingOfKneadingMachine); InstallTrueMethod(IsBoundedFRMachine,IsKneadingMachine); InstallTrueMethod(IsLevelTransitive,IsKneadingMachine);

3.3-6 IsKneadingMachine
‣ IsKneadingMachine( m )( property )
‣ PlanarEmbeddingOfKneadingMachine( m )( attribute )
‣ IsPlanarKneadingMachine( m )( property )

Returns: Whether m is a (planar) kneading machine.

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> PlanarEmbeddingOfKneadingMachine(M);
[ 1, 2 ]
gap> IsPlanarKneadingMachine(GrigorchukMachine);
false

DeclareAttribute("AddingElement", IsSphereMachine);

3.3-7 AddingElement
‣ AddingElement( m )( attribute )

Returns: The element generating the adding submachine.

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.

gap> f := FreeGroup("a","b","c","x","y","z");;
gap> AssignGeneratorVariables(f);
gap> m := AsSphereMachine(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 := 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

DeclareSynonym("IsPolynomialSphereMachine",IsSphereMachine and HasAddingElement); DeclareAttribute("AsPolynomialSphereMachine",IsFRMachine); DeclareOperation("AsPolynomialSphereMachine",[IsFRMachine,IsWord]);

3.3-8 AsPolynomialSphereMachine
‣ AsPolynomialSphereMachine( m[, adder[, relator]] )( operation )

Returns: A polynomial sphere machine.

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

If the argument is a Mealy machine, it must be planar (see IsPlanarKneadingMachine (3.3-6)). 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.

gap> M := PolynomialMealyMachine(2,[1/7],[]);
<Mealy machine on alphabet [ 1 .. 2 ] with 4 states>
gap> Mi := AsPolynomialSphereMachine(M);
# (example still broken, have to fix spider algorithm)

DeclareOperation("LiftOfConjugacyClass", [IsGroupFRMachine,IsConjugacyClassGroupRep]);

3.3-9 LiftOfConjugacyClass
‣ LiftOfConjugacyClass( m, c )( operation )

Returns: A list of conjugacy classes and multiplicities.

This command computes the preimage of the conjugacy class c by the sphere machine m, namely, it applies the wreath recursion to a representative of c and collects the products on all cycles. It returns then a list of pairs [cc,len] where cc is the conjugacy class of a product on a cycle, and len is the length of the cycle.

DeclareAttribute("ComplexConjugate", IsFRMachine); # already declared for arithmetic objects

3.3-10 ComplexConjugate
‣ ComplexConjugate( m )( operation )

Returns: An FR machine with inverted states.

This function constructs an FR machine whose generating states are the inverses of the original states. If m came from a complex rational map f(z), this would construct the machine of the conjugate map overlinef(overline z).

gap> a := PolynomialSphereMachine(2,[1/7]);
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f4) on <object>/[ f4*f3*f2*f1 ]>
gap> Display(a);
 G  |            1            2
----+---------------+------------+
 f1 | f1^-1*f2^-1,2   f3*f2*f1,1
 f2 |          f1,1       <id>,2
 f3 |          f2,1       <id>,2
 f4 |          f4,2       <id>,1
----+---------------+------------+
Adding element: FRElement(...,f4)
Relator: f4*f3*f2*f1
gap> Display(ComplexConjugate(a));
 G  |            1                     2
----+---------------+---------------------+
 f1 | f1*f2*f3*f4,2   f4^-1*f2^-1*f1^-1,1
 f2 |          f1,1      <identity ...>,2
 f3 |          f2,1      <identity ...>,2
 f4 |          f4,2      <identity ...>,1
----+---------------+---------------------+
Adding element: FRElement(...,f4)
Relator: f1*f2*f3*f4
gap> ExternalAngle(a);
{2/7}
gap> ExternalAngle(ComplexConjugate(a));
{6/7}

DeclareOperation("RotatedSpider", [IsPolynomialSphereMachine]); DeclareOperation("RotatedSpider", [IsPolynomialSphereMachine, IsInt]);

3.3-11 RotatedSpider
‣ RotatedSpider( m[, p] )( operation )

Returns: A polynomial FR machine with rotated spider at infinity.

This function constructs an isomorphic polynomial FR machine, but with a different numbering of the spider legs at infinity. This rotation is accomplished by conjugating by adder^p, where adder is the adding element of m, and p, the rotation parameter, is 1 by default.

gap> a := PolynomialSphereMachine(3,[1/4]);
<FR machine with alphabet [ 1, 2, 3 ] and adder FRElement(...,f3) on <object>/[ f3*f2*f1 ]>
gap> Display(a);
 G  |      1        2         3
----+---------+--------+---------+
 f1 | f1^-1,2   <id>,3   f2*f1,1
 f2 |    f1,1   <id>,2    <id>,3
 f3 |    f3,3   <id>,1    <id>,2
----+---------+--------+---------+
Adding element: FRElement(...,f3)
Relator: f3*f2*f1
gap> Display(RotatedSpider(a));
 G  |     1            2               3
----+--------+------------+---------------+
 f1 | <id>,2   f2*f1*f3,3   f3^-1*f1^-1,1
 f2 | <id>,1       <id>,2   f3^-1*f1*f3,3
 f3 |   f3,3       <id>,1          <id>,2
----+--------+------------+---------------+
Adding element: FRElement(...,f3)
Relator: f3*f2*f1
gap> ExternalAngle(a);
{3/8}
gap> List([1..10],i->ExternalAngle(RotatedSpider(a,i)));
[ {7/8}, {1/4}, {7/8}, {1/4}, {7/8}, {1/4}, {7/8}, {1/4}, {7/8}, {1/4} ]

DeclareAttribute("KneadingSequence", IsRat);

3.3-12 KneadingSequence
‣ KneadingSequence( angle )( attribute )

Returns: The kneading sequence associated with angle.

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" ]

DeclareGlobalFunction("AllInternalAddresses");

3.3-13 AllInternalAddresses
‣ AllInternalAddresses( n )( attribute )

Returns: Internal addresses of maps with period up to n.

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 ] ] ]

DeclareGlobalFunction("ExternalAnglesRelation");

3.3-14 ExternalAnglesRelation
‣ ExternalAnglesRelation( degree, n )( function )

Returns: An equivalence relation on the rationals.

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 ] ]

DeclareGlobalFunction("ExternalAngle");

3.3-15 ExternalAngle
‣ ExternalAngle( machine )( function )

Returns: The external angle identifying machine.

In case machine is the sphere 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 (3.3-14).

gap> ExternalAngle(PolynomialSphereMachine(2,[1/7])); # the rabbit
{2/7}
gap> Elements(last);
[ 1/7, 2/7 ]

3.4 Automorphisms of sphere machines

Consider a sphere group G and its automorphism group A. If M is a sphere machine for the group G, then pre- and post-composition by automorphisms in A gives new sphere machines. The set of such sphere machines is naturally described by a machine for the group A. DeclareOperation("AutomorphismVirtualEndomorphism",[IsGroupHomomorphism]); DeclareOperation("AutomorphismSphereMachine",[IsSphereMachine]);

3.4-1 AutomorphismVirtualEndomorphism
‣ AutomorphismVirtualEndomorphism( v )( attribute )
‣ AutomorphismSphereMachine( m )( attribute )

Returns: A description of the pullback map on Teichmüller space.

Let m be a sphere 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> SetP1Points(PMCOMPLEX);
gap> z := Indeterminate(@IMG.field);;
gap> # a Sierpinski carpet map without multicurves
gap> m := SphereMachine((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> AutomorphismSphereMachine(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 := PolynomialSphereMachine(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
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 Bib Ind

generated by GAPDoc2HTML