Problem verschiedener Abstände von Erdős

Das Problem verschiedener Abstände von Erdős von Paul Erdős ist ein Problem der diskreten Geometrie. Erdős vermutete 1946, dass die minimale Anzahl $f(n)$ verschiedener Abstände von $n$ Punkten in der euklidischen Ebene von der Größenordnung ${\frac {n}{\sqrt {\log n}}}$ ist. Die Vermutung wurde 2015 von Larry Guth und Nets Katz bewiesen.

Aus elementaren Überlegungen folgt $f(3)=1$ (gleichseitiges Dreieck), $f(4)=2$ (Quadrat, die beiden Abstände sind die Seitenlänge und die Diagonale), $f(5)=2$ (Quadrat plus Schnittpunkt der Diagonalen).

Erdős bewies 1946:

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

mit einer Konstanten $c$.

Die untere Schranke folgt aus folgender Überlegung: Man bilde das minimale konvexe Polygon, das alle $n$ Punkte umfasst und $P_{1}$ sei eine beliebige Ecke des Polygons. Dann betrachte man die $n-1$ Abstände $P_{1}\,P_{i}$ zu den anderen Ecken. Die Anzahl verschiedener Abstände darunter sei $K$, die maximale Anzahl, mit der der gleiche Abstand vorkommt, sei $N$. Dann ist $KN\geq n-1$. Andererseits liegen die $N$ Punkte $P_{i}$ mit gleichem Abstand $r$ auf einem Halbkreis um $P_{1}$ mit Radius $r$, was $N-1$ paarweise verschiedene Abstände liefert. Aus beiden Überlegungen ergibt sich:

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

Die linke Seite ist minimal für $N(N-1)=n-1$. Auflösung der Gleichung ergibt die untere Schranke in der Ungleichung.

Für die obere Schranke werden die ganzzahligen Gitterpunkte in einem Quadrat der Seitenlänge ${\sqrt {n}}$ betrachtet. Es gibt $O({\frac {n}{\sqrt {\log n}}})$ Zahlen kleiner als $2n$, die Summe zweier Quadrate sind (siehe Landau-Ramanujan-Konstante), also von der Form $x^{2}+y^{2}$ mit $0\leq x\leq {\sqrt {n}}$, $0\leq y\leq {\sqrt {n}}$, und somit als Abstände in Frage kommen.

Erdős vermutete, dass die obere Schranke die minimale Anzahl der Abstände am besten abschätzt, was durch schrittweise Verbesserung der unteren Schranke schließlich bewiesen wurde.

Erdős behandelte auch den allgemeinen Fall von $k$ Dimensionen. Wie im Fall $k=2$ kann eine Ungleichung

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

abgeleitet werden (Erdős). Erdős vermutete, dass auch hier die obere Schranke scharf ist ($f(n)=\Omega (n^{\frac {2}{k}})$). Der allgemeine Fall ist unbewiesen. József Solymosi und Van H. Vu zeigten aber 2008, dass $f(n)=\Omega (n^{{\frac {2}{k}}-{\frac {2}{k(k+2)}}})$ ist.

Die offene Vermutung von Falconer (nach Kenneth Falconer, 1985) ist in gewisser Weise ein kontinuierliches Analogon der Erdös-Problems. Sei S eine kompakte Menge im d-dimensionalen euklidischen Raum mit Hausdorff-Dimension größer als ${\frac {d}{2}}$, dann hat nach der Vermutung die Menge der Abstände von Punkten in S ein positives Lebesgue-Maß.

Literatur

• Julia Garibaldi, Alex Iosevich, Steven Senger: The Erdös Distance Problem, Student Mathematical Library 56, American Mathematical Society 2011