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.
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.
Sarah-Marie Belcastro
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.
Gavin Brown
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.
Peter Buser
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
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.
Roland Dreier
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.
Birk Huber*, Frank Sottile, Bernd Sturmfels
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
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
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