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