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.