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.

- Matthew Baker
- Claire Baribaud
- Sarah-Marie Belcastro
- Phil Bowers
- Gavin Brown
- Peter Buser
- David Cantor
- Harvey Cohn
- Janos Csirik
- Roland Dreier
- Gaétan Haché (cancelled)
- Martin Hassner
- Birk Huber
- Kiran Kedlaya
- Kristin Lauter
- Robert Silhol (cancelled)
- Ken Stephenson
- Mark van Hoeij
- Brock Williams
- Thorsten Woermann

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}$.

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.

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.

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.

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.

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

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$.

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 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.

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.

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.

Please note that this talk has been cancelled.

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.

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.

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.

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.

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.

Please note that this talk has been cancelled.

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$.

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$.

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.

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.

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

- the polynomial ring R[X_1,..., X_n],
- zero-dimensional.

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