Een close-upbeeld onthult het ‘smeltpunt’ van een oneindige grafiek | Quanta-tijdschrift

In 2008 stierf de wiskundige Oded Schramm bij een wandelongeval in de Cascade-bergen, zo'n 50 kilometer ten oosten van Seattle. Hoewel hij nog maar 46 jaar oud was, had hij geheel nieuwe gebieden van de wiskunde ontwikkeld.

‘Hij was een fantastische wiskundige’, zei hij Itai Benjamini, een wiskundige aan het Weizmann Institute of Science en Schramm's vriend en medewerker. “Extreem creatief, extreem elegant, extreem origineel.”

De vragen die hij stelde, verleggen nog steeds de grenzen van de waarschijnlijkheidstheorie en de statistische natuurkunde. Veel van deze vragen hebben betrekking op wiskundige structuren die een faseovergang hebben: een plotselinge macroscopische verandering, zoals ijs dat smelt tot water. Net zoals verschillende materialen verschillende smeltpunten hebben, variëren ook faseovergangen van wiskundige structuren.

Schramm vermoedde dat de faseovergang in een proces dat percolatie wordt genoemd, kan worden geschat door voor veel belangrijke wiskundige structuren alleen een close-up van het systeem te gebruiken – het lokale perspectief genoemd. Helemaal uitzoomen en naar het geheel kijken, zal de berekening niet significant veranderen. In de afgelopen vijftien jaar hebben wiskundigen kleine stukjes van het vermoeden weggenomen, maar tot nu toe zijn ze er niet in geslaagd het volledig op te lossen.

In een voordruk geplaatst in oktober, Tom Hutchcroft van het California Institute of Technology en zijn promovendus Filips Eas bewees het vermoeden van Schramm over de plaats. Hun bewijs is gebaseerd op belangrijke ideeën uit de waarschijnlijkheidstheorie en andere gebieden van de wiskunde, die ze op een slimme manier hebben gecombineerd.

“Het is een opmerkelijk document. Het is een opeenstapeling van lang werk”, zei Benjamini.

Oneindige clusters

Het woord ‘percolatie’ verwees oorspronkelijk naar de beweging van vloeistof door een poreus medium, zoals water dat door koffiedik stroomt of olie die door scheuren in een rots sijpelt.

In 1957 ontwikkelden de wiskundigen Simon Ralph Broadbent en John Michael Hammersley een wiskundig model van dit fysieke proces. In de decennia daarna is dit model op zichzelf een object van studie geworden. Wiskundigen bestuderen percolatie omdat het een belangrijk evenwicht oplevert: de opzet is eenvoudig, maar vertoont complexe en raadselachtige kenmerken.

“Het is een soort canoniek model voor wiskundigen,” zei Hutchcroft. “Je kunt dingen visueel bedenken. Dat maakt het heel fijn om mee te werken.”

Percolatie begint met een grafiek, een verzameling hoekpunten (punten) die met elkaar kunnen worden verbonden door randen (lijnen). Een van de eenvoudigste voorbeelden is een vierkant raster, met hoekpunten op een rij om de hoeken van vierkanten te vormen en randen die sommige ervan verbinden.

Kort voor zijn dood vermoedde Schramm dat de stelling van Grimmett en Marstrand gegeneraliseerd kon worden. Hij dacht dat de percolatiedrempel volledig wordt bepaald door het close-up- of ‘microscopische’ perspectief voor een grote klasse grafieken die bekend staan ​​als transitieve grafieken.

In 2009, Benjamini, Asaf Nachmias en Yuval Peres bewezen Schramm's lokaliteitsvermoeden, zoals het nu bekend staat, voor een specifiek type transitieve grafiek die op een boom lijkt. Schramm had echter gepostuleerd dat dit zou gelden voor alle transitieve grafieken (met uitzondering van eendimensionale grafieken).

In een transitieve grafiek zien alle hoekpunten er hetzelfde uit. Een tweedimensionaal raster is daar een voorbeeld van. Als je twee hoekpunten kiest, kun je altijd een symmetrie vinden die het ene hoekpunt naar het andere verplaatst.

Deze relatie geldt voor elke transitieve grafiek. Vanwege deze symmetrieën zullen ze er hetzelfde uitzien als je inzoomt en naar twee gelijke delen van een transitieve grafiek kijkt. Om deze reden geloofde Schramm dat het close-upperspectief voldoende was om wiskundigen in staat te stellen de percolatiedrempel voor alle transitieve grafieken te berekenen.

Transitieve grafieken kunnen vele vormen aannemen. Ze kunnen een eenvoudig raster zijn, bestaande uit vierkanten, driehoeken, zeshoeken of een andere vorm. Of ze kunnen een complexer object vormen, zoals een ‘3-regelmatige boom’, waarbij één centraal punt verbinding maakt met drie hoekpunten, en elk hoekpunt zich vervolgens vertakt om tot in het oneindige twee nieuwe te creëren, waarvan de eerste paar stappen hier te zien zijn:

De verscheidenheid aan transitieve grafieken droeg bij aan de moeilijkheid om Schramms lokaliteitsvermoeden te bewijzen. In de vijftien jaar tussen het vermoeden van Schramm en het bewijs van Easo en Hutchcroft hebben verschillende groepen wiskundigen het vermoeden voor specifieke soorten grafieken bewezen, maar hun ideeën strekken zich nooit uit tot het algemene geval.

"De ruimte van alle mogelijke geometrieën is zo enorm, en er liggen altijd vreemde dingen op de loer", zei Hutchcroft.

De lens verbreden

Easo en Hutchcroft waren aanvankelijk niet op zoek naar een oplossing voor het plaatsvermoeden van Schramm, dat van toepassing is op oneindige grafieken. In plaats daarvan bestudeerden ze percolatie op eindige grafieken. Maar ze hadden een idee dat plotseling hun aandacht verlegde naar het vermoeden.

“We kwamen met dit nieuwe instrument en we dachten: oh, dit lijkt iets dat nuttig zou kunnen zijn om de plaats aan te vallen,” zei Easo.

Om het vermoeden te bewijzen, moesten ze aantonen dat het microscopische perspectief een nauwkeurige momentopname geeft van de percolatiedrempel. Wanneer je slechts een deel van een grafiek bekijkt en een groot samenhangend cluster waarneemt, zou je kunnen aannemen dat de grafiek een oneindig cluster heeft en daarom boven de percolatiedrempel ligt. Easo en Hutchcroft wilden het bewijzen.

Ze vertrouwden op een techniek die kan worden gezien als ‘het verbreden van de lens’. Begin bij een enkel hoekpunt. Zoom vervolgens uit om alle hoekpunten te bekijken die slechts één rand verwijderd zijn van de originele grafiek. Op het vierkante raster kun je nu in totaal vijf hoekpunten zien. Vergroot de lens opnieuw om alle hoekpunten binnen een afstand van twee randen te zien, en vervolgens een afstand van drie randen, vier randen, enzovoort.

Easo en Hutchcroft stelden de wijzerplaat in die bepaalt hoeveel schakels er zijn in de buurt van de plaats waar ze een grote cluster zagen. Vervolgens verbreedden ze de lens en zagen hoe steeds meer randen zich in hun grote cluster verzamelden. Terwijl ze dat deden, moesten ze de waarschijnlijkheid vergroten dat er links aanwezig zouden zijn, waardoor het gemakkelijker wordt om aan te tonen dat de grafiek een grote samenhangende component heeft. Dit is een delicate evenwichtsoefening. Ze moesten het gezichtsveld snel genoeg vergroten en langzaam genoeg koppelingen toevoegen om de volledige oneindige grafiek weer te geven zonder de positie van de wijzerplaat dramatisch te veranderen.

Ze konden aantonen dat grote clusters sneller groeien dan kleinere, zodat, zoals Easo het uitdrukte, “je cluster steeds sneller groeit naarmate het groter en groter wordt, net zoals wanneer je een sneeuwbal rolt.”

Voor het vierkante raster groeit het aantal hoekpunten relatief langzaam. Het is ongeveer de breedte van uw lens in het kwadraat. Na 10 stappen vind je ongeveer 100 hoekpunten. Maar een boom met 3 regulieren groeit exponentieel sneller – grofweg 2 verhoogd tot de kracht van je lensbreedte. Na 10 stappen zie je ongeveer 1,024 hoekpunten. De onderstaande illustratie laat zien hoe de drieregelige boom na slechts zeven stappen veel groter is, ook al heeft het vierkante raster aanvankelijk meer hoekpunten. Over het algemeen kunnen grafieken op verschillende schalen verschillende groeisnelheden hebben; ze kunnen snel beginnen en vervolgens vertragen.

In 2018, Hutchcroft gebruikte een soortgelijk idee om het lokaliteitsvermoeden te bewijzen voor snelgroeiende grafieken zoals de 3-reguliere boom. Maar het werkte niet voor grafieken met een langzame groei, zoals het vierkante raster, of voor grafieken die met gemiddelde snelheid groeien en niet voldoen aan de wiskundige criteria voor snelle groei, noch aan die voor langzame groei.

"Dit is waar dingen echt frustrerend worden gedurende drie jaar", zei Hutchcroft.

Structuur versus uitbreiding

Voor grafieken waarin groeisnelheden op verschillende schalen worden gecombineerd, moet je een verscheidenheid aan technieken gebruiken.

Een zeer nuttig feit is dat, zoals Easo uitlegde, “als een grafiek op een bepaalde schaal een langzame groei vertoont, deze vastloopt.” Het zal op grotere schaal langzaam blijven groeien. Omdat grafieken met langzame groei een extra structuur hebben die wordt bepaald door een tak van de wiskunde die groepentheorie wordt genoemd, was het ook bekend dat grafieken met langzame groei, als je ver genoeg uitzoomt, een geometrie vertonen die wiskundig tam is.

In 2021 werkte Sébastien Martineau van de Sorbonne Universiteit in Parijs, samen met Daniel Contreras en Vincent Tassie van ETH Zürich, kon dit pand gebruiken bewijs het plaatsvermoeden van Schramm voor grafieken die uiteindelijk langzaam groeien.

Op dit punt hadden de twee groepen wiskundigen het vermoeden met succes vanuit verschillende richtingen aangepakt: snelle groei en langzame groei. Maar dit liet grote gaten achter. Ten eerste is er een categorie van middelmatige groei die niet werd gedekt door de techniek van Easo en Hutchcroft of door het bewijs van Contreras, Martineau en Tassion. Een ander probleem was dat de argumenten nog steeds niet van toepassing waren op grafieken met veranderende groeicijfers – alleen op grafieken die snel of langzaam bleven. Om het argument van Contreras, Martineau en Tassion toe te passen op willekeurige grafieken, was het niet genoeg dat de geometrie er uiteindelijk tam uitziet als je uitzoomt, legde Easo uit: “We hebben het nodig om er nu tam uit te zien, in de buurt van de huidige schaal.”

Het midden van nergens

Transitieve grafieken van tussentijdse groei zijn erg mysterieus. Wiskundigen hebben nog nooit een voorbeeld gevonden van een transitieve grafiek waarvan de groei binnen dit bereik valt. Het is mogelijk dat ze niet eens bestaan. Maar wiskundigen hebben niet bewezen dat ze niet bestaan, dus elk volledig bewijs van Schramms lokaliteitsvermoeden moet hierop ingaan. Om de uitdaging nog groter te maken, moesten Easo en Hutchcroft grafieken aanpakken die op een bepaalde lengteschaal mogelijk slechts kortstondig een gemiddelde groei vertonen, zelfs als ze sneller of langzamer groeien als je in- of uitzoomt.

Easo en Hutchcroft hebben een groot deel van het afgelopen jaar gewerkt aan het uitbreiden van hun resultaten, zodat ze ook van toepassing konden zijn op grafieken die niet onder de eerdere methoden vielen.

Ten eerste hebben ze de techniek uit 2018 die Hutchcroft had toegepast op snelgroeiende grafieken aangepast om te werken aan grafieken die de groeiniveaus op verschillende schalen veranderen. Vervolgens pakten ze de trage-groei-zaak aan een document van 27 pagina's ze deelden in augustus een toelichting op het werk aan Contreras, Martineau en Tassion. Ten slotte bedachten ze in hun voordruk van oktober nog een argument waarbij ze gebruik maakten van de theorie van willekeurige wandelingen – lijnen die willekeurig door de ruimte wiebelen – om het geval van gemiddelde groei aan te pakken. Nu de trichotomie voltooid was, hadden ze Schramms lokaliteitsvermoeden bewezen.

"We moesten alles wat we wisten op het probleem gooien", zei Hutchcroft.

De oplossing geeft wiskundigen een beter inzicht in wat er gebeurt boven de percolatiedrempel, waar de kans op een oneindig cluster 100% is, en daaronder, waar de kans 0% is. Maar wiskundigen staan ​​nog steeds versteld van wat er precies gebeurt op de drempel van de meeste grafieken, inclusief het driedimensionale raster. “Dat is waarschijnlijk de beroemdste en meest fundamentele open vraag in de percolatietheorie,” zei hij Russel Lyons van de Universiteit van Indiana.

Het tweedimensionale raster is een van de weinige gevallen waarin wiskundigen hebben bewezen wat er precies op de drempel gebeurt: er vormen zich geen oneindige clusters. En nadat Grimmett en Marstrand een versie van het lokaliteitsvermoeden voor grote platen hadden bewezen, toonden Grimmett en medewerkers aan dat als je een 3D-raster horizontaal doormidden snijdt, een vloer creëert en de draaiknop precies op de percolatiedrempel afstemt, er geen oneindige clusters verschijnen. Hun resultaat duidt erop dat het volledige driedimensionale raster, net als zijn tweedimensionale tegenhanger, mogelijk geen oneindig cluster heeft op de percolatiedrempel.

In 1996, Benjamini en Schramm giste dat de kans om een ​​oneindig cluster precies op de drempel te vinden nul is voor alle transitieve grafieken, net zoals dat het geval is voor het 2D-raster of voor het doormidden gesneden 3D-raster. Nu het vermoeden van de plaats is opgelost, kan een begrip van wat er precies op het overgangspunt gebeurt, iets dichterbij komen.

correctie: 18 december 2023
Het aantal knooppunten binnen n schakels van een startknooppunt op een 3-reguliere grafiek groeit met ongeveer 2ⁿ, niet 3ⁿ zoals dit artikel oorspronkelijk vermeldde. Het artikel is gecorrigeerd.

Quanta voert een reeks onderzoeken uit om ons publiek beter van dienst te zijn. Neem onze lezersonderzoek wiskunde en je doet mee om gratis te winnen Quanta koopwaar.