A survey of Elekes-Rónyai-type problems

Abstract: We give an overview of recent progress around a problem introduced by Elekes and R'onyai. The prototype problem is to show that a polynomial

f i n m a t h b b R [x, y]

has a large image on a Cartesian product

A i m e s B s u b s e t m a t h b b R^{2}

, unless

f

has a group-related special form. We discuss a number of variants and generalizations. This includes the Elekes-Szab'o problem, which generalizes the Elekes-R'onyai problem to a question about an upper bound on the intersection of an algebraic surface with a Cartesian product, and curve variants, where we ask the same questions for Cartesian products of finite subsets of algebraic curves. These problems lie at the crossroads of combinatorics, algebra, and geometry: They ask combinatorial questions about algebraic objects, whose answers turn out to have applications to geometric questions involving basic objects like distances, lines, and circles, as well as to sum-product-type questions from additive combinatorics. As part of a recent surge of algebraic techniques in combinatorial geometry, a number of quantitative and qualitative steps have been made within this framework. Nevertheless, many tantalizing open questions remain.

Review text

This survey is concerned primarily with two closely related combinatorial problems. Given a degree \(d\) polynomial \(f:\mathbb R^2 \rightarrow \mathbb R\), what lower bounds can be given for the size of the set \[ f(A,A):=\{f(a,b); a,b \in A \},\] where \(A\) is arbitrary? This is the Elekes-Rónyai problem. The example of \(A=\{1,\dots,n\}\) and \(f(x,y)=x+y\) shows that the trivial bound \(|f(A,A)|= \Omega_d(n)\) cannot be improved. The other canonical counterexample for this problem is when \(A\) is a geometric progression and \(f(x,y)=xy\). These two polynomials are degenerate for this problem. Essentially, the only cases under which growth of \(f(A,A)\) is not guaranteed (i.e. the family of degenerate polynomials) derive from these two polynomials. The Elekes-Rónyai Theorem - augmented by a quantitative improvement of Raz, Sharir and Solymosi - proves that for non-degenerate polynomial \(f:\mathbb R^2 \rightarrow \mathbb R\) of degree \(d\) and any \(A \subset \mathbb R\), \[ |f(A,A)| =\Omega_d(|A|^{4/3}). \] The closely related Elekes-Szabó problem asks for upper bounds on the size of \(|Z(F) \cap (A \times A \times A)|\), where \(A \subset \mathbb R\) is arbitrary and \(F\) is a polynomial of three variables and degree \(d\). An upper bound \(O_d(|A|^2)\) follows from simple algebraic considerations, and it is not difficult to construct an example to show that this bound is tight in general. However, for non-degenerate polynomials (essentially not those of the form \(F(x,y,z)=x+y+z\) or \(F(x,y,z)=xyz\) and variants thereof) a better bound is known. The high level of generality given by these two results leads to many interesting applications. Connections with the sum-product problem are explored, as well as to Erdős-type problems in discrete geometry. As well as surveying the most important known results for these problems and many close relatives, this paper also includes several interesting conjectures. Many of these conjectures are not particularly well known, and it is likely that some are appearing in print for the first time. This survey is nicely written and achieves the difficult goal offering something both to experts and to those who are looking to familiarise themselves in these problems for the first time. I would recommend it to anyone with interest in the Elekes-Szabó or Elekes-Rónyai problems. For the entire collection see [Zbl 1411.52002].

Recommendations

Cited in

(16)

This page was built for publication: A survey of Elekes-Rónyai-type problems

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