112 The VKCURVE functions

We document here the various functions which are used in Van Kampen' s algorithm as described in the introduction.

Subsections

  1. Discy
  2. ResultantMat
  3. NewtonRoot
  4. SeparateRootsInitialGuess
  5. SeparateRoots
  6. LoopsAroundPunctures
  7. FollowMonodromy
  8. ApproxFollowMonodromy
  9. LBraidToWord
  10. BnActsOnFn
  11. VKQuotient
  12. Display for presentations
  13. ShrinkPresentation

112.1 Discy

Discy( Mvp p )

The input should be an Mvp in x and y, with rational coefficients. The function returns the discriminant of p with respect to x (an Mvp in y); it uses interpolation to reduce the problem to discriminants of univariate polynomials, and works reasonably fast (not hundreds of times slower than MAPLE...).

    gap> Discy(x+y^2+x^3+y^3);      
    4+27y^4+54y^5+27y^6

112.2 ResultantMat

ResultantMat( v, w )

v and w are vectors representing coefficients of two polynomials. The function returns Sylvester matrix for these two polynomials (whose determinant is the resultant of the two polynomials). It is used internally by Discy.

    gap>  p:=x+y^2+x^3+y^3; 
    x+y^2+x^3+y^3
    gap>  c:=Coefficients(p,"x");
    [ y^2+y^3, 1, 0, 1 ]
    gap> PrintArray(ResultantMat(c,Derivative(c)));
    [[      1,       0,       1, y^2+y^3,       0],
     [      0,       1,       0,       1, y^2+y^3],
     [      3,       0,       1,       0,       0],
     [      0,       3,       0,       1,       0],
     [      0,       0,       3,       0,       1]]
    gap> DeterminantMat(ResultantMat(c,Derivative(c)));
    4+27y^4+54y^5+27y^6

112.3 NewtonRoot

NewtonRoot(p,initial,precision)

Here p is a list of Complex rationals representing the coefficients of a polynomial. The function computes a complex rational approximation to a root of p, guaranteed of distance closer than precision (a rational) to an actual root. The first approximation used is initial. If initial is in the attraction basin of a root of p, the one approximated. A possibility is that the Newton method starting from initial does not converge (the number of iterations after which this is decided is controlled by VKCURVE.NewtonLim); then the function returns false. Otherwise the function returns a pair: the approximation found, and an upper bound of the distance between that approximation and an actual root. The upper bound returned is a power of 10, and the approximation denominator' s is rounded to a power of 10, in order to return smaller-sized rational result as much as possible. The point of returning an upper bound is that it is usually better than the asked-for precision. For the precision estimate a good reference is HSS01.

    gap> p:=List([1,0,1],Complex); # p=x\^2+1
    [ 1, 0, 1 ]
    gap> NewtonRoot(p,Complex(1,1),10^-7);  
    [ I, 1/1000000000 ]
    # obtained precision is actually 10\^-9
    gap> NewtonRoot(p,Complex(1),10^-7); 
    false
    # here Newton does not converge
    

112.4 SeparateRootsInitialGuess

SeparateRootsInitialGuess(p, v, safety)

Here p is a list of complex rationals representing the coefficients of a polynomial, and v is a list of approximations to roots of p which should lie in different attraction basins for Newton' s method. The result is a list l of complex rationals representing approximations to the roots of p (each element of l is the root in whose attraction basin the corresponding element of v lies), such that if d is the minimum distance between two elements of l, then there is a root of p within radius d/(2*safety) of any element of l. When the elements of v do not lie in different attraction basins (which is necessarily the case if p has multiple roots), false is returned.

    gap> p:=List([1,0,1],Complex);
    [ 1, 0, 1 ]
    gap> SeparateRootsInitialGuess(p,[Complex(1,1),Complex(1,-1)],100);
    [ I, -I ]
    gap> SeparateRootsInitialGuess(p,[Complex(1,1),Complex(2,1)],100);
    false # 1+I and 2+I not in different attraction basins

112.5 SeparateRoots

SeparateRoots(p, safety)

Here p is a univariate Mvp with rational or complex rational coefficients, or a vector of rationals or complex rationals describing the coefficients of such a polynomial. The result is a list l of complex rationals representing approximations to the roots of p, such that if d is the minimum distance between two elements of l, then there is a root of p within radius d/(2*safety) of any element of l. This is not possible when p has multiple roots, in which case false is returned.

    gap> SeparateRoots(x^2+1,100);
    [ I, -I ]
    gap> SeparateRoots((x-1)^2,100);
    false
    gap> SeparateRoots(x^3-1,100);  
    [ -1/2-108253175473/125000000000I, 1, -1/2+108253175473/125000000000I]

112.6 LoopsAroundPunctures

LoopsAroundPunctures(points)

The input is a list of complex rational numbers. The function computes piecewise-linear loops representing generators of the fundamental group of the complement of points in the complex line.

    gap> LoopsAroundPunctures([Complex(0,0)]);
    rec(
      points := [ -I, -1, 1, I ],
      segments := [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ] ],
      loops := [ [ 4, -3, -1, 2 ] ] )

The output is a record with three fields. The field points contains a list of complex rational numbers. The field segments contains a list of oriented segments, each of them encoded by the list of the positions in points of its two endpoints. The field loops contains a list of list of integers. Each list of integers represents a piecewise linear loop, obtained by concatenating the elements of segments indexed by the integers (a negative integer is used when the opposed orientation of the segment has to be taken).

112.7 FollowMonodromy

FollowMonodromy(r,segno,print)

This function computes the monodromy braid of the solution in x of an equation P(x,y)=0 along a segment [y0,y1]. It is called by FundamentalGroup, once for each of the segments. The first argument is a global record, similar to the one produced by FundamentalGroup (see the documentation of this function) but only containing intermediate information. The second argument is the position of the segment in r.segments. The third argument is a print function, determined by the printlevel set by the user (typically, by calling FundamentalGroup with a second argument).

The function returns an element of the ambient braid group r.B.

This function has no reason to be called directly by the user, so we do not illustrate its behavior. Instead, we explain what is displayed on screen when the user sets the printlevel to 2.

What is quoted below is an excerpt of what is displayed on screen during the execution of

    gap>  FundamentalGroup((x+3*y)*(x+y-1)*(x-y),2);

    <1/16>    1 time=          0   ?2?1?3
    <1/16>    2 time=      0.125   R2. ?3
    <1/16>    3 time=    0.28125   R2. ?2
    <1/16>    4 time=   0.453125   ?2R1?2
    <1/16>    5 time=   0.578125   R1. ?2
    ======================================
    =    Nontrivial braiding = 2         =
    ======================================
    <1/16>    6 time=   0.734375   R1. ?1
    <1/16>    7 time=    0.84375   . ?0. 
    <1/16>    8 time=   0.859375   ?1R0?1
    # The following braid was computed by FollowMonodromy in 8 steps.
    monodromy[1]:=B(2);
    # segment 1/16 Time=0.1sec

FollowMonodromy computes its results by subdividing the segment into smaller subsegments on which the approximations are controlled. It starts at one end and moves subsegment after subsegment. A new line is displayed at each step.

The first column indicates which segment is studied. In the example above, the function is computing the monodromy along the first segment (out of 16). This gives a rough indication of the time left before completion of the total procedure. The second column is the number of iterations so far (number of subsegments). In our example, FollowMonodromy had to cut the segment into 8 subsegments. Each subsegment has its own length. The cumulative length at a given step, as a fraction of the total length of the segment, is displayed after time=. This gives a rough indication of the time left before completion of the computation of the monodromy of this segment. The segment is completed when this fraction reaches 1.

The last column has to do with the piecewise-linear approximation of the geometric monodromy braid. It is subdivided into sub-columns for each string. In the example above, there are three strings. At each step, some strings are fixed (they are indicated by . in the corresponding column). A symbol like R5 or ?3 indicates that the string is moving. The exact meaning of the symbol has to do with the complexity of certain sub-computations.

As some strings are moving, it happens that their real projections cross. When such a crossing occurs, it is detected and the corresponding element of Bn is displayed on screen (Nontrivial braiding =...) The monodromy braid is the product of these elements of Bn, multiplied in the order in which they occur.

112.8 ApproxFollowMonodromy

ApproxFollowMonodromy(r,segno,pr)

This function computes an approximation of the monodromy braid of the solution in x of an equation P(x,y)=0 along a segment [y0,y1]. It is called by FundamentalGroup, once for each of the segments. The first argument is a global record, similar to the one produced by FundamentalGroup (see the documentation of this function) but only containing intermediate information. The second argument is the position of the segment in r.segments. The third argument is a print function, determined by the printlevel set by the user (typically, by calling FundamentalGroup with a second argument).

Contrary to FollowMonodromy, ApproxFollowMonodromy does not control the approximations; it just uses a heuristic for how much to move along the segment between linear braid computations, and this heuristic may possibly fail. However, we have not yet found an example for which the result is actually incorrect, and thus the existence is justified by the fact that for some difficult computations, it is sometimes many times faster than FollowMonodromy. We illustrate its typical output when printlevel is 2.

   VKCURVE.monodromyApprox:=true;
    FundamentalGroup((x+3*y)*(x+y-1)*(x-y),2);

....

    5.3.6. ***rejected
    4.3.6.<15/16>mindist=3 step=1/2 total=0 logdisc=1 ***rejected
    3.3.4.<15/16>mindist=3 step=1/4 total=0 logdisc=1 ***rejected
    3.3.4.<15/16>mindist=3 step=1/8 total=0 logdisc=1 ***rejected
    3.3.3.<15/16>mindist=3 step=1/16 total=0 logdisc=1
    3.2.3.<15/16>mindist=2.92 step=1/16 total=1/16 logdisc=1
    3.3.3.<15/16>mindist=2.83 step=1/16 total=1/8 logdisc=1
    3.2.3.<15/16>mindist=2.75 step=1/16 total=3/16 logdisc=1
    3.3.3.<15/16>mindist=2.67 step=1/16 total=1/4 logdisc=1
    ======================================
    =    Nontrivial braiding = 2         =
    ======================================
    3.2.3.<15/16>mindist=2.63 step=1/16 total=5/16 logdisc=1
    3.2.3.<15/16>mindist=2.75 step=1/16 total=3/8 logdisc=1
    3.3.3.<15/16>mindist=2.88 step=1/16 total=7/16 logdisc=1
    3.2.3.<15/16>mindist=3 step=1/16 total=1/2 logdisc=1
    3.3.3.<15/16>mindist=3.13 step=1/16 total=9/16 logdisc=1
    3.2.3.<15/16>mindist=3.25 step=1/16 total=5/8 logdisc=1
    3.3.3.<15/16>mindist=3.38 step=1/16 total=11/16 logdisc=1
    3.2.3.<15/16>mindist=3.5 step=1/16 total=3/4 logdisc=1
    3.2.3.<15/16>mindist=3.63 step=1/16 total=13/16 logdisc=1
    3.2.3.<15/16>mindist=3.75 step=1/16 total=7/8 logdisc=1
    3.2.3.<15/16>mindist=3.88 step=1/16 total=15/16 logdisc=1 ***up
    # Monodromy error=0
    # Minimal distance=2.625
    # Minimal step=1/16=-0.05208125+0.01041875I
    # Adaptivity=10
    monodromy[15]:=B(2);
    # segment 15/16 Time=0.2sec

Here at each step the following information is displayed: first, how many iterations of the Newton method were necessary to compute each of the 3 roots of the current polynomial f(x,y0) if we are looking at the point y0 of the segment. Then, which segment we are dealing with (here the 15th of 16 in all). Then the minimum distance between two roots of f(x,y0) (used in our heuristic). Then the current step in fractions of the length of the segment we are looking at, and the total fraction of the segment we have done. Finally, the decimal logarithm of the absolute value of the discriminant at the current point (used in the heuristic). Finally, an indication if the heuristic predicts that we should halve the step (***rejected) or that we may double it (***up).

The function returns an element of the ambient braid group r.B.

112.9 LBraidToWord

LBraidToWord(v1,v2,B)

This function converts the linear braid given by v1 and v2 into an element of the braid group B.

    gap> B:=Braid(CoxeterGroupSymmetricGroup(3)); 
    function ( arg ) ... end
    gap> i:=Complex(0,1);
    I
    gap> LBraidToWord([1+i,2+i,3+i],[2+i,1+2*i,4-6*i],B);
    1

The list v1 and v2 must have the same length, say n. The braid group B should be the braid group on n strings, in its CHEVIE implementation. The elements of v1 (resp. v2) should be n distinct complex rational numbers. We use the Brieskorn basepoint, namely the contractible set C+iV where C is a real chamber; therefore the endpoints need not be equal (hence, if the path is indeed a loop, the final endpoint must be given). The linear braid considered is the one with affine strings connecting each point in v1 to the corresponding point in v2. These strings should be non-crossing. When the numbers in v1 (resp. v2) have distinct real parts, the real picture of the braid defines a unique element of B. When some real parts are equal, we apply a lexicographical desingularization, corresponding to a rotation of v1 and v2 by an arbitrary small positive angle.

112.10 BnActsOnFn

BnActsOnFn(braid b,Free group F)

This function implements the Hurwitz action of the braid group on n strings on the free group on n generators, where the standard generator σi of Bn fixes the generators f1,...,fn, except fi which is mapped to fi+1 and fi+1 which is mapped to fi+1-1fifi+1.

    gap> B:=Braid(CoxeterGroupSymmetricGroup(3));
    function ( arg ) ... end
    gap> b:=B(1);
    1
    gap> BnActsOnFn(b,FreeGroup(3));
    GroupHomomorphismByImages( Group( f.1, f.2, f.3 ), Group( f.1, f.2, f.3 ), 
    [ f.1, f.2, f.3 ], [ f.2, f.2^-1*f.1*f.2, f.3 ] )
    gap> BnActsOnFn(b^2,FreeGroup(3));
    GroupHomomorphismByImages( Group( f.1, f.2, f.3 ), Group( f.1, f.2, f.3 ), 
    [ f.1, f.2, f.3 ], [ f.2^-1*f.1*f.2, f.2^-1*f.1^-1*f.2*f.1*f.2, f.3 ] )

The second input is the free group on n generators. The first input is an element of the braid group on n strings, in its CHEVIE implementation.

112.11 VKQuotient

VKQuotient(braids,[bad])

The input braid is a list of braids b1,...,bd, living in the braid group on n strings. Each bi defines by Hurwitz action an automorphism φi of the free group Fn. The function return the group defined by the abstract presentation:

< f1,...,fn | ∀ i,j, φi(fj)=fj >

The optional second argument bad is another list of braids c1,...,ce (representing the monodromy around bad roots of the discriminant). For each ck, we denote by ψk the corresponding Hurwitz automorphism of Fn. When a second argument is supplied, the function returns the group defined by the abstract presentation:

< f1,...,fn,g1,...,gk | ∀ i,j,k, φi(fj)=fj, ψk(fj) gk=gk fj >

    gap> B:=Braid(CoxeterGroupSymmetricGroup(3));
    function ( arg ) ... end
    gap> b1:=B(1)^3; b2:=B(2);                   
    1.1.1
    2
    gap> g:=VKQuotient([b1,b2]);                 
    Group( f.1, f.2, f.3 )
    gap>  last.relators;  
    [ f.2^-1*f.1^-1*f.2*f.1*f.2*f.1^-1, IdWord,
      f.2^-1*f.1^-1*f.2^-1*f.1*f.2*f.1, f.3*f.2^-1, IdWord, f.3^-1*f.2 ]
    gap> p:=PresentationFpGroup(g);Display(p);
    << presentation with 3 gens and 4 rels of total length 16 >>
    1: c=b
    2: b=c
    3: bab=aba
    4: aba=bab
    gap> SimplifyPresentation(p);Display(p);
    #I  there are 2 generators and 1 relator of total length 6
    1: bab=aba

112.12 Display for presentations

Display(p)

Displays the presentation p in a compact form, using the letters abc... for the generators and ABC... for their inverses. In addition the program tries to show relations in "positive" form, i.e. as equalities between words involving no inverses.

    gap> F:=FreeGroup(2);;
    gap> p:=PresentationFpGroup(F/[F.2*F.1*F.2*F.1^-1*F.2^-1*F.1^-1]);
    << presentation with 2 gens and 1 rels of total length 6 >>
    gap> Display(p);
    1: bab=aba
    gap> PrintRec(p);
    rec(
      isTietze           := true,
      operations         := PresentationOps,
      generators         := [ f.1, f.2 ],
      tietze             := [ 2, 1, 6, [ f.1, f.2 ], [ 2, 1, 0, -1, -2 ], 
      [ [ -2, -1, 2, 1, 2, -1 ] ], [ 6 ], [ 0 ], 0, false, 0, 0, 0, 0, 
      [ 2, 1, 6 ], 0, 0, 0, 0, 0 ],
      components         := [ 1, 2 ],
      1                  := f.1,
      2                  := f.2,
      nextFree           := 3,
      identity           := IdWord,
      eliminationsLimit  := 100,
      expandLimit        := 150,
      generatorsLimit    := 0,
      lengthLimit        := infinity,
      loopLimit          := infinity,
      printLevel         := 1,
      saveLimit          := 10,
      searchSimultaneous := 20,
      protected          := 0 )

112.13 ShrinkPresentation

ShrinkPresentation(p [,tries])

This is our own program to simplify group presentations. We have found heuristics which make it somewhat more efficient than GAP3' s programs SimplifiedFpGroup and TzGoGo, but the algorithm depends on random numbers so is not reproducible. The main idea is to rotate relators between calls to GAP3 functions. By default 1000 such rotations are tried (unless the presentation is so small that less rotations exhaust all possible ones), but the actual number tried can be controlled by giving a second parameter tries to the function. Another useful tool to deal with presentations is TryConjugatePresentation described in the utility functions.

    gap> DisplayPresentation(p);
    1: ab=ba
    2: dbd=bdb
    3: bcb=cbc
    4: cac=aca
    5: adca=cadc
    6: dcdc=cdcd
    7: adad=dada
    8: Dbdcbd=cDbdcb
    9: adcDad=dcDadc
    10: dcdadc=adcdad
    11: dcabdcbda=adbcbadcb
    12: caCbdcbad=bdcbadBcb
    13: cbDadcbad=bDadcbadc
    14: cdAbCadBc=bdcAbCdBa
    15: cdCbdcabdc=bdcbadcdaD
    16: DDBcccbdcAb=cAbCdcBCddc
    17: CdaBdbAdcbCad=abdcAbDadBCbb
    18: bdbcabdcAADAdBDa=cbadcbDadcBDABDb
    19: CbdbadcDbbdCbDDadcBCDAdBCDbdaDCDbdcbadcBCDAdBCDBBdacDbdccb
        =abdbcabdcAdcbCDDBCDABDABDbbdcbDadcbCDAdBCabDACbdBadcaDbAdd
    gap> ShrinkPresentation(p);   
    #I  there are 4 generators and 19 relators of total length 332
    #I  there are 4 generators and 17 relators of total length 300
    #I  there are 4 generators and 17 relators of total length 282
    #I  there are 4 generators and 17 relators of total length 278
    #I  there are 4 generators and 16 relators of total length 254
    #I  there are 4 generators and 15 relators of total length 250
    #I  there are 4 generators and 15 relators of total length 248
    #I  there are 4 generators and 15 relators of total length 246
    #I  there are 4 generators and 14 relators of total length 216
    #I  there are 4 generators and 13 relators of total length 210
    #I  there are 4 generators and 13 relators of total length 202
    #I  there are 4 generators and 13 relators of total length 194
    #I  there are 4 generators and 12 relators of total length 174
    #I  there are 4 generators and 12 relators of total length 170
    #I  there are 4 generators and 12 relators of total length 164
    #I  there are 4 generators and 12 relators of total length 162
    #I  there are 4 generators and 12 relators of total length 148
    #I  there are 4 generators and 12 relators of total length 134
    #I  there are 4 generators and 12 relators of total length 130
    #I  there are 4 generators and 12 relators of total length 126
    #I  there are 4 generators and 12 relators of total length 124
    #I  there are 4 generators and 12 relators of total length 118
    #I  there are 4 generators and 12 relators of total length 116
    #I  there are 4 generators and 11 relators of total length 100
    gap> DisplayPresentation(p);
    1: ba=ab
    2: dbd=bdb
    3: cac=aca
    4: bcb=cbc
    5: dAca=Acad
    6: dcdc=cdcd
    7: adad=dada
    8: dcDbdc=bdcbdB
    9: dcdadc=adcdad
    10: adcDad=dcDadc
    11: BcccbdcAb=dcbACdddc

Previous Up Next
Index

gap3-jm
23 Nov 2017