🔢 mathematics

New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

Dit artikel presenteert nieuwe ondergrenzen voor het graad/diameter-probleem, specifiek $N(12,5)\ge 34{,}992$ en $N(16,5)\ge 147{,}456$ , behaald via een nieuw ontdekkingsproces waarbij de auteur rechtstreeks interactie had met een standaard via het web toegankelijk LLM om expliciete grafen te construeren zonder gebruik te maken van aangepaste agent-frameworks of vooraf gedefinieerde zoekstrategieën.

Oorspronkelijke auteurs: Ryosuke Mizuno

Gepubliceerd 2026-06-16

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ryosuke Mizuno

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Wiskundige Puzzel en een Digitale Partner

Stel je een gigantische puzzel voor genaamd het Graad/Diameter Probleem. Het doel is om de grootste mogelijke "stad" (een netwerk van punten en lijnen) te bouwen waarbij aan twee regels strikt wordt voldaan:

De Graad-regel: Elk gebouw (punt) kan maximaal een bepaald aantal wegen (lijnen) hebben die er verbonden zijn.
De Diameter-regel: Ongeacht welke twee gebouwen je kiest, je moet in een zeer kort aantal stappen van het ene naar het andere kunnen rijden (niet meer dan 5 stappen).

Wiskundigen proberen al decennia lang de grootste mogelijke steden te bouwen die aan deze regels voldoen. Hoe groter de stad, hoe beter de score.

De Doorbraak:
Dit artikel meldt dat een onderzoeker, werkend alleen met een standaard webbrowser en een AI-chatbot (ChatGPT), twee nieuwe "steden" heeft gebouwd die aanzienlijk groter zijn dan alle eerder bekende steden.

Stad A: Een netwerk met 34.992 gebouwen.
Stad B: Een netwerk met 147.456 gebouwen.

Beide steden volgen de regel dat je overal in 5 stappen of minder kunt komen, en geen enkel gebouw heeft meer dan respectievelijk 12 of 16 wegen. Deze cijfers verslaan de vorige wereldrecords.

Hoe Ze Het Deden: De "Controller" en de "Fiber"

Het geheim achter het bouwen van deze enorme steden was niet simpelweg gokken. De onderzoeker en de AI ontdekten een slimme manier om het probleem op te splitsen in twee kleinere, beheersbare stukken. Denk aan het bouwen van een enorme hotelketen:

De Controller (Het Blauwdruk): Stel je een kleine, eenvoudige kaart voor van een paar belangrijke knooppunten. Dit is de "Controller". Zijn taak is om de algemene richting te bepalen. In dit geval vond de AI een kleine kaart met 144 knooppunten die ervoor zorgt dat je van elk knooppunt naar elk ander knooppunt kunt reizen in exact 5 stappen zonder direct om te keren (een "non-backtracking" wandeling).
De Fiber (De Kamers): Stel je nu voor dat er op elk enkel knooppunt op die kleine kaart niet slechts één gebouw staat. In plaats daarvan heb je een enorme, complexe toren van kamers. Dit is de "Fiber". De AI bedacht een wiskundig "liftsysteem" (met behulp van algebra en eindige velden) dat precies vertelt hoe je tussen de kamers in deze torens beweegt op basis van de weg die je neemt.

De Magische Truc:
Het genie van de ontdekking was het besef dat als je de kleine kaart (de Controller) goed krijgt, en je het liftsysteem (de Fiber) goed krijgt, je ze kunt combineren om een gigantische stad te creëren. De kleine kaart regelt de navigatie op de "grote schaal", en het liftsysteem regelt de "fijne details" van het bewegen tussen miljoenen specifieke punten.

De Mens-AI Samenwerking: Een Dans van Begeleiding

Dit artikel is uniek omdat het niet beweert dat de AI de wiskunde alleen heeft opgelost, noch dat de mens het alleen heeft gedaan. Het beschrijft een specifieke manier waarop zij samenwerkten:

Geen Super-Systeem: De onderzoeker heeft geen complex robotprogramma of een gespecialiseerde software-engine gebouwd. Hij gebruikte gewoon de standaard ChatGPT-website, net zoals iedereen dat zou doen.
De Mens als Kapitein: De onderzocher trad op als een kapitein van een schip. Hij vertelde de AI niet hoe de lift gebouwd moest worden of hoe de kaart eruit moest zien. In plaats daarvan gaf hij instructies op hoog niveau, zoals:
- "Kopieer niet zomaar oude ideeën."
- "Als we een doodlopend pad raken, stop dan en denk de hele strategie opnieuw na."
- "Geef me een reden om te geloven dat dit nieuwe idee zal werken voordat we het gaan bouwen."
De AI als Ontdekkingsreiziger: De AI verkende duizenden wiskundige mogelijkheden. Het probeerde veel ideeën die mislukten. Wanneer de AI vastliep, zei de menselijke kapitein: "Stop, dat pad is een doodlopende weg. Probeer een andere invalshoek."

Het "Aha!" Moment:
Een tijdlang probeerde de AI kleine fouten in slechte ontwerpen te herstellen (zoals het repareren van een lekkende boot). De menselijke kapitein stopte dit en vroeg om een "nieuw principe". De AI stelde toen het Controller/Fiber-idee voor (de "routekaart-lift"). Dit was het moment waarop de abstractie verscheen. Zodra dit nieuwe principe werd gevonden, bestond de rest uit het verfijnen van de details om de records te verbreken.

Wat Dit Papier Niet Beweert

Het is belangrijk om vast te houden aan wat het artikel daadwerkelijk zegt:

Het is geen algemeen bewijs dat AI alle wiskundige problemen kan oplossen. Dit was één specifieke casestudy.
Het gaat niet over medische of klinische toepassingen. Dit is puur grafentheorie (wiskunde).
Het is niet zo dat de AI het uiteindelijke artikel heeft geschreven. De menselijke onderzoeker heeft elke stap geverifieerd, de bewijzen geschreven en de verantwoordelijkheid genomen voor het uiteindelijke resultaat. De AI was een instrument voor ontdekking, niet de auteur.

Samenvatting

Beschouw dit artikel als een logboek van een succesvolle expeditie. Een menselijke ontdekkingsreiziger gebruikte een digitale kompas (de AI) om door een wiskundige jungle te navigeren. De ontdekkingsreiziger liet de kompas de auto niet besturen; hij stuurde hem, vertelde hem wanneer hij moest stoppen en vroeg hem om nieuwe routes te bedenken. Samen vonden ze een pad naar een enorme, voorheen onontdekte wiskundige structuur, waarmee bewezen wordt dat zelfs een standaard browser-gebaseerde AI, wanneer geleid door een mens met een duidelijke strategie, kan helpen bij het verbreken van wereldrecords in de pure wiskunde.

Technische Samenvatting: Nieuwe ondergrenzen voor het graad/diameterprobleem via interactie met een browser-toegankelijk LLM

Probleemstelling
Het artikel behandelt het graad/diameterprobleem, dat streeft naar het bepalen van $N(\Delta, D)$ , het maximaal aantal knopen in een eenvoudige, ongerichte, samenhangende graaf met een maximale graad van hoogstens $\Delta$ en een diameter van hoogstens $D$ . Hoewel de Moore-bovengrens een bovengrens biedt voor $N(\Delta, D)$ , blijft de exacte waarde voor de meeste parameterparen onbekend. De specifieke focus van dit werk ligt op het verbeteren van de bekende ondergrenzen voor diameter $D=5$ met maximale graden $\Delta=12$ en $\Delta=16$ .

Methodologie
De studie documenteert een wiskundig ontdekkingsproces dat werd uitgevoerd via een langdurige dialoog met een browser-toegankelijk Large Language Model (ChatGPT, geïdentificeerd als gpt-5-5-pro in de metadata) via de standaard webinterface. Cruciaal is dat de auteur geen externe orchestratielagen, aangepaste agent-frameworks, automatische evaluatoren of formele bewijsassistenten heeft gebruikt. De zoektocht vertrouwde uitsluitend op de interactieve capaciteiten van het LLM en de meta-niveau interventies van de auteur.

Het ontdekkingsproces omvatte:

Initiële exploratie: Het onderzoeken van de literatuur en het proberen van diverse constructiemethoden (bijv. permutatie-lifts, voltage-grafen, willekeurige reguliere grafen), waarvan de meeste faalden in het leveren van een certificaat.
Abstractieverschuiving: Een cruciale transitie vond plaats toen het LLM een "route-chart lift"-principe voorstelde. Dit deconstrueerde het probleem in twee onafhankelijke eindige design-taken:
- Controller-probleem: Het construeren van een kleine hulp-graaf (de "controller") waar elk paar knopen verbonden is door een non-backtracking wand van een specifieke lengte.
- Fiber Chart-probleem: Het construeren van lineair-algebraïsche data (een "route chart") over een eindig lichaam zodanig dat specifieke controleerbaarheidsmatrices niet-singulier zijn voor alle gereduceerde woorden van de doel-lengte.
Meta-niveau interventies: De auteur stuurde de zoektocht bij door beperkingen op te leggen (bijv. het vermijden van webzoekopdrachten, het eisen van ideeën die niet essentieel in de bestaande literatuur zijn opgenomen, en het vragen om "a priori" redenen voor succes) en door in te grijpen wanneer de zoektocht afdwaalde naar lokale reparatie of trial-and-error.

Belangrijkste Bijdragen
Het artikel levert twee primaire bijdragen:

Verbeterde wiskundige ondergrenzen:
De auteurs presenteren expliciete constructies van eenvoudige ongerichte grafen die nieuwe ondergrenzen vaststellen:
- $N(12, 5) \ge 34.992$ (verbetering ten opzichte van het vorige record van 29.621).
- $N(16, 5) \ge 147.456$ (verbetering ten opzichte van het vorige record van 132.496).
Deze grafen worden geconstrueerd door een specifieke 144-knopen controller-graaf (afgeleid van een 6-knopen multigraf via een $C_4 \times C_6$ voltage-toewijzing) te liften met behulp van een universele route chart over de eindige lichamen $\mathbb{F}_3$ en $\mathbb{F}_4$ , respectievelijk. De diameter is bewezen exact 5 te zijn.
Procesanalyse van mens-AI-samenwerking:
Het artikel biedt een gedetailleerde transcript-gebaseerde analyse van een wiskundig ontdekkingsproces dat werd uitgevoerd zonder externe automatisering. Het benadrukt hoe meta-niveau interventies (zoals het vragen om nieuwe principes of het stoppen van lokale reparatiepogingen) hielpen om het LLM te sturen naar een succesvolle abstractie (de route-chart lift) en een uiteindelijke oplossing. De auteurs benadrukken dat het LLM fungeerde als een interactieve ontdekkingsmotor, terwijl de auteur alle claims, code en certificaten heeft geverifieerd.

Resultaten
De geconstrueerde grafen $G_3$ (12-regulier, 34.992 knopen) en $G_4$ (16-regulier, 147.456 knopen) voldoen aan de diameter-beperking van 5. De verbeteringen vertegenwoordigen een toename van respectievelijk ongeveer 18,13% en 11,29% ten opzichte van de vorige records. De constructies worden geverifieerd door middel van eindige berekening van de non-backtracking wanden van de controller en de niet-singulariteit van de controleerbaarheidsmatrices voor alle gereduceerde woorden van lengte 5.

Betekenis en Claims
Het artikel claimt bescheiden significantie op twee gebieden:

Wiskundig: Het levert de eerste expliciete constructies voor deze specifieke parameters en brengt de bekende ondergrenzen dichter bij de Moore-bovengrenzen.
Methodologisch: Het dient als een casus die aantoont dat significante wiskundige ontdekking mogelijk is met enkel een standaard browser-interface voor een LLM, zonder complexe agent-systemen. De auteurs verklaren expliciet dat zij het LLM niet als auteur of autonome bewijzer beschouwen; de menselijke onderzoeker behoudt de volledige verantwoordelijkheid voor de wiskundige geldigheid.

Het artikel claimt niet dat deze specifieke strategie algemeen effectief is of dat het LLM over algemene wiskundige redeneerkracht beschikt buiten deze specifieke instantie. Het presenteert het werk als een observationeel rapport van een enkel succesvol geval waarbij menselijke begeleiding en LLM-generatie samenkwamen om een specifiek open probleem in de grafentheorie op te lossen.

Het Grote Plaatje: Een Wiskundige Puzzel en een Digitale Partner

Hoe Ze Het Deden: De "Controller" en de "Fiber"

De Mens-AI Samenwerking: Een Dans van Begeleiding

Wat Dit Papier Niet Beweert

Samenvatting

Meer zoals dit