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 ${\displaystyle f(n)}$ verschiedener Abstände von ${\displaystyle n}$ Punkten in der euklidischen Ebene von der Größenordnung ${\displaystyle {\frac {n}{\sqrt {\log n}}}}$ ist. Die Vermutung wurde 2015 von Larry Guth und Nets Katz bewiesen.[1]

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

Erdős bewies 1946:[2]

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

mit einer Konstanten ${\displaystyle c}$.

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

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

Die linke Seite ist minimal für ${\displaystyle 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 ${\displaystyle {\sqrt {n}}}$ betrachtet. Es gibt ${\displaystyle O({\frac {n}{\sqrt {\log n}}})}$ Zahlen kleiner als ${\displaystyle 2n}$, die Summe zweier Quadrate sind (siehe Landau-Ramanujan-Konstante), also von der Form ${\displaystyle x^{2}+y^{2}}$ mit ${\displaystyle 0\leq x\leq {\sqrt {n}}}$, ${\displaystyle 0\leq y\leq {\sqrt {n}}}$, und somit als Abstände in Frage kommen.

Erdős vermutete, d​ass die o​bere Schranke d​ie minimale Anzahl d​er Abstände a​m besten abschätzt, w​as durch schrittweise Verbesserung d​er unteren Schranke schließlich bewiesen wurde.

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

${\displaystyle 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 (${\displaystyle f(n)=\Omega (n^{\frac {2}{k}})}$).[3] Der allgemeine Fall ist unbewiesen. József Solymosi und Van H. Vu zeigten aber 2008,[4] dass ${\displaystyle 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 ${\displaystyle {\frac {d}{2}}}$, dann hat nach der Vermutung die Menge der Abstände von Punkten in S ein positives Lebesgue-Maß.

Einzelnachweise

1. Guth, Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics, Band 181, 2015, S. 155–190, Arxiv
2. Erdős, On sets of distances of n points, American Mathematical Monthly, Band 53, 1946, S. 248–250, pdf, 260 kB
3. Für die Notation siehe Landau-Symbole
4. Solymosi, Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica, Band 28, 2008, S. 113–125