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

- Discy
- ResultantMat
- NewtonRoot
- SeparateRootsInitialGuess
- SeparateRoots
- LoopsAroundPunctures
- FollowMonodromy
- ApproxFollowMonodromy
- LBraidToWord
- BnActsOnFn
- VKQuotient
- Display for presentations
- ShrinkPresentation

`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

`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 *[y _{0},y_{1}]*. 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 *B _{n}* is displayed on screen (

`Nontrivial braiding =`

...) The
monodromy braid is the product of these elements of
`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 *[y _{0},y_{1}]*.
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,y _{0})* if we are looking at
the point

`***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

`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

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 *b _{1},...,b_{d}*, living in the
braid group on

< f_{1},...,f_{n} |
∀ i,j, φ_{i}(f_{j})=f_{j} > |

The optional second argument `bad` is another list of braids
*c _{1},...,c_{e}* (representing the monodromy around bad roots of the
discriminant). For each

< f_{1},...,f_{n},g_{1},...,g_{k} | ∀ i,j,k, φ_{i}(f_{j})=f_{j},
ψ_{k}(f_{j}) g_{k}=g_{k} f_{j} > |

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

`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 )

`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

19 Feb 2018