Efter at have knækket summen af ​​terninger puslespil for 42, forskere opdager en ny løsning til 3

Hvad gør du efter at have løst svaret på livet, universet, og det hele? Hvis du er matematikere Drew Sutherland og Andy Booker, du går efter det sværere problem.

I 2019, Booker, ved University of Bristol, og Sutherland, ledende forsker ved MIT, var de første til at finde svaret på 42. Tallet har popkulturel betydning som det fiktive svar på "det ultimative spørgsmål om livet, universet, og det hele, " som Douglas Adams berømt skrev i sin roman "The Hitchhiker's Guide to the Galaxy." Spørgsmålet, der afføder 42, i hvert fald i romanen, er frustrerende, sjovt ukendt.

I matematik, helt tilfældigt, der findes en polynomialligning, hvor svaret, 42, havde på samme måde undgået matematikere i årtier. Ligningen x ³ +y ³ +z ³ =k er kendt som summen af ​​terninger problem. Selvom det tilsyneladende er ligetil, ligningen bliver eksponentielt svær at løse, når den er indrammet som en "diofantisk ligning" - et problem, der bestemmer, at for enhver værdi af k, værdierne for x, y, og z skal hver være hele tal.

Når summen af ​​kubernes ligning er indrammet på denne måde, for visse værdier af k, heltalsløsningerne for x, y, og z kan vokse til enorme tal. Talrummet, som matematikere skal søge på tværs af for disse tal, er endnu større, kræver indviklede og massive beregninger.

I årenes løb, matematikere havde formået at løse ligningen på forskellige måder, enten at finde en løsning eller at bestemme, at en løsning ikke må eksistere, for hver værdi af k mellem 1 og 100 – undtagen 42.

I september 2019, Booker og Sutherland, at udnytte den kombinerede kraft fra en halv million hjemmecomputere rundt om i verden, for første gang fundet en løsning på 42. Det bredt rapporterede gennembrud ansporede holdet til at tackle en endnu sværere, og på nogle måder mere universelt problem:at finde den næste løsning for 3.

Booker og Sutherland har nu offentliggjort løsningerne til 42 og 3, sammen med flere andre tal større end 100, denne uge i Proceedings of the National Academy of Sciences .

Tager handsken op

De to første løsninger til ligningen x ³ +y ³ +z ³ =3 kan være indlysende for enhver algebrastuderende på gymnasiet, hvor x, y, og z kan være enten 1, 1, og 1, eller 4, 4, og -5. At finde en tredje løsning, imidlertid, har slået eksperter på talteoretikere i stykker i årtier, og i 1953 fik puslespillet den banebrydende matematiker Louis Mordell til at stille spørgsmålet:Er det overhovedet muligt at vide, om der findes andre løsninger for 3?

"Dette var ligesom Mordell, der kastede handsken ned, " siger Sutherland. "Interessen for at løse dette spørgsmål er ikke så meget for den specifikke løsning, men for bedre at forstå, hvor svære disse ligninger er at løse. Det er et benchmark, som vi kan måle os ud fra."

Da årtier gik uden nye løsninger for 3, mange begyndte at tro, at der ikke var nogen at finde. Men kort efter at have fundet svaret på 42, Booker og Sutherlands metode, på overraskende kort tid, viste den næste løsning for 3:

569936821221962380720 ³ + (-569936821113563493509) ³ + (-472715493453327032) ³ =3

Opdagelsen var et direkte svar på Mordells spørgsmål:Ja, det er muligt at finde den næste løsning på 3, og hvad mere er, her er den løsning. Og måske mere universelt, løsningen, involverer gigantiske, 21-cifrede tal, som ikke var muligt at frasortere indtil nu, antyder, at der er flere løsninger derude, for 3, og andre værdier af k.

"Der havde været nogen alvorlig tvivl i de matematiske og beregningsmæssige fællesskaber, fordi [Mordells spørgsmål] er meget svært at teste, " siger Sutherland. "Tallene bliver så store så hurtigt. Du vil aldrig finde mere end de første par løsninger. Men hvad jeg kan sige er, efter at have fundet denne ene løsning, Jeg er overbevist om, at der er uendeligt mange flere derude."

En løsnings twist

For at finde løsninger til både 42 og 3, holdet startede med en eksisterende algoritme, eller en drejning af ligningen af ​​summen af ​​terninger til en form, de mente ville være mere overskuelig at løse:

k - z ³ =x ³ + y ³ =(x + y)(x ² - xy + y ² )

Denne tilgang blev først foreslået af matematikeren Roger Heath-Brown, der formodede, at der skulle være uendeligt mange løsninger for hver passende k. Holdet modificerede yderligere algoritmen ved at repræsentere x+y som en enkelt parameter, d. De reducerede derefter ligningen ved at dividere begge sider med d og kun beholde resten - en operation i matematik kaldet "modulo d" - hvilket efterlader en forenklet repræsentation af problemet.

"Du kan nu tænke på k som en terningrod af z, modulo d, " forklarer Sutherland. "Så forestil dig at arbejde i et aritmetisk system, hvor du kun bekymrer dig om resten af ​​modulo d, og vi forsøger at beregne en terningrod af k."

Med denne slankere version af ligningen, forskerne behøvede kun at lede efter værdier af d og z, der ville garantere at finde de ultimative løsninger på x, y, og z, for k=3. Men stadig, det rum af tal, som de skulle søge igennem, ville være uendeligt stort.

Så, forskerne optimerede algoritmen ved at bruge matematiske "siningsteknikker" til dramatisk at skære ned på pladsen af ​​mulige løsninger til d.

"Dette involverer en ret avanceret talteori, bruge strukturen af ​​det, vi ved om talfelter, for at undgå at kigge på steder, vi ikke behøver at kigge, " siger Sutherland.

En global opgave

Holdet udviklede også måder til effektivt at opdele algoritmens søgning i hundredtusindvis af parallelle behandlingsstrømme. Hvis algoritmen kun blev kørt på én computer, det ville have taget flere hundrede år at finde en løsning på k=3. Ved at opdele jobbet i millioner af mindre opgaver, hver uafhængigt køre på en separat computer, holdet kunne fremskynde deres søgning yderligere.

I september 2019, forskerne satte deres plan i spil gennem Charity Engine, et projekt, der kan downloades som en gratis app af enhver personlig computer, og som er designet til at udnytte enhver ekstra hjemmecomputerkraft til i fællesskab at løse svære matematiske problemer. På det tidspunkt, Charity Engines net omfattede over 400, 000 computere rundt om i verden, og Booker og Sutherland var i stand til at køre deres algoritme på netværket som en test af Charity Engines nye softwareplatform.

"For hver computer i netværket, de får at vide, 'din opgave er at lede efter d'er, hvis primære faktor falder inden for dette område, underlagt nogle andre betingelser, "" siger Sutherland. "Og vi skulle finde ud af, hvordan vi skulle dele jobbet op i omkring 4 millioner opgaver, der hver især ville tage omkring tre timer for en computer at udføre."

Meget hurtigt, det globale gitter returnerede den allerførste løsning til k=42, og kun to uger senere, forskerne bekræftede, at de havde fundet den tredje løsning for k=3 - en milepæl, som de markerede, delvis, ved at udskrive ligningen på t-shirts.

Det faktum, at der findes en tredje løsning til k=3, tyder på, at Heath-Browns oprindelige formodning var rigtig, og at der er uendeligt flere løsninger ud over denne nyeste. Heath-Brown forudsiger også, at rummet mellem løsninger vil vokse eksponentielt, sammen med deres søgninger. For eksempel, snarere end den tredje løsnings 21-cifrede værdier, den fjerde løsning for x, y, og z vil sandsynligvis involvere tal med ufattelige 28 cifre.

"Mængden af ​​arbejde, du skal udføre for hver ny løsning, vokser med en faktor på mere end 10 mio. så den næste løsning for 3 skal bruge 10 millioner gange 400, 000 computere at finde, og der er ingen garanti for, at det er nok, " siger Sutherland. "Jeg ved ikke, om vi nogensinde vil kende den fjerde løsning. Men jeg tror på, at det er derude."