Matematiske tricks til at tæmme mellemdistancen | Quanta Magasinet

Hidtil i år, Quanta har skildret tre store fremskridt i Ramsey-teorien, studiet af, hvordan man undgår at skabe matematiske mønstre. Det første resultat sæt en ny grænse for, hvor stort et sæt heltal kan være uden at indeholde tre lige store tal, som {2, 4, 6} eller {21, 31, 41}. Det anden , tredje på samme måde sætter nye grænser for størrelsen af ​​netværk uden klynger af punkter, der enten alle er forbundet eller alle er isoleret fra hinanden.

Beviserne adresserer, hvad der sker, når de involverede tal vokser sig uendeligt store. Paradoksalt nok kan dette nogle gange være nemmere end at håndtere irriterende mængder i den virkelige verden.

Overvej for eksempel to spørgsmål om en brøk med en rigtig stor nævner. Du kan spørge, hvad decimaludvidelsen af ​​f.eks. 1/42503312127361 er. Eller du kan spørge, om dette tal vil komme tættere på nul, efterhånden som nævneren vokser. Det første spørgsmål er et specifikt spørgsmål om en mængde i den virkelige verden, og det er sværere at beregne end det andet, som spørger, hvordan mængden 1/n vil "asymptotisk" ændre sig som n vokser. (Det kommer tættere og tættere på 0.)

"Dette er et problem, der plager hele Ramsey-teorien," sagde William Gasarch, en datalog ved University of Maryland. "Ramsey-teorien er kendt for at have asymptotisk meget flotte resultater." Men at analysere tal, der er mindre end uendeligt, kræver en helt anden matematisk værktøjskasse.

Gasarch har studeret spørgsmål i Ramsey-teorien, der involverer endelige tal, der er for store til, at problemet kan løses med rå magt. I et projekt påtog han sig den endelige version af det første af dette års gennembrud - et februaravis af Zander Kelley, en kandidatstuderende ved University of Illinois, Urbana-Champaign, og Raghu Meka fra University of California, Los Angeles. Kelley og Meka fandt en ny øvre grænse for, hvor mange heltal mellem 1 og N du kan sætte ind i et sæt, mens du undgår tre-term progressioner eller mønstre af ligeligt fordelte tal.

Selvom Kelley og Mekas resultat gælder, selvom N er relativt lille, giver det ikke en særlig brugbar grænse i så fald. For meget små værdier af N, er du bedre til at holde dig til meget enkle metoder. Hvis N er f.eks. 5, se bare på alle de mulige talsæt mellem 1 og N, og vælg den største progressionsfrie: {1, 2, 4, 5}.

Men antallet af forskellige mulige svar vokser meget hurtigt og gør det for svært at anvende en så simpel strategi. Der er mere end 1 million sæt bestående af tal mellem 1 og 20. Der er over 10⁶⁰ ved at bruge tal mellem 1 og 200. At finde det bedste progressionsfrie sæt til disse tilfælde kræver en stor portion computerkraft, selv med effektivitetsforbedrende strategier. "Du skal være i stand til at presse en masse præstation ud af tingene," sagde James Glenn, en datalog ved Yale University. I 2008, Gasarch, Glenn og Clyde Kruskal fra University of Maryland skrev et program at finde de største progressionsfrie sæt op til en N af 187. (Tidligere arbejde havde fået svarene op til 150, såvel som for 157.) På trods af en liste af tricks tog deres program måneder at afslutte, sagde Glenn.

For at mindske deres beregningsbelastning brugte holdet enkle test, der forhindrede deres program i at forfølge blindgydesøgninger og opdelte deres sæt i mindre dele, som de analyserede separat.

Gasarch, Glenn og Kruskal prøvede også flere andre strategier. En lovende idé lænede sig op af tilfældighed. En simpel måde at komme frem til et progressionsfrit sæt er at sætte 1 i dit sæt, og derefter tilføje altid det næste tal, der ikke skaber en aritmetisk progression. Følg denne procedure, indtil du rammer tallet 10, og du får sættet {1, 2, 4, 5, 10}. Men det viser sig, at dette ikke er den bedste strategi generelt. "Hvad hvis vi ikke starter kl 1?" sagde Gasarch. "Hvis du starter et tilfældigt sted, klarer du det faktisk bedre." Forskere aner ikke, hvorfor tilfældighed er så nyttig, tilføjede han.

At beregne de endelige versioner af de to andre nye Ramsey-teoriresultater er endnu mere irriterende end at bestemme størrelsen af ​​progressionsfrie sæt. Disse resultater vedrører matematiske netværk (kaldet grafer), der består af knudepunkter forbundet med linjer kaldet kanter. Ramsey-nummeret r(s, t) er det mindste antal noder en graf skal have, før det bliver umuligt at undgå at inkludere enten en gruppe af s tilsluttede noder eller t afbrudte. Ramsey-tallet er sådan en hovedpine at beregne, at endda r(5, 5) er ukendt - det er et sted mellem 43 og 48.

I 1981, blev Brendan McKay, nu en datalog ved Australian National University, skrev et softwareprogram kaldet nauty, som havde til formål at gøre beregningen af ​​Ramsey-tal enklere. Nauty sikrer, at forskere ikke spilder tid på at kontrollere to grafer, der blot er vendte eller roterede versioner af hinanden. "Hvis nogen er i området og ikke bruger nauty, er spillet slut. Du skal bruge det,” sagde Stanisław Radziszowski, en matematiker ved Rochester Institute of Technology. Alligevel er mængden af ​​​​beregning, der er involveret, næsten uforståelig. I 2013, Radziszowski og Jan Goedgebeur beviste det r(3, 10) er højst 42. "Det tog, tror jeg, næsten 50 CPU-år," sagde Goedgebeur, en datalog ved KU Leuven Universitet i Belgien.

Hvis du ikke kan beregne et nøjagtigt Ramsey-tal, kan du prøve at indsnævre dets værdi med eksempler. Hvis du fandt en 45-node graf uden fem noder, der alle var forbundet og uden fem noder, der alle var afbrudt, ville det bevise, at r(5, 5) er større end 45. Matematikere, der studerede Ramsey-tal, plejede at tro, at det ville være enkelt at finde disse eksempler, kaldet Ramsey-grafer, sagde Radziszowski. Men sådan var det ikke. "Der var en forventning om, at flotte, seje matematiske konstruktioner vil give de bedst mulige konstruktioner, og vi har bare brug for flere folk til at arbejde på det," sagde han. "Min følelse er mere og mere, at det er kaotisk."

Tilfældighed er både en hindring for forståelse og et nyttigt værktøj. Geoffrey Exoo, en datalog ved Indiana State University, har brugt år på at forfine tilfældige metoder til at generere Ramsey-grafer. I et 2015 papir Da de annoncerede snesevis af nye, rekordslående Ramsey-grafer, genererede Exoo og Milos Tatarevic tilfældige grafer og justerede dem derefter gradvist ved at slette eller tilføje kanter, der reducerede antallet af uønskede klynger, indtil de fandt en Ramsey-graf. Exoos teknikker er dog lige så meget en kunst som noget andet, sagde Radziszowski. De kræver nogle gange, at han kombinerer flere metoder eller bruger dømmekraft om, hvilken slags grafer man skal starte med. "Mange, mange mennesker prøver det, og de kan ikke gøre det," sagde Radziszowski.

De teknikker, der er udviklet til at generere Ramsey-grafer, kunne være mere generelt nyttige en dag, sagde Goedgebeur, der har arbejdet på producere andre slags grafer, såsom grafer, der repræsenterer kemiske forbindelser. "Det er ikke usandsynligt, at disse teknikker også kan overføres og justeres for at hjælpe med at generere andre klasser af grafer mere effektivt (og omvendt)," skrev han i en e-mail.

For Radziszowski er grunden til at studere de små Ramsey-tal dog meget enklere. "Fordi det er åbent, fordi ingen ved, hvad svaret er," sagde han. ”De trivielle sager laver vi i hånden; lidt større skal du bruge en computer, og lidt større er selv computeren ikke god nok. Og så dukker udfordringen op.”