## The coefficient formula and Chevalley-Warning

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 $f$ is a single variable polynomial of degree $d$ over a field $K$, then the values of $f$ over any arbitrary set $S$ of $d + 1$ elements from $K$ completely determines $f$. This is basically Lagrange’s polynomial interpolation. One way of seeing it is to define the polynomials $\delta_x(t) = \frac{\varphi(t)}{\varphi'(t)(t - x)}$ for each $x \in S$ where $\varphi(t) = \prod_{s \in S}(t - s)$ and note that $\delta_x(s) = 1$ if $x = s$ and $0$ otherwise. Then for each $s \in S$ we have $f(s) = \sum_{x \in S} f(x) \delta_x(s)$. And since no two degree $d$ polynomials can agree in more than $d$ points, we deduces that the polynomial $f$ must be equal to the polynomial $\sum_{x \in S} f(x) \delta_x = \sum_{x \in S} f(x) \prod_{s \in S \setminus \{x\}}\frac{t - s}{x - s}$. The situation becomes quite different when we look at polynomials in $n$ variables, but in fact we can still say something quite interesting using the same ideas.

Theorem 1. (Coefficient Formula) Let $f \in K[t_1, \dots, t_n]$ be a polynomial of degree at most $a_1 + \cdots + a_n$ for some positive integers $a_i$. Let $A_1, \dots, A_n$ be finite subsets of $K$ with $|A_i| = a_i + 1$. Then the coefficient of $t_1^{a_1}t_2^{a_2} \cdots t_n^{a_n}$ in $f$ is equal to

$\displaystyle \sum_{(x_1, \dots, x_n) \in A_1 \times \cdots \times A_n} \frac{f(x_1, \dots, x_n)}{\phi_1'(x_i)\cdots\phi_n'(x_n)}$

where $\varphi_i(t_i) = \prod_{x \in A_i}(t_i - x)$.

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 $f \in K[t_1, \dots, t_n]$ and suppose that the coefficient of the monomial $\prod_{i = 1}^n t_i^{d_i}$ in $f$ is non-zero where $d_1, \dots, d_n$ are some positive satisfying $\deg f = d_1 + \cdots + d_n$. Then for any finite subsets $A_1, \dots, A_n$ of $K$ satisfying $|A_i| > d_i$ for all $i$, there exists $(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n$ such that $f(a_1, \dots, a_n) \neq 0$.

Proof: We have $\deg f \leq \sum (|A_i| - 1)$. Then by Theorem 1, we get

$\displaystyle \sum_{(x_1, \dots, x_n) \in A_1 \times \cdots \times A_n} \frac{f(x_1, \dots, x_n)}{\varphi_1'(x_1) \cdots \varphi_n'(x_n)} \neq 0$,

which implies that there exists an $(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n$ for which $f(a_1, \dots, a_n) \neq 0$. $\blacksquare$

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 $f_1, \dots, f_r \in \mathbb{F}_q[t_1, \dots, t_n]$ such that $\sum \deg f_j < n$, then for $Z = \{x \in \mathbb{F}_q^n : f_1(x) = \cdots = f_r(x) = 0\}$ we have $|Z| \neq 1$. The stronger form says that the characteristic $p$ of the finite field $\mathbb{F}_q$ divides $|Z|$. This can be proved using Theorem 1 as follows.

Define $f := \prod_{j = 1}^r (1 - f_i^{q - 1})$. Then $\deg f = (q - 1) \sum \deg f_j$, and $f(x) = 1$ for all $x \in Z$ and $0$ otherwise. Since $\deg f < (q - 1) + (q - 1) + \cdots + (q - 1)$, the coefficient of $t_1^{q-1} \cdots t_n^{q - 1}$ in $f$ is equal to $0$, and we can apply Theorem 1 to get

$\displaystyle 0 = \sum_{(x_1, \dots, x_n) \in \mathbb{F}_q^n} \frac{f(x_1, \dots, x_n)}{\varphi'_1(x_1)\cdots\varphi_n'(x_n)} = \sum_{(x_1, \dots, x_n) \in Z} \frac{1}{\varphi'_1(x_1)\cdots\varphi_n'(x_n)}$,

where $\phi_i(t_i) = \prod_{\lambda \in \mathbb{F}_q} (t_i - \lambda)$. 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 $\prod_{\mu \in \mathbb{F}_q, \mu \neq \lambda} (\lambda - \mu) = -1$ for every $\lambda \in \mathbb{F}_q$. Therefore, our equation simplifies to $0 = \sum_{x \in Z} (-1)^n = |Z|(-1)^n$. This means that the characteristic $p$ of the field $\mathbb{F}_q$ must divide $|Z|$, which is the stronger Chevalley-Warning theorem. $\blacksquare$

Lemma 3. Let $d$ be a divisor of $q - 1$ and let $X = \{x^d : x \in \mathbb{F}_q\}$. Define $\phi(t) = \prod_{x \in X} (t - x)$. Then:

1. $\phi'(0) = -1$.
2. For all $x \in X$, we have $\phi'(x) = -1/d$.

Proof. Note that $\phi'(t) = \sum_{x \in X} \prod_{y \in X \setminus \{x\}} (t - y)$.

1. We have $\phi'(0) = \prod_{x \in X \setminus \{0\}} (-x) = (-1)^{(q-1)/d} \prod_{x \in X \setminus \{0\}} x$. Let $\theta$ be a primitive element of $\mathbb{F}_q$, then we have $X = \{0\} \cup \{\theta^{di} : 1 \leq i \leq (q - 1)/d\}$. Therefore,
$\displaystyle \prod_{x \in X \setminus \{0\}} x = \theta^{\frac{(q - 1)}{2}((q - 1)/d + 1)}= (-1)(-1)^{(q - 1)/d}$
where the las equality follows from the fact that $\theta^{(q-1)/2} = -1$.
2. Let $x \in X \setminus \{0\}$. Then
$\displaystyle \phi'(x) = \prod_{y \in X \setminus \{x\}} (x - y) = x \prod_{y \in X \setminus \{0, x\}} (x - y) = x \cdot x^{(q - 1)/d - 1} \prod_{y \in X \setminus \{0, x\}} (1 - y/x) = 1 \cdot \prod_{\lambda \in X \setminus \{0, 1\}} (1 - \lambda) = \phi'(1)$.
Since the elements of $X \setminus \{0\}$ are all the $\frac{q - 1}{d}$th roots of unity, we have $\prod_{\lambda \in X \setminus \{0,1\}} (t - \lambda) = (t^{(q - 1)/d} - 1)/(t - 1) = 1 + t + t^2 + \cdots + t^{(q - 1)/d - 1}$. Therefore, $\phi'(1) = (q - 1)/d = -1/d$. $\blacksquare$.

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 $1 \leq i \leq n - 1$ let $m_i$ be a positive integer and define $d_i = \gcd(m_i, q - 1)$. Let $f_1, \dots, f_r \in \mathbb{F}_q[t_1, \dots t_n]$ be such that

$\displaystyle \sum_{j = 1}^r \deg f_j < \sum_{i = 1}^n \frac{1}{d_i}.$

Then the characteristic $p$ of $\mathbb{F}_q$ divides the cardinality of the set $Z = \{(x_1, \dots, x_n) \in \mathbb{F}_q^n : f_1(x_1^{m_1}, \dots, x_n^{m_n}) = \cdots = f_r(x_1^{m_1}, \dots, x_n^{m_n}) = 0\}$.

Proof. Apply all the tools so far carefully, or see Pete’s paper.

When all $m_i$‘s are equal to $1$, Theorem 3 is just the Chevalley-Warning theorem. When $r = 1$ and $\deg f_1 = 1$, then this is a result due to Morlaye. Morlaye’s result has been generalized by Wan to prove that if $\sum 1/d_i > b \geq 1 = \deg f_1$, then $q^b$ divides $|Z|$.

Question. Is there such a generalization of Theorem 3, or some other special case of it?

Nice result. Perhaps for Lemma 3 it’s more straightforward to notice $\phi(t)=t^{1+(q-1)/d}-t$ and then evaluate the derivative at dth powers.