Polynomials vanishing on grids: The Elekes-Rónyai problem revisited
Orit E. Raz, Micha Sharir, József Solymosi · American Journal of Mathematics · 2016
In this paper we characterize real bivariate polynomials which have a small range over large Cartesian products.We show that for every constant-degree bivariate real polynomial f , either |f (A, B)| = Ω(n 4/3 ), for every pair of finite sets A, B ⊂ R, with |A| = |B| = n (where the constant of proportionality depends on deg f ), or else f must be of one of the special formsfor some univariate polynomials ϕ, ψ, h over R.This significantly improves a result of Elekes and Rónyai [10].Our results are cast in a more general form, in which we give an upper bound for the number of zeros of z = f (x, y) on a triple Cartesian product A × B × C, when the sizes |A|, |B|, |C| need not be the same; the upper bound is O(n 11/6 ) when |A| = |B| = |C| = n, where the constant of proportionality depends on deg f , unless f has one of the aforementioned special forms.This result provides a unified tool for improving bounds in various Erdős-type problems in geometry and additive combinatorics.Several applications of our results to problems of these kinds are presented.For example, we show that the number of distinct distances between n points lying on a constant-degree parametric algebraic curve which does not contain a line, in any dimension, is Ω(n 4/3 ), extending the result of Pach and de Zeeuw [23] and improving the bound of Charalambides [4], for the special case where the curve under consideration has a polynomial parameterization.We also derive improved lower bounds for several variants of the sum-product problem in additive combinatorics.