Computational Algebraic and Analytic Geometry

for Low-dimensional Varieties

Organized by Mika Seppälä (Florida State University) and Emil Volcheck (National Security Agency).

This special session will be held Thursday and Friday, 16-17 January 2003, at the Baltimore Joint Mathematics Meetings. This is the third special session on this topic to be held at the AMS/MAA Joint Mathematics Meetings. The first special session was held in 1999 at the San Antonio Joint Meetings, and the second special session was held in 2001 at the New Orleans Joint Meetings.

This session is devoted to algorithms and computational techniques for algebraic curves, Riemann surfaces, algebraic surfaces, and low-dimensional varieties. We are interested in reports on algorithms to solve problems or on a significant use of computational algebraic or analytic techniques to obtain results. Algorithmic, algebraic, arithmetic, and analytic aspects of curves and surfaces are appropriate topics.

Read the list of speakers and their abstracts for the special sessions in 1999 and 2001 on computational algebraic geometry for curves and surfaces to see what previous speakers in this series of special sessions have presented.

The deadline to guarantee consideration of your abstract was Tuesday, 6 August 2002.

The final deadline for abstract submission was Tuesday, 1 October 2002. Submissions are closed.

Please write to both of us, Mika Seppälä at seppala@math.fsu.edu and Emil Volcheck at volcheck@acm.org, to propose a topic or to inquire whether a topic would be appropriate. We encourage you to send us an abstract of your talk and/or a URL of a paper or manuscript on which you would like to speak.

To formally submit an abstract to the AMS, read the guidelines and submit your abstract. Indicate meeting number 983 (Baltimore) on the web form.

The list of speakers as of 4 November 2002 is

- Shreeram S. Abhyankar
- Ettore Aldrovandi
- Paolo Aluffi
- Mark Bauer
- Harvey Cohn
- David Eisenbud
- Jeffrey Farr
- Jane Gilman
- Milagros Izquierdo
- Michael Jacobson
- David Joyner
- Kiran Kedlaya
- Robert Lewis
- Matilde Marcolli
- Renate Scheidler
- Mika Seppälä
- Tony Shaska
- Bernard Shiffman
- Andreas Stein
- Ken Stephenson
- Andreas Strömbergsson
- Peter Turbek

The famous Theorems of Bertini imply that most members of a pencil of algebraic plane curves have no singularities outside the base points, and if the pencil is noncomposite and free from fixed components then most members are irreducible. In other words, consider a bivariate polynomial whose zero-set is a member of the pencil, and let its redset and singset consist of those constants by translating thru which we get the reducible and the singular members of the pencil respectively. Then Bertini says that these two sets are finite. With an eye on applications to finite fields, we sharpen the Bertini Theorems by finding bounds for these sets. The proofs are based on the group of units of an affine domain, the first homology rank, and the Zeuthen-Segre invariant. This is joint work with Assi, Heinzer, and Sathaye.

Let $X$ be a compact Riemann surface. Various symbol maps on $X$ can be expressed through Deligne cohomology. For example, if $U$ is open in $X$ and $f$ and $g$ are two invertible holomorphic functions on $U$, their symbol $(f,g]$ is a line bundle with connection satisfying the Steinberg relations in $K_2$. There are more general symbol maps, for example for pairs of line bundles $L$ and $L'$ on $X$. The corresponding symbol $(L,L']$ corresponds to Deligne's pairing $\langle L,L'\rangle$. This framework can be generalized to take into account hermitian fiber metrics via Hermitian Holomorphic Deligne (HHD) cohomology. If $L=TX$, the holomorphic tangent bundle of $X$, a hermitian fiber metric $\rho$ on it is just a conformal metric on $X$. We show that, modulo an area term, the square of the class of $(TX,\rho)$ in HHD cohomology is the functional whose extrema are constant negative curvature metrics. For the cover corresponding to the uniformization by a Kleinian gr! oup $\Gamma$ of the second kind, this functional can also be computed as the ``regularized volume'' of the associated $3$-manifold $N$ such that $X=\partial N$. We refine this result by expressing it in terms of the regulator class given by the Bloch-Wigner dilogarithm.

We will discuss an algorithm computing the push-forward to projective space of several classes associated to a (possibly singular, reducible, nonreduced) projective scheme. For example, the algorithm yields the topological Euler characteristic of the support of a projective scheme $S$, given the homogeneous ideal of $S$. The algorithm has been implemented in {\tt Macaulay2.\/}

In this talk, we will consider curves of the form $y^3=D$ over a given field ${\bf K}$ of characteristic different from 3, where $D \in {\bf K}[x]$ is a monic squarefree polynomial whose degree is not divisible by 3. For curves of this form, explicit techniques for performing arithmetic in the Jacobian have been developed by exploiting the relationship with the ideal class group of the maximal order contained inside the corresponding function field. The majority of the complexity that arises in the algorithms developed to perform arithmetic in these ideal class groups derives from pathological cases which can occur in performing ideal arithmetic with arbitrary ideals. However, we will show that almost all ideals that arise during computation have a distinct form and, by exploiting this, it is possible to develop a faster arithmetic. Furthermore, by considering only curves of small genus, it is possible to reduce the complexity of these algorithms by being able to predict what the outcome should look like.

Let $P=(E|Z)$ be the conventional Riemann matrix of genus $g$, where $E$ is $g$ by $g$ unit matrix and $Z$ is a symmetric $g$ by $g$ matrix with $\Im(Z)$ positive definite. A complex multiplier $W$ is a $g$ by $g$ matrix such that $WP=PQ$ for $Q$ a $2g$ by $2g$ integral matrix (so $WP$ creates a subspace of the periods as a column vector space of $P$).

We construct a ring $R$ of complex multipliers with subring $R_0$ generated by a rational matrix $S$ whose eigenvalues belong to a real field $k$ and extend it by $R$ by a matrix $W$ whose elements are in $K$ (cm field over $k$).

The condition on $R$ is that all matrices $RZ$ are symmetric. Then we take $W=ZU$ where $U$ and $US$ are symmetric ($U$ also rational). Thus $R$ is commutative.

We find $Z$ by forcing $W$ to satisfy a quadratic equation $W^2+GW+H=0, \ (G, H \in R_0)$, using computer algebra. Indeed $Z$ is determined by a set of $g$ algebraic equations. Classically, this generalizes the Hermite-Humbert-Frey parameters for $g=2$, where general complex multiplications emerge, but parameters are easily accessible for $g=3$.

A variety in P^n satisfies Green's condition "N_p" if it is projectively normal, has quadratic equations, and the k-th syzygies on them are generated in degree k+2 for k=1..p-1. There are a number of well-known open conjectures describing geometric consequences of this condition in various special cases.

I will describe recent work of mine with Mark Green, Klaus Hulek, William Oxbury, and Sorin Popescu that gives some conditions on plane sections of varieties satisfying the condition N_p when the sections are sets of points or curves.

Jeffrey Farr and Shuhong Gao

We present a new method for decoding algebraic geometry codes. This work generalizes a recent algorithm of Gao for decoding Reed-Solomon codes. Our method utilizes techniques such as bivariate interpolation and Groebner bases of modules to find the needed error-locator polynomial. Using the information gathered from this special polynomial, we are able to recover the original message polynomial.

Our algorithm is both efficient and simple. The time complexity is similar to the Berlekamp-Massey-Sakata algorithm; however, we do not require majority voting in order to decode up to the minimum distance of the code. Each of the major operations that we perform -- polynomial interpolation (via Fourier transform), polynomial addition and multiplication by a scalar -- are straightforward and easy to implement in practice.

Jane Gilman and Linda Keen

There are certain sequences of words in the generators of a two-generator group that frequently arise in the Teichm{\"u}ller theory of hyperbolic three-manifolds and Kleinian and Fuchsian groups. We establish the connection between the Keen-Series family of Farey words that have been used to understand the boundary of the Teichm{\"u}ller spaces of surfaces of type $(1,1)$ and $(0,3)$ and the sequences of words that arise in two-generator discreteness algorithms studied by Rosenberger-Purzitsy, Gilman-Maskit, and Jiang. In the case that the group under consideration is discrete, this connection allows us to interpret the exponents that arise in the algorithmic words or in their Farey expansions as self-intersection numbers of certain curves on the quotient surface. That is, the sequences of integers that arise as the exponents in words considered by the algorithm (or equivalently the Farey expansion) can be interpreted as unwinding and winding numbers for one curve on the surface about others. These sequences give what we call the {\em {complexity}} of a curve on a surface. This allows us to interpret the discreteness algorithm as an algorithm for finding short geodesics on surfaces. The complexity of the geodesics represented by the two initial generators is related to the computational complexity of the discreteness algorithm.

Milagros Izquierdo and Antonio F Costa

An important step in the Enge-Gaudry algorithm for computing discrete logarithms in the Jacobian of a hyperelliptic curve over a finite field is rapidly finding many smooth divisors, i.e., divisors that factor into a sum of prime divisors whose norms have small degree. We describe our investigation into finding an efficient strategy for finding and testing smooth divisors, including distinct-degree factorization based methods, Bernstein's smoothness testing algorithm, and sieving. The implications of our results to the Weil descent attack for solving the elliptic curve discrete logarithm problem over characteristic 2 finite fields of composite degree will also be discussed.

We study the action of a finite group on the Riemann-Roch space of a curve. Our main result is the following: if $G$ is a finite subgroup of the automorphism group of a projective curve $X$ and if $D$ is a divisor on $X$ fixed by $G$ then the natural representation of $G$ on $L(D)$ is a direct sum of irreducible representations of dimension $\leq d$, where $d$ is the size of the largest $G$-orbit acting on $X$. We show by example that this is best possible (i.e., that dimension $d$ subrepresentations do occur). In some fairly general cases we are able to determine the dimension and multiplicity of the trivial subrepresentation exactly.

One standard method for computing in the algebraic closure of the rationals (within the complex numbers) is to represent an algebraic integer by its minimal polynomial plus an approximation to its real and complex parts, to distinguish it from its conjugates. One can do likewise over the rational function field in characteristic zero, using Puiseux expansions, but this fails in positive characteristic. We describe an approach that works over a finite field, using Hahn's generalized power series and some finite automata.

The Bezout-Cayley-Dixon resultant is a useful and efficient way to solve systems of polynomial equations. This has been known since at least the 1994 paper by Kapur, Saxena, and Yang. Their key idea was proven correct in great generality by the 2000 paper of Buse, Elkadi, and Mourrain [BEM]. The technique seems to be much more efficient than elimination with Grobner bases.

Many computational geometry problems can be reduced to systems of polynomial equations, which can then be attacked by the Dixon Resultant. I will describe how this approach has worked on Apollonius-type tangency problems in two and three dimensions; generalizing the Fermat-Steiner point to three dimensions; finding formulas for the distance between ellipses and ellipsoids; and proving the Steiner-Lehmus Theorem.

Yuri I Manin and Matilde Marcolli

According to the holography principle (due to G.`t Hooft, L. Susskind, J. Maldacena, et al.), quantum gravity and string theory on certain manifolds with boundary can be studied in terms of a conformal field theory on the boundary. Only a few mathematically exact results corroborating this exciting program are known. In this paper we interpret from this perspective several constructions which arose initially in the arithmetic geometry of algebraic curves. We show that the relation between hyperbolic geometry and Arakelov geometry at arithmetic infinity involves e xactly the same geometric data as the Euclidean $AdS_3$ holography of black holes. Moreover, in the case of Euclidean $AdS_2$ holography, we present some results on bulk/boundary correspondence where the boundary is a non-commutative space.

This talk continues our study of purely cubic function fields, i.e., fields generated by a curve of the form $y^3 = D$; however, in contrast to part I of this investigation, we require that the degree of $D$ be divisible by 3. Here, it is no longer true that the Jacobian is isomorphic to the ideal class group of the maximal order, since the curve has more than one place at infinity. We present ideal arithmetic in this setting, focusing in particular on ideal reduction and how this reduction method can be used to find the fundamental unit(s) of the maximal order of the field. This method is also instrumental in finding the order of the Jacobian of the field.

J. Gutierrez and T. Shaska

Let $\L_g$ be the moduli space of genus $g$ hyperelliptic curves with non-hyperelliptic involutions. This is an algebraic variety of dimension $g$. We identify points in $\L_g$ by a $g$-tuple of {\it dihedral invariants}. Moreover, we present an efficient algorithm to decide if a curve $C$ is in $\L_g$, and compute its dihedral invariants. Finally, we show how these invariants can be used to answer questions on the automorphism group and the field of definition of hyperelliptic curves and conjecture that $\L_g$ is a fine moduli space.

Bernard Shiffman and Steve Zelditch

We describe the distribution of simultaneous zeros of random polynomials with fixed Newton polytopes. For the 0-dimensional case, we show that there is a "classically allowed region" where the zeros tend toward uniformity, and a "classically forbidden region" where the zeros are sparse. For the 1-dimensional case, we study statistical patterns for the amoebas of random algebraic curves in C^2 with fixed Newton polytope. Our results are asymptotic as the polytope is dilated.

We present recent results on the computation of regulators and class numbers of cubic function fields. Hereby, we provide tight estimates for the divisor class number of a cubic function field with the help of truncated Euler products. These analytically derives estimates can be used to develop an effective method of computing the divisor class number. Our main focus will be cubic function fields of large characteristic, in which case not much is known about class number computations. We thus generalize earlier results on hyperelliptic function fields. By considering the function fields of irreducible curves we can also evaluate the cardinality of Jacobians of cubic curves. Although these methods are very general, we will apply our techniques to purely cubic function fields of unit rank one, where we can report several interesting phenomena. In these function fields, arithmetic can be performed efficiently with Voronoi's algorithm. Time-permitting, we will discuss the effect of our investigations on curve cryptography.

Charles Collins and Ken Stephenson

This talk is about conformal "flat mapping". Suppose S is a piecewise flat topological rectangle, so it has a piecewise euclidean metric with "cone points" where the pieces come together. The metric gives S a natural conformal structure, and by the Riemann Mapping Theorem there is a conformal mapping F:S --> R to an essentially unique rectangle R in the plane.

These maps F are now accessible via circle packing methods. One consequence is that the flattening can be treated as a parameterized process, giving a continuum of conformal surfaces between S and R. In particular, prescribing that the cone points be "flattened" at rates proportional to their curvatures is a type of "motion by mean (conformal) curvature". The circle packing machinery provides a very graphic "curvature flow" for this process and raises issues of both mathematical and conputational interest. The talk will illustrate such flows and formulate a connection to Schwarz-Christoffel type methods with singularities.

I will present an algorithm for the numerical computation of modular forms on an arbitrary cofinite Fuchsian group (with at least one cusp). I will also show some applications of this algorithm to the problem of finding algebraic presentations of Riemann surfaces.

The mapping class group $\M _{g,0}$ of a compact surface $X$ of genus $g$ is defined to be the group of all orientation-preserving homeomorphisms of $X$ modulo the subgroup generated by those isotopic to the identity. If $x \in X,$ let $\pi(X,x)$ denote the fundamental group of $X$ with base point $x,$ let $\Aut(\pi(X,x))$ denote its automorphism group, and let $\Aut_0(\pi(X,x))$ denote the subgroup of all inner automorphisms. Neilsen proved that \break $\M _{g,0} \cong \Aut(\pi(X,x))/\Aut_0(\pi(X,x))$. The Nielsen realization problem shows that each element of $\Aut(\pi(X,x))$ is induced by a conformal automorphism acting on some compact Riemann surface of genus $g.$

In this paper, we consider any element $\sigma \in \Aut(\pi(X,x))$ of prime order. We determine an explicit set of $2g$ generators for $\pi(X,x)$ and determine a defining relation for $\pi(X,x)$ in which each generator and its inverse appear exactly once. In terms of these generators, the automorphism $\sigma $ is explicitly calculated. We then discuss algorithms for converting the above generators into standard ones where the product of commutators yields the identity. This is applied to several specific cases. Many of the results obtained are through the representation of $X$ as the orbit space of the upper half plane under a Fuchsian group.

Session I: Thursday January 16, 2003, 1:00 p.m.-4:10 p.m. 1:00-1:20 Ettore Aldrovandi 1:30-1:50 Paolo Aluffi 2:00-2:20 Jane Gilman 2:30-2:50 Milagros Izquierdo 3:00-3:20 Mika Seppala 3:30-3:50 Tony Shaska Session II: Friday January 17, 2003, 8:00 a.m.-10:55 a.m. 8:00--8:20 Mark Bauer 8:30--8:50 Renate Scheidler 9:00--9:20 Andreas Stein 9:30--9:50 Michael Jacobson 10:00-10:20 David Eisenbud 10:30-10:50 Kiran Kedlaya Session III: Friday January 17, 2003, 1:00 p.m.-6:00 p.m. 1:00-1:20 Andreas Strombergsson 1:30-1:50 Ken Stephenson 2:00-2:20 Peter Turbek 2:30-2:50 David Joyner 3:00-3:20 Shreeram Abhyankar 3:30-3:50 Matilde Marcolli 4:00-4:20 Harvey Cohn 4:30-4:50 Robert Lewis 5:00-5:20 Bernard Shiffman 5:30-5:50 Jeffrey Farr

Participants in the special session and friends are invited to join us for dinner at the Helmand Restaurant. The Helmand Restaurant is known for outstanding Afghani cuisine and is one of Baltimore's top-rated restaurants in the Zagat Survey. The Helmand is owned by a brother of Afghan Head of State Hamid Karzai.

Dinner will be Friday evening at 8:45 PM. The Helmand is located at 806 N. Charles St., a short cab ride from the Convention Center. The phone number for the Helmand is (410) 752-0311.

Return to the top of this page.

This page is at URL http://www.AlgebraicCurves.net/Baltimore.html.

*Last modified 16 January 2003 by Emil Volcheck*