Applications of Alon-Furedi to finite geometry

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 A = A_1 \times \cdots \times A_n be a finite grid in \mathbb{F}^n where |A_i| = a_i. Let f \in \mathbb{F}[t_1, \dots, t_n] be an n-variable polynomial of degree d such that the set \mathcal{U}_A(f) = \{x \in A : f(x) \neq 0\} is nonempty (in other words, f does not vanish on the entire grid). Then |\mathcal{U}_A(f)| \geq \mathfrak{m}(a_1, \dots, a_n; \sum_{i = 1}^n a_i - d). Moreover, the bound is sharp.

Here \mathfrak{m}(a_1, \dots, a_n; k) denotes the minimum value of the product y_1 \cdots y_n where y_i‘s are integers satisfying y_1 + \cdots + y_n = k and 1 \leq  y_i \leq a_i for all i. 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 d in a finite grid, given that the polynomial does not vanish on the entire grid.

If we take \mathbb{F} to be the finite field \mathbb{F}_q, and A_i = \mathbb{F}_q for all i, 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 \mathbb{F}_q is obtained by evaluating each reduced polynomial (degree in each variable at most q - 1, see this) of degree at most d on the points of \mathbb{F}_q^n. Clearly, the minimum Hamming distance of this linear code is the minimum number of non-zeros a reduced polynomial of degree at most d can have. But that’s precisely what the Alon-Furedi theorem is about! After an easy computation one can show that if d = a(q - 1) + b where 0 < b \leq q - 1, then this minimum is equal to (q - b)q^{n - a - 1}, 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 A_1 \times \cdots \times A_n  in \mathbb{F}^n and we are asked to show that the number of hyperplanes required to cover all points of the grid except one is equal to \sum (|A_i| - 1). 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 \sum (|A_i| - 1), then by Theorem 1 there are at least \mathfrak{m}(|A_1|, \dots, |A_n|; n + 1) \geq 2 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 \mathbb{F}_q. It would be important to remember that the projective space PG(n, q) can be obtained from the affine space AG(n, q) (which is isomorphic to \mathbb{F}_q^n after fixing a point), by adding a hyperplane at infinity. Let H_1, \dots, H_k be k hyperplanes in PG(n, q) which do not cover all the points. Treating H_k as the hyperplane at infinity, we get hyperplanes H_1', \dots, H_{k-1}' in \mathbb{F}_q^n which do not cover all the points of the grid \mathbb{F}_q^n. Therefore, by Theorem 1, there are at least \mathfrak{m}(q, \dots, q; nq - k + 1) points of PG(n, q) 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 0 \leq a < q, then a partial cover of PG(n, q) of size q + a has at least q^{n-1} - aq^{n-2} holes.

By projective duality, we can translate our statement to sets of points in PG(n, q) 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 PG(n, q) does not meet the hyperplane at infinity:

Theorem 2. Let S be a set of k points in AG(n, q). Then there are at least \mathfrak{m}(q, \dots, q; nq - k + 1) - 1 hyperplanes of AG(n, q) which do not meet S.

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 AG(n, q) is n(q - 1) + 1.

(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 PG(n, q). A point x of a blocking set B in PG(n, q) is called an essential point if removing x from B we have a set which does not meet all hyperplanes. Clearly, through every essential point of B, there must be a hyperplane H such that H \cap B = \{x\}. These are known as tangent hyperplanes. How many tangent hyperplanes can be there through an essential point of a blocking set?

Theorem 3. Let B be a blocking set in PG(n, q) and x an essential point of B. Then there are at least \mathfrak{m}(q, \dots, q; nq - |B| + 2) tangent hyperplanes through x.

(Proof: fix a hyperplane through x and treat it as the hyperplane at infinity; removing this hyperplane reduces the problem to Theorem 2 if we take S = B \setminus \{x\}.)

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 PG(2, q) is a set S of points with the property that for every point x in S, there is a unique line tangent to S at x (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 q + \sqrt{q} + 1 on the size of a blocking set in an arbitrary projective plane of order q given by Bruen, but for blocking semiovals we can obtain a much better lower bound. From Theorem 3, it follows that if |B| < 2q, then there are at least \mathfrak{m}(q, q; 3) \geq 2 tangent lines through an essential point of B. Therefore, if B is a blocking set of size less than 2q, then B cannot be a semioval.


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 Combinatorics, Finite Geometry, Polynomial Method and tagged , , . Bookmark the permalink.

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 )

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