Svaret på livet, universum och allting
En grupp ledd av Andrew Sutherland från MIT och Andrew Booker från Bristol University har löst den sista biten i ett berömt 65 år gammalt matematiskt pussel med ett svar på det mest svårfångade talet av alla: 42.
Talet 42 är särskilt viktigt för fans av science fiction-författaren Douglas Adams’ ”Liftarens guide till galaxen”, eftersom det är det tal som en superdator ger som svar på ”den ultimata frågan om livet, universum och allting”.
Booker ville också veta svaret på 42. Det vill säga, finns det tre kuber vars summa är 42?
Detta pussel om summan av tre kuber, som först lades 1954 vid universitetet i Cambridge och som är känt som den diophantinska ekvationen x3+y3+z3=k, utmanade matematikerna att hitta lösningar för talen 1-100. Med mindre tal är denna typ av ekvation lättare att lösa: till exempel kan 29 skrivas som 33 + 13 + 13, medan 32 är olösligt. Alla ekvationer löstes så småningom, eller visade sig vara olösliga, med hjälp av olika tekniker och superdatorer, med undantag för två tal:
Booker utarbetade en genial algoritm och tillbringade veckor på sitt universitets superdator när han nyligen kom fram till en lösning för 33. Men när han vände sig till att lösa 42 upptäckte Booker att den dator som krävdes var en storleksordning högre och att den kanske låg utanför hans superdatorns kapacitet. Booker säger att han fick många erbjudanden om hjälp för att hitta svaret, men i stället vände han sig till sin vän Andrew ”Drew” Sutherland, en huvudforskare vid avdelningen för matematik. ”Han är världens expert på den här typen av saker”, säger Booker.
Sutherland, vars specialitet omfattar massivt parallella beräkningar, slog 2017 rekordet för det största Compute Engine-klustret, med 580 000 kärnor på Preemptible Virtual Machines, det största kända klustret för högpresterande datorer som körs i det offentliga molnet.
Likt andra beräkningstekniska talteoretiker som arbetar med aritmetisk geometri kände han till problemet med ”summan av tre kuber”. Och de två hade arbetat tillsammans tidigare och hjälpt till att bygga upp L-functions and Modular Forms Database (LMFDB), en online-atlas över matematiska objekt med anknytning till det som är känt som Langlands-programmet. ”Jag blev jätteglad när Andy bad mig delta i det här projektet”, säger Sutherland.
Booker och Sutherland diskuterade den algoritmiska strategi som skulle användas i sökandet efter en lösning på 42. Precis som Booker upptäckte med sin lösning på 33 visste de att de inte behövde ta till alla möjligheter för x, y och z.
”Det finns en enda heltalsparameter, d, som bestämmer en relativt liten uppsättning möjligheter för x, y och z så att det absoluta värdet av z ligger under en vald sökgräns B”, säger Sutherland. ”Man räknar sedan upp värden för d och kontrollerar var och en av de möjliga x, y, z som är associerade med d. I försöket att knäcka 33 var sökgränsen B 1016, men denna B visade sig vara för liten för att knäcka 42. Vi använde i stället B = 1017 (1017 är 100 miljoner miljarder).”
I annat fall skulle den största skillnaden mellan sökningen efter 33 och sökningen efter 42 vara storleken på sökningen och den datorplattform som används. Tack vare ett generöst erbjudande från brittiska Charity Engine kunde Booker och Sutherland utnyttja beräkningskraften från över 400 000 frivilliga personers hemdatorer runt om i världen, som var och en tilldelades en rad olika värden för d. Beräkningen på varje dator körs i bakgrunden så att ägaren fortfarande kan använda sin dator för andra uppgifter.
Sutherland är också ett fan av Douglas Adams, så projektet var oemotståndligt.
Metoden för att använda Charity Engine liknar en del av handlingen kring siffran 42 i romanen ”Hitchhiker”: Efter att Deep Thought’s svar 42 visar sig vara otillfredsställande för vetenskapsmännen, som inte vet vilken fråga den är tänkt att besvara, bestämmer sig superdatorn för att beräkna den ultimata frågan genom att bygga en superdator som drivs av jorden … med andra ord genom att använda en världsomspännande massivt parallell beräkningsplattform.
”Detta är ytterligare en anledning till att jag verkligen gillade att köra den här beräkningen på Charity Engine – vi använde faktiskt en dator i planetarisk skala för att lösa en långvarig öppen fråga vars svar är 42.”
De körde ett antal beräkningar med lägre kapacitet för att testa både sin kod och nätverket Charity Engine. De använde sedan ett antal optimeringar och anpassningar för att göra koden bättre lämpad för en massivt distribuerad beräkning, jämfört med en beräkning som körs på en enda superdator, säger Sutherland.
Varför kunde inte Bristols superdator lösa det här problemet?
”Ja, vilken dator som helst *kan* lösa problemet, förutsatt att du är villig att vänta tillräckligt länge, men med ungefär en halv miljon datorer som arbetade med problemet parallellt (var och en med flera kärnor) kunde vi slutföra beräkningen mycket snabbare än vad vi hade kunnat göra med Bristol-maskinen (eller någon av maskinerna här på MIT)”, säger Sutherland.
Att använda nätverket Charity Engine är också mer energieffektivt. ”För det mesta använder vi beräkningsresurser som annars skulle gå till spillo”, säger Sutherland. ”När du sitter vid din dator och läser ett e-postmeddelande eller arbetar med ett kalkylblad använder du bara en liten del av den tillgängliga CPU-resursen, och Charity Engine-applikationen, som är baserad på Berkeley Open Infrastructure for Network Computing (BOINC), drar nytta av detta. Därför är koldioxidavtrycket från denna beräkning – relaterat till den elektricitet som våra beräkningar fick datorerna i nätverket att använda utöver vad de skulle ha använt i vilket fall som helst – lägre än vad det skulle ha varit om vi hade använt en superdator.”
Sutherland och Booker körde beräkningarna under flera månader, men den sista framgångsrika körningen genomfördes på bara några veckor. När mejlet från Charity Engine kom, gav det den första lösningen på x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
”När jag hörde nyheten var det definitivt ett ögonblick av knytnävepumpning”, säger Sutherland. ”När det gäller dessa storskaliga beräkningar lägger man mycket tid och energi på att optimera genomförandet, justera parametrarna och sedan testa och ompröva koden under veckor och månader, utan att egentligen veta om alla ansträngningar kommer att ge resultat, så det är oerhört tillfredsställande när det gör det.”
Booker och Sutherland säger att det återstår 10 tal till, från 101-1000, att lösa, och att nästa tal är 114.
Men båda är mer intresserade av en enklare men beräkningsmässigt mer utmanande gåta: om det finns fler svar på summan av tre kuber för 3.
”Det finns fyra mycket enkla lösningar som var kända för matematikern Louis J. Mordell, som 1953 skrev det berömda följande: ”Jag vet ingenting om helhetslösningarna av x3 + y3 + z3 = 3 utöver existensen av de fyra tripplarna (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4), och det måste vara mycket svårt att ta reda på något om alla andra lösningar”. Detta citat motiverade en stor del av intresset för problemet med summan av tre kuber, och fallet k=3 i synnerhet. Även om man antar att det borde finnas oändligt många lösningar, känner vi trots mer än 65 års sökande endast till de enkla lösningar som Mordell redan kände till. Det skulle vara mycket spännande att hitta ytterligare en lösning för k=3.”