The ACO Seminar (2013–2014)

During 2013, significant progress has been obtained for several problems that are related to the Erdős distinct distances problem. In this talk I plan to briefly describe some of these results and the tools that they rely on. I will focus on the following two results.

Let P and P' be two sets of points in the plane, so that P is contained in a line L, P' is contained in a line L', and L and L' are neither parallel nor orthogonal. Then the number of distinct distances determined by the pairs of P⨯P' is Ω(min{|P|^2/3|P'|^2/3,|P|², |P'|²}). In particular, if |P|=|P'|=m, then the number of these distinct distances is Ω(m^4/3), improving upon the previous bound Ω(m^5/4) of Elekes.

In the second result, we study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains Ω(n^7/8) points of P and no circle contains Ω(n^5/6) points of P.

In both cases, we rely on a bipartite and partial variant of the Elekes–Sharir framework, which has been used by Guth and Katz in their 2010 solution of the general distinct distances problem. We combine this framework with some basic algebraic geometry, with a theorem from additive combinatorics by Elekes, Nathanson, and Ruzsa, and with a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang.

The first result is a joint work Micha Sharir (Tel Aviv) and József Solymosi (UBC). The second is a joint work with Joshua Zahl (MIT) and Frank de Zeeuw (EPFL).