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

## The Ellenberg-Gijswijt bound on cap sets

Four days back Jordan Ellenberg posted the following on his blog:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

Then two days later Dion Gijswijt made this comment on Ellenberg’s post:

What a nice result, congratulations!

Last week, I’ve also been writing a proof of an upper bound O(p^{cn}), c<1 for progression-free sets, in Z_p^n based on the same paper of Croot, Lev and Pach, see

http://homepage.tudelft.nl/64a8q/progressions.pdf

So I guess, you beat me to it! Also, your constant for the case p=3 is better than mine (O(2.76^n) vs O(2.84^n)). I think the CLP-paper is a real gem in its simplicity.

This is a true breakthrough, settling an important open problem in combinatorics that survived even after a lot of effort from several mathematicians (see this, this, this and this). Ultimately, just like the finite field Kakeya problem, it succumbed to the polynomial method. I really like the following comment by Ben Green on a Facebook post: “It’s amazing how the polynomial method seems to be so orthogonal to other methods. It’s a bit like Dvir’s proof of the finite field Kakeya – in a couple of pages, it sweeps aside a large body of partial results using complicated combinatorial and analytic methods to get much weaker statements.”

Problem statement: Find the maximum possible size of a subset of $\mathbb{F}_q^n$ which does not contain any three distinct elements in arithmetic progression.

A set with such a property is known as a cap set, a name probably inspired from the fact that the early examples of such sets in three dimension came from elliptic quadrics over finite fields, which look like hats (or caps) in real spaces. The elliptic quadrics are 3-dimensional examples of affine caps; sets of points  which do not contain any three points collinear with the same line (this condition is stronger than the condition above when $q > 3$ as it says that for any three distinct elements $a, b, c$ we have $c - b \neq \lambda (b -a)$ for all $\lambda \in \mathbb{F}_q \setminus \{0, -1\}$.). The oldest reference that I could find mentioning the term “cap” for such sets is this 1958 paper by Segre: On Galois Geometries. When $q = 3$, affine caps are related to the game SET and you can read the following brilliant paper by B. L. Davis and D. Maclagan which explains this connnection: The card game SET.

Ellenberg and Gijswijt  have proved that a cap set in $\mathbb{F}_q^n$ has size at most a constant times the number of monomials $x_1^{e_1}x_2^{e_2}\cdots x_n^{e_n}$ of total degree at most $(q-1)n/3$ that satisfy $0 \leq e_i \leq q - 1$ for all $i$.

Understanding their beautiful proof requires only some knowledge of basic linear algebra and polynomials. I’ll try to explain the main arguments here. Ultimately, one also needs to estimate the total number of monomials that satisfy the conditions above, for which I will refer to the preprints of Ellenberg and Gijswijt, and to the comments section of the blog post by Ellenberg. One crucial thing to note about the estimates is that this bound is good only because $(q-1)n/3$ is strictly less than the mean $(q-1)n/2$.

Let $q$ be an odd prime power and let $\mathcal{P}_d(n, q)$ denote the set of all polynomials $f$ in $\mathbb{F}_q[x_1, \dots, x_n]$ that satisfy $\deg f \leq d$ and $\deg_{x_i} f \leq q - 1$ for all $i$, aka, the set of reduced polynomials of degree at most $d$. The set of all reduced polynomials with no restriction on the total degree is simply denoted by $\mathcal{P}(n, q)$. There is a vector space isomorphism between $\mathcal{P}(n, q)$ and the space of all $\mathbb{F}_q$-valued functions on $\mathbb{F}_q^n$ given by evaluating the polynomials. Let $k_d$ denote the dimension of $\mathcal{P}_d(n, q)$, which is equal to the total number of integral solutions of $e_1 + \dots + e_n \leq d$ and $0 \leq e_i \leq q - 1$. Clearly, $k_{n(q - 1) - d} = q^n - k_d$ via the bijection $(e_1, \dots, e_n) \mapsto (q - 1 - e_1, \dots, q - 1 - e_n)$.

For a $3$-term arithmetic progression free subset $A$ of $\mathbb{F}_q^n$, the sets $A + A = \{a + a' : a, a' \in A, a \neq a'\}$ and $2A = \{a + a : a \in A\}$ are disjoint as otherwise we will have three distinct elements $a, b, c$ in $A$ satisfying $a + c = 2b$.
Let $U$ be the subspace of $\mathcal{P}(n, q)$ consisting of all polynomials that vanish on the complement of $2A$.
Then $\dim U = |2A| = |A|$ (since $q$ is odd) and thus we try to find upper bounds on $\dim U$.
For any integer $d \in \{0, 1, \dots, n(q - 1)\}$ let $U_d$ be the intersection of $\mathcal{P}_d(n, q)$ with $U$.
Then since the span $\langle U, \mathcal{P}_d(n, q) \rangle$ is a subspace of  $\mathcal{P}(n, q)$, by the dimension formula we have $\dim U \leq \dim \mathcal{P}(n, q) - \dim \mathcal{P}_d(n, q) + \dim U_d$, or equivalently, $|A| \leq q^n - k_d + \dim U_d = k_{n(q - 1) - d} + \dim U_d.$

Now the crux of the proof is Proposition 1 in Jordan’s preprint, which is essentially equivalent to Lemma 1 of Croot-Lev-Pach’s paper, and says that every (reduced) polynomial of degree at most $d$ which vanishes on $A + A$ has at most $2 k_{d/2}$ non-zeros in $2A$. The proof of this is an interesting dimension argument which I will skip for now (also see this old mathoverflow question by Seva).

Since $A + A$ is a subset of the complement of $2A$, the above proposition implies that every element of $U_d$, when seen as an element of $\mathbb{F}_q^{\mathbb{F}_q^n}$ via the evaluation isomorphism, has at most $2 k_{d/2}$ non-zero coordinates. I leave it as an exercise to show that a vector subspace $V$ of $F^n$ with the property that every element of $V$ has at most $k$ non-zero coordinates must have its dimension less than or equal to $k$ (hint: row reduction). And thus $\dim U_d \leq 2 k_{d/2}$.

Therefore, from the earlier inequality on $|A|$, we get $|A| \leq k_{n(q - 1) - d} + 2k_{d/2}$.
Finally, observe that $n(q - 1) - d = d/2$ when $d = 2(q - 1)n/3$, which gives us the bound $|A| \leq 3 k_{(q - 1)n/3}$ (whenever $(q - 1)n/3$ is an integer).
The reason why this is a good bound is that $k_{d}$ is bounded above by $q^{\lambda n}$ for some $\lambda < 1$ whenever $d < (q - 1)n/2$ (see the preprints).

Some questions:
(1) Can we obtain a better bound on affine caps since they are much more restrictive than cap sets?
(2) Do these techniques say anything about sets which do not contain any full line, i.e., the complements of affine blocking sets with respect to lines? As Ferdinand has pointed out in this comment, we have a general upper bound of the form $q^n - 2q^{n - 1} + 1$ there.
(3) What about sets which do not contain any $k$ terms in arithmetic progression, for $k > 3$?

[1] Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem! by Gil Kalai
[2] Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven. by Gil Kalai
[3] A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound by Terence Tao
[4] Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets by Fedor Petrov
[5] Large caps in projective Galois spaces, by Jürgen Bierbrauer and Yves Edel
[6] Zero-sum problems in finite abelian groups and affine caps, by Edel et al.
[7] Sumsets and sumsets of subsets, by Jordan Ellenberg.
[8] Bounds for sum free sets in prime power cyclic groups – three ways, by David speyer.
[9] Talk by Jordan Ellenberg at Discrete Math Seminar in IAS, Princeton.

## The Erdős-Ginzburg-Ziv theorem

Let $S = (a_1, \dots, a_n)$ be  a sequence of integers (not necessarily distinct). Then there exists a subsequence of $S$ the sum of whose elements is divisible by $n$

This is one of the first problems I saw when learning the pigeonhole principle. And it’s a good exercise to try it yourself by taking the pigeonhole principle as a hint. For our purpose, it’s best stated and proved in the following form.

Theorem 1. Let $S = (g_1, \dots, g_n)$ be a sequence of elements of an abelian group $(G, +, 0)$ of order $n$. Then there exists a non-empty subsequence of $S$ that sums up to $0$

Proof. Define $s_1 = g_1$, $s_2 = g_1 + g_2$, $\dots$, $s_n = g_1 + \dots + g_n$. Say none of the $s_i$‘s are zero. Since there are $n - 1$ non-zero elements in $G$, we must have $s_i = s_j$ for some $i < j$ by the pigeonhole principle. Hence $s_j - s_i = \sum_{k = i+1}^j a_k = 0$.

In 1961, Erdős, Ginzburg and Ziv proved an interesting similar looking result which later became one of the pioneering results in the field of additive combinatorics/combinatorial number theory/arithmetic combinatorics. It says that given a sequence of $2n - 1$ integers, $n$ of them must have their sum divisible by $n$. In fact, the original paper  implicitly proves the following more general result.

Theorem 2 (EGZ). Let $S = (g_1, \dots, g_{2n-1})$ be a sequence of elements of an abelian group $(G, +, 0)$ of order $n$. Then there exists a non-empty subsequence of $S$ that sums up to $0$ and has size $n$

There is an induction step in the paper which shows that it suffices to prove Theorem 2 in the special case when $G$ is the cyclic group of prime order $p$, i.e., $G \cong (\mathbb{F}_p, + , 0)$ where $\mathbb{F}_p$ is the finite field of order $p$. In this post I will discuss the proof of this prime case using the Alon-Furedi theorem, which was originally discovered by Clark, Forrow and Schmitt in Warning’s Second Theorem with Restricted Variables and then rediscovered by me and potu. The proof is quite similar to the 1989 proof by C. Bailey and R.B. Richter which used the famous Chevalley-Warning theorem, but instead we use a generalisation of CW; the so-called Restricted-Variable Chevalley-Warning theorem due to David Brink that follows directly from Alon-Furedi. I believe that this is a more natural proof than the one that uses Chevalley-Warning.

Theorem 3 (RV CW). Let $P_1, \dots, P_r \in \mathbb{F}_q[t_1, \dots, t_n]$. For $1 \leq i \leq n$, let $A_i \subseteq \mathbb{F}_q$ and put $A = \prod_{i = 1}^n A_i \subseteq \mathbb{F}_q^n$. If $\sum (q -1) \deg P_i < \sum (|A_i| - 1)$, then $P_i$‘s can’t have a unique common zero in $A$

Proof. Let $P = \prod (1 - P_i^{q-1})$. Say all $P_i$‘s have a common zero $a \in A$. Then $P(a) \neq 0$, so $P$ is a non-zero polynomial of degree $d = \sum (q - 1)\deg P_i < \sum (|A_i| - 1)$. Thus, by Alon-Furedi it has at least $\mathfrak{m}(|A_1|, \dots, |A_n|; \sum |A_i| - d) \geq 2$ non-zeros in $A$, which gives us at least two common zeros of $P_i$‘s.

We are now ready to prove the EGZ theorem for $G \cong \mathbb{F}_p$. Let $a_1, \ldots, a_{2p - 1}$ be elements of $\mathbb{F}_p$. Let $f = \sum a_i t_i$ and $g = \sum t_i$ be two polynomials in $\mathbb{F}_p[t_1, \dots, t_{2p-1}]$. Then $(0, \dots, 0)$ is a common zero of $f$ and $g$ and since $\deg f + \deg g = 2p - 2 < 2p-1$, there exists another common zero $x = (x_1, \dots, x_{2p-1})$ in $\{0, 1\}^{2p-1}$. Let $i_1, \dots, i_k$, be all the positions where $x_i$ is equal to $1$. Then $f(x) = 0$ gives us $a_{i_1} + \dots + a_{i_k} = 0$ and $g(x) = 0$ gives us $k \equiv 0 \pmod{p}$. Since $0 < k < 2p$, we must have $k = p$. $\blacksquare$

For the sake of completeness, let’s give the induction argument also which will completely prove Theorem 2. We say that a finite abelian group $(G, +, 0)$ satisfies the EGZ property if any sequence of $2|G| - 1$ elements of $G$ contains a subsequence of length $|G|$ that sums up to $0$.

Lemma 4. Let $G$ be a finite abelian group and $N$ a subgroup of $G$If both $N$ and $G/N$ satisfy the EGZ property, then $G$ also satisfies the EGZ property.

Proof. Say $|N| = n$ and $|G/N| = r$. Let $S = (g_1, \dots, g_{2nr - 1})$ be a sequence of elements of $G$.
Since $G/N$ satisfies the EGZ property, from the elements $g_1 + N, \dots, g_{2r - 1} + N$ of $G/N$ we can choose $r$ which sum to the identity of $G/N$. By renaming the elements say $g_1 + N, \dots, g_r + N$ are those elements, i.e., $(g_1 + \dots + g_r) + N = N$, or equivalently we have $h_1 = g_1 + \dots + g_r \in N$. Now look at the first $2r - 1$ elements of the remaining $2nr - 1 - r$ elements of $S$ and repeat the argument to get $h_2 = g_{r+1} + \dots + g_{2r} \in N$. We can repeat this procedure till we have $h_{2n - 1} = g_{(2n - 2)r + 1} + \dots + g_{(2n - 1)r} \in N$.
Since $N$ satisfies the EGZ property, after renaming $h_i$‘s, we have $h_1 + \dots + h_n = 0$. By plugging in the values of $h_1, \dots, h_n$ in terms of the elements of $S$ we obtain $nr$ elements of $G$ that sum up to $0$.

Lemma 4 along with the fundamental theorem of finite abelian groups now proves the theorem. In fact, one can prove a similar lemma for non-abelian groups and use it to prove EGZ for all solvable groups, as was done by B. Sury in this paper. For more discussion on this result, see these notes by Pete or any standard textbook on additive combinatorics/combinatorial number theory. Also see this famous paper by Alon and Dubiner that discusses several proofs of this result.

Posted in Combinatorics, Polynomial Method | | 7 Comments

## Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

In the post Balls in Bins I wrote about a combinatorial function $\mathfrak{m}(a_1, \dots, a_n; k)$ which denotes the minimum value of the product $y_1 \cdot y_2 \cdots y_n$ among all distributions $(y_1, y_2, \dots, y_n)$ of $k$ balls (so $y_1 + y_2 + \dots + y_n = k$) in $n$ bins with the constraints $1 \leq y_i \leq a_i$. It turns out that this combinatorial function is linked to zeros of a multivariable polynomial in a “finite grid”. Here, by a finite grid I mean a subset $A \subseteq \mathbb{F}^n$ of the form $A = A_1 \times \cdots \times A_n$ where $\mathbb{F}$ is a field and $A_i$‘s are finite subsets of $\mathbb{F}$. The Alon-Furedi theorem, which provides this link, is as follows:

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.

For the sharpness of this bound let $(y_1, \dots, y_n)$ be any feasible distribution of $\sum_{i = 1}^n a_i - d$ balls in bins. Pick subsets $B_i \subseteq A_i$ with $|B_i| = y_i$ and define $f = \prod_{i = 1}^n \prod_{\lambda \in A_i \setminus B_i} (t_i - \lambda)$ which has degree $\sum_{i = 1}^n (a_i - y_i) = d$ and doesn’t vanish on $y_1 \cdot y_2 \cdots y_n$ points of the grid $A$.

This theorem appears in the last pages of [1] as Theorem 5, and until the appearance of [4] where Clark, Forrow and Schmitt used it to obtain a generalization of Warning’s second theorem and several interesting results in combinatorics and additive number theory, it seems like this result was largely ignored. In [3] Pete further generalized the results of [4] and gave some nice applications to graph theory, additive group theory and polynomial interpolation. In fact, he also generalized the Alon-Füredi theorem by replacing the field $\mathbb{F}$ by a commutative ring $R$ and imposing some extra conditions on the grid which are vacuously true for the field case. While discussing some results of [4] with Pete and John I realised that we can do much more with this Alon-Furedi theorem, and this resulted in my joint paper with Pete, Aditya and John [2], which I have also discussed here. A particular contribution of [2] is the following generalization of Alon-Furedi (Theorem 3 below) for which we first need some motivation.

The famous Schwartz-Zippel lemma says that a polynomial in $\mathbb{F}_q[t_1, \dots, t_n]$ of degree $d \leq q$ has at most $dq^{n-1}$ zeros in $\mathbb{F}_q^n$. In fact it works over more general grids as well where it says that if $A_1, A_2, \dots, A_n$ are finite subsets of $\mathbb{F}$ with $|A_1| \geq |A_2| \geq \cdots \geq |A_n|$ and $f$ a polynomial of degree $d \leq |A_n|$, then $f$ has at most $d|A_1||A_2|\cdots|A_{n-1}|$ zeros in $A_1 \times \dots \times A_n$. Since Theorem 1 gives a lower bound on the number of non-zeros of a polynomial in a finite grid, it automatically gives an upper bound on the numbers of zeros of that polynomial. This observation leads to a natural question.

When the degree of the polynomial is at most $|A_n|$, does Theorem 1 imply the Schwartz-Zippel lemma?

If you do the math, then you would see that indeed, it does. So, the Alon-Füredi theorem is in fact a generalization of the so-called Schwartz-Zippel lemma (see the blog post by RJ Lipton and some comments on it for why I have used “so-called” in this sentence). But, there are other results in the spirit of Schwartz-Zippel lemma, which do not follow from Theorem 1! The following result is due to DeMillo-Lipton and Zippel:

Theorem 2. Let $f \in \mathbb{F}[t_1, \dots, t_n]$ be a non-zero polynomial such that for all $i$, we have $\deg_{t_i} f \leq d$ for some constant $d$. Then for a subset $S \subseteq \mathbb{F}$ of cardinality at least $d + 1$, the number of zeros of $f$ in $S^n$ is at most $|S|^n - (|S| - d)^n$

To see that this result doesn’t follow from Theorem 1, take $S = \{0, 1, 2\} \subseteq \mathbb{Q}$ and $f = t_1 t_1 \in \mathbb{Q}[t_1, t_2]$. Then Theorem 1 tells us that $f$ has at most $6$ zeros in $S^2$, while Theorem 2 tells us that $f$ has at most $5$ zeros (which is stronger and the sharp bound in this case). This doesn’t mean that DeMillo-Lipton/Zippel’s result is always better. In fact, if you take $f = t_1 + t_2$, then Theorem 1 gives the better bound. To “rectify” this situation was one of our main motivation to give the following generalization of Theorem 1, which appears as Theorem 1.2 in [2].

Theorem 3 (Generalized Alon-Furedi). Let $A = A_1 \times \cdots \times A_n$ be a finite grid in $\mathbb{F}^n$ where $|A_i| = a_i$.  For $i \in \{1, 2, \dots, n\}$ let $b_i$ be an integer such that $1 \leq b_i \leq 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 and $\deg_{t_i} f \leq a_i - b_i$ for all $i$. Then we have $|\mathcal{U}_A(f)| \geq \mathfrak{m}(a_1, \dots, a_n; b_1, \dots, b_n; \sum_{i = 1}^n a_i - d)$. Moreover, the bound is sharp.

Here $\mathfrak{m}(a_1, \ldots, a_n; b_1, \ldots, b_n; k)$ is defined to be the minimum value of the product $y_1 \cdot y_2 \cdots y_n$ among all distributions $(y_1, y_2, \dots, y_n)$ of $k = y_1 + y_2 + \dots + y_n$ balls in $n$ bins with the constraints $b_i \leq y_i \leq a_i$. If you “do the math” (see Section 4 of [2]), then Theorem 3 is a common generalization of Theorem 1, Schwartz-Zippel lemma and Theorem 2.

References
[1] N. Alon and Z. Füredi, Covering the cube by affine hyperplanes. Eur. J. Comb. 14 (1993), 79–83.
[2] A. Bishnoi, P. L. Clark, A. Potukuchi, J. R. Schmitt, On Zeros of a Polynomial in a Finite Grid (2015). arXiv preprint arXiv:1508.06020.
[3] P. L. Clark, Fattening up Warning’s Second Theorem (2015). arXiv preprint arXiv:1506.06743.
[4] P. L. Clark, A. Forrow and J. R. Schmitt, Warning’s Second Theorem With Restricted Variables. To appear in Combinatorica, (2016).

Posted in Combinatorics, Polynomial Method | | 2 Comments

## A timeline of the polynomial method up-to combinatorial nullstellensatz

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s  paper on the Kakeya conjecture, where he solved a major open problem by a short and easy polynomial argument. After that, many prominent mathematicians from different areas of mathematics started looking into these techniques, and in some cases, ended up resolving some famous open problems: On the Erdős distinct distances problem in the plane.

In this post I will give a timeline of some important papers (in my opinion) related to the polynomial method, starting from Tom H. Koornwinder’s paper on equiangular lines till the appearance of Combinatorial Nullstellensatz by Noga Alon (1999) (so, this timeline will cover only the part A of polynomial method as mentioned here). But first, here are some quotes that describe the general philosophy behind the polynomial method:

Given a set of points (or vectors, or sets) that satisfy some property, we want to say something about the size or the structure of this set. The approach is then to associate to this set a polynomial, or a collection of polynomials, and use properties of polynomials to obtain information on the size or structure of the set.

– Aart Blokhuis, 1993

Broadly speaking, the strategy is to capture (or at least partition) the arbitrary sets of objects (viewed as points in some configuration space) in the zero set of a polynomial whose degree (or other measure of complexity) is under control; for instance, the degree may be bounded by some function of the number of objects. One then uses tools from algebraic geometry to understand the structure of this zero set, and thence to control the original sets of object.

– Terence Tao, 2013

1975
A note on the absolute bound for systems of lines, by Koornwinder

1977
On Two-Distance Sets in Euclidean Space, by Larmen, Rogers and Seidel
Covering finite fields with cosets of subspaces, by Jamison

1978
The blocking number of an affine space, by Brouwer and Schrijver

1981
A New Upper Bound for The Cardinality of 2-Distance Sets in Euclidean Space, by Blokhuis
Intersection theorems  with geometric consequences, by Frankl and Wilson
Remarks on a theorem of Rédei, by Lovasz and Schrijver

1984
Regular subgraphs of almost regular graphs, by Alon, Friedland and Kalai
Every 4-regular graph plus an edge contains a 3-regular subgraph, by Alon, Friedland and Kalai

1987
– A characterization of exterior lines of certain sets of points in PG (2, q), by Blokhuis and Wilbrink

1988
A nowhere zero point in linear mappings, by Alon and Tarsi
A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality, by Babai
Balancing set of vectors, by Alon, Bergmann, Coppersmith and Odlyzko

1989
Sum zero (mod n), size n subsets of integers, by Bailey and Richter

1991
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems, by Alon, Babai and Suzuki

1992
Polynomial multiplicities over finite fields and intersection sets, by Bruen
Colorings and orientations of graphs, by Alon and Tarsi

1993
The Dinitz problem solved for rectangles, by Janssen
Covering the Cube by Affine Hyperplanes, by Alon and Furedi
Polynomials in finite geometries and combinatorics, by Blokhuis
Zero-sum sets of prescribed size, by Alon and Dubiner

1994
On the size of a blocking set in PG(2,p), by Blokhuis
On nuclei and affine blocking sets, by Blokhuis
– On multiple nuclei and a conjecture of Lunelli and Sce, by Blokhuis

1995
Tools from higher algebra, by Alon
Adding Distinct Congruence Classes Modulo a Prime, by Alon, Nathanson and Ruzsa
A new proof of several inequalities on codes and sets, by Babai, Snevily and Wilson
The number of directions determined by a function f on a finite field, by Blokhuis, Brouwer and Szonyi

1996
The Polynomial Method and Restricted Sums of Congruence Classes, by Alon, Nathanson and Ruzsa
Multiple blocking sets and arcs in finite planes, by Ball

1998
An easier proof of the maximal arcs conjecture, by Ball and Blokhuis
Sumsets in Vector Spaces over Finite Fields, by Eliahou and Kervaire

1999
– Multilinear Polynomials and a Conjecture of Frankl and Füredi, by Sankar and Vishwanathan
Combinatorial Nullstellensatz, by Alon

Beyond this, many excellent surveys on the polynomial method are available in which one can find further developments. For example,

| | 1 Comment

## On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound

My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020.

This work started a few months back when I emailed Pete and John, pointing out an easy generalization of Chevalley-Warning theorem using something known as the punctured combinatorial nullstellensatz, after reading their paper on Warning’s second theorem: arXiv:1404.7793. They got pretty excited about it and we started discussing some related things. Finally, it’s not the generalization of Chevalley-Warning that this paper is about but the theorem of Alon-Füredi itself, which is the main tool they used in their paper to generalize Warning’s second theorem. In our discussions we found several unexplored connections between this elementary result on polynomials and results from different areas of maths. My friend Aditya joined us in between with his amazingly simple proof of Alon-Füredi which, along with the annoying realization that a result of DeMillo-Lipton-Zippel doesn’t follow from Alon-Füredi, led us to generalize Alon-Füredi.

These results when combined with the recent work by Pete, Aden Forrow and John (and the follow up by Pete: arXiv:1506.06743) shows how powerful this Alon-Füredi bound is. Among many other things, it implies the following results:

1. Chevalley-Warning theorem, Warning’s second theorem and their generalizations.
2. Olson’s theorem on the Davenport constant of p-groups.
3. Schwartz-Zippel lemma (or rather DeMillo-Lipton-Schwartz-Zippel lemmas).
4. Minimum Hamming distance of Reed-Muller type affine variety codes.
5. Jamison/Brouwer-Schrijver bound on affine blocking sets.

I am hopeful that there are many other connections which will be discovered. Much like Alon’s Combinatorial Nullstellensatz, this is a pretty basic result on polynomials with several interesting applications. In some subsequent posts, I will try to discuss this in much more detail.

## Discrete version of the Intermediate Value Theorem

While working on a combinatorial problem with Potu today I came up with an easy theorem that can be called a discrete version of the Intermediate Value Theorem. It can be stated as follows.

For integers $a < b$, let $f$ be a function from the integers in $[a, b]$ to $\mathbb{Z}$ that satisfies the property, $|f(i+1) - f(i)| \leq 1$ for all $i$. If $f(a) < 0 < f(b)$, then there exists an integer $c \in (a, b)$ such that $f(c) = 0$.

Note the similarity with the continuous version of this theorem:

For real numbers $a < b$, let $f$ be a continuous function from $[a, b]$ to $\mathbb{R}$. If $f(a) < 0 < f(b)$, then there exists a real number $c \in (a, b)$ such that $f(c) = 0$.

The discrete analog of continuity is the property that going from integer $i$ to $i + 1$, we make a jump of at most $1$. It turns out that the similarity of these two theorems extends to their proofs as well. Here’s a proof of the discrete version:

Proof. Let $S = \{x \in \mathbb{Z} \cap [a, b] : f(x) < 0\}$ and let $c = \max S + 1$. We claim that $f(c) = 0$.
Say $f(c) < 0$. Then $c \in S$. This contradicts the fact that $c-1$ is an upper bound on $S$. Say $f(c) > 0$. This implies that $f(c-1) \geq 0$ (by “continuity”), which contradicts the fact that $c - 1 \in S$. $\blacksquare$

And here’s the standard proof for the continuous version.

Proof.  Let $S = \{x \in [a, b] : f(x) < 0\}$ and let $c = \sup S$. We claim that $f(c) = 0$.
Say $f(c) < 0$. Pick a number $c' > c$ such that $f(c') < 0$ (we can do so because of continuity of $f$). Then $c' \in S$. This contradicts the fact that $c$ is an upper bound. Say, $f(c) > 0$. Then there exists a $\delta > 0$ such that $f(x) > 0$ for all $x \in (c - \delta, c + \delta)$ (again by continuity). But, by the definition of supremum there exists an element $c'' \in S$ satisfying $c - \delta < c'' < c$. Then $f(c'') > 0$, which contradicts the fact that $c'' \in S$. $\blacksquare$

Here’s the combinatorial theorem where the discrete version showed up. Let $S_1, \dots, S_{2n}$ be subsets of $\{1, \dots, 4n\}$ defined by $S_i := \{i, i + 1, \dots, i + 2n - 1\}$. Then for every subset $T \subset \{1, \dots, 4n\}$ of cardinality $2n$ there exists a $k$ such that $|S_k \cap T| = n$.

Proof. Define $f(i) = |T \cap S_i| - n$ for $i \in \{1, \dots, 2n\}$. Then it’s easy to check that $|f(i+1) - f(i)| \leq 1$ for all $i$. In fact, we can define the function on $i = 2n + 1$ as well by taking $S_{2n + 1} = \{2n + 1, 2n + 2, \dots, 4n\}$. Since $T$ has cardinality $2n$ we have $f(1) < 0$ implies $f(2n+1) > 0$, and vice versa. Say $f(1) \neq 0$. Then without loss of generality we may assume that $f(1) < 0$. Then $f(2n + 1) > 0$. Therefore, there exists a $k \in \{2, \dots, 2n\}$ such that $f(k) = 0$. $\blacksquare$

After I wrote this argument in my notes, I googled “discrete intermediate value theorem” and found out that someone has already written about this theorem. See this article by Richard Johnsonbaugh. He gives another cute application of this theorem. It’ll be fun to find more applications of this easy theorem.

Edit: As pointed out by Peter, a similar problem is discussed here: http://artofproblemsolving.com/community/c6h14981

Posted in Real Analysis | Tagged | 3 Comments