🔢 mathematics

The lonely runner conjecture holds for nine runners

Dieses Papier beweist, dass die Lonely-Runner-Vermutung für neun Läufer wahr ist, indem es die Methode verfeinert, die zuvor verwendet wurde, um das Ergebnis für acht Läufer zu etablieren.

Ursprüngliche Autoren: Matthieu Rosenfeld

Veröffentlicht 2026-01-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Matthieu Rosenfeld

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine kreisförmige Laufbahn vor. Auf dieser Bahn befinden sich mehrere Läufer, die jeweils unterschiedliche Geschwindigkeiten haben. Einige laufen schnell, andere langsam, und niemand hat exakt dieselbe Geschwindigkeit.

Die Lonely Runner Vermutung ist eine mathematische Frage über diese Läufer. Sie fragt: Gibt es jemals einen Moment in der Zeit, in dem jeder einzelne Läufer „einsam“ ist?

In diesem Zusammenhang bedeutet „einsam“: Jeder Läufer ist weit genug von allen anderen entfernt. Konkret: Wenn man sich die Laufbahn als einen Kreis mit dem Umfang 1 vorstellt, ist ein Läufer einsam, wenn er mindestens den Abstand $1/(k+1)$ von jedem anderen Läufer entfernt ist (wobei $k$ die Anzahl der Läufer ist). Die Vermutung behauptet, dass es ungeachtet der Wahl der Geschwindigkeiten immer einen spezifischen Moment in der Zeit geben wird, in dem dies für alle gleichzeitig geschieht.

Lange Zeit war bewiesen, dass dies für Gruppen von 3, 4, 5, 6, 7 und 8 Läufern wahr ist. Aber für 9 Läufer blieb es ein Rätsel.

Der Durchbruch: Die Lösung des Falles für 9 Läufer

In dieser Arbeit beweist der Autor, Matthieu Rosenfeld, dass die Vermutung tatsächlich für 9 Läufer zutrifft.

Hier ist seine Vorgehensweise, erklärt durch eine einfache Analogie:

1. Das „unmögliche“ Szenario

Um die Vermutung zu beweisen, nutzt der Autor einen klassischen Logiktrick: den Widerspruchsbeweis.
Er beginnt mit der Annahme des Gegenteils: Angenommen, es gäbe eine Gruppe von 9 Läufern mit ganz bestimmten Geschwindigkeiten, bei denen sie niemals alle gleichzeitig einsam sein können.

Falls eine solche „schlechte“ Gruppe von Läufern existieren würde, müssten ihre Geschwindigkeiten sehr spezifische Zahlen sein. Die Arbeit verwendet einen mathematischen „Zaun“ (eine Formel), um zu zeigen, dass das Produkt dieser Geschwindigkeiten, falls diese schlechte Gruppe existiert, nicht zu riesig sein kann. Er setzt eine Obergrenze dafür, wie groß diese Zahlen sein dürfen.

2. Die Detektivarbeit der „Teilbarkeit“

Als Nächstes agiert der Autor wie ein Detektiv, der nach Hinweisen sucht. Er fragt: Wenn diese „schlechte“ Gruppe von Läufern existiert, durch welche Zahlen müssen ihre Geschwindigkeiten teilbar sein?

Er nutzt eine Reihe von logischen Regeln (Lemmata), um herauszufinden, dass die Geschwindigkeiten dieser hypothetischen Läufer durch eine sehr lange Liste spezifischer Zahlen teilbar sein müssen (wie 17, 19, 23, 29 usw. und sogar Potenzen von Zahlen wie 64 und 81).

Stellen Sie sich das so vor: Wenn Sie einen Geheimcode (das Produkt der Geschwindigkeiten) haben, beweist der Autor, dass dieser Code den „Schlüssel“ für 17, den „Schlüssel“ für 19, den „Schlüssel“ für 23 und so weiter enthalten muss.

3. Der Widerspruch

Hier geschieht die Magie.

Die Obergrenze: Der „Zaun“ aus Schritt 1 besagt, dass das gesamte Produkt der Geschwindigkeiten kleiner als eine bestimmte riesige Zahl (nennen wir sie $X$ ) sein muss.
Die Untergrenze: Die „Detektivarbeit“ aus Schritt 2 besagt, dass das Produkt durch eine Liste von Zahlen teilbar sein muss, deren kombiniertes Produkt größer als $X$ ist.

Es ist wie zu sagen: „Dieses Glas kann nur 100 Murmeln fassen“, aber dann zu beweisen, dass „Die Murmeln darin so viel wiegen müssen, dass sie ein Glas füllen würden, das 200 Murmeln fasst“.

Da das Produkt nicht gleichzeitig kleiner als $X$ und größer als $X$ sein kann, muss die ursprüngliche Annahme falsch sein. Es gibt keine solche „schlechte“ Gruppe von 9 Läufern. Daher muss die Lonely Runner Vermutung für 9 Läufer wahr sein.

Die Rolle der Computer

Sie fragen sich vielleicht: „Wie hat er all diese Zahlen überprüft?“
Die Arbeit gibt zu, dass es unmöglich ist, jede mögliche Kombination von Geschwindigkeiten von Hand zu prüfen. Der Autor schrieb ein spezialisiertes Computerprogramm, um die Schwerstarbeit zu erledigen.

Das Problem: Der Computer musste prüfen, ob bestimmte komplexe Zahlenmuster eine Strecke „bedecken“ können, ohne eine Lücke (einen „einsamen“ Punkt) zu hinterlassen.
Die Innovation: Der Autor hat nicht einfach Standard-Computer-Solver verwendet (die so sind, als würde man einen Hammer benutzen, um eine Nuss zu knacken). Er entwickelte einen maßgeschneiderten, hocheffizienten „Backtracking“-Algorithmus.
- Stellen Sie sich vor, Sie versuchen, einen Weg durch ein Labyrinth zu finden. Anstatt jeden einzelnen Pfad zu gehen, ist sein Programm klug genug zu erkennen: „Wenn ich hier links abbiege, laufe ich 10 Schritte später in eine Sackgasse, also mache ich mir gar nicht erst die Mühe, so weit zu gehen.“
- Diese Optimierung machte den Computer viel schneller als bisherige Versuche und verkürzte die Zeit für ähnliche Probleme von 32 Stunden auf 50 Minuten.

Was ist mit 10 Läufern?

Die Arbeit erwähnt kurz, dass die Methode theoretisch für 10 Läufer funktionieren könnte, die Mathematik jedoch unglaublich schwierig wird. Der „Zaun“ wird viel höher, und der Computer müsste Zahlen prüfen, die so groß sind, dass ein einzelner Computerprozessor etwa zwei Jahre benötigen würde, um die Aufgabe zu bewältigen.

Der Autor stellt fest, dass ein anderer Forscher den Fall für 10 Läufer unabhängig davon mit einer etwas anderen, schnelleren „Sieb“-Methode gelöst hat, aber diese Arbeit konzentriert sich strikt auf den Beweis für 9 Läufer und die spezifischen Verbesserungen an der Logik und dem Code, die dorthin führten.

Zusammenfassung

Kurz gesagt löst diese Arbeit ein jahrzehntealtes Rätsel für 9 Läufer, indem sie:

Annimmt, dass eine „schlechte“ Gruppe von Läufern existiert.
Beweist, dass eine solche Gruppe Zahlen erfordern würde, die mathematisch unmöglich sind (zu groß, um in den erlaubten Raum zu passen).
Ein cleveres, maßgeschneidertes Computerprogramm nutzt, um die mathematischen Regeln zu verifizieren, die zu diesem Widerspruch führen.

Das Ergebnis bestätigt, dass es auf jeder Bahn mit 9 Läufern unterschiedlicher Geschwindigkeit immer einen Moment gibt, in dem jeder perfekt allein ist.

Technisches Resümee: Die Lonely Runner Vermutung für neun Läufer

Problemstellung
Die Arbeit befasst sich mit der Lonely Runner Vermutung, einem langjährigen offenen Problem der kombinatorischen Zahlentheorie, das erstmals 1967 von Wills vorgeschlagen wurde. Die Vermutung besagt, dass es für jede ganze Zahl $k \ge 1$ und jede Menge von $k$ distinkten ganzen Zahlen (die Läufergeschwindigkeiten darstellend) eine reelle Zeit $t$ gibt, zu der jeder Läufer „einsam“ ist. Mathematisch bedeutet dies, dass es ein $t$ gibt, für das der Abstand jedes Läufers zum Ursprung auf einem Einheitskreis mindestens $1/(k+1)$ beträgt, ausgedrückt als $\|t v_i\| \ge 1/(k+1)$ für alle $i$ .

Während die Vermutung für kleine Werte von $k$ (bis $k=7$ ) verifiziert wurde, bleibt sie im allgemeinen Fall offen. Diese Arbeit konzentriert sich spezifisch auf den Fall von neun Läufern ( $k=9$ ).

Methodik
Die Beweisstrategie baut auf der vorangegangenen Arbeit des Autors auf, mit der die Vermutung für acht Läufer etabliert wurde. Der Kern des Arguments beruht auf einem Beweis durch Widerspruch unter Verwendung der Eigenschaften eines hypothetischen „minimalen Gegenbeispiels“.

Reduktion auf Teilbarkeitsbeschränkungen:
Der Beweis nutzt eine von Malikiosis, Santos und Schymura abgeleitete Schranke (Theorem 1), die impliziert, dass die Vermutung für $k$ gilt, sofern die Vermutung auch für $k+1$ gilt, vorausgesetzt das Produkt der Geschwindigkeiten in jedem minimalen Gegenbeispiel einen spezifischen Schwellenwert überschreitet. Folglich genügt es, um die Vermutung für $k+1$ zu beweisen, zu zeigen, dass keine Menge von $k$ Geschwindigkeiten existiert, welche die „Lonely Runner Eigenschaft“ (LR-Eigenschaft) verletzt und gleichzeitig die durch die Schranke auferlegten Teilbarkeitsbeschränkungen erfüllt.
Generalisiertes Lemma für Teiler:
Die Autoren führen Lemma 6 ein, eine verstärkte und generalisierte Version eines vorangegangenen Lemmas (Lemma 3). Dieses Lemma etabliert Bedingungen, unter denen eine spezifische ganze Zahl $d$ das Produkt der Geschwindigkeiten einer Menge von 8 ganzen Zahlen teilen muss, die die LR-Eigenschaft vermissen lassen.
- Das Lemma führt einen Koeffizienten $c$ ein und betrachtet Geschwindigkeiten modulo $9cd$.
- Es bezieht spezifische Teilbarkeitsbedingungen bezüglich der Anzahl der durch 3 und 9 teilbaren Geschwindigkeiten ein (abgeleitet aus Lemma 5).
- Die Bedingung erfordert die Verifizierung, dass für jede Menge von 8 Geschwindigkeiten, die spezifische GCD- und Teilbarkeitsbeschränkungen erfüllen, eine Zeit $t$ existiert, welche die LR-Eigenschaft erfüllt.
Computergestützte Verifizierung (Set-Cover-Reformulierung):
Die Verifizierung der Bedingungen von Lemma 6 ist rechenintensiv. Die Autoren reformulieren das Problem als Set-Cover-Problem (Lemma 7).
- Eine ganze Zahl $v$ „deckt“ eine ganze Zahl $j$ ab, wenn $\| \frac{jv}{9cd} \| < 1/8$ .
- Das Ziel ist es zu verifizieren, dass kein „schlechtes“ 8-Tupel existiert, das alle notwendigen ganzen Zahlen abdeckt und dabei die Teilbarkeitsbeschränkungen erfüllt.
- Die Autoren implementierten einen Backtracking-Algorithmus mit signifikanten Optimierungen gegenüber ihrer vorherigen Arbeit für $k=7$ $k = 7$ :
  - Vorberechnete Bitsets für die abgedeckten Positionen.
  - Pruning-Strategien basierend auf der maximalen Anzahl neuer ganzer Zahlen, die ein Kandidatenelement abdecken kann.
  - Memoization zur Eliminierung redundanter Suchpfade.
- Die Autoren testeten auch SAT-Solver-Ansätze (unter Verwendung von Cardinality-CDCL und Minicard), fanden diese jedoch als signifikant langsamer als ihre benutzerdefinierte Backtracking-Implementierung für diese spezifische Problemstruktur an.

Wesentliche Beiträge und Ergebnisse

Beweis für neun Läufer: Die Arbeit liefert einen vollständigen Beweis dafür, dass die Lonely Runner Vermutung für $k=9$ gilt.
Identifikation von Teilern: Durch Anwendung von Lemma 6 mittels eines Computerprogramms identifizierten die Autoren eine Menge $S$ von ganzen Zahlen (einschließlich Primzahlpotenzen wie $64, 81, 25$ und Primzahlen bis 191), die das Produkt der Geschwindigkeiten in jedem minimalen Gegenbeispiel für 9 Läufer teilen müssen.
Widerspruch: Das Produkt der Elemente in der Menge $S$ (welche paarweise teilerfremd sind) beträgt etwa $9,09 \times 10^{79}$ . Das theoretische obere Limit für das Produkt der Geschwindigkeiten in einem minimalen Gegenbeispiel (abgeleitet aus Korollar 2) liegt jedoch bei etwa $8,47 \times 10^{79}$ . Da das erforderliche Produkt der Teiler das maximal mögliche Produkt der Geschwindigkeiten überschreitet, kann ein solches Gegenbeispiel nicht existieren.
Algorithmische Verbesserungen: Die Arbeit detailliert spezifische Implementierungsverbesserungen, welche die Laufzeit für den Verifizierungsfall $k=7$ von 32 Stunden auf 50 Minuten reduzierten, was die komplexere Verifizierung für $k=9$ ermöglichte.

Bedeutung und Ansprüche
Die Autoren stellen fest, dass dieses Ergebnis den bekannten Bereich der Lonely Runner Vermutung von 7 auf 9 Läufer erweitert. Sie merken an, dass die verwendete Technik theoretisch auf jede beliebige Anzahl von Läufern anwendbar ist, wenngleich die Rechenkosten rapide ansteigen.

Unabhängigkeit: Die Autoren räumen ein, dass Trakulthongchai unabhängig Beweise für $k=9$ und $k=10$ kurz vor dieser Einreichung angekündigt hat. Trakulthongchais Arbeit baut ebenfalls auf dem $k=7$ Beweis auf und nutzt einen „cleveren Sieb-Ansatz“, der offenbar etwa 100-mal schneller ist als die hier vorgestellte Methode.
Ausblick: Die Arbeit diskutiert die Machbarkeit einer Erweiterung auf $k=10$ . Während die Methode adaptierbar ist, wird geschätzt, dass die Rechenkosten für die Verifizierung von Primzahlen bis etwa 263 zwei Jahre auf einem einzelnen Kern in Anspruch nehmen würden. Die Autoren schlagen vor, dass die Kombination ihrer Verbesserungen (wie das Berücksichtigen von Potenzen kleiner Primzahlen) mit dem Sieb-Ansatz von Trakulthongchai den Fall $k=10$ handhabbarer machen könnte, sie beanspruchen jedoch nicht, diesen selbst gelöst zu haben.

Zusammenfassend löst die Arbeit den Fall $k=9$ erfolgreich durch eine Kombination aus verfeinerten theoretischen Lemmata und hochoptimierter Computerverifizierung und positioniert die Arbeit damit bescheiden als einen Schritt voran, der sowohl von als auch zu den Bemühungen zur Lösung der Vermutung für höhere $k$ beiträgt.