This post is about a certain result on coefficients of a multivariate polynomial obtained by Schauz, Lason and Karasev-Petrov, which generalises Alon’s combinatorial nullstellensatz (or to be more precise, Theorem 1.2 in Alon’s paper). This sharpening of Alon’s result has seen some very interesting applications, for example a short proof of dyson conjecture and its q-analog. Now there is a new application by Pete Clark who has used it to obtain a simultaneous generalization of Chevalley-Warning and Morlaye’s theorem, building up on the work of Baoulina. We will see how this result is proved.
If is a single variable polynomial of degree over a field , then the values of over any arbitrary set of elements from completely determines . This is basically Lagrange’s polynomial interpolation. One way of seeing it is to define the polynomials for each where and note that if and otherwise. Then for each we have . And since no two degree polynomials can agree in more than points, we deduces that the polynomial must be equal to the polynomial . The situation becomes quite different when we look at polynomials in variables, but in fact we can still say something quite interesting using the same ideas.
Theorem 1. (Coefficient Formula) Let be a polynomial of degree at most for some positive integers . Let be finite subsets of with . Then the coefficient of in is equal to
Unlike the single variable case, the Coefficient formula does not uniquely determine the full polynomial but just some coefficients of the polynomial. This looks quite weak, but surprisingly it has some really interesting consequences. For a proof of Theorem 1 look at these notes (Theorem 13) or any of the original papers.
Let’s first see how this a generalization of Alon’s combinatorial nullstellensatz.
Theorem 2. (Combinatorial Nullstellensatz) Let and suppose that the coefficient of the monomial in is non-zero where are some positive satisfying . Then for any finite subsets of satisfying for all , there exists such that .
Proof: We have . Then by Theorem 1, we get
which implies that there exists an for which .
Therefore, Theorem 2 is a direct consequence of Theorem 1. Let’s now see how Theorem 1 can sometimes give more general results than Theorem 2.
One of the first applications of combinatorial nullstellensatz that Alon gave in his paper was to prove that the classical Chevalley-Warning theorem follows directly from his result. Actually, he only proved the weaker form of Chevalley-Warning (also known as Chevalley’s theorem), which is as follows: let such that , then for we have . The stronger form says that the characteristic of the finite field divides . This can be proved using Theorem 1 as follows.
Define . Then , and for all and otherwise. Since , the coefficient of in is equal to , and we can apply Theorem 1 to get
where . We will now use Lemma 3 below, which is a nice result on finite fields that will be useful in another context as well. In particular that result will show that for every . Therefore, our equation simplifies to . This means that the characteristic of the field must divide , which is the stronger Chevalley-Warning theorem.
Lemma 3. Let be a divisor of and let . Define . Then:
- For all , we have .
Proof. Note that .
- We have . Let be a primitive element of , then we have . Therefore,
where the las equality follows from the fact that .
- Let . Then
Since the elements of are all the th roots of unity, we have . Therefore, . .
We now have all the ingredients for the new result of Clark, which is a generalization of Chevalley-Warning theorem obtained by restricting the variables to power residues. More precisely, we have the following:
Theorem 3. (Clark 2017) For let be a positive integer and define . Let be such that
Then the characteristic of divides the cardinality of the set .
Proof. Apply all the tools so far carefully, or see Pete’s paper.
When all ‘s are equal to , Theorem 3 is just the Chevalley-Warning theorem. When and , then this is a result due to Morlaye. Morlaye’s result has been generalized by Wan to prove that if , then divides .
Question. Is there such a generalization of Theorem 3, or some other special case of it?