Numerical computation of the genus of an irreducible curve within an algebraic set

Dan Bates^{∗} Chris Peterson^{†} Andrew J. Sommese^{‡}

Charles W. Wampler^{§}

March 21, 2007

Abstract

The common zero locus of a set of multivariate polynomials (with complex coefficients) determines an algebraic set. Any algebraic set can be decomposed into a union of irreducible components. Given a one dimensional irreducible component, i.e. a curve, it is useful to understand its invariants. The most important invariants of a curve are the degree, the arithmetic genus and the geometric genus (where the geometric genus denotes the genus of a desingularization of the projective closure of the curve). This article presents a numerical algorithm to compute the geometric genus of any one-dimensional irreducible component of an algebraic set. Keywords. genus, geometric genus, generic points, homotopy continuation, irreducible components, numerical algebraic geometry, polynomial system AMS Subject Classification. 65H10, 14Q05, 65E05, 14H99

1 Introduction

Let

f(x) := [ f_{1}(x_{1}, …, x_{N}) ; ⋮ ; f_{n}(x_{1}, …, x_{N}) ] = 0  (1)

∗Supported by the Institute for Mathematics and Its Applications (IMA)

†Supported by Colorado State University, NSF grant MSPA-MCS-0434351 and the Institute for Mathematics and Its Applications (IMA)

‡Supported by the Duncan Chair of the University of Notre Dame, the University of Notre Dame, NSF grant DMS-0410047 and the Institute for Mathematics and Its Applications (IMA)

§Supported by General Motors, NSF grant DMS-0410047 and the Institute for Mathematics and Its Applications (IMA)

denote a system of n polynomials belonging to ℂ[x_{1}, …, x_{N}]. Let V (f) denote the affine algebraic set

V (f) := {x ∈ ℂ^{N} | f(x) = 0} .

In this article we present a numerical method to compute the geometric genus of any irreducible one-dimensional component C of V (f), i.e., the genus g of a desingularization of the closure \overline{C} of C in ℙ^{N}. By essentially the same methodology, we may also compute the Euler characteristic of \overline{C}. The method is built around the numerical irreducible decomposition algorithm described in [5, 6, 7, 9]. The advantage of this particular numerical approach is that the procedure can be carried out on each irreducible curve component of a nonequidimensional algebraic set in situations where the components may have complicated self-intersection and may intersect other components. The algorithm bypasses the (computationally intensive) algorithms involved in symbolic primary decomposition, radical determination and desingularization. This allows the applicability of the approach to settings that are beyond the capabilities of present day symbolic algorithms on present day computational machinery. For instance, if the algebraic set defined by a set of polynomials has many irreducible components which self intersect and/or intersect other components then a symbolic approach can become very involved and may not terminate in a timely manner. The numerical approach outlined in this paper will compute the geometric genus of each irreducible curve component of an algebraic set without carrying out a primary decomposition or a desingularization. It is important to note that there are settings where a symbolic approach to the computation of the geometric genus is preferred. Indeed, there are occasions where a symbolic approach can yield results that are beyond the reach of any known numerical algorithm. As a consequence, the procedure presented in this paper complements (and eventually should be partnered with) available symbolic algorithms. In the next several paragraphs, we introduce the fundamentals of our approach, postponing a more rigorous discussion to § 2.

Let us discuss first the Euler characteristic of \overline{C}, denoted E(\overline{C}). Recall that the Euler characteristic of any irreducible complex curve is V − E + F, where V, E, F are the number of vertices, edges, and faces, resp., in a triangulation of the (two real dimensional) complex curve. We may find e(\overline{C}) by considering the map π : \overline{C} → ℙ^{1} obtained by restricting, to \overline{C}, a generic linear projection from ℙ^{N} → ℙ^{1}. The degree of this map is d := deg C, i.e., on a Zariski-open subset of ℙ^{1}, the fibers of π consist of d isolated points. The points of \overline{C} where the differential dπ of π is zero are called branchpoints, denoted B, and their images, π(B) are called ramification points, of which there are a finite number, say M. The fiber above a ramification point may contain fewer than d isolated points: let the number over the i-th ramification point be ν_{i}. Suppose T is a triangulation of ℙ^{1} having V vertices, E edges, and F faces, such that T includes the ramification points among its vertices. Then π^{−1}(T) will be a triangulation of \overline{C} having de edges and df faces, but only dV − ∑_{i=1}^{M}(d − ν_{i}) vertices. Since e(ℙ^{1}) = V − E + F = 2, we have

e(\overline{C}) = (dV − ∑_{i=1}^{M}(d − ν_{i})) − dE + dF = 2d − ∑_{i=1}^{M}(d − ν_{i}).  (2)

Thus, we may compute e(\overline{C}) by finding the ramification points and determining the number of points in the fiber over each of these.

The geometric genus of the desingularization of \overline{C} can be found in a similar fashion. The desingularization of \overline{C} is a smooth algebraic curve Ĉ with a proper, generically one-to-one, algebraic map ϕ : Ĉ → \overline{C}. Let us denote by q : Ĉ → ℙ^{1} the composition π ∘ ϕ, where π is a generic linear projection as in the previous paragraph. Then, exactly as above, we have

e(Ĉ) = 2d − ∑_{i=1}^{M′}(d − γ_{i}),  (3)

where now the sum is over the ramification points of q and γ_{i} is the cardinality of the fiber over the i-th point. If B̂ is the set of branchpoints for q and B the branchpoints for π, we have ϕ(B̂) ⊆ B. At the common ramification points, γ_{i} and ν_{i} may differ. The difference is that over the neighborhood of a ramification point, \overline{C} is a union of punctured disks plus the ν_{i} points over the ramification point, whereas for Ĉ the disks have been separated, so γ_{i} ≥ ν_{i}. The geometric genus, g, i.e., the number of topological holes, is related to the Euler characteristic, e, as 2 − 2g = e, so using (3) and solving for g, one obtains

g(Ĉ) = 1 − d + \frac{1}{2} ∑_{i=1}^{M}(d − γ_{i}).  (4)

From these considerations, one sees that the two main computational tasks to obtain the genus are: (1) find the ramification points of q, and (2) determine the number of disks, γ_{i}, above each. We wish to do this knowing the curve C only from evaluations of f and its derivatives. At first sight, the following facts appear troublesome: C is often singular; C might have multiplicity greater than one; and C has special nonreduced points where other components of V (f) meet C. Fortunately, as we shall show, numerical methods can be structured to compute a finite set of points that includes the ramification points and to determine the number of disks γ above each. In this regard, it is inconsequential if we include in the analysis a finite number of points that are not ramification points, as such points will have d disks and therefore contribute nothing to the genus.

The remainder of this paper is organized as follows. In § 2, we give a more rigorous treatment of genus and Euler characteristic. Then, in § 3, we give a prescription for a numerical algorithm for computing the genus, using techniques from numerical algebraic geometry. In § 4, we give the results of our numerical method on an example in which the curve in question is traced out by a mechanism.

2 The Hurwitz formula

Throughout this article, we work over the complex numbers, e.g., when we say a set is an algebraic curve, we mean a complex algebraic curve. Recall that an algebraic curve is a quasiprojective algebraic set with all components having dimension one.

We start with the classical Hurwitz formula relating the genus of a curve to the genus of the image of the curve under a finite-to-one algebraic map. Given an holomorphic map h : Δ → ℂ from a disk Δ around the origin in ℂ to ℂ, we define the local branch order of h at 0 to be the degree of the first nonzero term in the Taylor series of h at 0.

Now consider an holomorphic map ψ : X → Y from a one-dimensional complex manifold X to a one dimensional complex manifold Y. If ψ is nonconstant in a neighborhood of a point x ∈ X, we can define the local branch order of ψ at x by choosing local coordinates at x and ψ(x). We define ρ_{x}(ψ), or ρ_{x} when the map ψ is clear from the context, to be one less than the local branch order of ψ at x. Note that ρ_{x} is the order of the zero of the differential dψ at x.

Theorem 1 (Hurwitz Theorem [1]). Let ψ : X → Y denote a generically dto-one map from a smooth irreducible compact curve X of genus g(X) onto a compact curve Y of genus g(Y). Then

2g(X) − 2 = d(2g(Y) − 2) + ρ,

where ρ = ∑_{x∈B} ρ_{x} with B equal to the branch points of ψ, i.e., the finite set of

points at which dψ is zero.

Remark 2. There is a simple monodromy interpretation of ρ_{x} in the above theorem. Given x ∈ B, we may choose local coordinates z and w, with z(x) = 0 for a neighborhood of x and w(ψ(x)) = 0 for a neighborhood of ψ(x), such that w = z^{ρ_{x}+1}. In particular choose a coordinate zero at ψ(x) with the unit disk Δ_{1} an open set around ψ(x) and with π(B) ∩ Δ_{2} = ψ(x) for a disk Δ_{2} of radius strictly smaller than the radius of Δ_{1}. For any point τ ∈ Δ_{2} carry out the monodromy transformation T : ψ^{−1}(τ) → ψ^{−1}(τ) around the circle going through τ. This breaks up ψ^{−1}(τ) into γ sets, one for each point in the fiber ψ^{−1}(τ). We define

ρ_{ψ(x)} := ∑_{y∈ψ^{−1}(τ)∩B} ρ_{y} = ∑_{y∈ψ^{−1}(τ)} ρ_{y} = d − γ.

That is, we define the contribution ρ_{ψ(x)} for a ramification point ψ(x) as the sum of the contributions for all the branchpoints in its fiber. Then, since the contribution of a regular point is zero, this is the sum of the contributions of all points in its fiber, which comes to d − γ.

We need the extension of the Hurwitz formula for maps from a singular curve onto a smooth curve. To do this we need the classical uniformization theorem, e.g., [9, Corollary A.3.3].

Theorem 3 (Uniformization). Let X denote an algebraic curve. Given x ∈ X, there exist a finite number, κ, of holomorphic maps {ϕ_{i} : Δ_{1} → X |i = 1, …, κ} of the unit disk Δ_{1} to X such that:

1. ϕ_{i}(0) = x for all i and ϕ_{i}(Δ_{1}) ∩ ϕ_{j}(Δ_{1}) = x for i ≠ j;

2. ϕ_{i} gives a biholomorphism from Δ_{1} \ {0} to its image in X;

3. ⋃_{i=1}^{κ} ϕ_{i}(Δ_{1}) is a neighborhood of x ∈ X.

In short, a small enough punctured neighborhood of x is a union of disjoint punctured disks.

One consequence of this is that X has a well defined number of irreducible components locally, i.e., in the notation of Theorem 3, this number is κ for the point x ∈ X. We use the notation κ_{x}(X) (or simply κ_{x} when X is clear from the context) for this integer. To see how this number comes into calculations, here is a simple lemma. We let e(W) denote the Euler characteristic of a space.

Lemma 4. Let p : X → X be a desingularization map from a smooth projective curve onto a compact curve X, i.e., X is smooth and projective and the map from X \ p^{−1}(Sing(X)) → X \ Sing(X) induced by p is a biholomorphism. Then

e(X) = e(X) + ∑_{x∈Sing(X)}(κ_{x} − 1).

To deal with local contributions to the ramification, we first define it for a map between punctured disks and then use the local uniformization theorem to define the local ramification.

Let ψ : X → Y denote a finite-to-one algebraic map from an irreducible compact algebraic curve X onto a smooth algebraic curve Y. Let x ∈ X with y := ψ(x) ∈ Y. By the one-dimensional uniformization theorem, Theorem 3, there exist a finite number of maps ϕ_{i} : Δ_{1} → X satisfying the properties of the Theorem. Consider the map q_{i} : Δ_{1} → Y obtained by composing ϕ_{i} with ψ. We see that there is a well-defined local contribution to the ramification ρ_{x}(q_{i}).

We define ρ_{x}(ψ) to be the sum ∑_{i=1}^{κ_{x}} ρ_{x}(q_{i}).

Let ψ : X → Y denote a nonconstant holomorphic map from an irreducible germ at x of a complex curve to a germ of a smooth complex curve at y = ψ(x). The map ψ gives rise to a map between the desingularization of X and Y. We define ρ_{x} as the corresponding local ρ for the map between the desingularizations. Since the singularities of curves are isolated, computing the monodromy breakup of a ψ fiber as in Remark 2 by going around the boundary of a disk in Y containing the images of no branchpoints but x, we can compute ρ_{x}. Let ϕ : X̂ → X be the desingularization of X and let q := ϕ ∘ ψ be the composed map. Note that the degree of q and ψ is the same and that ρ_{x}(ψ) is exactly the sum of the numbers ρ_{y}(q) over the points y ∈ \overline{X} that map to x. Thus with the geometric genus g(X) of X equal to g(X̂) we have the following.

Theorem 5. Let ψ : X → Y denote a generically d-to-one map from a compact irreducible compact curve X of genus g(X) onto a smooth compact curve Y of genus g(Y). Then

2g(X) − 2 = d(2g(Y) − 2) + ρ,

where ρ = ∑_{x∈B} ρ_{x} with B equal to the union of the branch points B of ψ, i.e.,

the finite set of points at which dψ is zero or X is singular.

3 The Algorithms

In what follows we do the result over ℂ, and then we talk about the extensions where the image curve is any Zariski open set in a smooth Riemann surface.

Let f(x) be as in (1), and let

Z := V (f) = ∪_{i=1}^{dim V (f)}Z_{i} = ∪_{i=1}^{dim V (f)} ∪_{j∈I_{i}} Z_{ij}

be the irreducible decomposition of V (f). Here the I_{i} are finite sets; Z_{ij} is irreducible of dimension i; and Z_{ik} is not contained in ∪_{i=1}^{dim V (f)} ∪_{j∈I\{k}} Z_{ij}. The numerical irreducible decomposition of V (f) [5, 6, 7, 9] is a set of finite sets Z_{ij} and a flag

L_{N} ⊂ ⋯ ⊂ L_{0}

of general linear spaces L_{i} of codimension i such that

Z_{ij} = Z_{ij} ∩ L_{i}

for all i. Set (Z_{ij}, L_{i}) is called a witness set for component Z_{ij}.

Input: A polynomial system f(x) = 0 consisting of n polynomials on ℂ^{N} and a witness set (W, L) for some irreducible component C of V (f) of dimension one, i.e., L is a generic hyperplane and W = C ∩ L. Output: The geometric genus of C, i.e., the genus of the desingularization of the closure of C in ℙ^{N}.

1. Preprocess so that n = N − 1 and C is reduced;

(a) If the multiplicity of C is greater than one, deflate [9, § 13.3.2] until we have a curve birational to C having multiplicity one. For simplicity, we rename the deflated system, the deflated curve, the dimension of the space it is defined on, the witness point set, and the linear space slicing the deflated curve in the witness point set as (f(x), C, N, W, L). Set d := deg C, i.e., the cardinality of W.

(b) Randomize the system so that n = N − 1.

2. Letting π : ℂ^{N} → ℂ be the linear projection with fiber over the origin equal to L, choose a basis v_{1}, …, v_{N−1} of L.

3. Let J denote the Jacobian of f(x); let V denote the matrix whose columns are the v_{i}; and let a_{1}ξ_{1} +⋯+a_{N−1}ξ_{N−1} = 1 be a random linear equation. Compute the irreducible components S_{1}, …, S_{M} of the intersection of the solution set of the system

[ \begin{matrix}J · V · [ ξ_{1} ; ⋮ ; ξ_{N−1} ] \\ a_{1}ξ_{1} + ⋯ + a_{N−1}ξ_{N−1} − 1 \end{matrix} ] = 0  (5)

with the inverse image of C in the (x, ξ)-space. Note that the sets S_{i} may have positive dimension, but under the natural projection π_{x} : (x, ξ) ↦ (x), each π_{x}(S_{i}) is a single point for each i. Let S′_{i} = π_{x}(S_{i}), i = 1, …, M, which we call “potential branchpoints.” The full irreducible decomposion is unneeded for this step: at the expense of having more “potential branchpoints,” we may compute a witness point superset for the intersection using the algorithm of [8].

4. For i from 1 to M let s_{i} := π(S′_{i}) and set s_{0} = ∞.

5. For each s_{i}, with i ≥ 1, choose a disk Δ_{i} around s_{i} that contains no other s_{i}: in the case of s_{0} a disk is a set of the form {z ∈ ℂ|z > R} for some R > 0. Adjust the radii and R so that the disks are all disjoint.

6. For each i choose a point z_{i} on the boundary of Δ_{i} and carry out the monodromy transformation of π^{−1}(z_{i}) ∩ C to compute the number of distinct groups γ_{i} that π^{−1}(z_{i}) ∩ C breaks into.

7. Output g(X) = −d + 1 + \frac{1}{2} ∑_{i=0}^{M}(d − γ_{i}).

Because it is formulated on ℂ^{N} instead of ℙ^{N}, the above algorithm must make a special case to account for contributions from branchpoints at infinity. A slightly modified approach removes this special case by working on ℙ^{N}, or rather, by picking a random patch of ℙ^{N} so that branchpoints at infinity in the original formulation become finite points in the new patch. The modifications are as follows.

• Homogenize the system f and preprocess it as in the above algorithm so that it is a system F (X) of N − 1 homogeneous polynomials in the variables X = [x_{0}, x_{1}, …, x_{n}] ∈ ℙ^{N}. Treat X as a column vector in the following steps.

• Choose a random linear projection π : ℙ^{N} → ℙ^{1} given as X ↦ [μ·X, λ·X], where μ and λ are mutually orthogonal 1 × (N + 1) complex row vectors, i.e., μ · λ^{T} = 0.

• Let v_{1}, …, v_{N−1} be a basis for the orthogonal complement of μ and λ and carry out the same computation as in Step 3 above to find the solutions S_{1}, …, S_{M} and their projections onto X, S′_{i} = π_{X}(S_{i}).

• Work on a patch λ·X = 1 with projection to ℂ defined by μ. Accordingly, the solutions S′_{i} are mapped to ℂ as s_{i} := μ · (S′_{i}/(λ · S′_{i})), i = 1, …, M. (There is no s_{0} now, but M might be larger than before.)

• Do monodromy as before. That is, for the loop around s_{i}, we track solutions of the system

[F (X), μ · X − s_{i} − r_{i}e^{\sqrt{−1} θ}, λ · X − 1] = 0

as θ goes from 0 to 2π, where r_{i} is chosen such that the disk of radius r_{i} centered on s_{i} does not contain any s_{j}, j ≠ i. In this notation, s_{i} + r_{i} is the point z_{i} of Step 6 above.

• Determine the number of distinct monodromy groups γ_{i} for each point s_{i} and output g(X) = −d + 1 + \frac{1}{2} ∑_{i=1}^{M}(d − γ_{i}).

Note that in either case, we must initialize the monodromy loop by finding the d points of the fiber π^{−1}(z_{i}) ∩ C. This is done by following the paths from the witness set for C as L is moved to π^{−1}(z_{i}).

To compute the Euler characteristic of \overline{C}, we do the same steps as above except for each z_{i} compute the number ν_{i} of distinct limits as the points π^{−1}(z_{i})∩C are continued to π^{−1}(s_{i})∩C. When ν_{i} < d, these continuation paths have singular endpoints, so a singular endgame must be used to compute them accurately [3, 4]. A particularly apt technique in the present context is to perform the monodromy loop as in the algorithm for the genus and compute a Cauchy integral from the points collected around the loop [3]. Then the output is

e(\overline{C}) = 2d − ∑_{i=0}^{M}(d − ν_{i}).

Note that the arithmetic genus of the reduction of X is at least 1 − e(X)/2 which in turn is at least g(X).

4 An Example

In this section, we demonstrate the application of our approach on a curve arising from the kinematics of mechanisms: the coupler curve of a four-bar linkage in the plane.

A planar four-bar linkage is a hinged quadrilateral. We may hold one link fixed, extend the opposing side into a so-called coupler triangle, and study the motion of the new vertex of this triangle, the coupler point. This defines a curve in the plane, called a four-bar coupler curve. It is well known that for a general four-bar, this curve is degree 6 and that it can be written in isotropic coordinates as a curve of bidegree (3,3). Whereas a general plane curve of degree 6 has genus 10 and a general curve of bidegree (3,3) has genus 4, the four-bar coupler curve has genus only one, e.g., [?]. Thus, this is an ideal initial test case for our method.

Figure 1: Four-bar ramification points with monodromy loops

We treated the problem as an homogenized system on ℙ^{3} and selected random complex numbers to define the sides of the four bar. At equation (5), we have f(x) as degree 6 and J(x) · V as degree 5, hence we obtain 30 potential branch points. Of these, 12 occur as a pair of multiplicity 6 roots. These correspond to the triple self intersections of the curve at the isotropic points at infinity [1, ±\sqrt{−1}, 0]. Another 6 potential branchpoints occurs as three double points. These are the finite points where the curve crosses itself. As all of these points are simple crossings, they each contribute zero to the genus, that is, γ_{i} = 6 at each one. All of the remaining 12 potential branchpoints are true branchpoints, each having γ_{i} = 5. Hence, the genus of the four-bar coupler curve is found to be

g = −6 + 1 + \frac{1}{2} ∑_{i=1}^{12}(6 − 5) = 1,

as expected.

In Figure 1, we plot the projections s_{i} of the potential branchpoints. For ease of programming, we used diamond shaped monodromy loops, also shown. The twelve monodromy loops drawn with bold lines are the ones which contributed to the genus.

5 Conclusions

References

[1] R. Miranda. Algebraic Curves and Riemann Surfaces. American Mathematical Society. Providence, RI, 1995.

[2] E.J.F. Primrose and F. Freudenstein. Geared Five-Bar Motion: Part 2— Arbitrary Commensurate Gear Ratio. Trans. ASME, J. of Applied Mechanics, June 1963, pp. 170–175.

[3] A.P. Morgan, A.J. Sommese, and C.W. Wampler. Computing singular solutions to nonlinear analytic systems. Numer. Math. 58:7:669–684, 1991.

[4] A.P. Morgan, A.J. Sommese, and C.W. Wampler. A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math. 63:3:391–409, 1992.

[5] A.J. Sommese, J. Verschelde, and C.W. Wampler. Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM J. Numer. Anal. 38(6):2022–2046, 2001.

[6] A.J. Sommese, J. Verschelde, and C.W. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. In Application of Algebraic Geometry to Coding Theory, Physics and Computation, edited by C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel, pages 297–315, Kluwer Academic Publishers.

[7] A.J. Sommese, J. Verschelde and C.W. Wampler. Symmetric functions applied to decomposing solution sets of polynomial systems. SIAM J. Numer. Anal. 40(6):2026–2046, 2002.

[8] A.J. Sommese, J. Verschelde, and C.W. Wampler. Homotopies for intersecting solution components of polynomial systems. SIAM J. Numer. Anal. 42(4):1552–1571, 2004.

[9] A. Sommese and C. Wampler. The Numerical Solution to Systems of Polynomials Arising in Engineering and Science. World Scientific. Singapore, 2005.

Dan Bates Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55122 dbates1@nd.edu, www.nd.edu/∼dbates1 Chris Peterson Dept. of Mathematics, Colorado State University, Fort Collins, Colorado 80525 peterson@math.colostate.edu, www.math.colostate.edu/∼peterson

Andrew Sommese Dept. of Mathematics, University of Notre Dame, Notre Dame, IN 46556 sommese@nd.edu, www.nd.edu/∼sommese

Charles Wampler General Motors Research and Development, Mail Code 480-106-359, 30500 Mound Road, Warren, MI 48090-9055 Charles.W.Wampler@gm.com