Calculation system for the dual graph of resolutionof the algebraic curve singularities using Risa/AsirM. Fujimoto
Department of Mathematics
Fukuoka University of Education
fujimoto@fukuoka-edu.ac.jp
M. Suzuki
Graduate School of Mathematics
Kyushu University
suzuki@math.kyushu-u.ac.jp
September 8, 2004

Abstract
In this paper, we introduce a method of generating the dual graphof the minimal normal resolution of the algebraic curve singularities.
Using factorization of polynomials over algebraic extension field, wecan calculate the dual graph from the coefficients of the given polynomial exactly. The computing process includes no approximation.
We constructed the system to generate the dual graph on Risa/Asir.
Users can get the resulting dual graph by the list form and also by thegraphical form.

1Introduction

A resolution of an algebraic curve C at a singular point p of C is said minimal
normal, if the union of the proper transform of C and the exceptional curve
E of the resolution is of normal crossing type in a neighborhood of E, and
it is “minimal” among the resolutions having this property. Usually, thegeometric configuration of the resolution is represented by a weighted graph,called the “dual graph”.
The dual graph of the minimal normal resolution of the algebraic curve
singularities is one of the most fundamental invariants in algebraic geometry.
At present, there is no computing system for the dual graphs.
Our method computes the dual graphs of the minimal normal resolutionsof the algebraic curve singularities at origin defined by polynomials in two

variables with coefficients in the algebraic extension field over the rational
number field. We can calculate the dual graph from the coefficients of thegiven polynomial exactly. The computing process includes no approximation.
In our algorithm, Newton Polygon Algorithm is used to obtain Puiseux
pairs. Newton Polygon Algorithm needs finding roots of polynomials withcoefficients in the algebraic extension field over the rational number field.
We implemented this algorithm on Risa/Asir, a computer algebra systemdeveloped at FUJITSU LABORATORIES LIMITED ([4]). Risa/Asir isgood at computing Gröbner basis and factoring polynomials over algebraic
extension fields, which was very suited to implement our algorithm.
In this paper, we show the algorithm generating the dual graph, andintroduce our system on Risa/Asir.

2Blowing Ups and Dual Graphs

We shall assume from now on that M is a non-singular projective algebraic
surface over the complex number field and E an algebraic curve on M .
Definition 1 (Normal crossing type) If each irreducible compornent of
E is non-singular and intersect each other at only one point at most, thenE is called of normal crossing type.
Definition 2 (Dual graph) For a curve E of normal crossing type, werepresent each irreducible component of E by a vertex and join the vertices
if and only if the corresponding irreducible components intersect each other.
We associate to each vertices an integer, called weight, equal to the selfintersection number of the corresponding irreducible component on M . The
weighted graph thus obtained will be called the dual graph of E.
Let C be an algebraic curve on M passing through a point P . By
replacing the point P with P1 we can construct new algebraic surface M 0 .
This operation is called blowing up at a point P . And the curve on M 0
corresponding to C \ P (resp. P1 ) is called proper transform of C (resp.
exceptional curve). The resolution of an algebraic curve at a singular point
is obtained by finitely many blowing up operations ([2]).
Following lemmas related to blowing up are well-known.
Lemma 1 The self-intersection number of the exceptional curve obtainedby a blowing up is −1.
Lemma 2 The self-intersection number N of the exceptional curve E decrease to N − 1 by a blowing up at a point of E.

From these lemmas, the dual graph relating a resolution of an algebraic
curve at a singular point is obtained.
For example, (See Definition 2)
f = y 2 − x3−3−1f = (y 2 − x3 )2 + y 5−3−2−2−2−3

PSfrag replacements

PSfrag replacements−1
f = y 2 − x3
f = (y 2 − x3 )2 + y 5−2−1−2−3Lemma 3 Let E1 , E2 , . . . , Er , Er+1 be the irreducible components of E andassume that the dual graph is of the following linear type :−n1−n2−nr

E1E2Er

Er+1

Furthermore assume that there exists a holomorphic function f on aneighborhood U in the following form.
(f ) =rXmi Ei + mr+1 Er+1 ∩ U.

i=0Then,(1) m2 , . . . , mr+1 are all multiple of m1 .
(2) Set pi = mi /m1 (1 ≤ i ≤ r + 1), then (pr+1 , pr ) are coprime eachother and the following continuous fraction expansion holds.
pr+1= nr −pr1
nr−1 −

1
nr−2 − . .

.

−

1
n1

Proof. Since (f ) · Ei = 0, we have mi+1 = ni mi − mi−1 for i = 1, 2, . . . , r,where m0 = 0. The two assertions of the lemma are immediate consequencesof these equations. Definition 3 (Intersection matrix) Let E1 , E2 , . . . , Er be the irreducible
components of E. We call
IE = ((Ei · Ej ))i,j=1,...,rthe intersection matrix of E.
PSfrag replacements
f = y 2 − x3
2The
f = (y − x3 )2 +y 5 following two lemmas can also be proved by a direct computation.
−1Lemma−2 4 The determinant det(−IE ) is invariant under the blowing ups ofthe points−3 on E. Namely, if τ : M 0 → M is a blowing up of a point P on
E, we have then det(−Iτ −1 (E) ) = det(−IE ).
Lemma 5 Assume that the dual graph is of the following type :−mr−mr−1−m1−1−n1−ns−1 −ns

We have thendet(−IE ) = pq − aq − bp,
where p, a, q, b are the natural numbers defined by the continuous fractions
p= m1 −a1
1m2 −m3 − . .

q= n1 −b.

−1
mr

1n2 −

1n3 − . .

.

−1nssatisfying(p, a) = 1, (q, b) = 1, 0 < a < p, 0 < b < q.

3

Newton Polygon Algorithm

Let f (x, y) be a polynomial
in two variables with complex coefficients. WeP
can write f (x, y) =cαβ xα y β .

Definition 4 (Newton polygon) The Newton Polygon of f is the convex
closure of set[{(α, β) + R2+ }cαβ 6=0

The Newton boundary of f is the union of compact faces of the boundaryof the Newton polygon of f .
Notice that the boundary of the Newton polygon differs from the Newton
boundary by two non-compact faces parallel to the coordinates axes.
We assume f (0, 0) = 0 and f (x, y) is not divisible by x. We choose
one among segments constructing Newton boundary, let ∆0 be the segment.
And let − µ10 be its slope. Then µ0 is a positive rational, sayµ0 =p0qoP
where p0 , q0 are coprime positive integers. Let f∆0 (x, y) = (α,β)∈∆0 cαβ xα y β
and t0 a nonzero root of f∆0 (1, t) = 0.
Next we shall substitute x = xq10 and y = xp10 (t0 + y1 ) for f (x, y). Andwe get
Xf (xq10 , xp10 (t0 + y1 )) =cαβ x1q0 α+p0 β (t0 + y1 )β= xq10 α0 +p0 β0 f1 (x1 , y1 )where (α0 , β0 ) ∈ ∆0 and f1 (x1 , y1 ) is a polynomial in x1 and y1 , not divisibleby x1 .
We now repeat the whole process, replacing f (x, y) by f1 (x1 , y1 ), andcontinue indefinitely. We obtain a sequence of positive rationals
µ0 =

p1
p2
p0, µ1 = , µ2 = , . . .
q0q1q2and complex numbers
t0 , t1 , t2 , . . .
(pi , qi ) is called Puiseux pair. Using {(pi , qi )} and {ti } we can get thePuiseux expansion of f (x, y) ([3]). The whole process is called Newton Polygon Algorithm.

4Computation of Dual Graph

Let f (x, y) be a polynomial in two variables with coefficients in the algebraic
extension field over the rational number field. Moreover we assume that thealgebraic curve C defined by f (x, y) = 0 has an isolated singularity at origin.

4.1

The method by Puiseux PairUsing Squarefree Decomposition Algorithm we can find multiple factors off ([1]). Here, we assume that f has not multiple factors.
Using Newton Polygon Algorithm we get Puiseux pairs (pi , qi ) of f until(i) Newton boundary is parallel to a coordinate axis or (ii) Newton polygon
is of following type :PSfrag replacements
f = y 2 − x32
f = (y − x3 )2 + y 5−1−2−3β1.

.
pkαNotice that in case of (ii) the proper transform of C and yk -axis intersecttransversely.
Let (p0 , q0 ), (p1 , q1 ), . . . , (pk−1 , qk−1 ), (pk , 1) be obtained Puiseux pairs.
Asshown
PSfrag replacements below, using k Puisuex pairs (p0 , q0 ), (p1 , q1 ), . . . , (pk−1 , qk−1 ) we
f = cany 2 −getx3 the dual graph for f .
232Forf = (y − x ) +y 5 each Puiseux pair (pi , qi ) of f if pi > 1 and qi > 1, then (pi , qi ) coinsides−1with (p, q) in Lemma 5. From the fact that the determinant det(−IE )is equal−2 to 1 when the algebraic curve E is locally irreducible, we get a pairof natural−3 numbers (a, b) such thatαβppikqi − aqi − bpi = 1, (pi , a) = 1, (qi , b) = 1, 0 < a < pi , 0 < b < qi ,1and we can determine m1 , m2 , . . . , mr , n1 , n2 , . . . , ns in Lemma 5 by continuous fraction expansions of pi /a, qi /b. Namely, the dual graph corresponding
to this Puiseux pair is following type :−2Bi−mr −mr−1−m1−n1−ns−1 −nsBi+1

where Bi is a branch vertex such that B0 is omitted and the weight of Bk
is −1.
If pi = 1, then the dual graph is of following type :r−1pk 1−m1−2−mr1−n−mr−1−ns−1−m1s−n−2−n1−ns−1−ns|−qi − 1
Bi−2Bi+1 |−2−2−2{z}qi −1

If qi = −21, then the dual graph is of following type :−qi − 1{z} −2−2−2−2−2qi −1Bi4.2|{zpi −1}

Bi+1

Another method for locally irreducible case

The algorithm described in 4.1 is not only used in case of locally irreducible
but also locally reducible. However, the algorithm needs factoring polynomials over algebraic extension field. In general, this computation is very
heavy.
If f is locally irreducible, there exists another algorithm for the computation of dual graph does not need factoring polynomials over algebraic
extension field. Here we introduce the another method.
Let f (x, y) be a polynomial in two variables with coefficients in the algebraic extension field L over the rational number field Q. Moreover assume
that the algebraic curve C defined by f (x, y) = 0 has an isolated singularity
at origin and is locally irreducible. Let C 0 be the proper transform of C
obtained by a blowing up, h(x, s) the defining polynomial of C 0 . Notice that
if f is locally irreducible, the exceptional curve obtained by the blowing up
intersects C 0 at only one point. Using this fact, it follows that the root ofh(0, s) is in L. Thus we can compute the intersection point without factoringpolynomials over algebraic extension field.

Step 1. For the defining polynomial f of C, compute the defining polynomial
h of the proper transform C 0 of C by a blowing up.
Step 2. Compute the intersection point P of C 0 and the exceptional curve
obtained by Step 1.
Step 3. If P is in origin, then let f = h and go to Step 1. Otherwise, forh do the coordinate transformation such that C 0 passes through origin, say
h0 .
Step 4. If the multiplicity of h0 is 1, then terminate. Otherwise, let f = h0and go to Step 1.

4.3

Implementation and Examples

In this section, we introduce some of functions on Risa/Asir, which wereimplemented by us in order to compute dual graphs.
4.3.1

roots

Let poly be a polynomial in one variable with coefficients in the algebraic
extension field over the rational number field.
roots(poly) returns the list of all roots of the polynomial poly. In thisfunction, the function af in the package ‘sp’ is used.
Example 1[0] A0=newalg(x^2-x+1);(#0)
PSfrag replacements[1] roots(81*x^4+(-18*A0)*x^2+(A0-1));
f = y 2 − x3[(#1),(-#1)]
2
f = (y − x3 )2 + y 5[2] roots(x^5+A0*x^2-1);−1[(#4),(-#4-#3-#2+#0-1),(#3),(#2),(-#0+1)]−2−34.3.2 n polygon
αβ in two variables with coefficients in the algebraic
Let poly be a polynomial
pextension field over thekrational number field.
1 returns the Newton polygon of poly. If flag is 0,n polygon(poly,flag)−mrthen the result is outputted by the list form. If flag is 1, by the list form
−mr−1
and the graphical form.
−m1−2Example 2−n1−ns−1[0] F=3*y^3+x*y^5-2*x*y+x^3*y^2+x^4+x^5+x^6*y^2$−ns[1] n_polygon(F,0);Bi+1[[[3,[0,3]],[-2,[1,1]]],[[-2,[1,1]],[1,[4,0]]]]Bi[2] n_polygon(F,1);−2−qi − 1
|
{z}
qi −1

|

{zpi −1−2}(0, 3)(1, 1)(4, 0)

4.3.3p pair

Let poly be a polynomial in two variables with coefficients in the algebraic
extension field over the rational number field.
p pair(poly,n) returns n Puisuex pairs of poly.
Example 3[0] F=((y^3+x)^2+x^5)^2+x^9*y^3+x^10$[1] p_pair(F,4);[[1,3],[9,2],[9,2],[9,1]]
4.3.4 dualgraph
PSfrag replacements
f = y 2 − x3
Let poly be a polynomial in two variables with coefficients in the algebraic
2f = (y − x3 )2 + y 5
extension field over the rational number field, C the algebraic curve defined−1by poly.
−2dualgraph(poly,flag) returns the dual graph of the minimal normal res−3
olution of the algebraic curve defined by poly. If flag is 0, then the result isαoutputted
β by the list form. If flag is 1, by the list form and the graphicalform. pkIn case
1 of locally irreducible, this function use the method of 4.2. Otherwise,function use the method of 4.1.
−mthisr−mr−1−m1 4Example−2−n1
F=((y^3+x)^2+x^5)^2+x^9*y^3+x^10$
−n[0]
s−1
[1]
−ns dualgraph(F,0);
B[[],-2,[-2,-2]]
i+1[[-2,-2,-2,-3],-2,[-2]]Bi[[-2,-2,-2,-3],-1,[-2]]−2−qi [2]− 1 dualgraph(F,1);|qi −1{z}|{z−2}

pi −1(0, 3)(1, 1)(4, 0)

Where the square in the figure is associated with the proper transform of C.

5Conclusion

We have presented the method for the computation of the dual graph. Furthermore we implemented our algorithm on Risa/Asir. This system cancompute the dual graph in both of locally irreducible case and reduciblecase. In reducible case, factoring polynomials over algebraic extension field
is needed. This computation is very heavy. However, since this factoring
function is planning to be improved on next version of Risa/Asir, the performance of our system will be also improved.

References[1] T. Becker and V. Weispfenning. Gröbner bases, Graduate Texts inMathematics 141, Springer-Verlag, 1993.
[2] E. Brieskorn and H. Knörrer. Plane Algebraic Curves, Birkhäuser Verlag, 1986.
[3] F. Kirwan. Complex Algebraic Curves, London Mathematical Society,StudentTexts 23, Cambridge Univ. Press, 1992.
[4] M. Noro and T. Takeshima. Risa/Asir – a computer algebra system,
Proc. of ISSAC’92, ACM Press, 387–396, 1992.
[5] M. Suzuki. Affine plane curves with one place at infinity, preprint.