# Solutions to system of polynomial equations over finite fields

If $P_1$, $P_2$, ..., $P_m$ are $n$-variate homogeneous polynomials of degree d over a finite field $F_q$, where $q$ is much larger than $d$, but much smaller than $n$, then do we know good lower bounds on the number of common zeros of $P_1$, $P_2$, ..., $P_m$?

If $m$ is equal to $1$, then we would get some non-trivial lower bounds from the Weil bounds. But what happens for a general $m < n$? Are there any accessible references?

• Your question is very broad. Can you perhaps ask a more specific question? Currently, it is not clear even what would constitute an answer to this question. (It is hard to guess the right tool to for your application, if we do not know what it is even approximately.) – Boris Bukh Aug 4 '15 at 18:59
• @BorisBukh I meant, do we have good lower bounds on the number of common zeros of a system of low degree homogeneous polynomials over finite fields? If the degree of the polynomials is one, then the number of solutions is $q^{n-r}$, where $r$ is the rank of the system. Are there similar statements for higher degree homogeneous polynomials? – mrinal Aug 4 '15 at 20:15
• In the case when $n$ is very large compared with $d,q,m$, the polynomial regularity lemma and polynomial counting lemma describes, in principle, the equidistribution of $P_1,\dots,P_m$: arxiv.org/abs/0711.3191 . Basically, one has equidistribution unless there are "low rank" obstructions, in that certain linear combinations of $P_1,\dots,P_m$ are expressible in terms of a small number of low-degree polynomials. – Terry Tao Aug 5 '15 at 3:26
• @TerryTao Thanks for the reference. I was thinking more in the regime of constant $d$ and $q$, but $m$ slightly growing with $n$. The dependency on the number of low-degree polynomials needed on $m$ seems quite bad in the paper. – mrinal Aug 5 '15 at 14:45

The Ax-Katz theorem gives a lower bound of:

$$q^{ \left\lceil \frac{n}{d} \right\rceil -m }$$

(Because it implies the number of roots is divisible by this, and there is at least one root.)

In this level of generality, you can't hope for much better. For instance if $d=n$ and $m=1$ then you can take the norm map from $\mathbb F_{q^n}$ to $\mathbb F_q$, viewed as a single degree $n$ polynomial in $n$ variables over $\mathbb F_q$ that has no roots.

• The question asks for $q$ much larger than $d$, but much smaller than $n$, so it seems $d=n$ does not apply. – Gerry Myerson Aug 4 '15 at 23:28
• @GerryMyerson Let me say instead that Weil does not immediately give you a lower bound. I't easy to see that you can get it down to $q^{n-dm}$ using different norm polynomials in different subsets of the variables. So there is still some room between this lower bound and the explicit examples. – Will Sawin Aug 5 '15 at 13:29

The simplest case occurs when the forms are diagonal:

$$P_i=a_{i1}x_1{d}+\cdots + a_{in}x_n^{d}$$ $$1\leq i \leq m$$.

and this has been investigated in detail. It's also the example with $$m=1$$ that Weil used in his paper proposing the Weil Conjectures. He used exponential sums in his analysis.

In general exponential sums are often the approach that gives reasonable bounds for specific cases.

As Will Sawin points out the only case where solutions are guaranteed is when $$n>dm$$. Chevalley-Warning gives you the simplest proof of this though Ax-Katz gives you more precise information on the number of solutions.

The other extreme is finding the least number of variables that still gives you a solution for $$q$$ large enough. In the diagonal case this requires $$n>2m$$. The problem then becomes finding good bounds for $$q$$. One can also relax the bound for n and look for better bounds for $$q$$.

For example it's a classical result that the equation $$ax^d+by^d+cz^d=0$$ has non-trivial solutions over $$\mathbb F_q$$ if $$q>k^4$$. Similarly for $$n>2m$$ Atkinson, Brudern and Cook $$^1$$ proved that we have a non-singular solution for $$p>d^{2m+2}$$. (Non-singularity is required for applications to the Hardy-Littlewood method and is a stronger condition than non-trivial of course)

I proved in a later paper $$^2$$ that for $$n>cm$$ you can find a non-singular solution if $$q>m^2d^{2+\frac{2}{c-1}}$$

These results are established using exponential sum estimates which gives you an estimate for the number of solutions $$N$$ of the form $$|N-q^{n-r}| which immediately gives you a bound $$N>q^{n-r}-o(q^{n-r})>0$$ for large enough $$q$$.

For more general forms there has been a lot of work over the years beginning with the Lang-Weil inequality. See more recent papers, here and here. The book by Schmidt, Equations over Finite Fields $$^3$$ covers quite a bit from a more elementary approach avoiding the really difficult algebraic geometry related to the Weil Conjectures.

1 Atkinson, O. D.; Brüdern, J.; Cook, R. J., Simultaneous additive congruences to a large prime modulus, Mathematika 39, No. 1, 1-9 (1992). ZBL0774.11016.

2 Meir, I. D., Simultaneous diagonal (p)-adic equations, Mathematika 45, No. 2, 337-349 (1998). ZBL0992.11030.

3 Schmidt, Wolfgang M., Equations over finite fields. An elementary approach, Lecture Notes in Mathematics. 536. Berlin-Heidelberg-New York: Springer-Verlag. IX, 267 p. (1976). ZBL0329.12001.