Matematiska knep för att tämja medeldistansen | Quanta Magazine

Så här långt i år, Quanta har krönikat tre stora framsteg inom Ramsey-teorin, studien av hur man undviker att skapa matematiska mönster. De första resultatet sätt ett nytt tak för hur stor en uppsättning heltal kan vara utan att innehålla tre jämnt fördelade tal, som {2, 4, 6} eller {21, 31, 41}. De 2:a och tredje sätter på samma sätt nya gränser för storleken på nätverk utan kluster av punkter som antingen är alla anslutna eller alla isolerade från varandra.

Bevisen tar upp vad som händer när antalet inblandade växer oändligt stort. Paradoxalt nog kan detta ibland vara lättare än att hantera irriterande verkliga kvantiteter.

Tänk till exempel på två frågor om ett bråk med en riktigt stor nämnare. Du kanske frågar vad decimalexpansionen av t.ex. 1/42503312127361 är. Eller så kan du fråga om det här talet kommer närmare noll när nämnaren växer. Den första frågan är en specifik fråga om en verklig kvantitet, och den är svårare att beräkna än den andra, som frågar hur kvantiteten 1/n kommer "asymptotiskt" att förändras som n växer. (Det kommer närmare och närmare 0.)

"Detta är ett problem som plågar hela Ramsey-teorin," sa William Gasarch, en datavetare vid University of Maryland. "Ramsey-teorin är känd för att ha asymptotiskt mycket fina resultat." Men att analysera siffror som är mindre än oändligheten kräver en helt annan matematisk verktygslåda.

Gasarch har studerat frågor i Ramsey-teorin som involverar ändliga tal som är för stora för att problemet ska kunna lösas med brute force. I ett projekt tog han sig an den ändliga versionen av det första av årets genombrott - en februaritidning av Zander Kelley, en doktorand vid University of Illinois, Urbana-Champaign, och Raghu Meka vid University of California, Los Angeles. Kelley och Meka hittade en ny övre gräns för hur många heltal mellan 1 och N du kan lägga till en uppsättning samtidigt som du undviker tre-terms progressioner, eller mönster av jämnt fördelade nummer.

Fast Kelley och Mekas resultat gäller även om N är relativt liten, det ger inte en särskilt användbar gräns i så fall. För mycket små värden på N, det är bättre att du håller dig till mycket enkla metoder. Om N är, säg, 5, titta bara på alla möjliga uppsättningar av tal mellan 1 och N, och välj ut den största progressionsfria: {1, 2, 4, 5}.

Men antalet olika möjliga svar växer mycket snabbt och gör det för svårt att använda en så enkel strategi. Det finns mer än 1 miljon set som består av nummer mellan 1 och 20. Det finns över 10⁶⁰ använder siffror mellan 1 och 200. Att hitta den bästa progressionsfria uppsättningen för dessa fall kräver en rejäl dos datorkraft, även med effektivitetsförbättrande strategier. "Du måste kunna pressa mycket prestanda ur saker," sa James Glenn, en datavetare vid Yale University. 2008, Gasarch, Glenn och Clyde Kruskal från University of Maryland skrev ett program att hitta de största progressionsfria uppsättningarna till en N av 187. (Tidigare arbete hade fått svaren upp till 150, såväl som för 157.) Trots en lista med trick tog deras program månader att slutföra, sa Glenn.

För att minska sin beräkningsbelastning använde teamet enkla tester som förhindrade deras program från att söka efter återvändsgränd och delade upp sina set i mindre delar som de analyserade separat.

Gasarch, Glenn och Kruskal provade också flera andra strategier. En lovande idé lutade sig åt slumpmässighet. Ett enkelt sätt att komma på en progressionsfri uppsättning är att sätta 1 i din uppsättning och sedan alltid lägga till nästa nummer som inte skapar en aritmetisk progression. Följ denna procedur tills du träffar siffran 10 och du får setet {1, 2, 4, 5, 10}. Men det visar sig att detta inte är den bästa strategin i allmänhet. "Tänk om vi inte börjar vid 1?" sa Gasarch. "Om du börjar på ett slumpmässigt ställe gör du det faktiskt bättre." Forskare har ingen aning om varför slumpmässighet är så användbar, tillade han.

Att beräkna de ändliga versionerna av de två andra nya Ramsey-teoriresultaten är ännu mer irriterande än att bestämma storleken på progressionsfria uppsättningar. Dessa resultat gäller matematiska nätverk (kallade grafer) som består av noder sammankopplade med linjer som kallas kanter. Ramsey-numret r(s, t) är det minsta antalet noder en graf måste ha innan det blir omöjligt att undvika att inkludera antingen en grupp av s anslutna noder eller t frånkopplade sådana. Ramsey-numret är en sådan huvudvärk att räkna ut det ens r(5, 5) är okänd - det är någonstans mellan 43 och 48.

1981, Brendan McKay, nu en datavetare vid Australian National University, skrev ett program som heter nauty, som var avsett att göra det enklare att beräkna Ramsey-tal. Nauty ser till att forskare inte slösar tid på att kontrollera två grafer som bara är vända eller roterade versioner av varandra. "Om någon är i området och inte använder nauty, är spelet över. Du måste använda den”, sa Stanisław Radziszowski, en matematiker vid Rochester Institute of Technology. Ändå är mängden beräkningar som är involverade nästan obegriplig. 2013, Radziszowski och Jan Goedgebeur bevisade det r(3, 10) är högst 42. "Det tog, tror jag, nästan 50 CPU-år", säger Goedgebeur, datavetare vid KU Leuven University i Belgien.

Om du inte kan beräkna ett exakt Ramsey-tal kan du försöka begränsa dess värde med exempel. Om du hittade en graf med 45 noder utan fem noder som alla var anslutna och utan fem noder som alla var frånkopplade, skulle det bevisa att r(5, 5) är större än 45. Matematiker som studerade Ramsey-tal brukade tro att det skulle vara enkelt att hitta dessa exempel, kallade Ramsey-grafer, sa Radziszowski. Men så var det inte. "Det fanns den här förväntningen att snygga, coola matematiska konstruktioner kommer att ge bästa möjliga konstruktioner, och vi behöver bara fler människor att arbeta med det," sa han. "Min känsla är mer och mer att det är kaotiskt."

Slumpmässighet är både ett hinder för förståelse och ett användbart verktyg. Geoffrey Exoo, en datavetare vid Indiana State University, har ägnat år åt att förfina slumpmässiga metoder för att generera Ramsey-grafer. I ett 2015-papper Exoo och Milos Tatarevic tillkännagav dussintals nya, rekordslående Ramsey-grafer, genererade slumpmässiga grafer och justerade dem sedan gradvis genom att ta bort eller lägga till kanter som minskade antalet oönskade kluster tills de hittade en Ramsey-graf. Exoos tekniker är lika mycket en konst som något annat, sa Radziszowski. De kräver ibland att han kombinerar flera metoder, eller använder omdöme om vilken typ av grafer att börja med. "Många, många människor provar det, och de kan inte göra det," sa Radziszowski.

Teknikerna som utvecklats för att generera Ramsey-grafer skulle kunna vara mer allmänt användbara någon gång, sa Goedgebeur, som har jobbade på producerar andra typer av grafer, till exempel grafer som representerar kemiska föreningar. "Det är inte osannolikt att dessa tekniker också kan överföras och justeras för att hjälpa till att generera andra klasser av grafer mer effektivt (och vice versa)", skrev han i ett mejl.

För Radziszowski är dock anledningen till att studera de små Ramsey-talen mycket enklare. "För att det är öppet, för ingen vet vad svaret är," sa han. ”De triviala fallen gör vi för hand; lite större behöver du en dator och lite större är inte ens datorn tillräckligt bra. Och så uppstår utmaningen.”