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.

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Polynomial Method and tagged , , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s