Schwartz-Zippel bounds for two-dimensional products

Hossein Nassajian Mojarrad ; Thang Pham ; Claudiu Valculescu ; Frank de Zeeuw

Discrete analysis (2017)

Résumé

We prove bounds on intersections of algebraic varieties in $\mathbb{C}^4$ with Cartesian products of finite sets from $\mathbb{C}^2$, and we point out connections with several classic theorems from combinatorial geometry. Consider an algebraic variety $X$ in $\mathbb{C}^4$ of degree $d$, such that the polynomials defining $X$ are not all of the form $F(x,y,s,t) = G(x,y)H(x,y,s,t) + K(s,t)L(x,y,s,t)$. Let $P$ and $Q$ be finite subsets of $\mathbb{C}^2$ of size $n$. If $X$ has dimension one or two, then we prove $|X\cap (P\times Q)| = O_d(n)$, while if $X$ has dimension three, then $|X\cap (P\times Q)| =O_{d,\varepsilon}(n^{4/3+\varepsilon})$ for any $\varepsilon>0$. Both bounds are best possible in this generality (except for the $\varepsilon$). These bounds can be viewed as different generalizations of the Schwartz-Zippel lemma, where we replace a product of "one-dimensional" finite subsets of $\mathbb{C}$ by a product of "two-dimensional" finite subsets of $\mathbb{C}^2$. The bound for three-dimensional varieties generalizes the Szemerédi-Trotter theorem. A key ingredient in our proofs is a two-dimensional version of a special case of Alon's combinatorial Nullstellensatz. As corollaries of our two bounds, we obtain bounds on the number of repeated and distinct values of polynomials and polynomial maps of pairs of points in $\mathbb{C}^2$, with a characterization of those maps for which no good bounds hold. These results generalize known bounds on repeated and distinct Euclidean distances.

Détail

Publié le : 2017-12-20