On the Erdos distinct distance problem in the plane

Abstract

In this paper, we prove that a set of $N$ points in ${\mathbf{R}}^2$ has at least $c\frac{N}{\log N}$ distinct distances, thus obtaining the sharp exponent in a problem of Erdös. 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.

37 pages. This is a revised version in response to referee comments. The exposition is expanded and some errors corrected

References in corpus (1)

• On the size of Kakeya sets in finite fields

Cited by in corpus (46)

• Polynomial partitioning for a set of varieties
• Improved bounds for incidences between points and circles
• Distinct Distances: Open Problems and Current Bounds
• Algebraic curves, rich points, and doubly-ruled surfaces
• Distinct Distances on Curves via Rigidity
• Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
• An improved bound on the number of point-surface incidences in three dimensions
• Group actions and geometric combinatorics in ${\mathbb{F}}_q^d$
• Counting joints with multiplicities
• A note on distinct distance subsets
• Bounds of incidences between points and algebraic curves
• Incidences between points and lines in R^4
• On the use of Klein quadric for geometric incidence problems in two dimensions
• Projections of planar sets in well-separated directions
• An incidence theorem in higher dimensions
• Discrete analogues of Kakeya problems
• Incidence Bounds for Block Designs
• Rigidity, graphs and Hausdorff dimension
• Three-variable expanding polynomials and higher-dimensional distinct distances
• Distinct and repeated distances on a surface and incidences between points and spheres
• Incidences between points on a variety and planes in R^3
• Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory
• Exposition of Elekes Szabo paper
• Sets with few distinct distances do not have heavy lines
• Polynomials with dense zero sets and discrete models of the Kakeya conjecture and the Furstenberg set problem
• Highly incidental patterns on a quadratic hypersurface in ${\mathbb{R}}^4$
• On Range Searching with Semialgebraic Sets II
• New results for the growth of sets of real numbers
• On three point configurations determined by subsets of the Euclidean plane, the associated bilinear operator and applications to discrete geometry
• On lattices, distinct distances, and the Elekes-Sharir framework
• Constructive Polynomial Partitioning for Algebraic Curves in ${\mathbb{R}}^3$ with Applications
• Multilevel polynomial partitions and simplified range searching
• Incidences with curves in R^d
• Embeddings of weighted graphs in Erdős-type settings
• The number of distinct distances from a vertex of a convex polygon
• Three-point configurations determined by subsets of ${\mathbb{F}}_q^2$ via the Elekes-Sharir paradigm
• On the Wolff circular maximal function
• New sum-product estimates for real and complex numbers
• A bound on the multiplicative energy of a sum set and extremal sum-product problems
• Results on the Erd\H os-Falconer distance problem in ${\mathbb{Z}}_q^d$ for odd $q$
• Refinements of the 2-dimensional Strichartz estimate on the maximum wave packet
• Incidences with curves in three dimensions
• Distinct distances between a collinear set and an arbitrary set of points
• Unit Distance Problems
• Generalizations of the Szemerédi-Trotter Theorem
• On the Distance Sets of Self-Similar Sets