Bivariate polynomials over finite fields

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.


Solutions Collecting From Web of "Bivariate polynomials over finite fields"

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 should be understood as a corollary of 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.