A survey of Elekes-Rónyai-type problems (Q2417581): Difference between revisions

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].