On the Erdos distinct distance problem in the plane

By Larry Guth, Nets Hawk Katz. 2010

221 citations recorded by the source corpus.

In this paper, we prove that a set of $N$ points in ${\bf R}^2$ has at least $c{N \over \log N}$ distinct distances, thus obtaining the sharp exponent in a problem of Erd\"os. We follow the set-up of Elekes and Sharir which, in the spirit of the Erlangen program, allows us to study the problem in the group of rigid motions of the plane. This converts the problem to one of point-line incidences in space. We introduce two new ideas in our proof. In order to control points where many lines are incident, we create a cell decompostion using the polynomial ham sandwich theorem. This creates a dichotomy: either most of the points are in the interiors of the cells, in which case we immediately get sharp results, or alternatively the points lie on the walls of the cells, in which case they are in the zero set of a polynomial of suprisingly low degree, and we may apply the algebraic method. In order to control points where only two lines are incident, we use the flecnode polynomial of the Rev. George Salmon to conclude that most of the lines lie on a ruled surface. Then we use the geometry of ruled surfaces to complete the proof.

Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/9d8f2b84461b0ad077331985e2f46d1dcf7c3407

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computer Graphics and Computer-Aided Design

In Geometry and Topology

Citations in the corpus

Incidence Estimates for Well Spaced Tubes (2019, methodology): “We recall the Elekes-Sharir framework[7], which was used in the Erdős distinct distance problem[12].”
Modular hyperbolas (2011, background): “1] and also surveys [32, 120] (we also note the recent remarkable achievement [69, 105]).”
On the distance sets of Ahlfors–David regular sets (2015, background): “Katz [4] nearly resolved the question in 2011 by showing that |D(K)| & |P |/ log |P |.”
An improved point‐line incidence bound over arbitrary fields (2016, methodology): “As mentioned in Section 1, Guth and Katz [15] solved the distinct distance problem in R(2) (up to a logarithmic factor).”
An improved bound on the Hausdorff dimension of Besicovitch sets in ℝ³ (2017, methodology): “We will use the discrete polynomial partitioning bound from [10].”
An improved result for Falconer’s distance set problem in even dimensions (2020, background): “[10] L. Guth, N. H. Katz, On the Erdős distinct distance problem in the plane, Ann. of Math.”
A restriction estimate using polynomial partitioning (2014, unknown): “≥k0Ak |Wj| ≤ Z Z(f) |Wj| = 0. This proves that limk→∞ |Fj(vk) −Fj(v)| = 0, showing that Fj is continuous on V\{0}. Polynomial partitioning is a corollary of the ham sandwich theorem. It was proven in [GK] in a discrete setting. Here we give the same argument in a continuous setting. Theorem 1.4. Sup”
On asymptotic formulae in some sum–product questions (2018, result): “, [2], [33]—[39], [43] and this wave is connected with a fundamental incidence result of Rudnev [42] (see a simple proof of his theorem in [59] and also the famous Guth–Katz [19] solution of the Erdős distinct distance problem which contains the required technique for such incidence results), as wel”
On Falconer’s distance set problem in the plane (2018, background): “[23] N. Katz and T. Tao, Some connections between Falconer’s distance set conjecture and sets of Furstenburg type.”