The Elekes-Rónyai-Szabó theory and its applications

Micha Sharir, Tel Aviv University

February 16, 2015

Let $F(x,y,z)$ be a real trivariate polynomial of constant degree, and let $A$, $B$, $C$ be three sets of real numbers, each of size $n$.

How many roots can $F$ have on $A \times B \times C$?

This setup arises in many interesting problems in combinatorial geometry, including distinct distances between points on curves, distinct distances from three points, collinear triples of points on curves (the ‘orchard problem’), unit-area triangles, triple intersection points of families of circles, and more.

This question has been studied by Elekes and Róonyai and then by Elekes and Szabó about 15 years ago. One of their striking results is that, for the special case where $F(x,y,z) = z-f(x,y)$, either $F$ vanishes at quadratically many points of $A \times B \times C$, or else f must have one of the special forms $f(x,y) = h(p(x)+q(y))$ or $f(x,y) = h(p(x)q(y))$, for univariate polynomials $p$, $q$, $h$.

In this talk I will survey recent progress on this problem, in which the analysis is greatly simplified, and the bounds become sharp: If $F$ does not have a special form, the number of roots is at most $O(n^{11/6})$. Moreover, the results also hold over the complex field. This yields significantly improved bounds for many geometric problems, as listed above.

The proofs use techniques from algebra and algebraic geometry, which are somewhat related to the recent growing body of work on algebraic techniques for incidences and distance problems, inspired by Guth and Katz's seminal papers.

Joint work with Orit Raz, Jozsef Solymosi, and Frank de Zeeuw (and others).