On the Erdős distinct distances problem in the plane

DOI10.4007/ANNALS.2015.181.1.2zbMATH Open1310.52019arXiv1011.4105OpenAlexW2101788557WikidataQ59664728 ScholiaQ59664728MaRDI QIDQ482909FDOQ482909

Authors: Nets Hawk Katz, Larry Guth 

Publication date: 6 January 2015

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: In this paper, we prove that a set of $N$ points in $$ has at least $cNoverlogN$ 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.

Full work available at URL: https://arxiv.org/abs/1011.4105

Recommendations

• Distinct distances in the plane
• Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
• Distinct Distances in Three and Higher Dimensions
• Near optimal bounds for the Erdős distinct distances problem in high dimensions
• Erdős’s Unit Distance Problem

zbMATH Keywords

ruled surfaceincidence geometrydistinct distancespolynomial methodpolynomial ham sandwich

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Cites Work

• Title not available (Why is that?)
• On Sets of Distances of n Points
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• The number of different distances determined by a set of points in the Euclidean plane
• Algebraic methods in discrete analogs of the Kakeya problem
• On lines, joints, and incidences in three dimensions
• On the size of Kakeya sets in finite fields
• Point–Line Incidences in Space
• On the Different Distances Determined by n Points
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• On distinct sums and distinct distances.
• Title not available (Why is that?)
• The Erdős distance problem
• Generalized sandwich theorems
• Title not available (Why is that?)
• Counting and cutting cycles of lines and rods in space
• A geometric inequality with applications to the Kakeya problem in three dimensions
• An improved bound for joints in arrangements of lines in space
• The joints problem in \(\mathbb{R}^n\)
• Is a linear space contained in a submanifold? -- On the number of derivatives needed to tell
• Incidences in three dimensions and distinct distances in the plane
• THE MAXIMUM NUMBER OF LINES LYING ON A QUARTIC SURFACE
• Distinct distances in the plane
• On lines and joints
• The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture

Cited In (only showing first 100 items - show all)

• Distinct distances with \(\ell_p\) metrics
• Title not available (Why is that?)
• Optimal point sets determining few distinct triangles
• On the restriction problem for discrete paraboloid in lower dimension
• Bisectors and pinned distances
• Improved restriction estimate for hyperbolic surfaces in \(\mathbb{R}^3\)
• Working session: Additive combinatorics, entropy, and fractal geometry. Abstracts from the working session held October 8--13, 2017
• An \(L^2\)-identity and pinned distance problem
• Distribution of the determinants of sums of matrices
• A construction for difference sets with local properties
• A reduction for the distinct distances problem in \(\mathbb{R}^d\)
• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• Products of differences over arbitrary finite fields
• Almost tight bounds for eliminating depth cycles in three dimensions
• Incidence estimates for well spaced tubes
• On the multiparameter Falconer distance problem
• On the polynomial Wolff axioms
• Homotheties and incidences
• Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
• An improved bound on the Hausdorff dimension of Besicovitch sets in \(\mathbb {R}^3\)
• On bipartite distinct distances in the plane
• A restriction estimate for a certain surface of finite type in \(\mathbb{R}^3\)
• Distinct distances on curves via rigidity
• Incidences with curves in \(\mathbb{R}^{d}\)
• Improved bounds for the expected number of \(k\)-sets
• A crossing lemma for Jordan curves
• Nearly \(k\)-distance sets
• Planar point sets determine many pairwise crossing segments
• Title not available (Why is that?)
• Three conjectures in extremal spectral graph theory
• On the use of the Klein quadric for geometric incidence problems in two dimensions
• Distinct Distances Between a Circle and a Generic Set
• On the Minkowski distances and products of sum sets
• DIMENSIONS OF TRIANGLE SETS
• Expanders with superquadratic growth
• New Kakeya estimates using Gromov's algebraic lemma
• Maximal directional operators along algebraic varieties
• Distinct distances on hyperbolic surfaces
• Sets with many pairs of orthogonal vectors over finite fields
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Nondegenerate spheres in four dimensions
• Pinned algebraic distances determined by Cartesian products in 𝔽_{𝕡}²
• On pointwise convergence for Schrödinger operator in a convex domain
• On discrete values of bilinear forms
• A survey of mass partitions
• Falconer's \((K, d)\) distance set conjecture can fail for strictly convex sets \(K\) in \(\mathbb{R}^d\)
• Finite point configurations in the plane, rigidity and Erdős problems
• An improved result for Falconer's distance set problem in even dimensions
• New results for the growth of sets of real numbers
• On Falconer's distance set problem in the plane
• Configurations of lines in space and combinatorial rigidity
• On the number of incidences between points and planes in three dimensions
• Joints formed by lines and a \(k\)-plane, and a discrete estimate of Kakeya type
• A new bound for the Erdős distinct distances problem in the plane over prime fields
• Schwartz-Zippel bounds for two-dimensional products
• Non-commutative methods in additive combinatorics and number theory
• Group actions, the Mattila integral and applications
• Simplex Range Searching and Its Variants: A Review
• Distribution of distances in positive characteristic
• Areas spanned by point configurations in the plane
• Ruled surface theory and incidence geometry
• On incidences of lines in regular complexes
• On distinct distances between a variety and a point set
• Probabilities of incidence between lines and a plane curve over finite fields
• On the number of edges of separated multigraphs
• Incidences with curves in \(\mathbb{R}^d\)
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
• New sum-product type estimates over finite fields
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• A sharp Schrödinger maximal estimate in \(\mathbb{R}^2\)
• Bounds of trilinear and quadrilinear exponential sums
• Refined bounds on the number of connected components of sign conditions on a variety
• Incidences between points and lines on two- and three-dimensional varieties
• Distinct Distances in Three and Higher Dimensions
• A note on distinct distances
• Distinct distances in the complex plane
• Drawing outerplanar graphs using thirteen edge lengths
• Projections of planar sets in well-separated directions
• Distinct volume subsets
• Improved bounds for incidences between points and circles
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Zarankiewicz's problem for semi-algebraic hypergraphs
• More distinct distances under local conditions
• Point-curve incidences in the complex plane
• Szemerédi-Trotter-type theorems in dimension 3
• On ray shooting for triangles in 3-space and related problems
• Title not available (Why is that?)
• A note on distinct distance subsets
• On the number of rich lines in high dimensional real vector spaces
• Erdős type problems in modules over cyclic rings
• Counting multijoints
• Incidence bounds for block designs
• Title not available (Why is that?)
• New results on sum-product type growth over fields
• A note on distinct distances in rectangular lattices
• Group actions and geometric combinatorics in \(\mathbb{F}_{q}^{d}\)
• Bisector energy and few distinct distances
• Subtended angles
• Generalizations of the Szemerédi-Trotter theorem
• A Szemerédi-Trotter type theorem in \(\mathbb R^4\)

This page was built for publication: On the Erdős distinct distances problem in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482909)