Wieviele unterschiedliche Abstände gibt es, wenn man n Punkte in der Ebene anordnet?
| 3 Punkte kann man in Form eines gleichseitigen Dreiecks anordnen und dann gibt es nur einen möglichen Wert für Abstände je zweier unterschiedlicher Punkte: |
 |
Bei 4 Punkten funktioniert das nicht mehr, man kann sie aber in Form eines Quadrates anordnen und hat dann nur 2 mögliche Abstände. Auch 5 Punkte kann man noch so anordnen, dass es nur 2 Werte für den Abstand gibt, wärend man bei 6 oder 7 Punkten immer mindestens 3 unterschiedliche Abstände hat:
Paul Erdős hatte 1946 bewiesen, dass für die Mindestanzahl f(n) der Abstände von n Punkten die Ungleichung
$latex \sqrt{n-1}-1 < f(n) < \frac{c_1n}{\sqrt{log n}} $
mit einer Konstante c1 gilt
und stellte dann 1970 die Frage, ob es auch eine untere Schranke der Form
![f(n)\ge \sqrt[3]{\frac{n^2}{72}}-1](http://s0.wp.com/latex.php?latex=f%28n%29%5Cge+%5Csqrt%5B3%5D%7B%5Cfrac%7Bn%5E2%7D%7B72%7D%7D-1+&bg=ffffff&fg=000&s=0 "f(n)\ge \sqrt[3]{\frac{n^2}{72}}-1")
Die obere Schranke läßt sich übrigens nicht verbessern, man erhält sie durch Anordnung von Punkten auf einem Quadratgitter (siehe auch den Appendix der unten verlinkten Arbeit von Guth-Katz):
Es hat mehr als 40 Jahre gebraucht, aber jedenfalls ist Erdős's Vermutung jetzt bewiesen worden, im Januar-Heft der Annals of Mathematics von Larry Guth und Nets Hawk Kats: On the Erdős distinct distances problem in the plane. Der Beweis benutzt quantitative Abschätzungen aus der Inzidenzgeometrie, die Geometrie von Regelflächen und das Ham-Sandwich-Theorem.
Guth, L., & Katz, N. (2015). On the Erdős distinct distances problem in the plane Annals of Mathematics, 155-190 DOI: 10.4007/annals.2015.181.1.2
Kommentare (4)