Het getal 15 beschrijft de geheime limiet van een oneindig raster

Als student aan de Universiteit van Chili, Bernardo Subercaseaux had een vage kijk op het gebruik van computers om wiskunde te doen. Het leek haaks op echte intellectuele ontdekkingen.

"Er is een instinctieve of onderbuikreactie tegen het gebruik van computers om je problemen op te lossen, alsof het indruist tegen de ideale schoonheid of elegantie van een fantastisch argument," zei hij.

Maar toen werd Subercaseaux in 2020 verliefd, en zoals vaak gebeurt, veranderden zijn prioriteiten. Het object van zijn obsessie was een vraag die hij op een online forum zag. De meeste problemen scande hij en vergat hij, maar deze trok zijn aandacht. Hij veegde naar rechts.

"Het eerste wat ik deed, was het bericht in de Facebook-groep leuk vinden, in de hoop later een melding te krijgen wanneer iemand anders een oplossing plaatste", zei hij.

De vraag ging over het vullen van een oneindig raster met getallen. Het was niet, zoals later bleek, het soort probleem dat je op een leeuwerik oplost. Om dit te kunnen doen, moest Subercaseaux Chili verlaten om naar de Carnegie Mellon University te gaan.

Daar, in augustus 2021, had hij een toevallige ontmoeting met Marijn Heule, een computerwetenschapper die enorme rekenkracht gebruikt om moeilijke wiskundige vragen op te lossen. Subercaseaux vroeg Heule of hij het probleem wilde proberen, het begin van een samenwerking die in januari culmineerde in een bewijs dat kan worden samengevat met een enkel getal: 15.

Elke mogelijke manier

In 2002, Wayne Goddard van Clemson University en enkele gelijkgestemde wiskundigen waren spuwende problemen in de combinatoriek en probeerden nieuwe wendingen te bedenken op de belangrijkste vragen van het veld over het inkleuren van kaarten, gegeven bepaalde beperkingen.

Uiteindelijk kwamen ze uit op een probleem dat begint met een raster, zoals een vel ruitjespapier dat eeuwig doorgaat. Het doel is om het te vullen met cijfers. Er is slechts één beperking: de afstand tussen elk voorkomen van hetzelfde getal moet groter zijn dan het getal zelf. (Afstand wordt gemeten door de verticale en horizontale scheiding bij elkaar op te tellen, een maatstaf die bekend staat als "taxiafstand" voor de manier waarop het lijkt op bewegen in gerasterde stadsstraten.) Een paar 1's kunnen geen aangrenzende cellen bezetten, die een taxiafstand van 1 hebben, maar ze kunnen in direct diagonale cellen worden geplaatst, die een afstand van 2 hebben.

Aanvankelijk wilden Goddard en zijn medewerkers weten of het überhaupt mogelijk was om een ​​oneindig raster te vullen met een eindige reeks getallen. Maar tegen de tijd dat hij en zijn vier medewerkers publiceerde dit probleem met het inkleuren van verpakkingen in het tijdschrift Ars Combinatoria in 2008 hadden ze bewezen dat het met 22 cijfers kan worden opgelost. Ze wisten ook dat het op geen enkele manier opgelost kon worden met slechts vijf cijfers. Dat betekende dat het eigenlijke antwoord op het probleem - het minimum aantal benodigde nummers - ergens tussenin lag.

De onderzoekers vulden eigenlijk geen oneindig raster. Dat hoefde niet. In plaats daarvan is het voldoende om een ​​kleine subset van het raster te nemen — bijvoorbeeld een vierkant van 10 bij 10 — dat met getallen te vullen en vervolgens aan te tonen dat kopieën van de gevulde subset naast elkaar kunnen worden geplaatst, zoals je een vloer met kopieën van een tegel.

Toen Subercaseaux voor het eerst van het probleem hoorde, begon hij met pen en papier naar tegels te zoeken. Hij zou rasters van getallen schetsen, ze doorstrepen en het opnieuw proberen. Hij was die aanpak al snel beu en hij vroeg een vriend om een ​​webgebaseerde tool te ontwerpen die leek op het spel Mijnenveger en waarmee hij sneller combinaties kon testen. Na nog een paar weken werk had hij zichzelf ervan overtuigd dat er geen manier was om een ​​raster met acht getallen in te pakken, maar hij kwam niet verder dan dat - er waren gewoon te veel mogelijke vormen die de tegels konden aannemen, en te veel verschillende manieren waarop ze met getallen kunnen worden gevuld.

Het probleem, zoals later duidelijk zou worden, is dat het veel moeilijker is om aan te tonen dat het raster niet kan worden gedekt door een bepaalde reeks getallen dan om aan te tonen dat dit wel het geval is. "Het laat niet alleen zien dat één manier niet werkt, het laat zien dat alle mogelijke manieren niet werken", zei Goddard.

Nadat Subercaseaux bij CMU begon en Heule overtuigde om met hem samen te werken, vonden ze al snel een manier om de grid met 15 nummers te dekken. Ze konden ook de mogelijkheid uitsluiten om het probleem op te lossen met slechts 12 nummers. Maar hun gevoelens van triomf waren van korte duur, omdat ze zich realiseerden dat ze alleen maar resultaten hadden gereproduceerd die al lang bestonden: al in 2017 wisten onderzoekers dat het antwoord niet minder dan 13 of meer dan 15 was. .

Voor een eerstejaarsstudent die een grote professor had overgehaald om aan zijn huisdierenprobleem te werken, was het een verontrustende ontdekking. “Ik was geschokt. Ik had eigenlijk al een aantal maanden aan een probleem gewerkt zonder het te beseffen, en erger nog, ik had Marijn gemaakt verspilt er zijn tijd aan!” Subercaseaux schreef in een blogpost waarin ze hun werk samenvatten.

Heule vond de ontdekking van resultaten uit het verleden echter stimulerend. Het toonde aan dat andere onderzoekers het probleem belangrijk genoeg vonden om aan te werken, en bevestigde voor hem dat het enige resultaat dat de moeite waard was om te behalen, was om het probleem volledig op te lossen.

"Toen we erachter kwamen dat er 20 jaar aan het probleem was gewerkt, veranderde dat het beeld volledig", zei hij.

Het vulgaire vermijden

In de loop der jaren had Heule zijn carrière gemaakt door efficiënte manieren te vinden om te zoeken tussen de enorme mogelijke combinaties. Zijn aanpak wordt SAT-oplossing genoemd - een afkorting van 'satisfiability'. Het omvat het construeren van een lange formule, een Booleaanse formule genaamd, die twee mogelijke resultaten kan hebben: 0 of 1. Als het resultaat 1 is, is de formule waar en is het probleem opgelost.

Voor het verpakkingskleurprobleem kan elke variabele in de formule aangeven of een bepaalde cel wordt ingenomen door een bepaald getal. Een computer zoekt naar manieren om variabelen toe te wijzen om aan de formule te voldoen. Als de computer het kan, weet je dat het mogelijk is om het raster in te pakken onder de voorwaarden die je hebt ingesteld.

Helaas kan een eenvoudige codering van het verpakkingskleurprobleem als een Booleaanse formule zich uitstrekken tot vele miljoenen termen - een computer, of zelfs een vloot van computers, kan eindeloos alle verschillende manieren testen om variabelen toe te wijzen.

"Proberen om deze brute kracht uit te oefenen, zou duren totdat het universum eindigt als je het naïef deed, " zei Goddard. "Dus je hebt een aantal coole vereenvoudigingen nodig om het terug te brengen tot iets dat zelfs maar mogelijk is."

Bovendien wordt elke keer dat u een getal toevoegt aan het kleurprobleem van de verpakking, het ongeveer 100 keer moeilijker, vanwege de manier waarop de mogelijke combinaties zich vermenigvuldigen. Dit betekent dat als een bank van parallel werkende computers er 12 zou kunnen uitsluiten in een enkele rekendag, ze 100 dagen rekentijd nodig zouden hebben om 13 uit te sluiten.

Heule en Subercaseaux beschouwden het opschalen van een brute-force computationele aanpak in zekere zin als vulgair. "We hadden verschillende veelbelovende ideeën, dus namen we de mentaliteit aan van 'Laten we proberen onze aanpak te optimaliseren totdat we dit probleem kunnen oplossen in minder dan 48 uur rekenwerk op het cluster'", aldus Subercaseaux.

Om dat te doen, moesten ze manieren bedenken om het aantal combinaties dat het rekencluster moest proberen te beperken.

"[Ze] willen het niet alleen oplossen, maar het op een indrukwekkende manier oplossen", zei Alexander Soifer van de Universiteit van Colorado, Colorado Springs.

Heule en Subercaseaux erkenden dat veel combinaties in wezen hetzelfde zijn. Als je een ruitvormige tegel probeert te vullen met acht verschillende nummers, maakt het niet uit of het eerste nummer dat je plaatst één boven en één rechts van het middelste vierkant is, of één beneden en één links van het middenplein. De twee plaatsingen zijn symmetrisch ten opzichte van elkaar en beperken je volgende zet op precies dezelfde manier, dus er is geen reden om ze allebei te controleren.

Heule en Subercaseaux voegden regels toe waardoor de computer symmetrische combinaties als equivalent kon behandelen, waardoor de totale zoektijd met een factor acht werd verkort. Ze gebruikten ook een techniek die Heule in eerder werk had ontwikkeld, genaamd kubus en veroveren, waardoor ze meer combinaties parallel aan elkaar konden testen. Als je weet dat een bepaalde cel 3, 5 of 7 moet bevatten, kun je het probleem splitsen en elk van de drie mogelijkheden tegelijkertijd testen op verschillende sets computers.

Tegen januari 2022 stelden deze verbeteringen Heule en Subercaseaux in staat om 13 uit te sluiten als het antwoord op het verpakkingskleurprobleem in een experiment dat minder dan twee dagen rekentijd vergde. Hierdoor hadden ze twee mogelijke antwoorden: 14 of 15.

Een groot pluspunt

Om er 14 uit te sluiten en het probleem op te lossen, moesten Heule en Subercaseaux aanvullende manieren vinden om het zoeken op de computer te versnellen.

Aanvankelijk hadden ze een Booleaanse formule geschreven die variabelen toewees aan elke afzonderlijke cel in het raster. Maar in september 2022 realiseerden ze zich dat ze niet cel voor cel hoefden te werk te gaan. In plaats daarvan ontdekten ze dat het effectiever was om kleine regio's te beschouwen die uit vijf cellen bestonden in de vorm van een plusteken.

Ze herschreven hun Booleaanse formule zodat verschillende variabelen vragen representeerden zoals: Is er ergens in dit plus-vormige gebied een 7? De computer hoefde niet precies te identificeren waar in de regio de 7 zou kunnen zijn. Het hoefde alleen maar te bepalen of het erin zat of niet - een vraag die aanzienlijk minder rekenkracht vereist om te beantwoorden.

"Variabelen hebben die alleen over plussen praten in plaats van over specifieke locaties, bleken veel beter te zijn dan erover te praten in specifieke cellen," zei Heule.

Geholpen door de efficiëntie van de plus-zoekopdracht, sloten Heule en Subercaseaux er 14 uit in een computerexperiment in november 2022 dat uiteindelijk minder tijd kostte dan het experiment dat ze hadden gebruikt om 13 uit te sluiten. Ze besteedden de volgende vier maanden aan het verifiëren dat de conclusie van de computer was juist - bijna evenveel tijd als ze hadden besteed om de computer überhaupt tot die conclusie te laten komen.

"Het was verheugend om te bedenken dat wat we als een soort bijvraag in een willekeurig tijdschrift hadden voortgebracht, ertoe had geleid dat groepen mensen, zoals later bleek, maanden van hun tijd besteedden aan het proberen uit te zoeken hoe ze het konden oplossen," Goddard gezegd.

Voor Subercaseaux was het de eerste echte triomf in zijn onderzoekscarrière. En hoewel het misschien niet het soort ontdekking was dat hij had geïdealiseerd toen hij voor het eerst overwoog om in de wiskunde te gaan werken, ontdekte hij dat het uiteindelijk zijn eigen intellectuele beloningen had.

"Het is geen begrip van het formulier waar je me een schoolbord geeft en ik kan je laten zien waarom het 15 is," zei hij. “Maar we hebben inzicht gekregen in hoe de beperkingen van het probleem werken, hoeveel beter het is om een ​​6 hier of een 7 daar te hebben. We hebben veel intuïtief inzicht gekregen.”