Erdős Distinct Distances Problem
   HOME

TheInfoList



OR:

In
discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...
, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
in 1946 and almost proven by Larry Guth and
Nets Katz Nets Hawk Katz is the W.L. Moody Professor of Mathematics at Rice University. He was a professor of mathematics at Indiana University Bloomington until March 2013 and the IBM Professor of Mathematics at the California Institute of Technology until ...
in 2015.


The conjecture

In what follows let denote the minimal number of distinct distances between points in the plane, or equivalently the smallest possible
cardinality The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...
of their
distance set In geometry, the distance set of a collection of points is the Set (mathematics), set of distances between distinct pairs of points. Thus, it can be seen as the generalization of a Minkowski difference, difference set, the set of distances (and th ...
. In his 1946 paper, Erdős proved the estimates :\sqrt-1/2\leq g(n)\leq c n/\sqrt for some constant c. The lower bound was given by an easy argument. The upper bound is given by a \sqrt\times\sqrt square grid. For such a grid, there are O( n/\sqrt) numbers below ''n'' which are sums of two squares, expressed in
big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
; see
Landau–Ramanujan constant In mathematics and the field of number theory, the Landau–Ramanujan constant is the positive real number ''b'' that occurs in a theorem proved by Edmund Landau in 1908, stating that for large x, the number of positive integers below x that are th ...
. Erdős conjectured that the upper bound was closer to the true value of ''g''(''n''), and specifically that (using
big Omega notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul ...
) g(n) = \Omega(n^c) holds for every .


Partial results

Paul Erdős' 1946 lower bound of was successively improved to: * by Leo Moser in 1952, * by Fan Chung in 1984, * by Fan Chung,
Endre Szemerédi Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science a ...
, and William T. Trotter in 1992, * by László A. Székely in 1993, * by József Solymosi and Csaba D. Tóth in 2001, * by Gábor Tardos in 2003, * by Nets Katz and Gábor Tardos in 2004, * by Larry Guth and Nets Katz in 2015.


Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for d\ge 3 let g_d(n) denote the minimal possible number of distinct distances among n points in d-dimensional Euclidean space. He proved that g_d(n)=\Omega(n^) and g_d(n)=O(n^) and conjectured that the upper bound is in fact sharp, i.e., g_d(n)=\Theta(n^). József Solymosi and Van H. Vu obtained the lower bound g_d(n)=\Omega(n^) in 2008.


See also

* Falconer's conjecture * Erdős unit distance problem *'' The Erdős Distance Problem''


References


External links

* William Gasarch'
page
on the problem {{DEFAULTSORT:Erdos distinct distances problem Conjectures Paul Erdős Discrete geometry Eponyms in geometry