Number of Solutions to Polynomials in Finite Fields

1k Views Asked by At

Let $\mathbb{F}$ be a finite field and $f_i\in\mathbb{F}[x_1,x_2,\ldots,x_n]$ be polynomials of degree $d_i$, where $1\leq i\leq r$, such that $f_i(0,\ldots,0) = 0$ for all $i$. Show that if $n>\sum_{i=1}^r d_i$, then there exists nonzero solution to the system of equations: $f_i = 0$ for all $1\leq i \leq r$.

Hint: Let $q = \left|\mathbb{F}\right|$ and $p = \operatorname{char}\mathbb{F}$. The number of integral solutions is congruent to the following number modulo $p$ $$\sum_{x\in\mathbb{F}^n}\prod_{i=1}^r(1-f_i(x)^{q-1}).$$

Indeed, $x$ is a solution to the system of equations if and only if $\prod_{i=1}^r(1-f_i(x)^{q-1}) = 1$ because if $0 = a\in\mathbb{F}$, then $a^{q-1} = 0$; if $0\neq a\in\mathbb{F}$, then $a^{q-1} = 1$. In addition, the characteristic of $\mathbb{F}$ is $p$. Thus, the hint is proved. But I cannot see how to manipulate the value of $\sum_{x\in\mathbb{F}^n}\prod_{i=1}^r(1-f_i(x)^{q-1})$.

Since algebraic geometry studies the common zeros of $S$, a subset of $k[x_1,\ldots, x_n]$, where $k$ is a field, I classify this question into algebraic geometry.

Thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

This result is known as the Chevalley–Warning theorem.

First, you prove that for $i\geq 0$, $$ \sum_{x\in\mathbb{F}}x^i = \begin{cases}-1 &\text{ if } (q-1)\mid i \text{ and } i > 0\\ 0 & \text{otherwise} \end{cases}. $$ The case $i=0$ is trivial. When $i>0$, the only difficult case is when $(q-1)\not\mid i$. As $\mathbb{F}^*$ is a cyclic group of order $q-1$, there exists $y\in\mathbb{F}^*$ such that $y^i \neq 1$. Then $$ \sum_{x\in\mathbb{F}}x^i = \sum_{x\in\mathbb{F}^*}x^i = \sum_{x\in\mathbb{F}^*}(yx)^i = y^i\sum_{x\in\mathbb{F}^*}x^i = y^i\sum_{x\in\mathbb{F}}x^i $$ and $(y^i-1)\sum_{x\in\mathbb{F}}x^i = 0$. As $y^i\neq1$, $\sum_{x\in\mathbb{F}}x^i = 0$.

This implies that for any polynomial $P\in\mathbb{F}[X_1,\ldots,X_n]$ of degree $d<n(q-1)$, you have $$ \sum_{x\in \mathbb{F}^n}P(x_1,\ldots,x_n) = 0. $$ Indeed, it suffices, by linearity, to check the result for every monomial of the form $X_1^{i_1}\ldots X_n^{i_n}$ with $i_1+\ldots+i_n < n(q-1)$. There exists a $j$ such that $i_j<(q-1)$ and it is then easy to conclude with the previous result.

Now, back to your problem. The hypothesis on the degrees of the $f_i$'s give exactly that the degree of $\prod_{i=1}^r(1-f_i^{q-1})$ is $\sum_{i=1}^r d_i(q-1) < n(q-1)$ so that $$ \sum_{x\in\mathbb{F}^n}\prod_{i=1}^r(1-f_i^{q-1}(x)) = 0. $$ You noticed that $$ \mathrm{Card}(\{x\in\mathbb{F}^n\mid f_i(x) = 0 \text{ for all }i\}) \equiv \sum_{x\in\mathbb{F}^n}\prod_{i=1}^r(1-f_i^{q-1}(x)) \equiv 0 \pmod p. $$ But, by hypothesis $(0,\ldots,0)\in\{x\in\mathbb{F}^n\mid f_i(x) = 0 \text{ for all }i\}$ which proves the existence of a nonzero solution (and even p-1 nonzero solutions!).