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

Posted on October 19, 2015 by Anurag Bishnoi

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

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Polynomial Method and tagged , , , . Bookmark the permalink.

4 Responses to Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

  1. Pingback: The Erdos-Ginzburg-Ziv theorem | Anurag's Math Blog

  2. Pingback: Applications of Alon-Furedi to finite geometry | Anurag's Math Blog

  3. Pingback: The footprint bound | Anurag's Math Blog

  4. Pingback: A coding theoretic application of the Alon-Füredi theorem | Anurag's Math Blog

Leave a comment