Chevalley-Warning Theorem and Blocking Sets

The classical Chevalley-Warning theorem gives us a sufficient condition for a system of polynomial equations over a finite field to have common solutions. Affine blocking sets are sets of points in an affine geometry (aka affine space) that intersect every hyperplane. What’s the connection between them? It appears to be the following curious property of polynomials that vanish on all points of $\mathbb{F}_q^n$ except one:

Lemma Let ${P \in \mathbb{F}_q[x_1, \ldots, x_n]}$ such that ${P(a) \neq 0}$ for some ${a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n}$ but ${P(x) = 0}$ for all ${x \in \mathbb{F}_q^n \setminus \{a\}}$ . Then ${\deg P \geq n(q-1)}.$

In this post, I will show how this property implies both the Chevalley-Warning (CW) theorem, and the Jamison/Brouwer-Schrijver bound on the size of affine blocking sets. The Lemma itself can be proved in many different ways. In my mathoverflow answer I have mentioned six different proofs (how “different” two proofs are can vary). But there are even more ways to prove this lemma, some of which I will discuss in later blog posts.

CW theorem states that given $k$ polynomials $P_1, \dots, P_k$ in $\mathbb{F}_q[x_1, \dots, x_n]$ with $\sum \deg P_i < n$ , if they have a common zero, then they have another common zero in $\mathbb{F}_q^n$ .

Proof. Define $P = (1 - P_1^{q-1})(1 - P_2^{q-1}) \cdots (1 - P_k^{q-1})$ . The polynomial $P$ has the property that it is equal to $1$ at all the common zeroes and $0$ otherwise. For sake of contradiction assume that $P$ takes the value $1$ at exactly one point, i.e., there is a unique common zero. Then, from the lemma above we see that $\deg P = \sum (q-1) \deg P_i \geq n(q-1)$ , which contradicts that $\sum \deg P_i < n$ . Hence, there must be another common zero. (Warning’s second theorem states that there are at least $q^{n-\deg P}$ common zeroes). $\blacksquare$

This proof is essentially due to Chevalley. For a historical discussion on this theorem and its proofs see this. For a full survey, wait till Pete Clark finishes his book size notes titled “Around the Chevalley-Warning Theorem”.

Now we turn to affine blocking sets. As discussed here blocking sets appeared in 1955 as a game theoretic concept. Later on some mathematicians picked up the concept and started studying it for its own sake. The kind of blocking sets we’ll be concerned with are called affine blocking sets. These are sets of points in $\mathbb{F}_q^n$ that intersect every hyperplane. A simple example of such a set is given by taking the $n(q-1) + 1$ points on the axes, i.e., the points $\lambda e_i$ for $\lambda \in \mathbb{F}_q$ , where $e_i$ is the vector with $1$ at $i$ -th position and zero elsewhere. It was conjectured by J. Doyen in 1976 at an Oberwolfach lecture that this is the least possible size of an affine blocking set. An year later two independent proofs of this appeared, one by R. E. Jamison, and another by Andries E. Brouwer and Alexander Schrijver. The latter was a short argument which can be seen as a direct application of the lemma above (which they proved!). Let’s look at that argument in a slightly different way than how it appears in their paper.

Every hyperplane corresponds to a linear equation of the form $a_1x_1 + \dots + a_nx_n = \lambda$ , i.e., every hyperplane is the zero set of a degree $1$ polynomial. And hence union of $d$ hyperplanes correspond to the zero set of a degree $d$ polynomial which is the product of all the corresponding degree $1$ polynomials. The lemma above shows that if there are $d$ hyperplanes that cover all points of $\mathbb{F}_q^n$ except one, then $d \geq n(q-1)$ . To use this in our problem, we first embed the points of blocking set in a projective space by adding a hyperplane at infinity, and then look at the dual problem. An affine blocking set has the property that it intersects every hyperplane except the hyperplane at infinity. The number of hyperplanes in $\mathbb{P}^n(\mathbb{F}_q)$ that cover all points except one is one more than such hyperplanes in the corresponding affine space because of an extra hyperplane at infinity. Thus, by projective duality we have at least $n(q-1) + 1$ points in the blocking set.

The curious property of polynomials mentioned in the main Lemma of this post has been generalised to some other cases and it has been used to solve some interesting problems, which I might discuss in future posts. For now, see this interesting paper by Blokhuis, Brouwer and Szőnyi: Covering all points except one.

Edit (23 Jan 2016): This paper by Noga Alon gives a more direct connection between the Jamison theorem and the Chevalley-Warning theorem for the prime case: Tools from Higher Algebra. See page Theorem 6.5 on page 23.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.

View all posts by Anurag Bishnoi →

2 Responses to Chevalley-Warning Theorem and Blocking Sets

Seva says:

May 17, 2023 at 3:12 pm

A nice exposition, thanks! Incidentally, is anything known about $m(n/2,n,q)$, the smallest size of a set in $\mathbb F_q^n$ blocking every affine subspace of dimension $n/2$?

- Anurag Bishnoi says:
  
  May 17, 2023 at 7:41 pm
  
  Dear Seva,
  
  Thank you for your comment. The best upper bounds on $m(n/2, n, q)$ are of the form $C_q q^{n/2} n^2$ , obtained via picking points randomly (or if you want, you can pick $n/2$ -dimensional vector subspaces randomly to get improvements on $C_q$ : https://arxiv.org/abs/2301.09457).
  
  The best lower bounds are obtained via an inductive argument, reducing it to the hyperplane case, which then gives $m(n/2, n, q) \geq (q^{n/2} - 1)(n/2 + 1) + 1$ . Therefore, there is a huge gap. There is some belief that the upper bound must be (asymptotically) tight.
  
  I would be very interested in improving any of these bounds. Even determining $m(n - 2, n, q)$ is an open problem, and linked to many other interesting open problems that we mention in the paper linked above.