The main function of the **VKCURVE** package computes the fundamental group
of the complement of a complex algebraic curve in *ℂ ^{2}*, using an
implementation of the Van Kampen method (see for example C73 for a
clear and modernized account of this method).

gap> FundamentalGroup(x^2-y^3); #I there are 2 generators and 1 relator of total length 6 1: bab=aba gap> FundamentalGroup((x+y)*(x-y)*(x+2*y)); #I there are 3 generators and 2 relators of total length 12 1: cab=abc 2: bca=abc

The input is a polynomial in the two variables `x`

and `y`

, with
rational coefficients. Though approximate calculations are used at
various places, they are controlled and the final result is exact.

The output is a record which contains lots of information about the computation, including a presentation of the computed fundamental group, which is what is displayed when printing the record.

Our motivation for writing this package was to find explicit
presentations for generalized braid groups attached to certain complex
reflection groups. Though presentations were known for almost all cases,
six exceptional cases were missing (in the notations of Shephard and
Todd, these cases are *G _{24}*,

This package was developed thanks to computer resources of the Institut de Mathématiques de Jussieu in Paris. We thank the computer support team, especially Joël Marchand, for the stability and the efficiency of the working environment.

We have tried to design this package with the novice **GAP3** user in mind.
The only steps required to use it are

• Run **GAP3** 3 (the package is not compatible with **GAP3** 4).

• Make sure the packages **CHEVIE** and **VKCURVE** are loaded
(beware that we require the development version of **CHEVIE**,
`http://www.math.jussieu.fr/\~{}jmichel/chevie.html`

and not the one in
the **GAP3**.3.3.4 distribution)

• Use the function `FundamentalGroup`

, as demonstrated in the above
examples.

If you are not interested in the details of the algorithm, and if
`FundamentalGroup`

gives you satisfactory answers in a reasonable time,
then you do not need to read this manual any further.

We use our own package for multivariate polynomials which is more
effective, for our purposes, than the default in **GAP3** 3 (see `Mvp`

).
When **VKCURVE** is loaded, the variables `x`

and `y`

are pre-defined as
`Mvp`

s; one can also use **GAP3** polynomials (which will be converted to
`Mvp`

s).

The implementation uses `Decimal`

numbers, `Complex`

numbers and braids as
implemented in the (development version of the) package **CHEVIE**, so
**VKCURVE** is dependent on this package.

To implement the algorithms, we needed to write auxiliary facilities, for instance find zeros of complex polynomials, or work with piecewise linear braids, which may be useful on their own. These various facilities are documented in this manual.

Before discussing our actual implementation, let us give an informal
summary of the mathematical background. Our strategy is adapted from the
one originally described in the 1930's by Van Kampen. Let *C* be an
affine algebraic curve, given as the set of zeros in *ℂ ^{2}* of a
non-zero reduced polynomial

P= α_{0}(y)x^{n} + α_{1}(y) x^{n-1} + ... + α_{n-1}(y) x
+ α_{n}(y), |

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

`VKQuotient`

) can be used to deal with bad roots of the discriminant.
This algorithm is implemented in the following way.

• As input, we have a polynomial *P*. The polynomial is reduced if
it was not.

• The discriminant *Δ* of *P* with respect to *x* is computed.
It is a polynomial in *y*.

• The roots of *Δ* are approximated, via the following
procedure. First, we reduce *Δ* and get *Δ _{red}* (generating
the radical of the ideal generated by

`SeparateRoots`

(which implements Newton's method).

• Loops around these roots are computed by `LoopsAroundPunctures`

.
This function first computes some sort of honeycomb, consisting of a set
*S* of affine segments, isolating the *y _{i}*. Since it makes the
computation of the monodromy more effective, each inner segment is a
fragment of the mediatrix of two roots of

• For each segment in *S*, we compute the monodromy braid obtained
by following the solutions in *x* of *P(x,y)=0* when *y* moves
along the segment. By default, this monodromy braid is computed by
`FollowMonodromy`

. The strategy is to compute a piecewise-linear braid
approximating the actual monodromy geometric braid. The approximations
are controlled. The piecewise-linear braid is constructed step-by-step,
by computations of linear pieces. As soon as new piece is constructed, it
is converted into an element of *B _{n}* and multiplied; therefore, though
the braid may consist of a huge number of pieces, the function

`FollowMonodromy`

works with constant memory. The packages also contains
a variant function `ApproxFollowMonodromy`

, which runs faster, but
without guarantee on the result (see below).

• The monodromy braids *b _{i}* corresponding to the loops

`BnActsOnFn`

and the resulting presentation of the
fundamental group is computed by `VKQuotient`

. It happens for some large
problems that the whole fundamental group process fails here, because
the braids `ShrinkBraidGeneratingSet`

which finds smaller generators for
the subgroup of `VKCURVE.shrinkBraid`

is set to `true`

(the default for this variable is
`false`

).

• Finally, the presentation is simplified by `ShrinkPresentation`

.
This function is a heuristic adaptation and refinement of the basic
**GAP3** functions for simplifying presentations. It is non-deterministic.

From the algorithmic point of view, memory should not be an issue, but
the procedure may take a lot of CPU time (the critical part being the
computation of the monodromy braids by `FollowMonodromy`

). For instance,
an empirical study with the curves *x ^{2}-y^{n}* suggests that the needed
time grows exponentially with

A global variable `VKCURVE.monodromyApprox`

controls which monodromy
function is used. The default value of this variable is `false`

, which
means that `FollowMonodromy`

will be used. If the variable is set by the
user to `true`

then the function `ApproxFollowMonodromy`

will be used
instead. This function runs faster than `FollowMonodromy`

, but the
approximations are no longer controlled. Therefore presentations obtained
while `VKCURVE.monodromyApprox`

is set to `true`

are not certified.
However, though it is likely that there exists examples for which
`ApproxFollowMonodromy`

actually returns incorrect answers, we still have
not seen one.

The second way of dealing with difficult examples is to parallelize the
computation. Since the computations of the monodromy braids for each
segment are independent, they can be performed simultaneously on
different computers. The functions `PrepareFundamentalGroup`

, `Segments`

and `FinishFundamentalGroup`

provide basic support for parallel
computing.

`FundamentalGroup(`

`curve` [, `printlevel`])

`curve` should be an `Mvp`

in `x` and `y`, or a **GAP3** polynomial in two
variables (which means a polynomial in a variable which is assumed to be
`y`

over the polynomial ring *ℚ[x]*) representing an equation *f(x,y)*
for a curve in *ℂ ^{2}*. The coefficients should be rationals, gaussian
rationals or

`Complex`

rationals. The result is a record with a certain
number of fields which record steps in the computation described in this
introduction:

gap> r:=FundamentalGroup(x^2-y^3); #I there are 2 generators and 1 relator of total length 6 1: bab=aba gap> RecFields(r); [ "curve", "discy", "roots", "dispersal", "points", "segments", "loops", "zeros", "B", "monodromy", "basepoint", "dispersal", "braids", "presentation","operations" ] gap> r.curve; x^2-y^3 gap> r.discy; X(Rationals) gap> r.roots; [ 0 ] gap> r.points; [ -I, -1, 1, I ] gap> r.segments; [ [ 1, 2 ], [ 1, 3 ], [ 2, 4 ], [ 3, 4 ] ] gap> r.loops; [ [ 4, -3, -1, 2 ] ] gap> r.zeros; [ [ 707106781187/1000000000000+707106781187/1000000000000I, -707106781187/1000000000000-707106781187/1000000000000I ], [ I, -I ], [ 1, -1 ], [ -707106781187/1000000000000+707106781187/1000000000000I, 707106781187/1000000000000-707106781187/1000000000000I ] ] gap> r.monodromy; [ (w0)^-1, w0, , w0 ] gap> r.braids; [ w0.w0.w0 ] gap> DisplayPresentation(r.presentation); 1: bab=aba

Here `r.curve`

records the entered equation, `r.discy`

its discriminant
with respect to `x`, `r.roots`

the roots of this discriminant,
`r.points`

, `r.segments`

and `r.loops`

describes loops around these
zeros as explained in the documentation of `LoopsAroundPunctures`

;
`r.zeros`

records the zeros of *f(x,y _{i})* when

`r.points`

; `r.monodromy`

records the monodromy along each of
`r.segments`

, and `r.braids`

is the resulting monodromy along the loops.
Finally `r.presentation`

records the resulting presentation (which is
what is printed by default when `r`

is printed).
The second optional argument triggers the display of information on the
progress of the computation. It is recommended to set the `printlevel`
at 1 or 2 when the computation seems to take a long time without doing
anything. `printlevel` set at 0 is the default and prints nothing; set
at 1 it shows which segment is currently active, and set at 2 it traces
the computation inside each segment.

gap> FundamentalGroup(x^2-y^3,1); # There are 4 segments in 1 loops # The following braid was computed by FollowMonodromy in 8 steps. monodromy[1]:=B(-1); # segment 1/4 Time=0sec # The following braid was computed by FollowMonodromy in 8 steps. monodromy[2]:=B(1); # segment 2/4 Time=0sec # The following braid was computed by FollowMonodromy in 8 steps. monodromy[3]:=B(); # segment 3/4 Time=0sec # The following braid was computed by FollowMonodromy in 8 steps. monodromy[4]:=B(1); # segment 4/4 Time=0sec # Computing monodromy braids # loop[1]=w0.w0.w0 #I there are 2 generators and 1 relator of total length 6 1: bab=aba

`PrepareFundamentalGroup(`

`curve`, `name`)

`VKCURVE.Segments(`

`name`[,`range`])

These functions provide a means of distributing a fundamental group
computation over several machines. The basic strategy is to write to
a file the startup-information necessary to compute the monodromy
along a segment, in the form of a partially-filled version of
the record returned by `FundamentalGroup`

. Then the monodromy along
each segment can be done in a separate process, writing again the
result to files. These results are then gathered and processed by
`FinishFundamentalGroup`

. The whole process is illustrated in an example
below. The extra argument `name` to `PrepareFundamentalGroup`

is a
prefix used to name intermediate files. One does first :

gap> PrepareFundamentalGroup(x^2-y^3,"a2"); ---------------------------------- Data saved in a2.tmp You can now compute segments 1 to 4 in different GAP sessions by doing in each of them: a2:=rec(name:="a2"); VKCURVE.Segments(a2,[1..4]); (or some other range depending on the session) Then when all files a2.xx have been computed finish by a2:=rec(name:="a2"); FinishFundamentalGroup(a2);

Then one can compute in separate sessions the monodromy along each
segment. The second argument of `Segments`

tells which segments to
compute in the current session (the default is all). An example of such
sessions may be:

gap> a2:=rec(name:="a2"); rec( name := "a2" ) gap> VKCURVE.Segments(a2,[2]); # The following braid was computed by FollowMonodromy in 8 steps. a2.monodromy[2]:=a2.B(1); # segment 2/4 Time=0.1sec gap> a2:=rec(name:="a2"); rec( name := "a2" ) gap> VKCURVE.Segments(a2,[1,3,4]); # The following braid was computed by FollowMonodromy in 8 steps. a2.monodromy[2]:=a2.B(1); # segment 2/4 Time=0.1sec

- When all segments have been computed the final session looks like:

gap> a2:=rec(name:="a2"); rec( name := "a2" ) gap> FinishFundamentalGroup(a2); 1: bab=aba

gap3-jm

19 Feb 2018