„Problem verschiedener Abstände von Erdős“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
K Das ist eine feste Wortverbindung, die man in aller Regel groß schreibt, z.B. "Institut für Diskrete Mathematik" | TeX verschönert. | ||
| Zeile 4: | Zeile 4: | ||
Erdős bewies 1946:<ref>Erdős, On sets of distances of n points, American Mathematical Monthly, Band 53, 1946, S. 248–250, [https://www.renyi.hu/~p_erdos/1946-03.pdf pdf], 260 kB</ref> | Erdős bewies 1946:<ref>Erdős, On sets of distances of n points, American Mathematical Monthly, Band 53, 1946, S. 248–250, [https://www.renyi.hu/~p_erdos/1946-03.pdf pdf], 260 kB</ref> | ||
:<math>\sqrt{n-3 | :<math>\sqrt{n-\frac{3}{4}}- \frac{1}{2} \leq f(n)\leq c \frac {n}{\sqrt{\log n}}</math> | ||
mit einer Konstanten <math>c</math>. | mit einer Konstanten <math>c</math>. | ||
| Zeile 10: | Zeile 10: | ||
Die untere Schranke folgt aus folgender Überlegung: Man bilde das minimale [[Konvexe Menge|konvexe]] [[Polygon]], das alle <math>n</math> Punkte umfasst und <math>P_1</math> sei eine beliebige Ecke des Polygons. Dann betrachte man die <math>n-1</math> Abstände <math>P_1 \, P_i</math> zu den anderen Ecken. Die Anzahl verschiedener Abstände darunter sei <math>K</math>, die maximale Anzahl, mit der der gleiche Abstand vorkommt, sei <math>N</math>. Dann ist <math>KN \geq n-1</math>. Andererseits liegen die <math>N</math> Punkte <math>P_i</math> mit gleichem Abstand <math>r</math> auf einem Halbkreis um <math>P_1</math> mit Radius <math>r</math>, was <math>N-1</math> paarweise verschiedene Abstände liefert. Aus beiden Überlegungen ergibt sich: | Die untere Schranke folgt aus folgender Überlegung: Man bilde das minimale [[Konvexe Menge|konvexe]] [[Polygon]], das alle <math>n</math> Punkte umfasst und <math>P_1</math> sei eine beliebige Ecke des Polygons. Dann betrachte man die <math>n-1</math> Abstände <math>P_1 \, P_i</math> zu den anderen Ecken. Die Anzahl verschiedener Abstände darunter sei <math>K</math>, die maximale Anzahl, mit der der gleiche Abstand vorkommt, sei <math>N</math>. Dann ist <math>KN \geq n-1</math>. Andererseits liegen die <math>N</math> Punkte <math>P_i</math> mit gleichem Abstand <math>r</math> auf einem Halbkreis um <math>P_1</math> mit Radius <math>r</math>, was <math>N-1</math> paarweise verschiedene Abstände liefert. Aus beiden Überlegungen ergibt sich: | ||
:<math>f(n)\geq \max (N-1, \frac {(n-1)}{N})</math>. | :<math>f(n)\geq \max \left(N-1, \frac {(n-1)}{N}\right)</math>. | ||
Die linke Seite ist minimal für <math>N(N-1)=n-1</math>. Auflösung der Gleichung ergibt die untere Schranke in der Ungleichung. | Die linke Seite ist minimal für <math>N(N-1)=n-1</math>. 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 <math>\sqrt n</math> betrachtet. Es gibt <math>O (\frac {n}{\sqrt {\log n}})</math> Zahlen kleiner als <math>2 n</math>, die Summe zweier Quadrate sind (siehe [[Landau-Ramanujan-Konstante]]), also von der Form <math>x^2+y^2</math> mit <math> 0 \leq x \leq \sqrt n</math>, <math> 0 \leq y \leq \sqrt n</math>, und somit als Abstände in Frage kommen. | Für die obere Schranke werden die ganzzahligen Gitterpunkte in einem Quadrat der Seitenlänge <math>\sqrt n</math> betrachtet. Es gibt <math>O \left(\frac {n}{\sqrt {\log n}}\right)</math> Zahlen kleiner als <math>2 n</math>, die Summe zweier Quadrate sind (siehe [[Landau-Ramanujan-Konstante]]), also von der Form <math>x^2+y^2</math> mit <math> 0 \leq x \leq \sqrt n</math>, <math> 0 \leq y \leq \sqrt n</math>, 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 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. | ||
| Zeile 22: | Zeile 22: | ||
:<math>C_1 n^{\frac {1}{k}}<f(n) < C_2 n^{\frac {2}{k}}</math> | :<math>C_1 n^{\frac {1}{k}}<f(n) < C_2 n^{\frac {2}{k}}</math> | ||
abgeleitet werden (Erdős). Erdős vermutete, dass auch hier die obere Schranke scharf ist (<math>f(n)=\Omega (n^{\frac {2}{k}})</math>).<ref>Für die Notation siehe [[Landau-Symbol]]e</ref> Der allgemeine Fall ist unbewiesen. [[József Solymosi]] und [[Van H. Vu]] zeigten aber 2008,<ref>Solymosi, Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica, Band 28, 2008, S. 113–125</ref> dass <math>f(n)=\Omega (n^{\frac {2}{k} - \frac {2}{k(k+2)}})</math> ist. | abgeleitet werden (Erdős). Erdős vermutete, dass auch hier die obere Schranke scharf ist (<math>f(n)=\Omega \left(n^{\frac {2}{k}}\right)</math>).<ref>Für die Notation siehe [[Landau-Symbol]]e</ref> Der allgemeine Fall ist unbewiesen. [[József Solymosi]] und [[Van H. Vu]] zeigten aber 2008,<ref>Solymosi, Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica, Band 28, 2008, S. 113–125</ref> dass <math>f(n)=\Omega \left(n^{\frac {2}{k} - \frac {2}{k(k+2)}}\right)</math> 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 <math>\frac {d}{2}</math>, dann hat nach der Vermutung die Menge der Abstände von Punkten in S ein positives [[Lebesgue-Maß]]. | 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 <math>\frac {d}{2}</math>, dann hat nach der Vermutung die Menge der Abstände von Punkten in S ein positives [[Lebesgue-Maß]]. | ||
Version vom 6. Mai 2024, 20:08 Uhr
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 verschiedener Abstände von Punkten in der euklidischen Ebene von der Größenordnung ist. Die Vermutung wurde 2015 von Larry Guth und Nets Katz bewiesen.[1]
Aus elementaren Überlegungen folgt (gleichseitiges Dreieck), (Quadrat, die beiden Abstände sind die Seitenlänge und die Diagonale), (Regelmäßiges Fünfeck).
Erdős bewies 1946:[2]
mit einer Konstanten .
Die untere Schranke folgt aus folgender Überlegung: Man bilde das minimale konvexe Polygon, das alle Punkte umfasst und sei eine beliebige Ecke des Polygons. Dann betrachte man die Abstände zu den anderen Ecken. Die Anzahl verschiedener Abstände darunter sei , die maximale Anzahl, mit der der gleiche Abstand vorkommt, sei . Dann ist . Andererseits liegen die Punkte mit gleichem Abstand auf einem Halbkreis um mit Radius , was paarweise verschiedene Abstände liefert. Aus beiden Überlegungen ergibt sich:
- .
Die linke Seite ist minimal für . 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 betrachtet. Es gibt Zahlen kleiner als , die Summe zweier Quadrate sind (siehe Landau-Ramanujan-Konstante), also von der Form mit , , 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 Dimensionen. Wie im Fall kann eine Ungleichung
abgeleitet werden (Erdős). Erdős vermutete, dass auch hier die obere Schranke scharf ist ().[3] Der allgemeine Fall ist unbewiesen. József Solymosi und Van H. Vu zeigten aber 2008,[4] dass 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 , 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
Einzelnachweise
- ↑ Guth, Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics, Band 181, 2015, S. 155–190, Arxiv
- ↑ Erdős, On sets of distances of n points, American Mathematical Monthly, Band 53, 1946, S. 248–250, pdf, 260 kB
- ↑ Für die Notation siehe Landau-Symbole
- ↑ Solymosi, Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica, Band 28, 2008, S. 113–125
