6
$\begingroup$

If $f$ is a bivariate polynomial of degree $r$ over $\mathbb{Z}_p$, then the number of solutions to $f(x,y)=0$ should be less than $rp$. This can be seen by writing $f(x,y) = \sum_{i=0}^r a_i(x) y^{r-i}$ where $a_i(x)$ are univariate polynomials of degree utmost $i$. For each fixed $x$ the $f(x,y)$ is a univariate polynomial in $y$ of degree $r$ and only $r$ roots are possible. There are $p$ $x$'s so the total is $rp$.

I wanted to know if this is this the best bound possible. While the univariate case seems to be much studied, I could not find many references for this question on multivariate polynomials.

Thanks, Phanindra

1 Answers 1

6

Versions of this question have been much studied, but it's not obvious what the correct keywords are. In this case you want to look at algebraic geometry, particularly the study of algebraic curves, over finite fields. The relevant theorem in this subject is the Hasse-Weil bound, which in turn massively generalizes to the Weil conjectures.

The Hasse-Weil bound implies that if $f$ is irreducible and a certain nonsingularity condition is met (actually I am not sure if this is necessary), the number of solutions is something like (but not quite)

$p \pm 2g \sqrt{p}$

where $g = \frac{(r-1)(r-2)}{2}$ by the genus-degree formula. This gives a bound which is worse than your bound if $r$ is large compared to $p$ but which is substantially better if $p$ is large compared to $r$, so which bound is better depends on which regime you care about.

Of course, if $r > p$ then an even better bound than $rp$ is $p^2$...

The Hasse-Weil bound should conjecturally be tight in a suitable sense (in particular, asymptotically in $p$) by a suitable generalization of the Sato-Tate conjecture. On the other hand, in general your bound can be tight, since $f$ may be a product of distinct linear factors. If $f$ is reducible then you should factor $f$ and apply the Hasse-Weil bound separately to each of its factors.

  • 0
    Qiaochu: Thanks for pointing me in the right direction. I have no idea of algebraic geometry but I think it will be very interesting.2012-11-27