3
$\begingroup$

Background

We are given a curve with integer coefficients. I want to make a suggestion in another question (Computationally bounding a curve's genus from below?) into a deterministic algorithm for finding the genus of a plane curve.

The suggestion is: reduce modulo a random prime and find all singular points there. If the prime was of good reduction, then these are the reductions of all of the algebraic singular points, and you can compute the genus easily from here.

Question

What is an effective bound on the largest prime of bad reduction?

What I imagine

Say $C$ is given by $\sum a_{ij} x^i y^j$, then I imagine a bound similar to: $\displaystyle\sum_{\sigma} \prod a_{i\sigma^{-1} (i)}$

Improve this question
$\endgroup$
7
  • $\begingroup$ What do you mean by a prime of good reduction of a singular curve? Usually good reduction means the special fiber is smooth. $\endgroup$
    – Pete L. Clark
    Commented Mar 31, 2010 at 18:08
  • $\begingroup$ @Pete: true. What I mean in this case is a looser condition, namely what I say: "... then these are the reductions of all of the algebraic singular points". Is there a term for this? If not, I'll put quotations around "good reduction", or maybe change the wording to something someone suggests. $\endgroup$
    – Dror Speiser
    Commented Mar 31, 2010 at 18:16
  • $\begingroup$ It seems that you want that the system $f=df/dx=df/dy=0$ admits the "same" solutions over Q as well as modulo your prime, correct? If this is so, then by using various resultants you should be able to produce an integer all of whose divisors correspond to "bad primes". I suspect that the bound coming from this description will be bigger than the one you suggested. $\endgroup$
    – damiano
    Commented Mar 31, 2010 at 18:24
  • 1
    $\begingroup$ Let me expand slightly on my comment. The scheme S over Spec(Z) defined by $f=df/dx=df/dy=0$ will have some primary decomposition. Some of the primes in the decomposition of S will dominate Spec(Z), some will not. The primes of Spec(Z) of "good reduction" should be the primes above which there is no isolated component of S. I am not sure how computationally feasible this approach is. $\endgroup$
    – damiano
    Commented Mar 31, 2010 at 18:33
  • $\begingroup$ @DS: What you suggest doesn't sound like a good definition of good reduction in this context. Suppose that the reduction map is a bijection on the set of singular points, but that some of the singularities become numerically worse after reduction mod p. This would mean that the geometric genus (of the normalization) would drop. $\endgroup$
    – Pete L. Clark
    Commented Mar 31, 2010 at 21:21

2 Answers 2

Reset to default
1
$\begingroup$

@Dror: I will address your last comment in the question about bounding the genus from below.

Here I wanted to add a remark: the explicit bound you found is such that any prime larger than this bound will be of "good" reduction. Unless the bound you compute is at most two, you are guaranteed the existence of smaller primes not dividing the resultant you computed. Since I assume from your question that you simply want to find a prime of "good" reduction, it is probably much more efficient to compute explicitly the resultant (over Z) and then look for primes not dividing it. In particular, it seems like you might necessarily have one such prime of the order not bigger than $d^3M$ (and possibly much smaller than this).

Finally, why did you include the computation of the gcd of the resultant in $\mathbb{F}_p$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ You are right, of course. The gcd is in order to find the singular points, and to compute the genus of the curve from there. This addresses the original problem from the Background. Now, can the procedure you propose be actually done with numbers never exceeding $O(d^3M)$? I mean, can we take candidate primes and test to see if $Res(Res,Res) mod p$ vanishes or something, and if it doesn't then we have found our prime? (This would make the exponent of $d$, in the complexity, linear) $\endgroup$
    – Dror Speiser
    Commented Apr 1, 2010 at 13:24
  • $\begingroup$ Unless I am mistaken, the vanishing set of Res(Res,Res) in your answer is the complement of the set U in my comment. Thus primes not dividing it will be "good" primes. Thanks to your estimate of the size of Res(Res,Res), it seems that you will find a prime of size roughly d^3 log(dM). $\endgroup$
    – damiano
    Commented Apr 1, 2010 at 15:02
0
$\begingroup$

The primes that are "bad" in your sense will divide the number $Res_x(Res_y(f,\frac{\partial f}{\partial x}), Res_y(f,\frac{\partial f}{\partial y}))$. (If I interpreted damiano's comment correctly).

All that is left is to bound this number. So:

Let $M := max (|a_{ij}|)$.

$\parallel Res_y(f,\frac{\partial f}{\partial x})\parallel and \parallel Res_y(f,\frac{\partial f}{\partial y})\parallel are < (2d)!M^{2d}$

$\Rightarrow \parallel Res_x(Res_y(f,\frac{\partial f}{\partial x}), Res_y(f,\frac{\partial f}{\partial y}))\parallel < (2d^2)^{2d^2}((2d)!M^{2d})^{2d^2} \ll (dM)^{4d^3+O(d^2)}$

So pick a random prime larger than this and then compute $gcd(Res_y(f,\frac{\partial f}{\partial x}), Res_y(f,\frac{\partial f}{\partial y}))$ in $\mathbb{F}_p$. The complexity is $O(poly(d)\times poly(\log(M))$. Is this better than Groebner computations in $\mathbb{Q}$? I have no idea...

Improve this answer
$\endgroup$
2
  • $\begingroup$ This seems correct. Roughly, what I had in mind was that you look at the singular subscheme S of your curve over Z, find an open subset U of Spec(Z) where S is smooth (assuming for simplicity that S is reduced), and then choose any prime from U to do your computation. Let me also iterate that I really think that it is far more practical to use the Hurwitz formula: you reduce most of your computations to computing resultants and gcd's of polynomials of degree at most d to get an "approximate" bound and throw in some integral closures to finish off, if needed. $\endgroup$
    – damiano
    Commented Apr 1, 2010 at 7:29
  • $\begingroup$ @Damiano: that sounds very good and that it can reduce the exponent of $d$ in the final algorithm. But, I don't understand this explicitly. Especially the "find an open subset $U$". Can you explain this and the Hurwitz stuff in a longer and computationally explicit answer? $\endgroup$
    – Dror Speiser
    Commented Apr 1, 2010 at 9:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .