# Computationally bounding a curve's genus from below?

### 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?

-
Counting points on singular curves can be tricky, the Weil bound applies to a non-singular model. Can you bound the number of singular points? – Felipe Voloch Mar 30 '10 at 21:29
@Felipe: Since that is equivalent to the question, I'm hoping you or someone else knows how to do that efficiently :) – Dror Speiser Mar 30 '10 at 21:34
This is just an affine plane curve, right? Did you factorize the equation? Did you look for singular points (including at infinity)? Both are very computationally easy. If it factors then you can compute the genus of the pieces. If it's irreducible and smooth then it has genus (d-1)(d-2)/2. If it has a singular point you can blow it up: move it to the origin and draw lines through it of the form y=tx; this decreases the degree, and then you keep doing. Have I missed an issue here? – Kevin Buzzard Mar 30 '10 at 21:52
@Buzzard: I believe you have. Finding singular points involves, with the simplest algorithm I can think of, factoring a polynomial of degree (d-1)(d-2)/2. In my specific case this is almost 300, which is quite large. – Dror Speiser Mar 30 '10 at 22:13
Before I thought of factoring $Res_y (f,df/dx)$, but actually it would be much faster to compute $GCD(Res_y(f,df/dx), Res_y(f,df/dy))$. But this isn't trivial either since if the degrees are large, then the coefficients get very big, making computation slow. – Dror Speiser Mar 30 '10 at 22:58

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!

-
It doesn't seem you need to factor polynomials. Finding the number of distinct roots is done by dividing by the gcd with the derivative. The degrees of the resultants are $O(d^2)$, making the computation in the rationals slow. Of course, as is mentioned above, one can reduce modulo. Finally, all of this needs to be implemented for sage (computation of genus for curve with integer/rational coefficients). – Dror Speiser Apr 1 '10 at 13:34
Agreed, though the "purging out of roots" might require computing the gcd several times. Also, you should make sure to begin with that the curve is geometrically integral, since otherwise the bound you get is off by the number of geometric irreducible components of C. Note also that you really only get a lower bound if you do not deal with the singular points of C. – damiano Apr 1 '10 at 15:06

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.

-
If you do recompute the equation for the specific curve you were interested in, either post it or email it to me and I can run the optimization program on it and see what it comes up with. – AVS Mar 31 '10 at 1:26

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.

-
This method seems to be unaffected by the specific coefficients, as long as they are non-zero: probably it computes an upper bound on the genus, rather than a lower bound. More precisely, it probably computes the geometric genus of a general curve with specified Newton polygon; a specific curve with specified Newton polygon might acquire extra singularities and hence have smaller geometric genus. – damiano Mar 31 '10 at 12:02
Fair point. I'd forgotten that this was indeed a very specific curve. – singe Mar 31 '10 at 12:40