Schwartz-Zippel bounds for two-dimensional products

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\subset\mathbb R^2\) of size \(n\), how many pairs \((a,b)\in A^2\) 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(n^{4/3})\), but it is conjectured that the true bound is \(O(n^{1+\epsilon})\) for every \(\epsilon>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 \(\mathbb R^2\) must give rise to at least \(c_\epsilon n^{1-\epsilon}\) distinct distances. This would be a consequence of a positive answer to the unit-distances problem, since there are \(n^2\) pairs of points and each distance would occur at most \(C_\epsilon n^{1+\epsilon}\) 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 \(\mathbb R^2\), 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+m^{2/3}n^{2/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 \(A^2\) is the set of all pairs \(((a,b),(c,d))\) such that \((a,b),(c,d)\in 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\times 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 \(\mathbb R^2\) of size \(n\) there is an upper bound of \(O(n^{4/3})\) on the intersection of \(A\times 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\times 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_\epsilon n^{4/3+\epsilon}\) for any \(\epsilon>0\) for the intersection of its zero set with a Cartesian product of two subsets of \(\mathbb C^2\) of size \(n\). It is not clear whether this can be improved to an upper bound of \(O(n^{4/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 \(\mathbb C\) rather than subsets of \(\mathbb C^2\). 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(n^{4/3})\). One of the merits of this paper is that it focuses our attention on this question.