Tallet 15 beskriver den hemmelige grensen for et uendelig rutenett

Som undergraduate ved University of Chile, Bernardo Subercaseaux tok et svakt syn på å bruke datamaskiner til å gjøre matematikk. Det virket antitetisk til ekte intellektuell oppdagelse.

"Det er en eller annen instinkt eller magreaksjon mot å bruke datamaskiner for å løse problemene dine, som om det går mot den ideelle skjønnheten eller elegansen til et fantastisk argument," sa han.

Men så i 2020 ble Subercaseaux forelsket, og som ofte skjer, endret prioriteringene hans. Objektet for besettelse hans var et spørsmål han så på et nettforum. De fleste problemene skannet han og glemte, men dette fanget han oppmerksomhet. Han sveipet til høyre.

"Det første jeg gjorde var å like innlegget i Facebook-gruppen, i håp om å få et varsel senere når noen andre la ut en løsning," sa han.

Spørsmålet handlet om å fylle et uendelig rutenett med tall. Det var ikke, som det viste seg, den typen problem man løser på en lerke. For å gjøre det, måtte Subercaseaux forlate Chile for å studere ved Carnegie Mellon University.

Der, i august 2021, hadde han et tilfeldig møte med Marijn Heule, en informatiker som bruker massiv datakraft til å løse vanskelige matematikkspørsmål. Subercaseaux spurte Heule om han ønsket å prøve problemet, og startet et samarbeid som kulminerte i januar i et bevis som kan oppsummeres med et enkelt tall: 15.

Alle mulige veier

I 2002, Wayne Goddard fra Clemson University og noen likesinnede matematikere satte i gang problemer i kombinatorikk, og prøvde å komme opp med nye vendinger på feltets bærebjelkespørsmål om fargelegging av kart gitt visse begrensninger.

Til slutt landet de på et problem som starter med et rutenett, som et ark med millimeterpapir som varer evig. Målet er å fylle den med tall. Det er bare én begrensning: Avstanden mellom hver forekomst av samme tall må være større enn selve tallet. (Avstanden måles ved å legge sammen den vertikale og horisontale separasjonen, en metrikk kjent som "drosjeavstand" for måten den ligner på å bevege seg i bygater med rutenett.) Et par 1-ere kan ikke okkupere tilstøtende celler, som har en drosjeavstand på 1, men de kan plasseres i direkte diagonale celler, som har en avstand på 2.

I utgangspunktet ønsket Goddard og hans samarbeidspartnere å vite om det i det hele tatt var mulig å fylle et uendelig rutenett med et begrenset sett med tall. Men da han og hans fire samarbeidspartnere publiserte dette "pakkefarging"-problemet i tidsskriftet Ars Combinatoria i 2008 hadde de bevist at det kan løses med 22 tall. De visste også at det ikke var mulig å løse det med bare fem tall. Det betydde at det faktiske svaret på problemet - minimum antall numre som trengs - lå et sted i mellom.

Forskerne fylte faktisk ikke et uendelig rutenett. Det trengte de ikke. I stedet er det nok å ta en liten delmengde av rutenettet – for eksempel en kvadrat på 10 ganger 10 – fyll den med tall, og vis deretter at kopier av den fylte delmengden kan plasseres ved siden av hverandre, slik du ville dekket en gulv med kopier av en flis.

Da Subercaseaux først fikk vite om problemet, begynte han å lete etter fliser ved hjelp av penn og papir. Han ville skissere rutenett med tall, krysse dem ut, prøve igjen. Han ble snart lei av den tilnærmingen, og han ba en venn designe et nettbasert verktøy som lignet spillet Minesweeper og lot ham teste kombinasjoner raskere. Etter noen flere uker med arbeid hadde han overbevist seg selv om at det ikke var mulig å pakke et rutenett med åtte tall, men han kunne ikke komme lenger enn det - det var bare for mange potensielle former flisene kunne ta, og for mange forskjellige måter de kan fylles med tall.

Problemet, som senere skulle bli klart, er at det er mye vanskeligere å vise at rutenettet ikke kan dekkes av et visst sett med tall enn å vise at det kan. "Det er ikke bare å vise at én måte ikke fungerer, det er å vise at alle mulige måter ikke fungerer," sa Goddard.

Etter at Subercaseaux begynte på CMU og overbeviste Heule om å jobbe med ham, fant de raskt en måte å dekke rutenettet med 15 tall. De kunne også utelukke muligheten for å løse problemet med bare 12 tall. Men følelsen av triumf var kortvarig, da de innså at de bare hadde gjengitt resultater som hadde eksistert i lang tid: Så langt tilbake som i 2017 hadde forskere visst at svaret ikke var mindre enn 13 eller større enn 15 .

For en førsteårsstudent som hadde lokket en storprofessor til å jobbe med kjæledyrproblemet sitt, var det en foruroligende oppdagelse. «Jeg ble forferdet. Jeg hadde egentlig jobbet i flere måneder med et problem uten å være klar over dette, og enda verre, jeg hadde laget Marijn kaste bort tiden sin på det!" Subercaseaux skrev i et blogginnlegg som oppsummerer arbeidet deres.

Heule fant imidlertid oppdagelsen av tidligere resultater forfriskende. Den demonstrerte at andre forskere fant problemet viktig nok til å jobbe med, og bekreftet for ham at det eneste resultatet verdt å oppnå var å løse problemet fullstendig.

"Når vi fant ut at det hadde vært 20 års arbeid med problemet, endret det bildet fullstendig," sa han.

Unngå det vulgære

Gjennom årene hadde Heule gjort en karriere ut av å finne effektive måter å søke blant enorme mulige kombinasjoner. Tilnærmingen hans kalles SAT-løsning - en forkortelse for "tilfredshet". Det innebærer å konstruere en lang formel, kalt en boolsk formel, som kan ha to mulige resultater: 0 eller 1. Hvis resultatet er 1, er formelen sann, og problemet er oppfylt.

For pakkefargeproblemet kan hver variabel i formelen representere om en gitt celle er okkupert av et gitt tall. En datamaskin ser etter måter å tilordne variabler for å tilfredsstille formelen. Hvis datamaskinen kan gjøre det, vet du at det er mulig å pakke rutenettet under betingelsene du har satt.

Dessverre kan en enkel koding av pakkefargeproblemet som en boolsk formel strekke seg til mange millioner termer - en datamaskin, eller til og med en flåte av datamaskiner, kan for alltid teste alle de forskjellige måtene å tilordne variabler i den.

"Å prøve å gjøre denne brutale kraften ville ta til universet er ferdig hvis du gjorde det naivt," sa Goddard. "Så du trenger noen kule forenklinger for å bringe det ned til noe som til og med er mulig."

Dessuten, hver gang du legger til et tall i pakkefargeproblemet, blir det omtrent 100 ganger vanskeligere, på grunn av måten de mulige kombinasjonene multipliseres på. Dette betyr at hvis en bank med datamaskiner som jobber parallelt kunne utelukke 12 på en enkelt dag med beregning, ville de trenge 100 dagers beregningstid for å utelukke 13.

Heule og Subercaseaux betraktet oppskalering av en brute-force beregningstilnærming som vulgær, på en måte. "Vi hadde flere lovende ideer, så vi tok tankegangen "La oss prøve å optimalisere tilnærmingen vår til vi kan løse dette problemet på mindre enn 48 timer med beregning på klyngen," sa Subercaseaux.

For å gjøre det måtte de komme opp med måter å begrense antall kombinasjoner dataklyngen måtte prøve.

"[De] ønsker ikke bare å løse det, men å løse det på en imponerende måte," sa Alexander Soifer ved University of Colorado, Colorado Springs.

Heule og Subercaseaux erkjente at mange kombinasjoner i hovedsak er de samme. Hvis du prøver å fylle en rombeformet brikke med åtte forskjellige tall, spiller det ingen rolle om det første tallet du plasserer er ett opp og ett til høyre for midtruten, eller ett ned og ett til venstre for torget i midten. De to plasseringene er symmetriske med hverandre og begrenser ditt neste trekk på nøyaktig samme måte, så det er ingen grunn til å sjekke dem begge.

Heule og Subercaseaux la til regler som gjorde at datamaskinen kunne behandle symmetriske kombinasjoner som likeverdige, noe som reduserte den totale søketiden med en faktor på åtte. De brukte også en teknikk Heule hadde utviklet i tidligere arbeid kalt cube and conquer, som tillot dem å teste flere kombinasjoner parallelt med hverandre. Hvis du vet at en gitt celle må inneholde enten 3, 5 eller 7, kan du dele problemet og teste hver av de tre mulighetene samtidig på forskjellige sett med datamaskiner.

I januar 2022 tillot disse forbedringene Heule og Subercaseaux å utelukke 13 som svaret på pakkefargeproblemet i et eksperiment som krevde mindre enn to dagers datatid. Dette ga dem to mulige svar: 14 eller 15.

Et stort pluss

For å utelukke 14 - og løse problemet - måtte Heule og Subercaseaux finne flere måter å øke hastigheten på datasøket på.

I utgangspunktet hadde de skrevet en boolsk formel som tildelte variabler til hver enkelt celle i rutenettet. Men i september 2022 innså de at de ikke trengte å fortsette på celle-for-celle basis. I stedet oppdaget de at det var mer effektivt å vurdere små områder som består av fem celler i form av et plusstegn.

De skrev om sin boolske formel slik at flere variabler representerte spørsmål som: Er det en 7-er et sted innenfor dette plussformede området? Datamaskinen trengte ikke å identifisere nøyaktig hvor i regionen de 7 kunne være. Det trengte bare å finne ut om det var der inne eller ikke - et spørsmål som krever betydelig færre beregningsressurser å svare på.

"Å ha variabler som bare snakker om plusser i stedet for spesifikke steder viste seg å være mye bedre enn å snakke om dem i spesifikke celler," sa Heule.

Godt hjulpet av effektiviteten til plusssøket utelukket Heule og Subercaseaux 14 i et dataeksperiment i november 2022 som endte opp med å ta kortere tid å kjøre enn det de brukte for å utelukke 13. De brukte de neste fire månedene på å bekrefte at datamaskinens konklusjon var riktig - nesten like mye tid som de hadde brukt på å gjøre det mulig for datamaskinen å komme til den konklusjonen i utgangspunktet.

"Det var gledelig å tenke på at det vi hadde skapt som et slags sidespørsmål i en tilfeldig journal hadde fått grupper av mennesker til å bruke, som det viste seg, måneder av tiden sin på å finne ut hvordan de skulle løse det," Goddard sa.

For Subercaseaux var det den første virkelige triumfen i hans forskerkarriere. Og selv om det kanskje ikke var den typen oppdagelse han idealiserte da han først vurderte å jobbe med matematikk, fant han ut at det til slutt hadde sine egne intellektuelle belønninger.

"Det er ikke å forstå skjemaet der du gir meg en tavle og jeg kan vise deg hvorfor det er 15," sa han. "Men vi har fått forståelse for hvordan begrensningene til problemet fungerer, hvor mye bedre det er å ha en 6 her eller en 7 der. Vi har fått mye intuitiv forståelse.»