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

De auteurs weerleggen de vermoeden van Erdős over de diameter van verzamelingen met onderling gescheiden afstanden in hoge dimensies door een tegenvoorbeeld te construeren en het bewijs volledig te formaliseren in Lean 4.

De kern

De Grote Wiskundige Raadsel: Waarom de "Afstands-Regel" in Hoge Dimensies Faalt

Stel je voor dat je een groep vrienden uitnodigt voor een feestje in een enorm, leeg plein. Je hebt één simpele regel: geen twee paren vrienden mogen op precies dezelfde afstand van elkaar staan. Als twee mensen 5 meter uit elkaar staan, mag geen ander paar ook 5 meter uit elkaar staan. Ze moeten allemaal minimaal 1 meter uit elkaar liggen, en de afstanden tussen de paren moeten allemaal verschillend zijn.

De wiskundige Paul Erdős stelde zich jaren geleden de vraag: "Als ik zo'n groep mensen heb, hoe groot moet het plein dan minimaal zijn?"

Hij dacht dat het antwoord simpel was: hoe meer mensen er zijn, hoe groter het plein moet zijn. Hij vermoedde dat als je $n$ mensen hebt, de grootte van het plein (de "diameter") minstens even groot zou moeten zijn als $n^2$ (het kwadraat van het aantal mensen). Hij dacht dat dit een universele wet was, ongeacht of je in een 2D-kaartje of in een 3D-ruimte zat.

De Nieuwe Ontdekking: De Regel is Gebroken!

De auteur van dit paper, Boon Suan Ho, heeft bewezen dat Erdős zich vergist heeft, maar alleen in heel hoge dimensies. Het is alsof je een wet ontdekt die werkt op aarde, maar faalt als je naar de ruimte vliegt.

Hier is hoe het werkt, vertaald in alledaagse termen:

1. De Bouwplaat: De "Singer-Bloemen"

In plaats van mensen op een willekeurige plek te zetten, gebruikt de auteur een slimme wiskundige constructie die lijkt op het planten van bloemen in een cirkelvormig tuinpatroon.

• Hij gebruikt een speciaal soort getallen (genoemd "Singer-different sets") die zorgen dat elke mogelijke afstand tussen twee bloemen uniek is.
• Vervolgens plaatst hij deze bloemen niet op een vlakke grond, maar in een extreem hoge dimensie (een ruimte met duizenden of miljoenen richtingen tegelijk).

2. Het Trucje: Het "Gedrukte" Plein

Stel je voor dat je een elastiek hebt. In een lage dimensie (zoals op een vel papier) zou je de mensen zo moeten verspreiden dat ze ver uit elkaar staan om aan de regel te voldoen. Dit maakt het plein enorm.

Maar in die hoge dimensie kan de auteur de mensen zo positioneren dat ze:

1. Allemaal voldoen aan de regel (geen twee paren hebben dezelfde afstand).
2. Toch dicht bij elkaar blijven.

Het is alsof je een touw hebt dat je in een 2D-ruimte moet uitrekken tot 100 meter, maar in een 1000-dimensionale ruimte kun je het touw "opvouwen" in een kleine hoek, zodat de uiteinden maar 89 meter uit elkaar liggen, terwijl alle knopen in het touw nog steeds unieke afstanden hebben.

3. Het Resultaat: Een Reusachtige Besparing

De berekeningen tonen aan dat de diameter van dit "feestje" niet $n^2$ is, maar ongeveer 0,89 keer $n^2$.

• Erdős dacht: "Je hebt 100% van de ruimte nodig."
• De realiteit: "Je hebt maar 89% van de ruimte nodig."

Dat klinkt misschien niet als veel, maar in de wiskunde is het een enorme klap voor een theorie die al decennia lang als waar werd aangenomen. Het betekent dat de "ruimte" die we nodig hebben om unieke afstanden te maken, in hoge dimensies veel efficiënter gebruikt kan worden dan we dachten.

Waarom is dit belangrijk?

Dit paper is niet alleen een wiskundig raadsel oplossen. Het laat zien dat onze intuïtie over hoe ruimte werkt, faalt als we de dimensies verhogen.

• Analogie: Het is alsof je denkt dat je voor een grote stad altijd een groot vlak stuk land nodig hebt. Maar als je gebouwen mag bouwen in de lucht (hoge dimensie), kun je dezelfde stad in een veel kleiner grondgebied passen, zonder dat de straten (afstanden) in de war raken.

De "AI" Factor

Het paper noemt ook iets heel opvallends: de auteur heeft de basis van deze constructie ontdekt met hulp van een geavanceerde AI (genaamd GPT-5.4 Pro), en het bewijs is volledig gecontroleerd door een andere AI (Harmonic Aristotle) in een programmeertaal genaamd Lean 4. De auteur heeft het daarna zelf nagelopen om zeker te zijn. Het is een voorbeeld van hoe menselijke wiskundigen en AI samenwerken om de grenzen van de kennis te verleggen.

Kortom: Erdős had gelijk voor platte vlakken en lage ruimtes, maar in de "multiversum" van hoge dimensies is de ruimte veel compacter dan we dachten. De "diameter-conjectuur" is dus niet universeel waar.

Technische samenvatting

Titel: Erdős' Diametervermoeden voor Gescheiden Afstanden Faalt in Hoge Dimensies

1. Het Probleem

Het artikel adresseert een open probleem dat door Paul Erdős is gesteld (Problem 20 in een hoofdstuk over onopgeloste problemen). De vraag luidt: wat is de ondergrens voor de diameter van een verzameling van $n$ punten in de Euclidische ruimte, gegeven dat alle $\binom{n}{2}$ onderlinge afstanden ten minste 1 uit elkaar liggen (d.w.z. $| |x-y| - |x'-y'| | \geq 1$ voor elke twee verschillende paren)?

Erdős vermoedde dat de diameter $D$ van zo'n verzameling voldoet aan:
$$D \geq (1 + o(1)) n^2$$
Deze ondergrens zou onafhankelijk moeten zijn van de dimensie van de ruimte. Hoewel het vermoeden in dimensie 1 is bewezen, was er weinig direct onderzoek naar de hogedimensionale vorm. Het doel van dit artikel is om aan te tonen dat dit vermoeden in het algemeen onjuist is.

2. Methodologie en Constructie

De auteur weerlegt het vermoeden door een expliciete constructie van puntverzamelingen in hoge dimensies die een diameter hebben die strikt kleiner is dan $(1 + o(1))n^2$. De kern van de methode bestaat uit de volgende stappen:

• Singer-verschilverzamelingen: Er wordt gebruikgemaakt van een klassiek resultaat van Singer. Voor elke priemkracht $q$ wordt een cyclische $(m, n, 1)$-verschilverzameling $D$ geconstrueerd in $\mathbb{Z}/m\mathbb{Z}$, waarbij $m = q^2 + q + 1$ en $n = q + 1$. Deze verzameling heeft de eigenschap dat elke niet-nul restklasse uniek geschreven kan worden als $a - b$ met $a, b \in D$.
• Cyclische Profielen: De $\binom{n}{2}$ ongeordende paren uit $D$ corresponderen met unieke cyclische scheidingen $s \in \{1, \dots, N\}$, waarbij $N = (m-1)/2$.
• Gewogen Product van Regelmatige Veelhoeken: De punten worden gerealiseerd in de ruimte $\mathbb{R}^{2N}$ (wat gelijk is aan $\mathbb{R}^{m-1}$) door ze te plaatsen op een gewogen product van regelmatige $m$-hoeken. De coördinaten worden bepaald door gewichten $W_r$ die gekoppeld zijn aan de frequenties van de Fourier-reeks.
• Eén-frequentie Perturbatie: De gewichten $W_r$ worden specifiek gekozen op basis van een reeks $c_j = 1/j^2$ voor oneven $j$, met een kleine verstoring bij $j=1$ (waar $c_1 = 1-\varepsilon$ met $\varepsilon = 1/8$). Dit leidt tot een functie $H(\theta)$ die de kwadratische afstanden bepaalt.
• Schaling: De resulterende afstanden $d_s$ worden zo gekozen dat de gaten tussen opeenvolgende afstanden ($d_{s+1} - d_s$) afnemen naarmate $s$ toeneemt. Door de hele configuratie te schalen met de reciproke van het kleinste gat, wordt gegarandeerd dat alle onderlinge afstanden minstens 1 uit elkaar liggen.

3. Belangrijkste Resultaten

De hoofdstelling (Theorema 1) stelt dat er voor oneindig veel waarden van $n$ een $n$-puntenset $X_n \subset \mathbb{R}^{n^2-n}$ bestaat met de volgende eigenschappen:

1. Alle onderlinge afstanden zijn gescheiden door ten minste 1.
2. De diameter van de set wordt begrensd door:
   $$\text{diam}(X_n) \leq (c^* + o(1)) n^2$$
   waarbij $c^* = 1 - \frac{1}{\pi^2} \approx 0.89867$.

Aangezien $c^* < 1$, weerlegt dit de oorspronkelijke conjectuur van Erdős die een factor van 1 (of groter) voorspelde.

Asymptotische Analyse:
De bewijzen tonen aan dat de verhouding tussen de diameter en $n^2$ convergeert naar $1 - 1/\pi^2$. Dit wordt bereikt door de analyse van de functie $G(\theta) = \sqrt{H(\theta)}$ en het toepassen van de middelwaardestelling op de randwaarden van het interval.

4. Significatie en Opmerkingen

• Dimensie-afhankelijkheid: Het resultaat toont aan dat de ondergrens voor de diameter niet uniform geldt voor alle dimensies. De conjectuur faalt in hoge dimensies.
• Open Vraag: Het blijft een open vraag of het vermoeden waar kan zijn voor een vaste dimensie $d \geq 2$. De constructie vereist dat de dimensie groeit met $n$ (namelijk $O(n^2)$).
• Optimalisatie: De auteur merkt op dat de gebruikte constante $c^* \approx 0.898$ niet de scherpst mogelijke is binnen deze familie van constructies. Door de parameter $\varepsilon$ te optimaliseren, kan de constante theoretisch worden verlaagd tot ongeveer $0.885$. Numerieke optimalisatie van meerdere frequenties suggereert zelfs een waarde rond $0.854$.
• Formalisatie: Een opmerkelijk aspect van dit artikel is dat het volledige bewijs is geformaliseerd in het Lean 4 bewijsassistentie-systeem. De auteur geeft aan dat AI-tools (zoals GPT-5.4 Pro en Harmonic Aristotle) zijn gebruikt voor het ontdekken van de constructie en het formaliseren, maar dat alle wiskundige argumenten onafhankelijk zijn geverifieerd door de auteur.

Conclusie

Het artikel levert een definitief tegenvoorbeeld voor de dimensie-onafhankelijke versie van Erdős' diametervermoeden voor verzamelingen met gescheiden afstanden. Door gebruik te maken van algebraïsche structuren (Singer-verschilverzamelingen) en harmonische analyse, wordt aangetoond dat in hoge dimensies de diameter significant kleiner kan zijn dan $(1+o(1))n^2$, met een asymptotische factor van ongeveer $0.899$.