www.wikidata.de-de.nina.az

Problem verschiedener Abstände von Erdős Das von Paul Erdős ist ein Problem der Diskreten Geometrie Erdős vermutete 1946

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 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.

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:

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 (). Der allgemeine Fall ist unbewiesen. József Solymosi und Van H. Vu zeigten aber 2008, 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 Bearbeiten

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

Einzelnachweise Bearbeiten

  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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Problem verschiedener Abstande von Erdos von Paul Erdos ist ein Problem der Diskreten Geometrie Erdos vermutete 1946 dass die minimale Anzahl f n displaystyle f n verschiedener Abstande von n displaystyle n Punkten in der euklidischen Ebene von der Grossenordnung n log n displaystyle frac n sqrt log n ist Die Vermutung wurde 2015 von Larry Guth und Nets Katz bewiesen 1 Aus elementaren Uberlegungen folgt f 3 1 displaystyle f 3 1 gleichseitiges Dreieck f 4 2 displaystyle f 4 2 Quadrat die beiden Abstande sind die Seitenlange und die Diagonale f 5 2 displaystyle f 5 2 Regelmassiges Funfeck Erdos bewies 1946 2 n 3 4 1 2 f n c n log n displaystyle sqrt n 3 4 1 2 leq f n leq c frac n sqrt log n mit einer Konstanten c displaystyle c Die untere Schranke folgt aus folgender Uberlegung Man bilde das minimale konvexe Polygon das alle n displaystyle n Punkte umfasst und P 1 displaystyle P 1 sei eine beliebige Ecke des Polygons Dann betrachte man die n 1 displaystyle n 1 Abstande P 1 P i displaystyle P 1 P i zu den anderen Ecken Die Anzahl verschiedener Abstande darunter sei K displaystyle K die maximale Anzahl mit der der gleiche Abstand vorkommt sei N displaystyle N Dann ist K N n 1 displaystyle KN geq n 1 Andererseits liegen die N displaystyle N Punkte P i displaystyle P i mit gleichem Abstand r displaystyle r auf einem Halbkreis um P 1 displaystyle P 1 mit Radius r displaystyle r was N 1 displaystyle N 1 paarweise verschiedene Abstande liefert Aus beiden Uberlegungen ergibt sich f n max N 1 n 1 N displaystyle f n geq max N 1 frac n 1 N Die linke Seite ist minimal fur N N 1 n 1 displaystyle N N 1 n 1 Auflosung der Gleichung ergibt die untere Schranke in der Ungleichung Fur die obere Schranke werden die ganzzahligen Gitterpunkte in einem Quadrat der Seitenlange n displaystyle sqrt n betrachtet Es gibt O n log n displaystyle O frac n sqrt log n Zahlen kleiner als 2 n displaystyle 2n die Summe zweier Quadrate sind siehe Landau Ramanujan Konstante also von der Form x 2 y 2 displaystyle x 2 y 2 mit 0 x n displaystyle 0 leq x leq sqrt n 0 y n displaystyle 0 leq y leq sqrt n und somit als Abstande in Frage kommen Erdos vermutete dass die obere Schranke die minimale Anzahl der Abstande am besten abschatzt was durch schrittweise Verbesserung der unteren Schranke schliesslich bewiesen wurde Erdos behandelte auch den allgemeinen Fall von k displaystyle k Dimensionen Wie im Fall k 2 displaystyle k 2 kann eine Ungleichung C 1 n 1 k lt f n lt C 2 n 2 k displaystyle C 1 n frac 1 k lt f n lt C 2 n frac 2 k abgeleitet werden Erdos Erdos vermutete dass auch hier die obere Schranke scharf ist f n W n 2 k displaystyle f n Omega n frac 2 k 3 Der allgemeine Fall ist unbewiesen Jozsef Solymosi und Van H Vu zeigten aber 2008 4 dass f n W n 2 k 2 k k 2 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 Erdos Problems Sei S eine kompakte Menge im d dimensionalen euklidischen Raum mit Hausdorff Dimension grosser als d 2 displaystyle frac d 2 dann hat nach der Vermutung die Menge der Abstande von Punkten in S ein positives Lebesgue Mass Literatur BearbeitenJulia Garibaldi Alex Iosevich Steven Senger The Erdos Distance Problem Student Mathematical Library 56 American Mathematical Society 2011Einzelnachweise Bearbeiten Guth Katz On the Erdos distinct distances problem in the plane Annals of Mathematics Band 181 2015 S 155 190 Arxiv Erdos On sets of distances of n points American Mathematical Monthly Band 53 1946 S 248 250 pdf 260 kB Fur die Notation siehe Landau Symbole Solymosi Vu Near optimal bounds for the Erdos distinct distances problem in high dimensions Combinatorica Band 28 2008 S 113 125 Abgerufen von https de wikipedia org w index php title Problem verschiedener Abstande von Erdos amp oldid 233091564