On the Erdős distinct distances problem in the plane

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

Larry Guth, Nets Hawk Katz

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?)
• Title not available (Why is that?)
• 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
• Incidences with curves in \(\mathbb{R}^d\)
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
• A NOTE ON RICH LINES IN TRULY HIGH DIMENSIONAL SETS
• New sum-product type estimates over finite fields
• A sharp Schrödinger maximal estimate in \(\mathbb{R}^2\)
• NEW RESULTS ON SUM‐PRODUCT TYPE GROWTH OVER FIELDS
• 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
• Variations on the Sum-Product Problem
• Improved Bounds for Incidences Between Points and Circles
• Erdös--Falconer Distance Problem under Hamming Metric in Vector Spaces over Finite Fields
• 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
• Sets in \(\mathbb{R}^d\) determining \(k\) taxicab distances
• Szemerédi-Trotter-type theorems in dimension 3
• Title not available (Why is that?)
• 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?)
• 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\)
• Distinct Distances on Algebraic Curves in the Plane
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• An incidence theorem in higher dimensions
• Distinct distances between a collinear set and an arbitrary set of points
• Incidence bounds on multijoints and generic joints
• Distinct distances between points and lines
• On asymptotic formulae in some sum–product questions
• A distance problem of P. Erdős with some further restrictions
• Title not available (Why is that?)
• New bounds on the dimensions of planar distance sets
• A general incidence bound in \(\mathbb{R}^d\)
• Three-point configurations determined by subsets of \({\mathbb{F}_q}^2\) via the Elekes-Sharir paradigm
• Near optimal bounds for the Erdős distinct distances problem in high dimensions
• Balanced convex partitions of lines in the plane
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• Polynomial partitioning for several sets of varieties
• A semi-algebraic version of Zarankiewicz's problem
• Cutting algebraic curves into pseudo-segments and applications
• Curves in \(\mathbb {R}^4\) and two-rich points
• Few distinct distances implies no heavy lines or circles
• Distinct distances in the plane
• Distinct distance estimates and low degree polynomial partitioning
• On the Erdős-Falconer distance problem for two sets of different size in vector spaces over finite fields
• New sum-product estimates for real and complex numbers
• The generalized Erdős-Falconer distance problems in vector spaces over finite fields
• On growth in an abstract plane
• A restriction estimate using polynomial partitioning
• Distinct distances in planar point sets with forbidden 4-point patterns
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Improvement on 2-chains inside thin subsets of Euclidean spaces
• Highly incidental patterns on a quadratic hypersurface in \(\mathbb{R}^4\)
• Polynomials with dense zero sets and discrete models of the Kakeya conjecture and the Furstenberg set problem
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Distinct Volume Subsets
• Computing the Distance between Piecewise-Linear Bivariate Functions
• Sets with few distinct distances do not have heavy lines
• On Cartesian products which determine few distinct distances
• On Ray Shooting for Triangles in 3-Space and Related Problems
• Upper bounds for \(s\)-distance sets and equiangular lines
• A solution of the Erdős-Ulam problem on rational distance sets assuming the Bombieri-Lang conjecture
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
• 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
• Variations on the Sum-Product Problem II
• 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
• 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
• Joints formed by lines and a $k$-plane, and a discrete estimate of Kakeya type
• Improved bounds for the expected number of \(k\)-sets
• Ruled Surface Theory and Incidence Geometry
• A crossing lemma for Jordan curves

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)