Computationally bounding a curve's genus from below?

Question

Background

In the course of answering another question (Infinite collection of elements of a number field with very similar annihilating polynomials) I found myself with a curve, that if it had a positive genus, then I could prove something about an interesting number field. Specifically, I was trying to show that, in the terminology of the above question, all biquadratic fields over the rationals have $r=2$.

The curve was defined by a single affine equation with large degrees in $x$ and in $y$ (23 and 25). Giving sage, or to be more precise Singular, the task of computing the genus, it broke down after an hour. The degree is just too much.

Question

But really, all I want is to bound the genus from below. What effective ways are there for doing so?

Possible solution

Compute the number of points in a random small finite field, hoping for no bad reduction, and checking this is much easier than finding all algebraic singular points. If it is not true that $q-2g\sqrt{q}+1 \le |C(\mathbb{F}_q)| \le q+2g\sqrt{q}+1$, then the genus is greater than $g$. Is this correct?

Answer 1

If you can check that the curve is geometrically irreducible, then you may try using the Hurwitz formula (you may use the formula in any case, but you would have to be more careful with the conclusions if the curve is not irreducible). Assuming that your example is geometrically integral, projection onto one of the axis is a morphism of degree 23. If you know that the morphism ramifies in at least 2*23+h smooth points, then the curve has genus at least 1+h/2. If you know the multiplicities of the ramification or if you know the behaviour of ramification at the singular points, then you can deduce more accurate information.

EDIT: here is an expanded, more computational, version. Write an equation f defining your curve C as a polynomial of degree d in y whose coefficients are polynomials in x. Thus the morphism $(x,y) \to x$ is a morphism of degree d to $\mathbb{A}^1$. We know that this induces a finite morphism from a smooth projective model C' of C to $\mathbb{P}^1$ and we use the Hurwitz formula to compute the (arithmetic) genus g of C': $2g-2=-2d+r$, where r is the degree of the ramification divisor. The better you can estimate r from below, the better the approximation to the geometric genus of C.

Clearly, the points where f=df/dy=0 but $df/dx \neq 0$ are smooth points of C that are ramified for the projection to $\mathbb{A}^1$ and hence contribute to the Hurwitz formula (ramification occurs in C' since such points are smooth and hence C and C' are locally isomorphic here).

Computationally we find the resultant in y of (f,df/dy) (thus you get a polynomial in x) and purge out of it the roots it has in common with the resultant in y of (df/dx,df,dy). Denote this final polynomial by R; the number of distinct roots of R is a lower bound for r. If you are more careful, you might do a little better than this without having to worry about the singular points of C, but for "generic" projections this is optimal.

It seems to me that all this requires is the ability to compute resultants of polynomials in two variables of relatively small degree as well as factoring polynomials in a single variable (and computing gcd's and quotients of polynomials in one variable).

This can further be improved to a better and better lower bound by analyzing more carefully the structure of the ramification at the singular points of C and what happens at infinity: some of the points that we threw out could in fact contribute to the arithmetic genus of C', and there could be ramification "at infinity". I leave this as an exercise!

Answer 2

I don't know an easy way to bound the genus from below (and I would love to hear of one), but there is a fairly general automated technique that can be used to simplify affine curves given by a plane equation (one that is not necessarily irreducible and possibly has many singularities). If the genus of the curve is small, the equation can often be simplified dramatically (possibly made trivial if the genus is 0). On the other hand, if the algorithm fails to make any progress you really can't say anything (so no lower bound).

The basic idea is as follows. First define a cost metric that measures the "complexity" of a given plane equation that defines your curve (e.g. in terms of the degree in each variable, number of nonzero terms, coefficient sizes, etc...). Now define a small set of atomic "steps", say $d$ of them, each of which corresponds to a simple birational transformation (e.g. $x \to 1/x$ might be one step).

Now consider the (infinite) $d$-regular graph whose edges correspond to atomic steps and whose vertices consist of birationally equivalent curves. We want to find a path from the given curve to one with lower cost. This is a combinatorial optimization problem that can be tackled with standard local search techniques (e.g. hill-climbing, simulated annealing, etc...). It isn't guaranteed to work (you could get stuck at a bad local minima), but it can be quite effective.

This technique was originally developed in an effort to find "good" defining equations for $X_1(N)$ (which came up in another Math Overflow question) but it applies to any plane curve, see Section 3 of http://arxiv.org/abs/0811.0296 for more details.

Answer 3

It's a plane curve, and even though the degree is large it shouldn't be too hard to compute its Newton Polygon, and then it's (reasonably) easy to compute the geometric genus... Well, depending on how complicated the polygon turns out to be, but you might be lucky enough to be able to do this by hand. Briefly: The Newton Polygon is the convex hull of the subset of the real plane formed by the points $(i,j)$ corresponding to monomials $x^iy^j$ with nontrivial coefficients in the curve equation. The genus of the curve is equal to the number of integer points in the interior of this polygon.

There's a blog post at http://lamington.wordpress.com/2009/09/23/how-to-see-the-genus/ which might be helpful.