Erd\H{o}s's diameter conjecture for separated distances fails in high dimensions

Die Autoren widerlegen Erdős' Vermutung über den Durchmesser von Punktmengen mit getrennten Abständen in hohen Dimensionen, indem sie eine formale Gegenbeispiel-Konstruktion in Lean 4 vorlegen, die einen Durchmesser von höchstens $(1-1/\pi^2+o(1))n^2$ zeigt.

Das Wesentliche

Das große Rätsel: Wie weit müssen Punkte auseinanderstehen?

Stell dir vor, du hast eine riesige Menge an Punkten (wie Sterne am Himmel oder Bälle auf einem Feld). Der Mathematiker Paul Erdős stellte vor langer Zeit eine sehr knifflige Frage:

Die Regel: Wenn du sicherstellst, dass jeder Abstand zwischen zwei beliebigen Punkten in deiner Menge mindestens 1 Meter beträgt (und dass alle diese Abstände untereinander unterschiedlich sind), wie groß muss dann der gesamte Durchmesser deiner Gruppe sein?

Der Durchmesser ist einfach die Entfernung zwischen den beiden Punkten, die am weitesten voneinander entfernt sind.

Erdős' Vermutung: Erdős glaubte, dass die Antwort immer ungefähr so aussieht: Wenn du $n$ Punkte hast, muss der größte Abstand zwischen zwei von ihnen mindestens so groß sein wie $n^2$ (also $n$ mal $n$). Er dachte, das gilt für jede Dimension, egal ob du auf einer Linie (1D), in einer Ebene (2D) oder in einem riesigen, hochdimensionalen Raum lebst.

Der neue Beweis: Die Vermutung platzt in hohen Dimensionen

Boon Suan Ho hat nun gezeigt, dass Erdős in sehr hohen Dimensionen falsch lag.

Stell dir den Raum nicht als unseren gewohnten 3D-Raum vor, sondern als einen Raum mit tausenden oder millionen von Dimensionen. In diesem riesigen, fast unvorstellbaren Raum hat Ho eine spezielle Anordnung von Punkten gebaut, die Erdős' Regel bricht.

Die Analogie: Der „perfekte Tanz" in einem riesigen Raum

Stell dir vor, du hast eine Gruppe von Tänzern ($n$ Personen).

1. Die Regel: Jeder Tänzer muss so tanzen, dass er nie näher als 1 Meter an einen anderen kommt. Außerdem darf der Abstand zwischen Tänzer A und B nicht genau so groß sein wie der Abstand zwischen Tänzer C und D. Alle Abstände müssen einzigartig sein.
2. Erdős' Erwartung: Er dachte, wenn du so viele Tänzer hast, müssen sie sich zwangsläufig über einen riesigen Raum verteilen. Wenn du 100 Tänzer hast, müssten sie sich über einen Bereich von 10.000 Metern erstrecken.
3. Ho's Überraschung: Ho hat einen Tanz choreografiert, bei dem die Tänzer zwar alle die Regeln einhalten (alle Abstände sind unterschiedlich und mindestens 1 Meter), aber sie bleiben trotzdem in einem viel kleineren Raum zusammengeballt. Statt 10.000 Meter reicht ihnen ein Raum von nur etwa 8.987 Metern (das ist der Faktor $1 - 1/\pi^2$).

Wie hat er das gemacht? (Die Magie der „Singer-Muster")

Der Trick liegt in der Geometrie und einem alten mathematischen Werkzeug namens Singer-Differenzmengen.

1. Der Bauplan: Ho nutzt eine spezielle mathematische Struktur (basierend auf Primzahlpotenzen), die wie ein perfektes Muster funktioniert. Stell dir vor, du hast einen Kreis mit vielen Markierungen. Diese Markierungen sind so angeordnet, dass jede mögliche Distanz zwischen zwei Markierungen genau einmal vorkommt.
2. Die Dimension: Er platziert diese Punkte nicht auf einer flachen Ebene, sondern in einem Raum mit so vielen Dimensionen, wie es Paare von Punkten gibt. Das klingt verrückt, aber in der Mathematik ist das erlaubt.
3. Die Gewichtung: Er gibt den verschiedenen Richtungen in diesem riesigen Raum unterschiedliche „Gewichte". Er verzerrt den Raum so, dass die Abstände zwischen den Punkten genau so wachsen, wie er es will.
4. Das Ergebnis: Durch diese geschickte Verzerrung werden die Abstände zwischen den Punkten alle größer als 1, aber der größte Abstand (der Durchmesser) bleibt überraschend klein.

Warum ist das wichtig?

• Es widerlegt eine Intuition: Wir denken oft, dass mehr Punkte automatisch mehr Platz brauchen. Ho zeigt, dass in hochdimensionalen Räumen die Geometrie viel „knapper" und effizienter sein kann als wir denken.
• Die Rolle der Dimension: Die Vermutung von Erdős funktioniert vielleicht in unserer 3D-Welt oder in der Ebene, aber sobald die Dimensionen in die Höhe schießen, bricht das Gesetz zusammen.
• KI und Mathematik: Ein besonders interessanter Punkt in der Arbeit ist, dass der Autor erwähnt, dass Künstliche Intelligenz (GPT-5.4 Pro) geholfen hat, die Konstruktion zu finden, und eine andere KI (Harmonic Aristotle) den Beweis in einer formalen Sprache (Lean 4) verifiziert hat. Der Mensch hat die Verantwortung übernommen, aber die Maschinen waren die Entdecker.

Zusammenfassung in einem Satz

Boon Suan Ho hat bewiesen, dass man in einem unvorstellbar hochdimensionalen Raum eine Gruppe von Punkten so anordnen kann, dass alle Abstände zwischen ihnen einzigartig und groß genug sind, aber die gesamte Gruppe trotzdem viel kompakter ist, als Paul Erdős es für möglich gehalten hätte.

Die Moral der Geschichte: In der Mathematik gilt: Je höher die Dimension, desto seltsamer und überraschender wird die Geometrie!

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert eine Vermutung von Paul Erdős aus einem Kapitel ungelöster Probleme. Die Fragestellung lautet:
Gegeben sei eine Menge $C$ von $n$ Punkten im euklidischen Raum. Angenommen, alle paarweisen Abstände zwischen diesen Punkten sind voneinander um mindestens 1 getrennt (d.h. für zwei verschiedene Paare $\{x, y\} \neq \{x', y'\}$ gilt $||x-y| - |x'-y'|| \ge 1$).

Erdős vermutete, dass der Durchmesser dieser Menge (die maximale Distanz zwischen zwei Punkten in $C$) eine untere Schranke von $(1 + o(1))n^2$ besitzt, unabhängig von der Dimension des Raumes.
Formal:
$$\text{diam}(C) \ge (1 + o(1))n^2$$

Bisher war diese Vermutung für die Dimension 1 bewiesen worden, aber für höhere Dimensionen gab es kaum direkte Untersuchungen. Das Ziel des Papers ist es zu zeigen, dass diese Vermutung im Allgemeinen falsch ist, insbesondere in hohen Dimensionen.

2. Methodik und Konstruktion

Der Autor widerlegt die Vermutung durch eine explizite Konstruktion einer Punktmenge $X_n$ in einem hochdimensionalen Raum, die die Trennungsbedingung erfüllt, aber einen Durchmesser hat, der signifikant kleiner als $n^2$ ist.

Schlüsselkomponenten der Konstruktion:

1. Singer-Differenzenmengen:
   Für jede Primzahlpotenz $q$ wird eine Primzahlpotenz $m = q^2 + q + 1$ definiert. Nach dem Satz von Singer existiert eine zyklische $(m, n, 1)$-Differenzenmenge $D \subset \mathbb{Z}/m\mathbb{Z}$ mit $n = q + 1$ Elementen.

   • Eigenschaft: Jeder von Null verschiedene Restklassen in $\mathbb{Z}/m\mathbb{Z}$ lässt sich eindeutig als Differenz $a - b$ mit $a, b \in D$ darstellen.
   • Dies führt dazu, dass die $N = \binom{n}{2} = (m-1)/2$ ungeordneten Paare aus $D$ eindeutig durch ihre zyklische Trennung $s \in \{1, \dots, N\}$ indiziert werden können.

2. Einbettung in den euklidischen Raum:
   Die Punkte werden in einem Raum der Dimension $2N = m-1$ (bzw. $n^2 - n$) platziert.

   • Für jedes $t \in \mathbb{Z}/m\mathbb{Z}$ wird ein Vektor $v_t \in \mathbb{R}^{2N}$ definiert, der als gewichtetes Produkt von regulären $m$-Ecken konstruiert wird.
   • Die Koordinaten basieren auf trigonometrischen Funktionen mit Gewichten $W_r$.
   • Der quadrierte Abstand zwischen zwei Punkten $v_t$ und $v_u$ mit zyklischer Trennung $s$ hängt nur von $s$ ab:
     $$d_s = \sqrt{\sum_{r=1}^N W_r \left(1 - \cos\left(\frac{2\pi r s}{m}\right)\right)}$$

3. Gewichtswahl und Störung (One-frequency perturbation):
   Um die Bedingung zu erfüllen, dass alle paarweisen Abstände mindestens 1 voneinander entfernt sind, müssen die Abstände $d_s$ so gewählt werden, dass die Differenzen $d_{s+1} - d_s$ streng positiv sind.

   • Der Autor wählt die Gewichte $W_r$ basierend auf einer Fourier-Reihe mit Koeffizienten $c_j$.
   • Spezifisch: $c_1 = 1 - \varepsilon$ (mit $\varepsilon = 1/8$) und $c_j = 1/j^2$ für ungerade $j \ge 3$.
   • Dies führt zu einer Abstandsfunktion $G(\theta) = \sqrt{H(\theta)}$, wobei $H(\theta) = \frac{\pi \theta}{4} - \varepsilon(1 - \cos \theta)$.
   • Es wird gezeigt, dass $G$ auf $(0, \pi)$ streng monoton steigend und streng konkav ist.

4. Skalierung:
   Da die Funktion $G$ konkav ist, nehmen die Differenzen zwischen aufeinanderfolgenden Abständen ($d_{s+1} - d_s$) ab. Der kleinste Abstand zwischen zwei verschiedenen Distanzen ist also $d_N - d_{N-1}$.
   Die gesamte Punktmenge wird mit dem Faktor $\lambda_m = \frac{1}{d_N - d_{N-1}}$ skaliert. Dadurch wird der kleinste Abstand zwischen zwei verschiedenen Distanzen exakt 1, und alle anderen Abstände sind größer als 1.

3. Hauptergebnisse

Satz 1 (Hauptresultat):
Es gibt unendlich viele $n$ (nämlich $n = q+1$ für Primzahlpotenzen $q$), für die eine $n$-Punkt-Menge $X_n \subset \mathbb{R}^{n^2-n}$ existiert, sodass:

1. Alle paarweisen Distanzen in $X_n$ um mindestens 1 voneinander getrennt sind.
2. Der Durchmesser von $X_n$ durch folgende Schranke beschränkt ist:
   $$\text{diam}(X_n) \le \left(1 - \frac{1}{\pi^2} + o(1)\right) n^2$$
   wobei $1 - \frac{1}{\pi^2} \approx 0.89867$.

Da $0.89867 < 1$, widerspricht dies direkt Erdős' Vermutung, dass der Durchmesser asymptotisch mindestens $n^2$ sein muss.

Asymptotische Analyse:
Durch Anwendung des Mittelwertsatzes auf die Funktion $G$ im Grenzwert $m \to \infty$ (was $n \to \infty$ impliziert) wird gezeigt, dass das Verhältnis von Durchmesser zu $n^2$ gegen den konstanten Faktor $c^* = 1 - 1/\pi^2$ konvergiert.

4. Bedeutung und Implikationen

• Widerlegung der Vermutung: Das Paper beweist, dass Erdős' untere Schranke für den Durchmesser nicht dimensionsunabhängig gilt. In hohen Dimensionen können Punktmenge mit stark getrennten Abständen einen deutlich kleineren Durchmesser haben als erwartet.
• Offene Fragen: Die Vermutung bleibt für feste Dimensionen $d \ge 2$ offen. Es ist unklar, ob für jedes feste $d$ eine Schranke von $(1 + o_d(1))n^2$ gilt. Die Konstruktion im Paper erfordert jedoch Dimensionen von der Größenordnung $O(n^2)$.
• Optimierungspotenzial: Der Autor weist in den Anmerkungen darauf hin, dass die Konstante $1 - 1/\pi^2$ durch Optimierung der Frequenzkoeffizienten $c_j$ weiter gesenkt werden könnte (numerisch auf ca. 0.854).
• Formalisierung: Ein bemerkenswertes Merkmal des Papers ist, dass der Beweis vollständig in der Beweissprache Lean 4 formalisiert wurde. Dies unterstreicht die mathematische Strenge der Konstruktion.

5. Zusammenfassung der technischen Details

• Raumdimension: $R^{n^2-n}$ (hochdimensional).
• Punktanzahl: $n = q+1$.
• Abstandsmuster: Die Abstände sind durch eine Funktion $G(2\pi s/m)$ gegeben, die aus einer modifizierten Fourier-Reihe abgeleitet ist.
• Konkavität: Die strenge Konkavität der Funktion $G$ ist entscheidend, um sicherzustellen, dass die kleinsten Lücken zwischen den Abständen am Ende des Spektrums ($s \approx N$) auftreten, was die Skalierung effizient macht.
• Konstante: Der Faktor $1 - 1/\pi^2$ resultiert aus dem Verhältnis $H(\pi) / (\pi^2/4)$ im Grenzwert, wobei $H(\pi)$ durch die spezifische Wahl von $\varepsilon = 1/8$ bestimmt wird.

Das Paper liefert somit ein konstruktives Gegenbeispiel, das zeigt, dass die Geometrie von Punktmengen mit getrennten Abständen in hohen Dimensionen viel flexibler ist als von Erdős vermutet.