AMS Special Session:

Computational Algebraic Geometry for Curves and Surfaces

Organized by Mika Seppala (Florida State University, seppala@math.fsu.edu) and Emil Volcheck (National Security Agency, volcheck@acm.org)

This special session will be held Friday and Saturday, 15-16 January 1999, at the San Antonio Joint Meetings of the AMS and MAA. This session is devoted to algorithms and constructive techniques for algebraic curves, Riemann surfaces, and algebraic surfaces. We are interested in reports on algorithms to solve problems or on a significant use of computational algebra techniques to obtain results.

Here are some examples of topics that would be appropriate for this special session: resolving singularities, computing a representation of a Riemann surface as an algebraic curve, techniques for Dessins d'Enfants, computing in the divisor class group or Jacobian of a curve.

Schedule

Speaker's List (18 total)

Abstracts

Matthew Baker

Computing Cartier Points of Algebraic Curves

A {\it Cartier point} on a curve $X$ in characteristic $p$ is a point $Q$ such
that the hyperplane of regular differentials vanishing at $Q$ is preserved
by the Cartier operator.  The definition was motivated by Robert Coleman's
study of torsion points on curves.  We give some methods for computing 
Cartier points, and explain how such computations can be useful in
determining which points of a given algebraic curve $Y$ over ${\bf C}$ map to
torsion points of Jac($Y$) under an Albanese embedding.  We also give some
bounds for the number of Cartier points an ordinary curve can have, though
it would be interesting to investigate how sharp these bounds are in general.
Our results on Cartier points can also be used to generalize the following result 
of Ekedahl: If $X$ is an algebraic curve in characteristic $p$ of genus $g$ 
whose Hasse-Witt matrix is zero, then $g \leq \frac{p(p-1)}{2}$.

Claire Baribaud

Geodesics on a pair of pants

We study the geodesics of the Riemann surfaces of signature (0,3). To do so, we define a parameter - the number of strings - and we show that for a given number of strings, a minimal closed geodesic exists. In the case of non-closed geodesics, i.e., geodesics having their extremities on the boundary geodesics of the pair of pants, the study is far more complicated, but we still are able to give a lower bound on the length.

Sarah-Marie Belcastro

Producing Networks of Curves on 2-dim Toric Hypersurfaces

By considering a 3-polytope $\Delta$ to be the Newton Polytope for a
Laurent polynomial $f$, we may associate to $\Delta$ a family of algebraic
surfaces with generic member $S$ defined by $f$.  Using combinatorial
information from $\Delta$, we may remove some (often all) singularities of
$S$ and produce a network of curves on $S$. This process has been
automated by means of a \emph{Mathematica} program.  We will explain what
the program does and give some applications for use of the output; for
example, if $S$ is a K3 surface, the network of curves produced often
gives rise to an elliptic fibration. 

Philip Bowers

Numerical uniformization of piecewise flat surfaces

We describe an algorithm for numerical uniformization of piecewise flat surfaces, ie, for constructing fundamental domains for such surfaces in the standard geometries as well as the corresponding conformal uniformizing maps. The initial work on this addressed the problem of uniformizing the piecewise equilateral surfaces that arise in the Grothendieck theory of dessins d'enfants. The crucial ingredient there was the ability to perform "conformal subdivisions" that allowed us to construct an iterative scheme based on circle packings and prove convergence of the scheme to a uniformizing map. In dealing with general piecewise flat surfaces, as opposed to equilateral ones, we lose the nice symbiosis between the subdivision combinatorics and the circle packing geometry that provided convergence to a uniformizing map. We remedy this by preserving the subdivision process while modifying the circle packing geometry by allowing "circle packings" involving pairwise disjoint collections of circles to model the conformal geometry of the surfaces. Convergence is forced by keeping tight control over inversive distances between the disjoint circles. We will end the talk with a brief report on applications of the algorithm to the problem of constructing good 2D representations of the human brain ("conformal brain flattening") in current biomedical research.

This work is joint with Ken Stephenson.

Gavin Brown

Toroidal methods for curve singularities

Curve singularities can be analysed by sequences of blowups or by calculating puiseux expansions. Toric methods mimic both techniques using the newton polygon to determine certain weighted blowups. I discuss this approach and show how to recover data, like details of neighbouring singularities for adjoint analysis, that seems at first glance to be lost.

Software demonstration: Magma

As part of the Saturday afternoon software demonstrations, Gavin Brown will demonstrate the new packages for algebraic curves in the Magma computer algebra system.

Peter Buser

About the numerical uniformization of real hyperelliptic curves

The lecture is about recent numerical experiments
which have been carried out at the EPFL in Lausanne
to compute numerically the canonical hyperbolic metric
of an algebraic curve $C$.  If $C$ is hyperelliptic,
real and with a maximal number of real components, then the
Fenchel--Nielsen parameters can be computed by determining
the hyperbolic lenghts of certain cycles.  This leads to the
uniformization of $C$ by a Fuchsian group.
The computation is based on the relation
$$
\triangleup \sigma - k\sigma + \tilde k e^{2\sigma} = 0
$$
where $\triangleup$ and $k$ are the Laplacian and the Gaussian curvature
of a Riemannian metric $g$, $\sigma$ is a conformal factor, and
$\tilde k$ is the curvature of the conformally equivalent metric
$\tilde g = \sigma g$.

David Cantor

Factoring Polynomials over Local Fields

We give an algorithm for factoring polynomials in one variable over local fields. This algorithm is closely related to an algorithm for this purpose due to A. Chistov (Proceedings ICM 1986).

Harvey Cohn

Third order splitting of genus two hyperelliptics

Harvey Cohn

Center for Computing Sciences, Bowie MD

Take the hyperelliptic $H$ (on ${\mathbf C}$), $y^2 = P(x)$,
($P(x)$ sextic or quintic with distinct roots).
What condition on the coefficients of $P(x)$ will split the Jacobian,
i.e., make the abelian differentials (of the first kind) on $H$
become differentials on an elliptic curve $E$ in $(X,Y)$?
The easy case (Legendre-Jacobi) is where $X = X(x)$ is rational
of degree two; the case of degree three has several diversified forms.
The explicit construction of the cubic $X(x)$ (Brioschi-Bolza) for 
$P(x) = (x^3 + ax + b)(x^3 + px^2 + q)$ can be made if $q = 4b + 4ap/3$.
Using Kummer surfaces, however, Humbert showed the existence of
$X(x)$ if $(s_1 s_2 - s_3)^2 = 4 s_3 (1+s_2)(s_1 + s_3)$ where
$P(x) = x (x-1) (x-\lambda^2) (x - \mu^2) (x - \nu^2)$ and
$s_1 = \sigma \lambda$, $s_2 = \sigma \lambda \mu$, $s_3 = \lambda \mu \nu$.
He also found a geometric condition using a conic on which the
(Weierstrass) points $\{ \infty, 0, 1, \lambda^2, \mu^2, \nu^2 \}$
are placed as values of a uniform parameter, namely that the triangle
formed by three of these points in inscribed in (another) conic through
the other three points.  These three conditions are shown to be equivalent
by computer algebra, thus bypassing some very deep connections.

Janos Csirik

Counting points on an elliptic curve on a low-memory device

In 1985 Schoof proposed the first algorithm to count the number of points on an elliptic curve defined over a finite field in polynomial time. It was later significantly speeded up and made practical by Elkies and Atkin. The algorithm involves writing down specific equations for various modular curves, and therefore uses a lot of memory. This talk is an exposition of a variant of the algorithm that uses relatively little memory (about a sixth of a megabyte) to produce cryptographically secure elliptic curves.

Roland Dreier

Torsion Points on Bielliptic Curves

Given a curve $C$ along with an embedding of $C$ in its Jacobian $J$,
a natural problem is to determine all points of $C$ whose image in $J$
is torsion.  In the preprint \textit{Torsion points on $y^2=x^6+1$},
Voloch uses the techniques of Buium to give a method for determining
the torsion on a genus 2 curve whose Jacobian is isogenous to the
product of two elliptic curves, both of which are canonical lifts of
their reductions modulo a prime $p$.  We extend this method to certain
genus 2 curves whose Jacobian splits as the product of two elliptic
curves, without requiring that the elliptic curves be canonical lifts.
Our method relies on analyzing the multiplication-by-$p$ map modulo
$p^2$, for $p$ a prime of good reduction.

Gaétan Haché

Please note that this talk has been cancelled.

Using the Brill-Noether algorithm for absolute factorisation

The Brill-Noether algorithm is usually used to compute a basis
of the vector space, so called $L(D)$, associated to 
a divisor of the function field of an absolutely irreducible 
plane curve. By generalising notions usually related to
absolutely irreducible curves, such as valuation of a function
field, we show how the Brill-Noether algorithm can be applied
to reducible curves. By doing so, and using D.~Duval's geometric
approach, one can compute the absolute factorisation of bivariate
polynomials defined over any perfect field.

Martin Hassner

Finite State Automata determined by Rational Division Values of Theta Functions

In this talk we describe a family of Finite State Automata defined on a set of Rational Division Values of the elliptic Jacobian. The state transitions are determined by theta function addition laws.

The motivation for this construction is an application to the processing of magnetic signals. We describe this application and outline further generalizations to the hyperelliptic case.

Birk Huber*, Frank Sottile, Bernd Sturmfels

Homotopy Methods for Effective Schubert Calculus

I will discuss numerical homotopy algorithms for solving systems of polynomial equations arising from the classical Schubert calculus. These methods involve carefully working out the equations encoding deformation techniques of computational algebra and enumerative geometry. These equations can then be used with numerical continuation of implicitly defined curves to recover solutions. In particular we describe the connection between Groebner bases and numerical continuation methods and illustrate that the over-determined systems which arise naturally in the description of algebraic geometric objects need not be an impediment to numerical continuation. Computational results will also be described.

Kiran Kedlaya

The Algebraic Closure of the Laurent Series Field in Characteristic $p$

For $K$ a field, let $K((t))$ denote the quotient field of
the power series ring over $K$. A classical result states that
if $K$ has characteristic 0, the algebraic closure of $K((t))$
is the union of the fields $K((t^{1/n}))$ over $n \in \NN$; however, this
statement is false in characteristic $p>0$. Following a suggestion of
Abhyankar, we construct an algebraic closure
of $K((t))$ for any field $K$ of positive characteristic explicitly in
terms of certain generalized power series. We also discuss how to
approximate the roots of a given polynomial to any desired accuracy, using
a variation of Newton's method in the classical case.

Kristin Lauter

An algorithm for determining possible zeta functions of curves over finite fields

We present an algorithm for determining all possible zeta functions of curves
over $\Bbb{F}_q$ of genus $g$ with a given number of rational points. 
Applications include (1) improvements on the bounds for the number of
rational points on a curve or (2) an indication of how to construct a curve with
many points using the factorization of the numerator of the zeta function. 
Curves with many points can be constructed via class field theory as covers 
of intermediate curves corresponding to factors of the numerator. Constructing
the covers involves computing in the divisor class group of the intermediate curve. 

Robert Silhol

Please note that this talk has been cancelled.

Equations for real hyperelliptic hyperbolic surfaces

Let $S=\Bbb H/G$ (where $\Bbb H$ is the Poincar\'e upper half plane and $G$ is
a Fuchsian group) be an hyperbolic surface of genus $g>1$.  

If $S$ has specific symmetries, for example if $S$ is such that the associated
algebraic curve is hyperelliptic and real, then a period matrix of the curve
may be expressed in terms of conformal capacities of certain geodesic polygons.
This yields an efficient and practical method to compute equations for the
algebraic curve associated to $S$.

Ken Stephenson

Experiments with polynomials having prescribed branch values

Abstract: Manipulating normalized polynomials
$P(z)=z+a_2z^2+\cdots+a_nz^n$ is easy enough if one controls
their branch points (critical values). However, control
through their branch {\bf values}, the images $w=P(z)$ of branch
points, is another matter entirely.  In general, branch values do not
determine a polynomial; indeed, a generic 4-tuple $\{w_1,\cdots,w_4\}$
of nonzero complex numbers will be the set of branch values for 125
normalized fifth degree polynomials. I will describe a classical
construction of the polynomials having prescribed branch values,
show how to mimic the construction discretely using circle packing
techniques, and then illustrate with some experiments directed 
towards Smale's 1981 conjecture that every normalized polynomial 
has a branch point $z$ satisfying $|P(z)/z|<1$.

Mark van Hoeij

Computing a parametrization for rational algebraic curves

Let $F$ be a polynomial of degree $N$ defining an algebraic curve $C$ in
$P^2$ of genus $0$. Then $C$ is birationally equivalent to $P^1$. In this
talk I will give an efficient method to compute such birational
equivalence (i.e. a parametrization). To compute a parametrization one
must deal with the singularities of the curve. A for computer computations
very suitable way to do this is an integral basis. Using an integral basis
we can compute efficiently the vector space $L(D)$ where $D$ is $-1$ times
a canonical divisor. This vector space gives a bijective morphism to a
conic, which reduces the problem to the case $N = 2$.
In this talk I will also try to explain how subtle differences in the
algorithm can make a big difference in the computation timings.

Brock Williams

Using Circle Packings to Approximate Conformal Weldings


Given two Jordan domains $D_1$ and $D_2$ on the Riemann sphere
and a homeomorphism  $\varphi:\partial D_1\rightarrow \partial D_2,$ we may
form a topological surface $S$ by identifying points $x$ of $\partial D_1$ with
points $\varphi(x)$ of $\partial D_2$.  If $S$ has a conformal structure which
extends the conformal stuctures of $D_1$ and $D_2$ , then we say a
\emph{conformal welding} exists for $\varphi$.
The interplay between the two domains as they find their new positions
as complementary  regions of $S$ will pull their ``seam'' into a
\emph{conformal welding curve.}

We will describe the use of circle packings to approximate the
conformal structure on $S$ and the conformal welding curve
for various classes of identification maps and Jordan domains.
By ``welding'' triangulations of $D_1$ and $D_2$, we construct
circle packings of $S$.  These packings induce maps which converge to
the uniformizing maps for $S$ while the curves formed by connecting
centers of circles on the ``seam'' converge to the conformal
welding curve.

Thorsten Woermann

Sums of squares in affine $R$-algebras: some algorithmic aspects

Suppose A is an affine R-algebra, f in A. An algorithm is presented that allows us to decide whether f is a sum of squares in A in the cases that A is

An upper bound for the length of the representation as a sum of squares can be given in the cases mentioned above.

Schedule

Friday:    8:00am-10:55am and 1pm-6pm
Saturday:  8:00am-10:55am and 1pm-5pm

19 speakers total

Friday, 15 January

0800 Kiran Kedlaya
0830 Kristin Lauter
         -- coffee break --
0930 Matt Baker
1000 David Cantor
1030 Harvey Cohn

1300 Janos A Csirik
1330 Roland Dreier
1400 Gavin Brown
1430 Mark van Hoeij
          -- coffee break --
1530 Sarah-Marie Belcastro
1600 Birk Huber
1630 Thorsten Woermann
1700 Claire Baribaud

Saturday, 16 January

0800 Peter Buser
0830 Martin Hassner
         -- coffee break --
0930 Ken Stephenson
1000 Phil Bowers
1030 Brock Williams

Discussions and software demonstrations

1300  Gavin Brown
1330
1400
1430
1500
1530
1600
1630