Wiskundige trucs voor het temmen van de halve fond | Quanta-tijdschrift

Tot nu toe dit jaar, Quanta heeft drie belangrijke vorderingen in de Ramsey-theorie opgetekend, de studie van hoe te voorkomen dat er wiskundige patronen ontstaan. De eerste resultaat stel een nieuwe limiet in voor hoe groot een reeks gehele getallen kan zijn zonder drie gelijkmatig verdeelde getallen te bevatten, zoals {2, 4, 6} of {21, 31, 41}. De tweede en derde legde op dezelfde manier nieuwe grenzen aan de grootte van netwerken zonder clusters van punten die allemaal met elkaar verbonden zijn of allemaal geïsoleerd van elkaar.

De bewijzen behandelen wat er gebeurt als de betrokken getallen oneindig groot worden. Paradoxaal genoeg kan dit soms gemakkelijker zijn dan omgaan met vervelende real-world hoeveelheden.

Neem bijvoorbeeld twee vragen over een breuk met een hele grote noemer. Je zou je kunnen afvragen wat de decimale uitbreiding is van bijvoorbeeld 1/42503312127361. Of je kunt je afvragen of dit getal dichter bij nul komt naarmate de noemer groter wordt. De eerste vraag is een specifieke vraag over een echte hoeveelheid, en het is moeilijker te berekenen dan de tweede, die vraagt ​​hoe de hoeveelheid 1/n zal "asymptotisch" veranderen als n groeit. (Het komt steeds dichter bij 0.)

"Dit is een probleem dat de hele Ramsey-theorie teistert," zei Willem Gaarch, een computerwetenschapper aan de Universiteit van Maryland. "Ramsey-theorie staat erom bekend asymptotisch zeer mooie resultaten te hebben." Maar het analyseren van getallen die kleiner zijn dan oneindig, vereist een geheel andere wiskundige toolbox.

Gasarch heeft vragen in de Ramsey-theorie bestudeerd met betrekking tot eindige getallen die te groot zijn om het probleem met brute kracht op te lossen. In één project nam hij de eindige versie van de eerste van de doorbraken van dit jaar op zich: een paper uit februari van Zander Kelly, een afgestudeerde student aan de Universiteit van Illinois, Urbana-Champaign, en Raghu Meka van de Universiteit van Californië, Los Angeles. Kelley en Meka hebben een nieuwe bovengrens gevonden voor het aantal gehele getallen tussen 1 en N je kunt ze in een set stoppen terwijl je progressies van drie termen of patronen van gelijkmatig verdeelde getallen vermijdt.

Hoewel het resultaat van Kelley en Meka zelfs van toepassing is als N relatief klein is, geeft het in dat geval geen bijzonder bruikbare grens. Voor zeer kleine waarden van N, kun je beter vasthouden aan zeer eenvoudige methoden. Als N is bijvoorbeeld 5, kijk maar eens naar alle mogelijke reeksen getallen tussen 1 en N, en kies de grootste progressievrije: {1, 2, 4, 5}.

Maar het aantal verschillende mogelijke antwoorden groeit zeer snel en maakt het te moeilijk om zo'n eenvoudige strategie toe te passen. Er zijn meer dan 1 miljoen sets bestaande uit nummers tussen 1 en 20. Er zijn er meer dan 10⁶⁰ met behulp van getallen tussen 1 en 200. Het vinden van de beste progressievrije set voor deze gevallen vergt een flinke dosis rekenkracht, zelfs met efficiëntieverbeterende strategieën. "Je moet veel prestaties uit dingen kunnen persen", zei hij James Glenn, een computerwetenschapper aan de Yale University. In 2008, Gasarch, Glenn en Clyde Kruskal van de Universiteit van Maryland een programma geschreven om de grootste progressievrije sets te vinden tot een N van 187. (Eerder werk had de antwoorden tot 150 opgeleverd, evenals voor 157.) Ondanks een reeks trucs duurde het maanden voordat hun programma was voltooid, zei Glenn.

Om hun rekenkracht te verminderen, gebruikte het team eenvoudige tests die verhinderden dat hun programma doodlopende zoekopdrachten uitvoerde en splitste hun sets op in kleinere delen die ze afzonderlijk analyseerden.

Gasarch, Glenn en Kruskal probeerden ook verschillende andere strategieën. Een veelbelovend idee leunde op willekeur. Een eenvoudige manier om een ​​progressievrije set te bedenken, is door 1 in je set te zetten en dan altijd het volgende getal toe te voegen dat geen rekenkundige progressie creëert. Volg deze procedure tot je het nummer 10 raakt, en je krijgt de set {1, 2, 4, 5, 10}. Maar het blijkt dat dit in het algemeen niet de beste strategie is. "Wat als we niet bij 1 beginnen?" zei Gasarch. "Als je op een willekeurige plek begint, doe je het eigenlijk beter." Onderzoekers hebben geen idee waarom willekeur zo nuttig is, voegde hij eraan toe.

Het berekenen van de eindige versies van de twee andere nieuwe resultaten van de Ramsey-theorie is nog erger dan het bepalen van de grootte van progressievrije sets. Die resultaten hebben betrekking op wiskundige netwerken (grafieken genoemd) die zijn samengesteld uit knooppunten die zijn verbonden door lijnen die randen worden genoemd. Het Ramsey-nummer r(s, t) is het kleinste aantal knooppunten dat een graaf moet hebben voordat het onmogelijk wordt om een ​​groep van op te nemen s verbonden knooppunten of t losgekoppelde. Het Ramsey-getal is zo'n hoofdpijn om dat zelfs te berekenen r(5, 5) is onbekend - het ligt ergens tussen 43 en 48.

In 1981, Brendan McKay, nu een computerwetenschapper aan de Australian National University, schreef een softwareprogramma genaamd nauty, dat bedoeld was om het berekenen van Ramsey-getallen eenvoudiger te maken. Nauty zorgt ervoor dat onderzoekers geen tijd verspillen aan het controleren van twee grafieken die slechts gespiegelde of gedraaide versies van elkaar zijn. 'Als iemand in de buurt is en geen nauty gebruikt, is het spel voorbij. Je moet het gebruiken, 'zei Stanislaus Radziszowski, een wiskundige aan het Rochester Institute of Technology. Toch is de hoeveelheid rekenwerk die ermee gemoeid is bijna onbegrijpelijk. In 2013, Radziszowski en Jan Goedgebeur bewees dat r(3, 10) is maximaal 42. "Het kostte, denk ik, bijna 50 CPU-jaren", zegt Goedgebeur, een computerwetenschapper aan de KU Leuven Universiteit in België.

Als u geen exact Ramsey-getal kunt berekenen, kunt u proberen de waarde ervan te beperken met voorbeelden. Als je een grafiek met 45 knooppunten zou vinden zonder vijf knooppunten die allemaal verbonden waren en zonder vijf knooppunten die allemaal losgekoppeld waren, zou dat bewijzen dat r(5, 5) is groter dan 45. Wiskundigen die Ramsey-getallen bestudeerden, dachten altijd dat het vinden van die voorbeelden, Ramsey-grafieken genoemd, eenvoudig zou zijn, zei Radziszowski. Maar zo was het niet. "Er was de verwachting dat mooie, coole wiskundige constructies de best mogelijke constructies zouden opleveren, en we hebben gewoon meer mensen nodig om eraan te werken," zei hij. "Ik heb steeds meer het gevoel dat het chaotisch is."

Willekeur is zowel een obstakel voor begrip als een nuttig hulpmiddel. Geoffrey Exoo, een computerwetenschapper aan de Indiana State University, heeft jarenlang gewerkt aan het verfijnen van willekeurige methoden om Ramsey-grafieken te genereren. In een 2015-papier Exoo en Milos Tatarevic kondigden tientallen nieuwe, recordbrekende Ramsey-grafieken aan en genereerden willekeurige grafieken en pasten ze vervolgens geleidelijk aan door randen te verwijderen of toe te voegen die het aantal ongewenste clusters verminderden totdat ze een Ramsey-grafiek vonden. De technieken van Exoo zijn echter net zo goed een kunst als wat dan ook, zei Radziszowski. Ze vereisen soms dat hij meerdere methoden combineert, of dat hij oordeelt met wat voor soort grafieken hij moet beginnen. "Veel, veel mensen proberen het, maar ze kunnen het niet", zei Radziszowski.

De technieken die zijn ontwikkeld om Ramsey-grafieken te genereren, zouden op een dag breder bruikbaar kunnen zijn, zei Goedgebeur, die dat wel heeft gedaan werkte aan het produceren van andere soorten grafieken, zoals grafieken die chemische verbindingen vertegenwoordigen. "Het is niet onwaarschijnlijk dat deze technieken ook kunnen worden overgedragen en aangepast om andere soorten grafieken efficiënter te genereren (en vice versa)", schreef hij in een e-mail.

Voor Radziszowski is de reden voor het bestuderen van de kleine Ramsey-getallen echter veel eenvoudiger. 'Omdat het open is, omdat niemand weet wat het antwoord is', zei hij. “De triviale gevallen doen we met de hand; een beetje groter, je hebt een computer nodig, en een beetje groter, zelfs de computer is niet goed genoeg. En zo ontstaat de uitdaging.”