In a previous post I discussed how the Alon-Furedi theorem serves as a common generalisation of the results of Schwartz, DeMillo, Lipton and Zippel. Here I will show some nice applications of this theorem to finite geometry (reference: Section 6 of my paper with Clark, Potukuchi and Schmitt). First, let’s recall the statement of Alon-Furedi.
Theorem 1 (Alon-Furedi). Let be a finite grid in where . Let be an -variable polynomial of degree such that the set is nonempty (in other words, does not vanish on the entire grid). Then . Moreover, the bound is sharp.
Here denotes the minimum value of the product where ‘s are integers satisfying and for all . See my post on balls in bins for some details about this function. Thus, the Alon-Furedi theorem gives us a sharp lower bound on the number of non-zeros a polynomial function of degree at most in a finite grid, given that the polynomial does not vanish on the entire grid.
If we take to be the finite field , and for all , then this theorem is in fact equivalent to a 1968 result of Kasami, Lin and Peterson, that determines the minimum Hamming distance of generalized Reed-Muller codes. The generalized Reed-Muller code over is obtained by evaluating each reduced polynomial (degree in each variable at most , see this) of degree at most on the points of . Clearly, the minimum Hamming distance of this linear code is the minimum number of non-zeros a reduced polynomial of degree at most can have. But that’s precisely what the Alon-Furedi theorem is about! After an easy computation one can show that if where , then this minimum is equal to , which is what Kasami-Lin-Peterson proved in 1968 (using more technical arguments involving BCH codes). This particular case of Alon-Furedi is what we need for most of our applications to finite geometry, and thus these results can also be seen as applications of the Kasami-Lin-Peterson theorem.
First let’s show that the original problem studied by Alon-Furedi, which also appeared as problem 6 in 2007 International Maths Olympiad, can be solved using Theorem 1. We are given a finite grid in and we are asked to show that the number of hyperplanes required to cover all points of the grid except one is equal to . Associate each hyperplane to the linear polynomial that defines it, and take the product of these linear polynomials. Then the set of points covered by the hyperplanes is equal to the set of zeros of this polynomial. If the degree of this polynomial, which is equal to the number of hyperplanes, is less than , then by Theorem 1 there are at least points of the grid which are not covered, a contradiction.
Now let’s look at this problem of hyperplane covering for the finite projective and affine spaces over . It would be important to remember that the projective space can be obtained from the affine space (which is isomorphic to after fixing a point), by adding a hyperplane at infinity. Let be hyperplanes in which do not cover all the points. Treating as the hyperplane at infinity, we get hyperplanes in which do not cover all the points of the grid . Therefore, by Theorem 1, there are at least points of which are missed by these hyperplanes. Such a collection of hyperplanes is known as a partial cover and the points missed are known as holes. By computing this function, we have the following corollary, which is a stronger version of a result of S. Dodunekov, L. Storme and G. Van de Voorde:
If , then a partial cover of of size has at least holes.
By projective duality, we can translate our statement to sets of points in which do not meet all hyperplanes. In fact, we get the following nice result for affine spaces by noticing that a subset of affine points in does not meet the hyperplane at infinity:
Theorem 2. Let be a set of points in . Then there are at least hyperplanes of which do not meet .
A direct corollary of Theorem 2 is the famous result of Jamison/Brouwer-Schrijver on affine blocking sets (sets of points which meet all hyperplanes, i.e., contain at least one point of each hyperplane):
The minimum number of points required to block all hyperplanes in is .
(Proof: if you take less than that many points, then by Theorem 2, there will be at least one hyperplane which does not meet the set of points)
We can obtain another interesting result on blocking sets, this time in . A point of a blocking set in is called an essential point if removing from we have a set which does not meet all hyperplanes. Clearly, through every essential point of , there must be a hyperplane such that . These are known as tangent hyperplanes. How many tangent hyperplanes can be there through an essential point of a blocking set?
Theorem 3. Let be a blocking set in and an essential point of . Then there are at least tangent hyperplanes through .
(Proof: fix a hyperplane through and treat it as the hyperplane at infinity; removing this hyperplane reduces the problem to Theorem 2 if we take .)
A nice direct corollary of Theorem 3 which I noticed today is a lower bound on the size of a blocking semioval that is almost the same as the bound obtained by Dover in 2000. A semioval in is a set of points with the property that for every point in , there is a unique line tangent to at (this property is satisfied by ovals but it does not characterise them). The classical examples of semiovals are obtained from polarities of projective planes. A semioval is called a blocking semioval if it is also a blocking set. There is a general lower bound of on the size of a blocking set in an arbitrary projective plane of order given by Bruen, but for blocking semiovals we can obtain a much better lower bound. From Theorem 3, it follows that if , then there are at least tangent lines through an essential point of . Therefore, if is a blocking set of size less than , then cannot be a semioval.