## 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  as Theorem 5, and until the appearance of  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  Pete further generalized the results of  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  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 , which I have also discussed here. A particular contribution of  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 .

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 ), then Theorem 3 is a common generalization of Theorem 1, Schwartz-Zippel lemma and Theorem 2.

References
 N. Alon and Z. Füredi, Covering the cube by affine hyperplanes. Eur. J. Comb. 14 (1993), 79–83.
 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.
 P. L. Clark, Fattening up Warning’s Second Theorem (2015). arXiv preprint arXiv:1506.06743.
 P. L. Clark, A. Forrow and J. R. Schmitt, Warning’s Second Theorem With Restricted Variables. To appear in Combinatorica, (2016). 