On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

Dieser Artikel liefert erstmals detaillierte Erläuterungen zu einem 2004 von Gábor Ellmann aufgedeckten Fehler in der heuristischen Argumentation von Guy und Kelly zur No-Three-In-Line-Problematik, was zu einer Korrektur ihrer vermuteten oberen Schranke führte.

Das Wesentliche

Stellen Sie sich vor, Sie haben ein riesiges Schachbrett, aber statt 8x8 Feldern hat es unendlich viele Felder. Auf jedem Schnittpunkt der Linien können Sie einen Punkt platzieren. Die Aufgabe, die Mathematiker seit Jahrzehnten beschäftigt, ist wie ein sehr schwieriges Puzzle: Wie viele Punkte können Sie auf dieses Brett setzen, ohne dass jemals drei Punkte auf einer einzigen geraden Linie liegen?

Dieses Problem nennt man das „No-Three-in-Line"-Problem (auf Deutsch: „Keine-Drei-in-einer-Reihe"-Problem).

Hier ist die Geschichte, die Paul Voutier in diesem Papier erzählt, einfach erklärt:

1. Das alte Rätsel und die falsche Vermutung

Früher dachten die Mathematiker Guy und Kelly, sie hätten die Lösung gefunden. Sie stellten eine These auf: Wenn das Brett sehr groß wird, können Sie ungefähr 1,814 Punkte pro Seite setzen.
Stellen Sie sich vor, das Brett ist 100 Felder breit. Nach ihrer alten Rechnung könnten Sie also etwa 181 Punkte setzen. Sie glaubten, das sei die absolute Grenze.

Aber sie hatten einen kleinen Rechenfehler gemacht. Es war wie bei einem Kochrezept, bei dem man versehentlich statt 1 Teelöffel Salz 2 Teelöffel nimmt. Das Ergebnis schmeckt anders, aber man merkt es beim ersten Probieren vielleicht nicht sofort.

2. Der Fehler wird entdeckt

Im Jahr 2004 (und später bestätigt) fand ein Mann namens Gabor Ellmann den Fehler in der Rechnung von Guy und Kelly.
Stellen Sie sich vor, Guy und Kelly hatten versucht, die Anzahl der Möglichkeiten zu berechnen, wie man Punkte auf das Brett legt. Dabei hatten sie versehentlich eine Zahl verdoppelt, die sie eigentlich variabel lassen sollten.

• Die Analogie: Stellen Sie sich vor, Sie wollen berechnen, wie viele Wege Sie durch ein Labyrinth gehen können. Guy und Kelly haben dabei angenommen, dass Sie immer genau 2 Schritte machen müssen, obwohl Sie eigentlich k Schritte machen können (wobei k sich je nach Situation ändert). Durch diesen starren „2-Schritte"-Ansatz kamen sie zu einem falschen Ergebnis.

3. Die Korrektur

Als Ellmann den Fehler korrigierte, änderte sich das Ergebnis nicht dramatisch in der Art, aber es wurde präziser.

• Das alte Ergebnis: Es sah so aus, als wäre die Grenze etwas unscharf.
• Das neue, korrekte Ergebnis: Die Grenze ist nun exakt $\pi / \sqrt{3}$ (Pi geteilt durch die Wurzel aus 3).
  Das ergibt eine Zahl von ungefähr 1,813799.

Das klingt fast gleich wie die alte Vermutung, aber in der Welt der Mathematik ist dieser Unterschied wichtig. Es ist wie bei einer Uhr: Wenn Sie eine Sekunde zu früh oder zu spät aufstehen, ist es für den Alltag egal. Aber für einen Wissenschaftler, der die genaue Zeit messen will, ist diese Sekunde alles.

4. Warum ist das Papier wichtig?

Das Besondere an diesem Papier von Paul Voutier ist nicht, dass er eine neue, riesige Entdeckung macht. Sondern er tut etwas, das oft vergessen wird: Er schreibt die Geschichte auf.

Guy und Kelly hatten den Fehler zwar bemerkt und privat mitgeteilt, aber sie haben es nie offiziell in einem wissenschaftlichen Artikel veröffentlicht, bevor Guy starb. Es war wie ein Geheimnis, das nur in Flüstergesprächen weitergegeben wurde.
Voutier sagt im Grunde: „Hört zu, hier ist genau, wo der Fehler war, hier ist die Korrektur, und hier ist der Beweis, warum die neue Zahl stimmt." Er füllt eine Lücke in der wissenschaftlichen Literatur.

Zusammenfassung in einem Satz

Dieses Papier ist wie eine „Berichtigung" in einem großen Mathe-Lehrbuch: Es zeigt genau, wo zwei berühmte Mathematiker sich verrechnet haben, und bestätigt, dass die wahre Grenze für das Puzzle bei etwa 1,814 Punkten pro Seite liegt – ein kleiner, aber wichtiger Unterschied, der nun endlich offiziell dokumentiert ist.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers von Paul M. Voutier auf Deutsch:

Titel und Kontext

Das Paper mit dem Titel „ON THE GUY-KELLY CONJECTURE FOR THE NO-THREE-IN-LINE PROBLEM" (Über die Guy-Kelly-Vermutung für das „Keine-Drei-in-einer-Linie"-Problem) befasst sich mit einer Korrektur eines heuristischen Arguments aus dem Jahr 1968, das von R. K. Guy und P. Kelly aufgestellt wurde. Der Autor liefert erstmals eine detaillierte Darstellung eines Fehlers, den Gabor Ellmann im Jahr 2004 identifiziert hatte, und zeigt, wie dieser zur Korrektur der vermuteten oberen Schranke für das Problem führt.

1. Das Problem: „No-Three-in-Line"

Das Problem untersucht die maximale Größe $f_n$ einer Teilmenge $T$ der Menge $S_n$ von $n^2$ Punkten mit ganzzahligen Koordinaten $(x, y)$ im Bereich $1 \le x, y < n$, sodass keine drei Punkte in$T$ kollinear (auf einer gemeinsamen Geraden) liegen.

• Bekannte Grenzen: Eine einfache Anwendung des Schubfachprinzips liefert die obere Schranke $f_n \le 2n$.
• Empirische Daten: Für $n \le 64$ ist bekannt, dass $f_n = 2n$ gilt (die Erweiterung auf $n=64$ wurde erst im Februar 2026 durch Prellberg erreicht).
• Vermutung: Es wird vermutet, dass für hinreichend große $n$ die Größe strikt kleiner als $2n$ist, also$f_n < 2n$.

2. Methodik und der ursprüngliche Ansatz (Guy & Kelly, 1968)

Guy und Kelly verwendeten einen heuristischen, probabilistischen Ansatz, um das asymptotische Verhalten von $f_n$ abzuschätzen:

1. Anzahl kollinearer Tripel: Sie bewiesen, dass die Anzahl $t_n$ der Mengen aus 3 kollinearen Punkten in $S_n$ asymptotisch durch $t_n \sim \frac{3}{\pi^2} n^4 \log(n)$ gegeben ist.
2. Wahrscheinlichkeitsrechnung: Basierend darauf wurde die Wahrscheinlichkeit berechnet, dass drei zufällig gewählte Punkte kollinear sind. Unter der Annahme der Unabhängigkeit dieser Ereignisse wurde die Wahrscheinlichkeit berechnet, dass eine Menge von $k n$ Punkten keine drei kollinearen Punkte enthält.
3. Schätzung der Lösungsanzahl: Durch Anwendung der Stirling-Approximation und der Exponentialfunktion wurde eine Schätzung für die Anzahl der gültigen Konfigurationen abgeleitet.
4. Ursprüngliche Vermutung: Guy und Kelly folgerten daraus, dass die Anzahl der Lösungen gegen Null geht, wenn $k > \pi / \sqrt{3}$ ist. Dies führte zu ihrer ursprünglichen Vermutung (Gleichung 1 im Paper):
   $$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.8138 \, n$$
   (Hinweis: Der ursprüngliche Wert war $c \approx 1.8138$, was mathematisch $\sqrt[3]{2\pi^2/3}$ entspricht, aber im Paper wird die Korrektur auf einen anderen Wert hinweisen, der scheinbar denselben numerischen Wert, aber eine andere Herleitung hat.)

3. Identifizierung des Fehlers und Korrektur

Der Kernbeitrag dieses Papers liegt in der Aufklärung eines spezifischen algebraischen Fehlers in der Originalarbeit von Guy und Kelly, der von Gabor Ellmann im März 2004 (laut Briefwechsel) bzw. März 2005 (laut Flammenkamp) entdeckt wurde.

• Ort des Fehlers: Der Fehler befindet sich auf Seite 530, Zeile -4 der Originalarbeit [3].
• Fehlerbeschreibung: In der Herleitung der Exponenten wurde fälschlicherweise $2n$anstelle von$k n$verwendet. Konkret wurde der Term$-2 + 3k^3/\pi^2$verwendet, während er korrekt$-k + 3k^3/\pi^2$ lauten müsste.
• Ursache: Der Fehler entstand durch die Annahme, dass die Größe der zu untersuchenden Menge fest $2n$ist, anstatt sie als variable Größe$k n$ zu behandeln, was für die asymptotische Analyse notwendig ist.
• Korrektur: Durch die Korrektur des Terms ändert sich die Bedingung dafür, dass die geschätzte Anzahl der Lösungen gegen Null geht. Die neue Bedingung führt zu einer anderen Konstante.

4. Ergebnisse und die korrigierte Vermutung

Durch die Korrektur des Fehlers ergibt sich eine neue asymptotische Vermutung für $f_n$:

$$f_n \sim \left(\frac{\pi}{\sqrt{3}}\right) n$$

Numerisch entspricht dies:
$$c = \frac{\pi}{\sqrt{3}} \approx 1.813799$$

Obwohl der numerische Wert der Konstante ($\approx 1.8138$) dem ursprünglichen Wert von Guy und Kelly sehr nahe kommt (und in der Tat fast identisch ist, da $\sqrt[3]{2\pi^2/3} \approx 1.8138$ und $\pi/\sqrt{3} \approx 1.8138$), ist die mathematische Herleitung und die zugrundeliegende Formel fundamental anders. Die ursprüngliche Formel basierte auf einem falschen Exponenten, während die korrigierte Formel auf der richtigen Behandlung der Variablen $k$ beruht.

5. Bedeutung und Beitrag des Papers

• Dokumentation einer Lücke: Obwohl der Fehler und die Korrektur in privaten Korrespondenzen (z. B. zwischen Guy und Ellmann) und auf Webseiten (Flammenkamp) erwähnt wurden, fehlte eine formale, detaillierte Darstellung in der wissenschaftlichen Literatur. Dieses Paper schließt diese Lücke.
• Bestätigung: Der Autor bestätigt die kürzlich von Thomas Prellberg (2026) veröffentlichte Herleitung der korrigierten Schranke.
• Kritische Würdigung: Das Paper erwähnt auch, dass die Unabhängigkeitsannahme in der heuristischen Argumentation von Guy und Kelly von einigen Forschern (z. B. Nathan Kaplan) und empirischen Daten (z. B. bei rotationssymmetrischen Gittern) in Frage gestellt wird. Dennoch liefert die Korrektur des algebraischen Fehlers den konsistentesten derzeitigen theoretischen Rahmen für die obere Schranke.

Zusammenfassend liefert Voutier die erste vollständige, peer-reviewte Darstellung der Korrektur des Guy-Kelly-Arguments, präzisiert den Ort des Fehlers (Verwechslung von $2n$und$kn$) und bestätigt die neue asymptotische Schranke$f_n \sim \frac{\pi}{\sqrt{3}} n$ als den korrekten heuristischen Konsens für das „No-Three-in-Line"-Problem.