Issues in Symbolic Parametrization of Algebraic Curves ^{∗}

Franz Winkler Institut für Mathematik and RISC-LINZ Johannes Kepler Universität A-4040 Linz, Austria

                       e-mail: winkler@risc.uni-linz.ac.at

A symbolic parametrization algorithm

The problem of rational parametrization of plane algebraic curves is best explained by an example. Suppose we consider the curve C_{1} in the complex plane, whose points are the zeros of the polynomial

f_{1}(x, y) = (x^{2} + 4y + y^{2})^{2} − 16(x^{2} + y^{2}).

C_{1} has a double point at the origin (0, 0) as the only affine singularity. But if we move to the associated projective curve C_{1}^{∗} defined by the homogeneous polynomial

f_{1}^{∗}(x, y, z) = (x^{2} + 4yz + y^{2})^{2} − 16(x^{2} + y^{2})z^{2},

we see that the singularities of C_{1}^{∗} are

O = (0 : 0 : 1), P_{1,2} = (1 : ±i : 0).

P_{1,2} is a family of conjugate algebraic points on C_{1}^{∗}. All of these singularities have multiplicity 2, so the genus of C_{1}^{∗} is 0, i.e. it can be parametrized. This also means that the affine curve C_{1} is parametrizable.

In order to achieve a parametrization, we need a simple point on C_{1}^{∗}. Intersecting C_{1}^{∗} by the line y + \frac{40}{9}x = 0, we get of course the origin as a double intersection point. The other two intersection points are also rational, namely

Q_{1} = (−36 : 160 : 1681), Q_{2} = (2916 : −12960 : 1681).

So now we construct the linear system L^{2} of curves of degree 2, having O, P_{1,2} and Q_{1} as base points of multiplicity 1.

The affine version L_{a}^{2} of L^{2} is defined by

h_{a}(x, y, t) = tx^{2} + ty^{2} + x + (−\frac{1}{10}t + \frac{9}{40})y.

Now we determine the free intersection point of L_{a}^{2} and C_{1}. The non–constant factors of res_{x}(f_{2}(x, y), h_{a}(x, y, t)) are

y^{2},
1681y − 160,
(430336t^{4} − 94464t^{3} + 58976t^{2} − 5904t + 1681)y +
(−40960t^{4} + 184320t^{3} − 204800t^{2} − 11520t + 12960).

∗Supported by Österr. Fonds zur Förderung der wissenschaftlichen Forschung, Proj. POSSO, Nr. P9181-TEC. (ESPRIT BRA No. 6846).

The first two factors correspond to the affine base points of the linear system L^{2}, and the third one determines the y–coordinate of the free intersection point depending rationally on t.

Similarly, the non–constant factors of res_{y}(f_{1}(x, y), h_{a}(x, y, t)) are

x^{2},
1681x + 36,
(430336t^{4} − 94464t^{3} + 58976t^{2} − 5904t + 1681)x +
(−9216t^{4} + 62464t^{3} − 141696t^{2} + 108864t − 2916).

The first two factors correspond to the affine base points of the linear system L^{2}, and the third one determines the x–coordinate of the free intersection point depending rationally on t.

So we have found a rational parametrization of C_{1}, namely

x(t) = \frac{9216t^{4}−62464t^{3}+141696t^{2}−108864t+2916}{430336t^{4}−94464t^{3}+58976t^{2}−5904t+1681} ,
y(t) = \frac{40960t^{4}−184320t^{3}+204800t^{2}+11520t−12960}{430336t^{4}−94464t^{3}+58976t^{2}−5904t+1681} .

Definition 1: In general we say that a curve C has a rational parametrization, iff there are (nontrivial) rational functions x(t), y(t) such that the defining polynomial f of C vanishes on them,

f(x(t), y(t)) = 0.  •

The parametrizable curves are exactly the irreducible curves of genus 0, i.e. they achieve the upper bound on the number of singularities. If such a parametrization exists, then it is by no means unique, even if we require that the degrees of the rational functions involved are minimal. In fact, one of the main problems is to determine a minimal extension of the field of definition, in which a parametrization can be expressed.

For this purpose we assume that K is a computable field of characteristic 0, we call it the field of definition. \overline{K} denotes the algebraic closure of K. The defining polynomial of the curve C that we want to parametrize has coefficients in K. The curve C itself, however, is considered to be a curve over \overline{K}. In the parametrization process we might have to extend K algebraically. We will ultimately construct a parametrization (if one exists) over some field K(γ) ⊆ \overline{K}, where γ is algebraic over K. Of course, we want to keep the degree of γ as low as possible.

We call a point, or a curve, or a system of curves rational, if they involve only coefficients from the field of definition K.

Points on algebraic curves occur only in full conjugacy classes. If we choose all the points in such a conjugacy class as base points of a linear system, then the coefficients of the system will still be rational.

Lemma 1: Let f(x, y, z) be a homogeneous polynomial in K[x, y, z] defining an algebraic curve C in P^{2}(\overline{K}). Let (a_{1}(α) : a_{2}(α) : a_{3}(α)) be a point of multiplicity r on C, α algebraic over K with minimal polynomial p(t), and a_{1}, a_{2}, a_{3} ∈ K[t]. Then for every conjugate β of α, also the point (a_{1}(β) : a_{2}(β) : a_{3}(β)) is a point of C. •

Definition 2: If p(t) ∈ K[t] is irreducible and a_{1}, a_{2}, a_{3} ∈ K[t] with p |̸ gcd(a_{1}, a_{2}, a_{3}), then we call

{ (a_{1}(α) : a_{2}(α) : a_{3}(α)) | p(α) = 0 }

a family of conjugate algebraic points. •

Lemma 2: Let L be a rational linear system of curves of degree d. Let P_{α} = {(a_{1}(α) : a_{2}(α) : a_{3}(α)|p(α) = 0} be a family of conjugate algebraic points. Then also the subsystem L̂ of L, having all the points in P_{α} as base points of multiplicity r, is a rational linear system of curves. •

So we can proceed as in the introductory example. An algorithm along these lines is presented in [4]. The only step which might force us to extend the field of definition is the determination of simple points on the curve C.

From the work of Nöther [3] and Hilbert and Hurwitz [1] we know that it is possible to parametrize any curve C of genus 0 over the field of definition K, if deg(C) is odd, and over some quadratic extension of K, if deg(C) is even. An algorithm which actually achieves this optimal field of parametrization is presented in [5]. Moreover, if the field of definition is the field of rational numbers, we can also decide if the curve can be parametrized over the reals.

\underline{Complexity}

The resulting parametrization algorithm is of polynomial bit complexity if we assume that the curve C defined over the rational numbers has only ordinary singularities [2]. If we allow curves with also non–ordinary singularities, then the bit complexity becomes exponential in the worst case. In fact, in [2] a family of curces {C_{k}} (cusps) is exhibited, for which the graph of neighboring singular points has depth proportional to deg(C_{k}). This implies that we need to introduce so many algebraic numbers, leading to the exponential behavior of the algorithm when we have to deal with non–ordinary singularities.

References

[1] D. Hilbert, A. Hurwitz, “Über die Diophantischen Gleichungen vom Geschlecht Null”, Acta math. 14, 217–224 (1890)

[2] M. Mňuk, J.R. Sendra, F. Winkler, “On the Complexity of Parametrizing Curves”, manuscript (1994)

[3] M. Nöther, “Rationale Ausführung der Operationen in der Theorie der algebraischen Functionen”, Math. Annalen 23, 311–358 (1884)

[4] J.R. Sendra, F. Winkler, “Symbolic Parametrization of Curves”, J. Symbolic Comp. 12, 607–631 (1991)

[5] J.R. Sendra, F. Winkler, “Optimal Parametrization of Algebraic Curves”, RISC-Report 94-65, J. Kepler Univ. Linz, Austria (1994)