Problem of different distances from Erdős

The problem of different distances from Erdős by Paul Erdős is a problem of discrete geometry . Erdős hypothesized in 1946 that the minimum number of different distances between points in the Euclidean plane is of the order of magnitude . The conjecture was proven in 2015 by Larry Guth and Nets Katz . ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle {\frac {n}{\sqrt {\log n}}}}$

From elementary considerations it follows (equilateral triangle), (square, the two distances are the side length and the diagonal), (square plus intersection of the diagonals). ${\displaystyle f(3)=1}$ ${\displaystyle f(4)=2}$ ${\displaystyle f(5)=2}$

Erdős proved in 1946:

${\displaystyle {\sqrt {n-3/4}}-1/2\leq f(n)\leq c{\frac {n}{\sqrt {\log n}}}}$

with a constant . ${\displaystyle c}$

The lower bound follows from the following consideration: Form the minimal convex polygon that includes all points and be any corner of the polygon. Then look at the distances to the other corners. Let the number of different spaces below it be , let the maximum number with which the same space occurs is . Then is . On the other hand, the points with the same distance lie on a semicircle with a radius , which results in different distances in pairs. Both considerations result in: ${\displaystyle n}$ ${\displaystyle P_{1}}$ ${\displaystyle n-1}$ ${\displaystyle P_{1}\,P_{i}}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle KN\geq n-1}$ ${\displaystyle N}$ ${\displaystyle P_{i}}$ ${\displaystyle r}$ ${\displaystyle P_{1}}$ ${\displaystyle r}$ ${\displaystyle N-1}$

${\displaystyle f(n)\geq \max(N-1,{\frac {(n-1)}{N}})}$.

The left side is minimal for . Solving the equation gives the lower bound in the inequality. ${\displaystyle N(N-1)=n-1}$

For the upper bound, the integer grid points in a square of the side length are considered. There are numbers smaller than the sum of two squares (see Landau-Ramanujan constant ), ie, of the form with , and thus come as distances in question. ${\displaystyle {\sqrt {n}}}$ ${\displaystyle O({\frac {n}{\sqrt {\log n}}})}$ ${\displaystyle 2n}$ ${\displaystyle x^{2}+y^{2}}$ ${\displaystyle 0\leq x\leq {\sqrt {n}}}$ ${\displaystyle 0\leq y\leq {\sqrt {n}}}$

Erdős hypothesized that the upper bound best estimates the minimum number of distances, which was finally proven by gradually improving the lower bound.

Erdős also dealt with the general case of dimensions. As in the case can be an inequality ${\displaystyle k}$ ${\displaystyle k=2}$

${\displaystyle C_{1}n^{\frac {1}{k}}<f(n)<C_{2}n^{\frac {2}{k}}}$

be derived (Erdős). Erdős assumed that the upper bound is sharp here too ( ). The general case is unproven. József Solymosi and Van H. Vu showed in 2008 that it is. ${\displaystyle f(n)=\Omega (n^{\frac {2}{k}})}$ ${\displaystyle f(n)=\Omega (n^{{\frac {2}{k}}-{\frac {2}{k(k+2)}}})}$

Falconer's open conjecture (after Kenneth Falconer , 1985) is, in a certain way, a continuous analogue of the Erdös problem. Let S be a compact set in d-dimensional Euclidean space with Hausdorff dimension larger than , then according to the conjecture the set of distances between points in S has a positive Lebesgue measure . ${\displaystyle {\frac {d}{2}}}$

Individual evidence

1. ↑ Guth, Katz, On the Erdős distinct distances problem in the plane , Annals of Mathematics, Volume 181, 2015, pp. 155–190, Arxiv
2. ↑ Erdős, On sets of distances of n points, American Mathematical Monthly, Volume 53, 1946, pp. 248–250, pdf , 260 kB
3. ↑ For the notation see Landau symbols
4. ↑ Solymosi, Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica, Volume 28, 2008, pp. 113–125