Tallet 15 beskriver den hemmelige grænse for et uendeligt gitter

Som bachelorstuderende ved University of Chile, Bernardo Subercaseaux havde et svagt syn på at bruge computere til at lave matematik. Det virkede i modstrid med ægte intellektuel opdagelse.

"Der er en eller anden instinkt eller tarmreaktion mod at bruge computere til at løse dine problemer, som om det går imod den ideelle skønhed eller elegance af et fantastisk argument," sagde han.

Men så i 2020 blev Subercaseaux forelsket, og som det ofte sker, ændrede hans prioriteter sig. Genstanden for hans besættelse var et spørgsmål, han så på et onlineforum. De fleste problemer scannede han og glemte, men dette fangede hans øje. Han strøg til højre.

"Det første, jeg gjorde, var at like opslaget i Facebook-gruppen, i håb om at få en notifikation senere, når en anden postede en løsning," sagde han.

Spørgsmålet handlede om at fylde et uendeligt gitter med tal. Det var, som det viste sig, ikke den slags problem, man løser på en lærke. For at gøre det var Subercaseaux nødt til at forlade Chile for at studere på Carnegie Mellon University.

Der havde han i august 2021 et tilfældigt møde med Marijn Heule, en datalog, der bruger massiv computerkraft til at løse svære matematiske spørgsmål. Subercaseaux spurgte Heule, om han ville prøve problemet, og startede et samarbejde, der kulminerede i januar i et bevis der kan opsummeres med et enkelt tal: 15.

Enhver mulig vej

I 2002, blev Wayne Goddard fra Clemson University og nogle ligesindede matematikere spøgte med problemer i kombinatorik og forsøgte at komme med nye drejninger på feltets hovedspørgsmål om farvelægning af kort givet visse begrænsninger.

Til sidst landede de på et problem, der starter med et gitter, som et ark millimeterpapir, der varer evigt. Målet er at fylde det med tal. Der er kun én begrænsning: Afstanden mellem hver forekomst af det samme tal skal være større end selve tallet. (Afstanden måles ved at lægge den lodrette og vandrette adskillelse sammen, en metrik kendt som "taxa-afstand" for den måde, den ligner at bevæge sig på bygader med gitter.) Et par 1'ere kan ikke optage tilstødende celler, som har en taxaafstand på 1, men de kan placeres i direkte diagonale celler, som har en afstand på 2.

Til at begynde med ville Goddard og hans samarbejdspartnere vide, om det overhovedet var muligt at fylde et uendeligt gitter med et endeligt sæt tal. Men da han og hans fire samarbejdspartnere udgivet dette "pakkefarve"-problem i tidsskriftet Ars Combinatoria i 2008 havde de bevist, at det kan løses ved hjælp af 22 tal. De vidste også, at der ikke var nogen måde, det kunne løses med kun fem numre. Det betød, at det faktiske svar på problemet - det mindste antal nødvendige numre - lå et sted midt imellem.

Forskerne udfyldte faktisk ikke et uendeligt gitter. Det behøvede de ikke. I stedet er det nok at tage en lille delmængde af gitteret - f.eks. en 10 x 10 firkant - udfyld den med tal, og vis derefter, at kopier af den udfyldte delmængde kan placeres ved siden af ​​hinanden, som du ville dække en gulv med kopier af en flise.

Da Subercaseaux først hørte om problemet, begyndte han at lede efter fliser ved hjælp af pen og papir. Han ville skitsere gitter af tal, strege dem ud, prøve igen. Han blev hurtigt træt af den tilgang, og han bad en ven om at designe et webbaseret værktøj, der lignede spillet Minesweeper og tillod ham at teste kombinationer hurtigere. Efter et par ugers arbejde havde han overbevist sig selv om, at der ikke var nogen måde at pakke et gitter med otte numre på, men han kunne ikke komme længere end det - der var bare for mange potentielle former, fliserne kunne tage, og for mange forskellige måder, de kunne fyldes med tal på.

Problemet, som det senere skulle blive klart, er, at det er langt sværere at vise, at gitteret ikke kan dækkes af et bestemt sæt tal end at vise, at det kan. "Det er ikke bare at vise, at én måde ikke virker, det er at vise, at alle mulige måder ikke virker," sagde Goddard.

Efter at Subercaseaux startede hos CMU og overbeviste Heule om at arbejde med ham, fandt de hurtigt en måde at dække nettet med 15 numre. De kunne også udelukke muligheden for at løse problemet med kun 12 numre. Men deres følelser af triumf var kortvarige, da de indså, at de blot havde gengivet resultater, der havde eksisteret i lang tid: Så langt tilbage som i 2017 havde forskere vidst, at svaret ikke var mindre end 13 eller større end 15 .

For en førsteårsstuderende, der havde truffet en stor professor til at arbejde på sit kæledyrsproblem, var det en foruroligende opdagelse. "Jeg var forfærdet. Jeg havde dybest set arbejdet i flere måneder på et problem uden at være klar over dette, og endnu værre, jeg havde lavet Marijn spilde sin tid på det!" Subercaseaux skrev i et blogindlæg, der opsummerer deres arbejde.

Heule fandt imidlertid opdagelsen af ​​tidligere resultater forfriskende. Det viste, at andre forskere fandt problemet vigtigt nok til at arbejde på, og bekræftede for ham, at det eneste resultat, der var værd at opnå, var at løse problemet fuldstændigt.

"Da vi fandt ud af, at der havde været 20 års arbejde på problemet, ændrede det billedet fuldstændig," sagde han.

Undgå det vulgære

I årenes løb havde Heule gjort en karriere ud af at finde effektive måder at søge blandt mange mulige kombinationer. Hans tilgang kaldes SAT solving - en forkortelse for "satisfiability". Det involverer at konstruere en lang formel, kaldet en boolsk formel, der kan have to mulige resultater: 0 eller 1. Hvis resultatet er 1, er formlen sand, og problemet er opfyldt.

For pakkefarveproblemet kan hver variabel i formlen repræsentere, om en given celle er optaget af et givet tal. En computer leder efter måder at tildele variabler for at opfylde formlen. Hvis computeren kan gøre det, ved du, at det er muligt at pakke nettet under de betingelser, du har indstillet.

Desværre kunne en ligetil kodning af pakkefarveproblemet som en boolsk formel strække sig til mange millioner termer - en computer, eller endda en flåde af computere, kunne køre for evigt og teste alle de forskellige måder at tildele variabler i den.

"At prøve at gøre denne rå kraft ville tage, indtil universet er færdigt, hvis du gjorde det naivt," sagde Goddard. "Så du har brug for nogle fede forenklinger for at bringe det ned til noget, der overhovedet er muligt."

Desuden, hver gang du tilføjer et tal til pakkefarveproblemet, bliver det omkring 100 gange sværere på grund af den måde, de mulige kombinationer formerer sig på. Dette betyder, at hvis en bank af computere, der arbejder parallelt, kunne udelukke 12 på en enkelt beregningsdag, ville de have brug for 100 dages beregningstid for at udelukke 13.

Heule og Subercaseaux betragtede opskalering af en brute-force beregningsmetode som vulgær på en måde. "Vi havde flere lovende ideer, så vi tog tankegangen om 'Lad os prøve at optimere vores tilgang, indtil vi kan løse dette problem på mindre end 48 timers beregning på klyngen'," sagde Subercaseaux.

For at gøre det var de nødt til at finde på måder at begrænse antallet af kombinationer, som computerklyngen skulle prøve.

"[De] ønsker ikke bare at løse det, men at løse det på en imponerende måde," sagde Alexander Soifer fra University of Colorado, Colorado Springs.

Heule og Subercaseaux erkendte, at mange kombinationer i det væsentlige er de samme. Hvis du forsøger at fylde en rombeformet brik med otte forskellige tal, er det lige meget, om det første tal, du placerer, er et op og et til højre for det midterste felt, eller et nede og et til venstre for den midterste plads. De to placeringer er symmetriske med hinanden og begrænser dit næste træk på nøjagtig samme måde, så der er ingen grund til at tjekke dem begge.

Heule og Subercaseaux tilføjede regler, der gjorde det muligt for computeren at behandle symmetriske kombinationer som ækvivalente, hvilket reducerede den samlede søgetid med en faktor på otte. De brugte også en teknik, Heule havde udviklet i tidligere arbejde kaldet cube and conquer, som gjorde det muligt for dem at teste flere kombinationer parallelt med hinanden. Hvis du ved, at en given celle skal indeholde enten 3, 5 eller 7, kan du opdele problemet og teste hver af de tre muligheder samtidigt på forskellige sæt computere.

I januar 2022 tillod disse forbedringer Heule og Subercaseaux at udelukke 13 som svaret på pakkefarveproblemet i et eksperiment, der krævede mindre end to dages regnetid. Dette efterlod dem med to mulige svar: 14 eller 15.

Et stort plus

For at udelukke 14 - og løse problemet - måtte Heule og Subercaseaux finde yderligere måder at fremskynde computersøgningen på.

I første omgang havde de skrevet en boolsk formel, der tildelte variabler til hver enkelt celle i gitteret. Men i september 2022 indså de, at de ikke behøvede at fortsætte celle for celle. I stedet opdagede de, at det var mere effektivt at overveje små områder bestående af fem celler i form af et plustegn.

De omskrev deres boolske formel, så adskillige variabler repræsenterede spørgsmål som: Er der et 7-tal et sted inden for dette plusformede område? Computeren behøvede ikke at identificere præcis, hvor i regionen de 7 måtte være. Det skulle bare afgøre, om det var derinde eller ej - et spørgsmål, som kræver betydeligt færre beregningsressourcer at besvare.

"At have variabler, der kun taler om plusser i stedet for specifikke steder, viste sig at være langt bedre end at tale om dem i specifikke celler," sagde Heule.

Godt hjulpet af effektiviteten af ​​plussøgningen udelukkede Heule og Subercaseaux 14 i et computereksperiment i november 2022, der endte med at tage kortere tid at køre end det, de havde brugt til at udelukke 13. De brugte de næste fire måneder på at bekræfte, at computerens konklusion var korrekt - næsten lige så meget tid, som de havde brugt på at sætte computeren i stand til at nå frem til den konklusion i første omgang.

"Det var glædeligt at tænke på, at det, vi havde affødt som en slags sidespørgsmål i en eller anden tilfældig journal, havde fået grupper af mennesker til at bruge, som det viste sig, måneder af deres tid på at finde ud af, hvordan de skulle løse det," siger Goddard. sagde.

For Subercaseaux var det den første rigtige triumf i hans forskerkarriere. Og selvom det måske ikke var den type opdagelse, han havde idealiseret, da han først overvejede at arbejde i matematik, fandt han ud af, at det i sidste ende havde sine egne intellektuelle belønninger.

"Det er ikke at forstå formularen, hvor du giver mig en tavle, og jeg kan vise dig, hvorfor den er 15," sagde han. "Men vi har fået en forståelse for, hvordan problemets begrænsninger fungerer, hvor meget bedre det er at have en 6'er her eller en 7'er der. Vi har fået en masse intuitiv forståelse.”