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

Dit artikel verstrekt de tot nu toe ontbrekende details over de fout die Gabor Ellmann in 2004 ontdekte in het heuristische argument van Guy en Kelly, wat leidde tot een correctie van hun bovengrens voor het "no-three-in-line"-probleem.

De kern

Stel je voor dat je een gigantisch rooster hebt, net als een bord met schijven of een pixelbeeld, dat $n$ rijen en $n$ kolommen heeft. In totaal zitten er dus $n^2$ punten op dit bord.

De vraag die wiskundigen al decennia lang bezighoudt is: Hoeveel punten kun je op dit bord kiezen zonder dat er ooit drie punten op één rechte lijn liggen?

Dit heet het "geen-drie-op-een-lijn"-probleem. Het is een beetje alsof je probeert je legpuzzelstukjes zo neer te leggen dat je nooit drie stukjes in een perfect rechte rij ziet staan.

Hier is wat dit nieuwe artikel van Paul Voutier vertelt, vertaald naar gewoon Nederlands met een paar leuke vergelijkingen:

1. De oude regel en de nieuwe ontdekking

Vroeger dachten wiskundigen dat je maximaal $2n$ punten kon kiezen. Dat is een simpele regel: als je een bord van 10 bij 10 hebt, kun je maximaal 20 punten kiezen. Voor kleine borden bleek dit ook te kloppen.

Maar Guy en Kelly (twee beroemde wiskundigen) dachten in 1968 dat voor heel grote borden dit maximum lager zou liggen. Ze gebruikten een slimme, maar ingewikkelde berekening (een "heuristische" schatting) om te voorspellen hoeveel punten je precies kunt kiezen. Ze kwamen uit op een getal dat ongeveer 2,08 keer $n$ was.

2. De fout in de machine

In 2004 ontdekte een wiskundige genaamd Gabor Ellmann dat er een klein, maar dodelijk foutje in de berekening van Guy en Kelly zat.

De analogie:
Stel je voor dat je een recept hebt om een enorme taart te bakken. Guy en Kelly hadden het recept geschreven, maar ze hadden per ongeluk een ingrediënt verkeerd gemeten. Ze dachten dat ze $2n$eieren nodig hadden voor hun berekening, terwijl ze eigenlijk$kn$ (een variabele hoeveelheid) eieren moesten gebruiken.

Door dit foutje in de formule, kwam hun eindresultaat net iets te hoog uit. Het was alsof ze dachten dat je een taart van 2,08 meter hoog kon bakken, terwijl de echte limiet lager ligt.

3. De correctie

Voutier legt in dit artikel precies uit waar die fout zat. Het was een heel klein typfoutje in de algebra, maar het veranderde de uitkomst drastisch.

Door de formule te corrigeren (de "eieren" opnieuw te tellen), kwam de nieuwe voorspelling uit op een veel mooier getal:
$$\frac{\pi}{\sqrt{3}} \times n$$
Dit is ongeveer 1,814 keer $n$.

Dus, in plaats van dat je op een bord van 100 bij 100 ongeveer 208 punten kunt kiezen, kun je er volgens de gecorrigeerde theorie maar ongeveer 181 kiezen zonder dat er drie op een lijn staan.

4. Waarom is dit belangrijk?

Je zou kunnen denken: "Ach, het gaat maar om een paar punten." Maar in de wiskunde is het cruciaal om te weten of je theorie klopt.

• Guy en Kelly hadden beloofd om hun fout te corrigeren, maar ze zijn helaas overleden voordat ze dat publiek konden doen.
• Dit artikel van Voutier is dus het officiële "reparatieverslag". Het legt uit waar de fout zat, hoe je hem oplost en wat het nieuwe antwoord is.
• Het bevestigt ook dat een andere wiskundige (Prellberg) onafhankelijk tot hetzelfde nieuwe antwoord is gekomen, wat het bewijs sterker maakt.

Samenvatting in één zin

Dit artikel is de officiële "reparatiehandleiding" voor een beroemde wiskundige voorspelling: door een klein rekenfoutje uit 1968 te vinden en te herstellen, weten we nu dat je op een groot rooster iets minder punten kunt kiezen dan eerder werd gedacht, en dat het juiste antwoord een mooie constante (ongeveer 1,81) is in plaats van een willekeurig getal.

Het is een mooi voorbeeld van hoe wetenschap werkt: zelfs als de grootste denkers een fout maken, zorgt de community ervoor dat het uiteindelijk wel goed komt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On the Guy-Kelly Conjecture for the No-Three-in-Line Problem" van Paul M. Voutier, geschreven in het Nederlands.

Samenvatting van het Artikel

Titel: On the Guy-Kelly Conjecture for the No-Three-in-Line Problem
Auteur: Paul M. Voutier
Doel: Het documenteren van een fout in de heuristische afleiding van Guy en Kelly (1968) en het publiceren van de correctie die door Gabor Ellmann in 2004 werd ontdekt.

---

1. Het Probleem: Het "No-Three-in-Line" Probleem

Het artikel behandelt een bekend probleem uit de discrete meetkunde:

• Definitie: Laat $S_n$ de verzameling zijn van $n^2$ punten in het vlak $\mathbb{R}^2$ met gehele coördinaten $(x, y)$ waarbij $1 \le x, y < n$.
• Doel: Vind het maximum aantal punten $f_n$ dat uit $S_n$ kan worden geselecteerd zodanig dat er geen drie punten collineair zijn (op één rechte lijn liggen).
• Bekende grenzen:
  • Een eenvoudige toepassing van het duivenhokprincipe levert de bovengrens $f_n \le 2n$.
  • Voor $n \le 64$ is bewezen dat $f_n = 2n$.
  • Voor grote $n$ wordt echter vermoed dat $f_n < 2n$.

2. De Oorspronkelijke Vermoeden en Heuristiek

In hun paper uit 1968 ([3]) stelden Guy en Kelly een heuristisch argument op om een asymptotische bovengrens voor $f_n$ te bepalen.

• Oorspronkelijk vermoeden: Zij concludeerden dat voor grote $n$:
  $$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.87 n$$
• Methodologie: Hun argument baseerde zich op een probabilistische benadering:
  1. Ze berekenden het aantal verzamelingen van 3 collineaire punten ($t_n$) in $S_n$, wat leidt tot $t_n \approx \frac{3}{\pi^2} n^4 \log(n)$.
  2. Ze berekenden de kans dat drie willekeurig gekozen punten collineair zijn.
  3. Ze namen aan dat deze gebeurtenissen onafhankelijk zijn om de kans te schatten dat een verzameling van $k n$ punten geen drie collineaire punten bevat.
  4. Door de Stirling-approximatie toe te passen, stelden ze een schatting op voor het aantal mogelijke oplossingen. Als deze schatting naar 0 gaat voor $n \to \infty$, betekent dit dat een dergelijke verzameling niet bestaat.

3. De Fout en de Correctie

In maart 2024 (en eerder in privécommunicatie in 2004) wees Gabor Ellmann op een fout in de heuristische redenering van Guy en Kelly. Voutier legt de exacte aard van deze fout en de correctie uit.

• Locatie van de fout: De fout bevindt zich op regel -4 van pagina 530 in het originele paper [3].
• De aard van de fout: Guy en Kelly gebruikten onterecht $2n$in plaats van een variabele$k n$in hun schattingen. Specifiek gebruikten ze de uitdrukking$-2 + 3k^3/\pi^2$in plaats van de correcte$-k + 3k^3/\pi^2$.
  • Dit komt doordat ze de factoriële termen $(n^2)! / (n^2 - 2n)!$ en $(2n)!$ gebruikten in plaats van de algemene vormen $(n^2)! / (n^2 - kn)!$ en $(kn)!$.
• Het gevolg: Door deze algebraïsche/transformatiefout was de exponent in hun asymptotische schatting verkeerd berekend.

4. Het Gecorrigeerde Vermoeden

Na het corrigeren van de fout leidt de heuristische afleiding tot een nieuwe constante.

• De nieuwe voorwaarde: De schatting voor het aantal oplossingen gaat naar 0 als $k - 3k^3/\pi^2 < 0$.
• De oplossing: Dit geldt voor $k > \pi/\sqrt{3}$.
• Het nieuwe vermoeden:
  $$f_n \sim \frac{\pi}{\sqrt{3}} n \approx 1.813799 n$$
  Dit is een lagere bovengrens dan het oorspronkelijke vermoeden van Guy en Kelly.

5. Bijdrage en Betekenis

• Publicatiestatus: Hoewel Gabor Ellmann de fout in 2004 ontdekte en R.K. Guy dit bevestigde, is de exacte locatie en de technische details van de correctie nooit eerder in de literatuur gepubliceerd. Voutier vult deze leemte op.
• Recente context: De auteur merkt op dat Thomas Prellberg in zeer recente werken ([5]) ook een afleiding van dit gecorrigeerde vermoeden heeft gepresenteerd, wat de validiteit van de correctie bevestigt.
• Kritische kanttekening: Het artikel erkent dat de onafhankelijkheidsaanname in het probabilistische argument (dat drie punten onafhankelijk van elkaar niet collineair zijn) door sommigen wordt betwijfeld, mede op basis van empirisch bewijs en recente seminars. Desondanks is de correctie van de algebraïsche fout in de oorspronkelijke afleiding van Guy en Kelly een noodzakelijke stap voor de huidige staat van de theorie.

Conclusie

Paul M. Voutier biedt de eerste gedetailleerde, gepubliceerde uitleg van de fout in het beroemde Guy-Kelly-paper uit 1968. Door een lokale algebraïsche fout te corrigeren (het vervangen van een constante 2 door een variabele $k$), wordt de geconjectureerde asymptotische bovengrens voor het "no-three-in-line" probleem aangepast van $\approx 1.87n$ naar $\approx 1.814n$. Dit werk verduidelijkt de historische ontwikkeling van dit probleem en bevestigt de correctie die door Ellmann en later Prellberg is gemaakt.