Een van de oudste en eenvoudigste problemen in de meetkunde heeft wiskundigen overrompeld - en niet voor de eerste keer.

Sinds de oudheid hebben kunstenaars en meetkundigen zich afgevraagd hoe vormen het hele vlak kunnen betegelen zonder gaten of overlappingen. En toch "was er tot vrij recent niet veel bekend", zei Alex Iosevitsj, een wiskundige aan de Universiteit van Rochester.

De meest voor de hand liggende herhaling van tegels: het is gemakkelijk om een ​​vloer te bedekken met kopieën van vierkanten, driehoeken of zeshoeken. In de jaren zestig vonden wiskundigen vreemde sets tegels die het vliegtuig volledig kunnen bedekken, maar alleen op manieren die zich nooit herhalen.

"Je wilt de structuur van dergelijke tegels begrijpen," zei Rachel Greenfeld, een wiskundige aan het Institute for Advanced Study in Princeton, New Jersey. "Hoe gek kunnen ze worden?"

Best gek, zo blijkt.

Het eerste dergelijke niet-herhalende of aperiodische patroon was gebaseerd op een set van 20,426 verschillende tegels. Wiskundigen wilden weten of ze dat aantal konden verlagen. Tegen het midden van de jaren 1970, Roger Penrose (die zou gaan naar win de Nobelprijs voor natuurkunde 2020 voor werk aan zwarte gaten) bewees dat een eenvoudige set van slechts twee tegels, genaamd "vliegers" en "darts", voldoende was.

Het is niet moeilijk om patronen te bedenken die zich niet herhalen. Veel herhalende of periodieke tegels kunnen worden aangepast om niet-herhalende tegels te vormen. Beschouw bijvoorbeeld een oneindig raster van vierkanten, uitgelijnd als een schaakbord. Als u elke rij verschuift zodat deze een bepaalde hoeveelheid verschoven is ten opzichte van de rij erboven, zult u nooit een gebied kunnen vinden dat kan worden geknipt en geplakt als een stempel om de volledige betegeling opnieuw te creëren.

De echte truc is om sets tegels te vinden - zoals die van Penrose - die het hele vlak kunnen bedekken, maar alleen op manieren die niet herhalen.

De twee tegels van Penrose riepen de vraag op: zou er een enkele, slim gevormde tegel kunnen zijn die precies past?

Verrassend genoeg blijkt het antwoord ja te zijn - als je de tegel mag verschuiven, roteren en reflecteren, en als de tegel losgekoppeld is, wat betekent dat er openingen zijn. Die openingen worden opgevuld door andere geschikt geroteerde, geschikt gereflecteerde kopieën van de tegel, die uiteindelijk het hele tweedimensionale vlak bedekken. Maar als je deze vorm niet mag draaien, is het onmogelijk om het vlak te betegelen zonder gaten achter te laten.

Inderdaad, een aantal jaar geleden, de wiskundige Siddharta Bhattacharya bewees dat - ongeacht hoe ingewikkeld of subtiel een tegelontwerp je bedenkt - als je alleen verschuivingen of vertalingen van een enkele tegel kunt gebruiken, het onmogelijk is om een ​​tegel te bedenken die het hele vlak periodiek kan bedekken, maar niet periodiek.

Wiskundigen vermoedden dat het tweedimensionale resultaat van Bhattacharya ook zou gelden in hoger-dimensionale ruimtes. Net zoals er geen aperiodieke tweedimensionale tegel bestaat, veronderstelden ze dat er geen geschikt driedimensionaal blok (of meer gecompliceerde tegel) bestaat, enzovoort in een willekeurig groot aantal dimensies.

Deze hypothese werd het vermoeden van periodieke tegels genoemd.

In een preprint geplaatst vorige maand, Greenfeld, samen met Terence tao van de Universiteit van Californië, Los Angeles, bevestigde uiteindelijk het vermoeden - maar niet op de manier waarop wiskundigen hadden verwacht. Ze construeerden een tegel die aperiodiek een hoogdimensionale ruimte kan vullen, maar niet periodiek, waardoor het vermoeden werd weerlegd.

“Dat was een verrassing. Ik verwachtte dat het vermoeden in alle dimensies waar zou zijn, 'zei Mihalis Kolountzakis, een wiskundige aan de Universiteit van Kreta. "Maar ik denk dat intuïtie in dimensies die hoog genoeg zijn, niet erg ver gaat."

De vreemde tegel is niet alleen opmerkelijk omdat hij de grenzen verlegt van wat geometrisch mogelijk is en wat niet. Het is ook nauw verbonden met vragen die verder gaan dan geometrie, inclusief vragen over de grenzen van de logica zelf.

De spil

In 2019 arriveerde Greenfeld bij UCLA als postdoctoraal onderzoeker, en zij en Tao - die beiden onafhankelijk hadden gewerkt aan een ander probleem met betrekking tot translationele tegels - richtten zich op het bewijzen van het vermoeden van periodieke tegels.

Omdat het al bekend was dat het vermoeden waar was in één en twee dimensies, probeerden ze het in drie dimensies te bewijzen: om aan te tonen dat als je kopieën van één vorm kunt verschuiven om de hele driedimensionale ruimte te betegelen, er een manier moet zijn om betegel de ruimte periodiek.

Ze boekten enige vooruitgang door het vermoeden in twee dimensies opnieuw te bewijzen met behulp van verschillende technieken - waarvan ze hoopten dat ze van toepassing zouden zijn op het driedimensionale geval. Maar toen stuitten ze op een muur. “Op een gegeven moment raakten we gefrustreerd en zeiden: 'OK, misschien is er een reden waarom we dit vermoeden niet in hogere dimensies kunnen bewijzen. We moeten op zoek gaan naar tegenvoorbeelden', zei Tao.

Ze kamden de literatuur uit op zoek naar andere aperiodieke constructies, te beginnen met de eerste: de set van meer dan 20,000 tegels, gepubliceerd in 1964, die het hele vlak door vertalingen kon bestrijken, maar alleen aperiodiek. Vervolgens gingen ze aan de slag met het ontwikkelen van nieuwe technieken voor het construeren van een enkele aperiodieke tegel.

Ze begonnen met een verandering van instelling. Stel dat u een tweedimensionale ruimte wilt betegelen. In plaats van te proberen een doorlopend vlak te betegelen, kunt u een tweedimensionaal rooster overwegen, een oneindige reeks punten die in een raster zijn gerangschikt. U kunt nu een tegel definiëren als een eindige verzameling punten op dat raster; als je een goede betegeling hebt, dan kun je elk punt in het rooster precies één keer bedekken door kopieën te maken van die eindige reeks punten en ze rond te schuiven.

Het bewijzen van het "discrete" periodieke tegelvermoeden voor hoogdimensionale roosters is een iets ander probleem dan het bewijzen van de continue versie van het vermoeden, aangezien er tegels zijn die mogelijk zijn in roosters maar niet in continue ruimte. Maar ze zijn verwant. Greenfeld en Tao waren van plan een discreet tegenvoorbeeld te bedenken voor het vermoeden dat ze vervolgens konden aanpassen om ook in het continue geval te werken.

In de zomer van 2021, ze kwamen dichtbij, twee tegels vinden in een zeer hoge dimensionale ruimte. De tegels kunnen de ruimte die ze bewonen vullen, maar slechts af en toe. "Dit is niet genoeg", zei Greenfeld. "Twee is heel dichtbij, maar betegelen met twee tegels is veel minder rigide dan betegelen met een enkele tegel." Het zou nog anderhalf jaar duren voordat ze een echt tegenvoorbeeld hadden samengesteld voor het vermoeden van periodieke tegels.

Tegels Sandwich

Ze begonnen met het creëren van een nieuwe taal, waarbij ze hun probleem herschreven als een speciaal soort vergelijking. De onbekende "variabele" in deze vergelijking - wat ze moesten oplossen - vertegenwoordigde alle mogelijke manieren om een ​​hoogdimensionale ruimte te betegelen. "Maar het is moeilijk om dingen te beschrijven met slechts één vergelijking," zei Tao. "Soms heb je meerdere vergelijkingen nodig om een ​​heel gecompliceerde set in de ruimte te beschrijven."

Dus herformuleerden Greenfeld en Tao de vraag die ze probeerden op te lossen. Ze realiseerden zich dat ze in plaats daarvan een systeem van vergelijkingen konden bedenken, waarbij elke vergelijking een andere beperking voor hun oplossing zou coderen. Hierdoor konden ze hun probleem opsplitsen in een vraag over veel verschillende tegels - in dit geval tegels die allemaal een bepaalde ruimte beslaan met dezelfde set vertalingen.

In twee dimensies kun je bijvoorbeeld het vlak betegelen met een vierkant door het één voor één omhoog, omlaag, naar links of naar rechts te schuiven. Maar andere vormen kunnen het vlak ook betegelen met exact dezelfde reeks verschuivingen: bijvoorbeeld een vierkant met een bult toegevoegd aan de rechterrand en verwijderd van de linkerrand, zoals een puzzelstukje.

Als je een vierkant, een puzzelstukje en andere tegels neemt die dezelfde reeks shifts gebruiken, en ze vervolgens op elkaar stapelt als vleeswaren in een sandwich, kun je één tegel maken die een enkele set vertalingen gebruikt om driedimensionale ruimte. Greenfeld en Tao zouden dit in veel meer dimensies moeten doen.

"Aangezien we toch in hoge dimensies werkten, deed het toevoegen van nog een dimensie ons niet echt pijn", zei Tao. Integendeel, het gaf hen de extra flexibiliteit die ze nodig hadden om een ​​goede oplossing te bemachtigen.

De wiskundigen probeerden deze sandwich-opbouwprocedure om te keren door hun hoog-dimensionale tegelprobleem met één vergelijking te herschrijven als een reeks tegelvergelijkingen in lagere dimensies. Die vergelijkingen zouden later dicteren hoe de hoger-dimensionale tegelconstructie eruit zou zien.

Greenfeld en Tao beschouwden hun systeem van tegelvergelijkingen als een computerprogramma: elke regel code, of vergelijking, is een commando, en in combinatie kunnen de commando's een programma genereren dat een specifiek doel bereikt. "Logische circuits zijn opgebouwd uit heel basale objecten, deze EN-poorten en OF-poorten enzovoort, die allemaal niet erg interessant zijn", zei Tao. "Maar je kunt ze op elkaar stapelen en je kunt een circuit maken dat een sinusgolf trekt of op internet communiceert."

"Dus begonnen we ons probleem te zien als een soort programmeerprobleem", vervolgde hij. Elk van hun commando's zou een andere eigenschap zijn waaraan hun uiteindelijke tegels moesten voldoen, zodat het programma als geheel zou garanderen dat tegels die aan alle criteria voldoen, aperiodiek moeten zijn.

De vraag werd toen wat voor soort eigenschappen ze nodig hadden om in al die tegelvergelijkingen te coderen om dat mogelijk te maken. Een tegel in een laag van de sandwich kan bijvoorbeeld zo zijn gevormd dat alleen bepaalde soorten bewegingen zijn toegestaan. De wiskundigen zouden hun lijst met beperkingen zorgvuldig moeten opstellen, zodat deze niet zo beperkend zou zijn dat ze alle mogelijke oplossingen zou uitsluiten, maar voldoende beperkend zou zijn om alle periodieke oplossingen uit te sluiten.

"Het spel hier is om het juiste niveau van beperking te construeren," zei Greenfeld, "om de juiste puzzel te coderen."

Oneindige Sudoku

De puzzel die Greenfeld en Tao hoopten te programmeren met hun tegelvergelijkingen was een raster met een oneindig aantal rijen en een groot maar eindig aantal kolommen. De wiskundigen probeerden elke rij en diagonaal te vullen met bepaalde cijferreeksen die overeenkwamen met het soort beperkingen dat ze konden beschrijven met tegelvergelijkingen: iets wat ze vergeleken met een gigantische sudoku-puzzel. Het paar vond vervolgens reeksen die aperiodiek waren - wat betekent dat de oplossing voor het bijbehorende systeem van tegelvergelijkingen ook aperiodiek was. "Er is eigenlijk maar één oplossing voor deze puzzel, en het is dit grappige ding dat bijna maar niet helemaal periodiek is," zei Tao. "Dat kostte veel tijd om te vinden."

"Dit soort dingen, waarbij je functies bestudeert die bijna periodiek zijn maar niet helemaal, is iets dat al bestaat in de wiskunde," zei Isabella Łaba, een wiskundige aan de Universiteit van British Columbia. "Maar dit is een heel andere manier om dat type structuur te gebruiken."

Zoals Iosevich het uitdrukte, creëerden Greenfeld en Tao "een volledig elementair object en tilden het op naar een situatie waarin de zaken er gecompliceerder uitzien."

Daarbij construeerden ze een hoogdimensionale aperiodische tegel - eerst in de discrete setting, daarna in de continue. Hun tegel is zo gecompliceerd, zo vol met kronkels en gaten, dat het nauwelijks de ruimte betegelt. 'Het is een akelige tegel,' zei Tao. "We hebben geen enkele poging gedaan om deze tegel mooi te maken." Hij en Greenfeld hebben de dimensie van de ruimte waarin het leeft niet berekend; ze weten gewoon dat het enorm is, mogelijk zo groot als $latex2^{{100}^{100}}$ (of ruwweg 3 gevolgd door 199 nullen). "Ons bewijs is constructief, dus alles is expliciet en berekenbaar", zei Greenfeld. "Maar omdat het verre van optimaal is, hebben we het gewoon niet gecontroleerd."

De wiskundigen denken inderdaad dat ze aperiodische tegels in veel lagere dimensies kunnen vinden. Dat komt omdat sommige van de meer technische onderdelen van hun constructie te maken hadden met het werken in speciale ruimtes die conceptueel "heel dicht bij tweedimensionaal zijn", zei Greenfeld. Ze denkt niet dat ze een driedimensionale tegel zullen vinden, maar ze zegt dat het mogelijk is dat er een 4D-tegel bestaat.

En dus, zei Iosevich, weerlegden ze niet alleen het vermoeden van periodieke tegels: "Ze deden dit op de meest vernederende manier mogelijk."

Uitstap naar onvolledigheid

Het werk markeert een nieuwe manier om aperiodische tegels te construeren - een manier waarvan Greenfeld en Tao nu denken dat deze kan worden toegepast om andere tegelgerelateerde vermoedens te weerleggen. Dat zal op zijn beurt wiskundigen waarschijnlijk in staat stellen om nog verder te gaan op de grenzen van waar complexiteit kan ontstaan. "Er lijkt een soort opkomend principe te zijn dat hoger-dimensionale geometrie gewoon smerig is," zei Tao. "Dat pathologieën kunnen opduiken, en dat de intuïtie die we krijgen van twee- en driedimensionale misleiding kan zijn."

Het werk boort ook vragen aan, niet alleen over de grenzen van de menselijke intuïtie, maar ook over de grenzen van wiskundig redeneren. In de jaren 1930 toonde de wiskundige Kurt Gödel aan dat elk logisch systeem dat voldoende is voor het ontwikkelen van basisrekenkunde onvolledig is: er zijn beweringen die kunnen worden noch bewezen noch weerlegd binnen dat systeem. Wiskunde, zo blijkt, zit vol met "onbeslisbare" uitspraken.

Op dezelfde manier zit het ook vol met rekenkundig onbeslisbare problemen - problemen die door geen enkel algoritme in een eindige hoeveelheid tijd kunnen worden opgelost. Wiskundigen ontdekten in de jaren zestig dat problemen met tegels ook onbeslisbaar kunnen zijn. Dat wil zeggen, voor sommige sets vormen kun je bewijzen dat het onmogelijk is om in een eindige tijd te bepalen of ze een bepaalde ruimte betegelen of niet. (De enige manier om dit in principe te doen, is alle mogelijke manieren te overwegen om tegels naast elkaar te leggen, tot het einde der tijden.)

"Het is een zeer eenvoudig te verklaren probleem, maar desalniettemin buiten het bereik van de wiskunde", zei Richard Kenjon, een wiskundige aan de Yale University. "Het is niet het eerste voorbeeld van deze situatie waarin een bepaalde wiskundige theorie onbeslisbaar of onvolledig is, maar het is wel de meest nuchtere."

Vorig jaar ontdekten Greenfeld en Tao dat een algemene uitspraak over paren van hoogdimensionale tegels onbeslisbaar is: ze bewezen dat niemand ooit zal kunnen achterhalen of bepaalde paren tegels kunnen worden gemaakt om de ruimte die ze bewonen volledig te bedekken (of het nu gaat om periodieke of periodiek).

Kan een uitspraak over een enkele tegel ook onbeslisbaar zijn? Het is al sinds de jaren zestig bekend dat als het vermoeden van periodieke tegels waar zou zijn, het altijd mogelijk zou zijn om te bepalen of een bepaalde tegel het vlak zou kunnen bedekken.

Maar het tegendeel is niet noodzakelijk waar. Alleen omdat er een aperiodische tegel bestaat, wil dat nog niet zeggen dat er een onbeslisbare tegel bestaat.

Dat is wat Greenfeld en Tao nu willen uitzoeken, gebruikmakend van enkele van de technieken die ze hebben ontwikkeld voor hun recente resultaat. "Het is redelijk aannemelijk, denken we, dat de taal die we hebben gemaakt in staat zou moeten zijn om een ​​onbeslisbare puzzel te creëren," zei Tao. "Dus er kan een tegel zijn waarvoor we nooit zullen kunnen bewijzen dat het wel of geen tegelruimte is."

Om te bewijzen dat een bewering onbeslisbaar is, laten wiskundigen doorgaans zien dat deze equivalent is aan een andere vraag waarvan al bekend is dat deze onbeslisbaar is. Als gevolg hiervan, als dit tegelprobleem ook onbeslisbaar blijkt te zijn, kan het dienen als een extra hulpmiddel om onbeslisbaarheid in andere contexten aan te tonen - contexten die veel verder gaan dan vragen over hoe ruimtes te betegelen.

In de tussentijd dient het resultaat van Greenfeld en Tao echter als een soort waarschuwing. "Wiskundigen houden van mooie, zuivere uitspraken," zei Iosevich. 'Maar geloof niet alles wat je hoort. … Helaas is het geen feit dat alle interessante uitspraken in de wiskunde mooi moeten zijn, en dat ze moeten werken zoals wij dat willen.”