Schwartz-Zippel bounds for two-dimensional products

DOI10.19086/DA.2750MaRDI QIDQ4645025zbMATH OpenOpenAlexFDO

Authors Hossein Nassajian Mojarrad, Pham Van Thang, Claudiu Valculescu, Frank de Zeeuw

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1507.08181

Mathematics Subject Classification ID

Algebraic combinatorics (05E99) Classification of affine varieties (14R05) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: 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 $|Xcap(PimesQ)|=O_d(n)$, while if $X$ has dimension three, then $|Xcap(PimesQ)|=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 $mathbbC$ by a product of "two-dimensional" finite subsets of $mathbb{C}^2$. The bound for three-dimensional varieties generalizes the Szemer'edi-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.

Recommendations

• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Incidence bounds for complex algebraic curves on Cartesian products
• Incidences between points and lines on two- and three-dimensional varieties

Cites work

• A semi-algebraic version of Zarankiewicz's problem
• A Szemerédi-Trotter type theorem in R^4
• Algebraic methods in sum-product phenomena
• Approximate subgroups of linear groups.
• Combinatorial Nullstellensatz
• Distinct Distances on Algebraic Curves in the Plane
• Distinct distances on two lines
• Distinct values of bilinear forms on algebraic curves
• Extremal problems in discrete geometry
• Graph theory
• scientific article; zbMATH DE number 1943961 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• On an application of Guth-Katz theorem
• On Sets of Distances of n Points
• On the Erdős distinct distances problem in the plane
• On the Minkowski distances and products of sum sets
• On the use of the Klein quadric for geometric incidence problems in two dimensions
• Point-curve incidences in the complex plane
• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Reducibility of rational functions in several variables
• Repeated angles in the plane and related problems
• The Erdős distance problem
• The total reducibility order of a polynomial in two variables

Cited in

(8)

• The Elekes-Szabó theorem in four dimensions
• How to find groups?
• Subquadratic algorithms for algebraic 3SUM
• Incidence bounds for complex algebraic curves on Cartesian products
• The Multivariate Schwartz--Zippel Lemma
• Model-theoretic Elekes–Szabó in the strongly minimal case
• Bounding 2d functions by products of 1d functions
• Edge weight based colouring and matching in inhomogenous random graphs

This page was built for publication: Schwartz-Zippel bounds for two-dimensional products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645025)