## 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.