Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited

DOI10.1215/00127094-3674103MaRDI QIDQ504018zbMATH OpenOpenAlexFDO

Authors Orit E. Raz, Micha Sharir, Frank de Zeeuw

Publication date 25 January 2017

Published in Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.05012, https://projecteuclid.org/euclid.dmj/1473275860

zbMATH Keywords

combinatorial geometrydiscrete geometryincidencespolynomials

Mathematics Subject Classification ID

Extremal combinatorics (05D99) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: Let $FinmathbbC[x,y,z]$ be a constant-degree polynomial,and let $A,B,CsubsetmathbbC$ be finite sets of size $n$. We show that $F$ vanishes on at most $O(n^{11/6})$ points of the Cartesian product $AimesBimesC$, unless $F$ has a special group-related form. This improves a theorem of Elekes and Szab'o [Combinatorica, 2012], and generalizes a result of Raz, Sharir, and Solymosi [Amer. J. Math., to appear]. The same statement holds over $mathbbR$, and a similar statement holds when $A,B,C$ have different sizes (with a more involved bound replacing $O(n^{11/6})$). This result provides a unified tool for improving bounds in various ErdH os-type problems in combinatorial geometry, and we discuss several applications of this kind.

Review text

This 50-pages paper has a 6-page introduction, which succinctly summarizes the motivation and the results of earlier papers. I recommend reading this introduction to anyone, who wants to know more about this paper. G. Elekes and his collaborators, working on hard Erdős problems in discrete geometry, identified an algebraic problem behind the geometric problems: how many zeros a trivariate polynomial \(F(x,y,z)\) can have on a finite Cartesian product set \(A\times B\times C\)? It turned out that the answer depends on whether the polynomial is generic or belongs to a very special family, at least for the instance \(F(x,y,z)=f(x,y)-z\). The paper under review generalizes the existing results, and reproduces the best earlier bounds, which were available for special cases. The main theorem states: Let \(F\in \mathbb{C}[x,y,z]\) be an irreducible polynomial of degree \(d\), and assume that none of the derivatives \(\partial F/\partial x\), \(\partial F/\partial y\), \(\partial F/\partial z\) is identically zero. Let \(Z(F) \) denote the zero set of \(F\). Then one of the following two statements hold: (i) For all \(A,B,C \subset \mathbb{C}\) with \(|A|=|B|=|C|=n\), we have \(|Z(F)\cap(A\times B\times C)|=O(d^{13/2}n^{11/6})\), (ii) There exists a 1-dimensional subvariety \(Z_0\subset Z(F)\) such that for all \(v\in Z(F)\setminus Z_0\) there exist open sets \(D_1,D_2,D_3\subset \mathbb{C}\) and one-to-one analytic functions \(\phi_i:D_i\rightarrow \mathbb{C}\) with analytic inverses, for \(i=1,2,3\), such that \(v\in D_1\times D_2\times D_3\) and for all \((x,y,z)\in D_1\times D_2\times D_3\), \((x,y,z)\in Z(F)\) if and only if \(\phi_1(x)+\phi_2(y)+\phi_3(z)=0\). The theorem can be extended (a) to reducible polynomials, (b) for cases, where \(A,B,C\) are not of the same size, (c) for polynomials of real variables instead of complex variables. The bounds in part (i) of the theorem are unlikely to be tight. One application of the main theorem is the following: Any \(n\) points on a constant-degree irreducible algebraic curve in \(\mathbb{C}^2\) determines \(O(n^{11/6})\) collinear triples of 3 distinct points, unless the curve is a line or a cubic.

Recommendations

• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Constructions for the Elekes-Szabó and Elekes-Rónyai problems
• The Elekes-Szabó theorem in four dimensions

Cited in

(29)

• The Elekes-Szabó theorem in four dimensions
• On sets defining few ordinary circles
• Geometric and o-minimal Littlewood-Offord problems
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• The Elekes-Szabó problem and the uniformity conjecture
• How to find groups?
• Constructions for the Elekes-Szabó and Elekes-Rónyai problems
• Extensions of a result of Elekes and Rónyai
• Note on separately symmetric polynomials on the Cartesian product of \(\ell_1\)
• Expanding polynomials: a generalization of the Elekes-Rónyai theorem to \(d\) variables
• Distinct distances on non-ruled surfaces and between circles
• Schwartz-Zippel bounds for two-dimensional products
• A note on distinct distances
• Projectives geometries arising from Elekes-Szabó problems
• The Multivariate Schwartz--Zippel Lemma
• Convex polygons in Cartesian products
• EXPANDING POLYNOMIALS ON SETS WITH FEW PRODUCTS
• Improved bounds for pencils of lines
• Model-theoretic Elekes–Szabó in the strongly minimal case
• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Sums, products, and dilates on sparse graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Improved Elekes-Szabó type estimates using proximity
• Convexity, squeezing, and the Elekes-Szabó theorem
• On the dimension of exceptional parameters for nonlinear projections, and the discretized Elekes-Rónyai theorem
• Distinct distances in \(\mathbf{R}^3\) between quadratic and orthogonal curves
• Distinct distances for points lying on curves in \(\mathbb{R}^d\) -- the bipartite case
• The number of unit-area triangles in the plane: theme and variation

This page was built for publication: Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited

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