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)}{\varphi_1'(x_i)\cdots\varphi_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 \varphi_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 \varphi(t) = \prod_{x \in X} (t - x). Then:

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

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

  1. We have \varphi'(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 \varphi'(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) = \varphi'(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, \varphi'(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?


About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Number Theory, Polynomial Method and tagged , , , , , , . Bookmark the permalink.

2 Responses to The coefficient formula and Chevalley-Warning

  1. dke says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s