Schwartz-Zippel bounds for two-dimensional products

- Mathematics, EPFL

- Mathematics, EPFL

- Mathematics, EPFL

- Mathematics, EPFL

*Discrete Analysis*, December. https://doi.org/10.19086/da.2750.

### Editorial introduction

Schwartz-Zippel bounds for two-dimensional products, Discrete Analysis 2017:20,

A famous open problem in combinatorial geometry is Erdős’s unit-distances problem, which asks the following: given a subset A⊂R2 of size n, how many pairs (a,b)∈A2 can there be with d(a,b)=1? (Here d is the usual Euclidean distance.) The best-known upper bound, due to Spencer, Szemerédi and Trotter, is O(n4/3), but it is conjectured that the true bound is O(n1+ϵ) for every ϵ>0. (By putting all the points along a line, one can obtain a lower bound of n−1 with ease.) This problem is closely related to Erdős’s distinct-distances problem, which was spectacularly solved by Guth and Katz, who showed that every set of size n in R2 must give rise to at least cϵn1−ϵ distinct distances. This would be a consequence of a positive answer to the unit-distances problem, since there are n2 pairs of points and each distance would occur at most Cϵn1+ϵ times.

An equally famous theorem in combinatorial geometry is the Szemerédi-Trotter theorem, which asserts that amongst any n points and m lines in R2, the number of incidences (that is, pairs (P,L) where P is one of the points, L is one of the lines, and P is on L) is at most O(m+n+m2/3n2/3).

This paper concerns a simultaneous generalization of the Szemerédi-Trotter theorem and the upper bound above for the unit-distances problem. The connection is that both problems can be viewed as giving upper bounds for the size of the intersection of a variety with a Cartesian product of two finite subsets of the plane. In the case of the unit-distances problem, the two subsets are equal and the variety is the zero set of the function f(a,b,c,d)=(a−c)2+(b−d)2−1. The intersection of this zero set with the Cartesian product A2 is the set of all pairs ((a,b),(c,d)) such that (a,b),(c,d)∈A and d((a,b),(c,d))=1, so the size of the intersection is the number of unit distances in A. As for the Szemerédi-Trotter theorem, if we let P be the set of points, given by their Cartesian coordinates, and L be the set of lines, associating the line y=cx+d with the pair (c,d), then the point (a,b) belongs to the line (c,d) if and only if b=ca+d, so the number of incidences is the size of the intersection of P×L with the zero set of the polynomial ac+d−b.

This observation makes it tempting to conjecture that for every non-zero 4-variable polynomial F and every pair A,B of subsets of R2 of size n there is an upper bound of O(n4/3) on the intersection of A×B with the zero set of F. However, this is easily seen to be false. If F has a formula of the form F(x,y,s,t)=G(x,y)H(x,y,s,t)+K(s,t)L(x,y,s,t), then A×B is contained in the zero set of F if G vanishes on A and K vanishes on B. So some condition is needed on the polynomial for the conjecture to have a chance of being correct. The main result of this paper is essentially that the above source of examples is the only one: if a polynomial in four complex variables cannot be written in this way, then there is an upper bound of Cϵn4/3+ϵ for any ϵ>0 for the intersection of its zero set with a Cartesian product of two subsets of C2 of size n. It is not clear whether this can be improved to an upper bound of O(n4/3) – hence the word “essentially” above.

The title of the paper comes from the fact that this result can be viewed as a generalization of a special case of the Schwartz-Zippel lemma, which concerns products of subsets of C rather than subsets of C2. The proof depends on a two-dimensional generalization of a special case of yet another central result in combinatorial geometry, Alon’s combinatorial Nullstellensatz. The paper also contains results about varieties of dimensions 1 and 2: for these the authors obtain a linear upper bound for the size of the intersection.

The Szemerédi-Trotter theorem is known to give a tight bound, so in general the main result of the paper cannot be improved. However, this does not rule out improvements for specific polynomials. In the light of the unit-distances problem, it would naturally be of great interest to understand which polynomials might give rise to upper bounds that are better than O(n4/3). One of the merits of this paper is that it focuses our attention on this question.