We document here the various functions which are used in Van Kampen' s algorithm as described in the introduction.
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
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
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
113.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
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]
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).
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.
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.
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.
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.
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);DisplayPresentation(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);DisplayPresentation(p);
#I there are 2 generators and 1 relator of total length 6
1: bab=aba
113.12 Display for presentations
DisplayPresentation(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> DisplayPresentation(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 )
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
gap3-jm