2014/01/29 by Orit E. Raz, Micha Sharir, Raz, Orit E. +3 · 5 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1401.7419
openalex publication_date 2014/01/29 · arxiv created 2014/03/19 · arxiv updated 2014/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)|=Ω(n4/3), for every pair of finite sets A,B⊂\mathbb R, with |A|=|B|=n (where the constant of proportionality depends on \rm deg f), or else f must be of one of the special forms f(u,v)=h(φ(u)+ψ(v)), or f(u,v)=h(φ(u)⋅ψ(v)), for some univariate polynomials φ,ψ,h over \mathbb R. This significantly improves a result of Elekes and Rónyai (2000). 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(n11/6) when |A|=|B|=|C|=n, where the constant of proportionality depends on \rm deg f, unless f has one of the aforementioned special forms. This result provides a unified tool for improving bounds in various Erd\H os-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 Ω(n4/3), extending the result of Pach and de Zeeuw (2013) and improving the bound of Charalambides (2012), 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.