In een willekeurig gekozen reeks getallen kan de optelling wild worden.

Tel elk paar uit zo'n set bij elkaar op en je krijgt een nieuwe lijst die waarschijnlijk veel meer getallen zal bevatten dan waar je mee begon. Begin met 10 willekeurige getallen, en deze nieuwe lijst (de somset genoemd) zal ongeveer 50 elementen bevatten. Begin met 100 en de som zal waarschijnlijk ongeveer 5,000 bevatten; 1,000 willekeurige begingetallen vormen een somset van 500,000 getallen.

Maar als uw initiële set structuur heeft, kan de somset uiteindelijk minder getallen bevatten dan dit. Overweeg nog een set van 10 cijfers: alle even getallen van 2 tot en met 20. Omdat verschillende paren optellen tot hetzelfde getal – 10 + 12 is hetzelfde als 8 + 14 en 6 + 16 – heeft de somset slechts 19 getallen, niet 50. Dit verschil wordt steeds groter naarmate de sets groter worden. Een gestructureerde lijst van 1,000 getallen kan een somset bevatten met slechts 2,000 getallen.

In de jaren zestig noemde een wiskundige Gregorius Freiman begon verzamelingen met kleine sommensets te onderzoeken in een poging het verband tussen optelling en verzamelingsstructuur te onderzoeken - een cruciale verbinding die het wiskundige veld van additieve combinatoriek definieert. Freiman boekte indrukwekkende vooruitgang en bewees dat een set met een kleine somset moet worden omvat door een grotere set waarvan de elementen in een zeer regelmatig patroon zijn geplaatst. Maar daarna stagneerde het veld. “Freimans oorspronkelijke bewijs was buitengewoon moeilijk te begrijpen, tot het punt waarop niemand er echt zeker van was dat het juist was. Het had dus niet echt de impact die het had kunnen hebben”, zegt hij Timothy Gowers, een wiskundige aan het Collège de France en de Universiteit van Cambridge en een Fields-medaillewinnaar. "Maar dan Imre Ruzsa kwam op het toneel.”

In een reeks van twee papieren in de jaren negentig bewees Ruzsa de stelling van Freiman opnieuw met een elegant nieuw argument. Een paar jaar later, Katalin Marton, een invloedrijke Hongaarse wiskundige die in 2019 stierf, heeft de vraag aangepast wat een kleine somset impliceert over de structuur van de originele set. Ze verving de soorten elementen die in de set verschenen en het soort structuur waar wiskundigen naar moesten zoeken, in de veronderstelling dat wiskundigen hierdoor nog meer informatie zouden kunnen extraheren. Martons vermoeden heeft verband met bewijssystemen, codeertheorie en cryptografie, en neemt een verheven plaats in in de additieve combinatoriek.

Haar vermoeden ‘voelt als een van de meest fundamentele dingen die we niet begrepen’, zei ze Ben Groen, een wiskundige aan de Universiteit van Oxford. Het "onderbouwde gewoon een heleboel dingen waar ik om geef."

Green bundelde de krachten met Gowers, Freddie Manieren van de Universiteit van Californië, San Diego, en Terence tao, een Fields-medaillewinnaar aan de Universiteit van Californië, Los Angeles, vormde wat de Israëlische wiskundige en blogger Gil Kalai genaamd een "Een ploeg' van wiskundigen. Ze bewezen een versie van het vermoeden in een paper gedeeld op 9 november.

Netten Katz, een wiskundige aan de Rice University die niet bij het werk betrokken was, beschrijft het bewijs als ‘prachtig eenvoudig’ – en ‘min of meer volledig uit het niets’.

Tao startte vervolgens een poging om het bewijs te formaliseren Lean, een programmeertaal die wiskundigen helpt stellingen te verifiëren. Binnen een paar weken slaagde die poging. Vroege dinsdagochtend van 5 december Tao aangekondigd dat Lean het vermoeden had bewezen zonder enige ‘sorry’ – de standaardverklaring die verschijnt wanneer de computer een bepaalde stap niet kan verifiëren. Dit is het meest opvallende gebruik hiervan verificatietools sinds 2021, en markeert een keerpunt in de manier waarop wiskundigen bewijzen schrijven in termen die een computer kan begrijpen. Als deze instrumenten eenvoudig genoeg worden voor wiskundigen om te gebruiken, kunnen ze mogelijk het vaak langdurige en moeizame peer review-proces vervangen, aldus Gowers.

De ingrediënten van het bewijs sudderden al tientallen jaren. Gowers zette begin jaren 2000 de eerste stappen. Maar het duurde twintig jaar om te bewijzen wat Kalai ‘de heilige graal’ van het veld noemde.

De ingroep

Om het vermoeden van Marton te begrijpen, helpt het om bekend te zijn met het concept van een groep, een wiskundig object dat bestaat uit een verzameling en een bewerking. Denk aan de gehele getallen – een oneindige reeks getallen – en de werking van optellen. Elke keer dat je twee gehele getallen bij elkaar optelt, krijg je een ander geheel getal. Optellen voldoet ook aan een paar andere regels voor groepsbewerkingen, zoals associativiteit, waarmee je de volgorde van bewerkingen kunt wijzigen: 3 + (5 + 2) = (3 + 5) + 2.

Binnen een groep kun je soms kleinere sets vinden die aan alle groepseigenschappen voldoen. Als u bijvoorbeeld twee even getallen optelt, krijgt u nog een even getal. De even getallen vormen een groep op zichzelf, waardoor ze een subgroep van de gehele getallen zijn. De oneven getallen vormen daarentegen geen subgroep. Als je twee oneven getallen bij elkaar optelt, krijg je een even getal – niet in de originele set. Maar je kunt alle oneven getallen krijgen door simpelweg 1 toe te voegen aan elk even getal. Een dergelijke verschoven subgroep wordt een nevengroep genoemd. Het heeft niet alle eigenschappen van een subgroep, maar behoudt op veel manieren de structuur van zijn subgroep. Net als de even getallen zijn de oneven getallen bijvoorbeeld allemaal gelijkmatig verdeeld.

Marton veronderstelde dat als je een set hebt die we zullen bellen A samengesteld uit groepselementen waarvan de som niet veel groter is dan A zelf, dan bestaat er een subgroep – noem die maar G – met een bijzondere eigenschap. Verschuiving G een paar keer om nevenklassen te maken, en die nevenklassen zullen, samengenomen, de originele set bevatten A. Bovendien veronderstelde ze dat het aantal nevenklassen niet veel sneller groeit dan de omvang van de somset; ze was van mening dat dit verband zou moeten houden met een polynomiale factor, in tegenstelling tot een veel snellere exponentiële groei.

Dit klinkt misschien als een zeer technische nieuwsgierigheid. Maar omdat het om een ​​eenvoudige test gaat: wat gebeurt er als je slechts twee elementen aan de set toevoegt? — voor de overkoepelende structuur van een subgroep is het van groot belang voor wiskundigen en computerwetenschappers. Hetzelfde algemene idee komt naar voren wanneer computerwetenschappers berichten proberen te coderen, zodat je slechts een klein deel van het bericht per keer kunt decoderen. Het komt ook voor in probabilistisch controleerbare bewijzen, een vorm van bewijs die computerwetenschappers kunnen verifiëren door slechts een paar geïsoleerde stukjes informatie te controleren. In elk van deze gevallen werk je met slechts een paar punten in een structuur – het decoderen van slechts een paar bits uit een lang bericht, of het verifiëren van een klein deel van een ingewikkeld bewijs – en concludeer je iets over een grotere structuur op een hoger niveau.

"Je kunt doen alsof alles een grote subset van een groep is", zei hij Tom Sanders, een voormalig student van Gowers en nu een collega van Green in Oxford, of je kunt, ‘haal alles wat je wilde uit het bestaan ​​van veel additieve toevalligheden. Beide perspectieven zijn nuttig.”

Ruzsa publiceerde het vermoeden van Marton in 1999, waardoor ze alle eer kreeg. “Ze kwam tot dat vermoeden onafhankelijk van mij en Freiman, en waarschijnlijk vóór ons”, zei hij. ‘Daarom besloot ik, toen ik met haar sprak, het haar vermoeden te noemen.’ Toch noemen wiskundigen het nu het polynoom Freiman-Ruzsa vermoeden, of PFR.

Nullen en enen

Groepen nemen, net als veel wiskundige objecten, veel verschillende vormen aan. Marton veronderstelde dat haar vermoeden voor alle groepen gold. Dit moet nog worden aangetoond. Het nieuwe artikel bewijst dit voor een bepaald soort groep, dat lijsten met binaire getallen zoals (0, 1, 1, 1, 0) als elementen gebruikt. Omdat computers binair werken, is deze groep cruciaal in de informatica. Maar het is ook nuttig geweest bij additieve combinatoriek. “Het is net een speelgoedomgeving waarin je kunt spelen en dingen kunt uitproberen”, zei Sanders. “De algebra is veel, veel leuker” dan het werken met hele getallen, voegde hij eraan toe.

De lijsten hebben een vaste lengte en elk bit kan 0 of 1 zijn. Je telt ze bij elkaar op door elk item toe te voegen aan zijn tegenhanger in een andere lijst, met de regel dat 1 + 1 = 0. Dus (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR is een poging om erachter te komen hoe een set eruit kan zien als deze niet echt een subgroep is, maar wel enkele groepsachtige kenmerken heeft.

Om PFR nauwkeurig te maken, stel je voor dat je een reeks binaire lijsten hebt opgeroepen A. Neem nu elk paar elementen uit A en tel ze op. De resulterende bedragen vormen de som van A, Genaamd A + A. Als de elementen van A willekeurig worden gekozen, verschillen de meeste sommen van elkaar. Als er zijn k elementen in A, dat betekent dat er in de buurt zal zijn k²/2 elementen in de somset. Wanneer k is groot – zeg 1,000 – k²/2 is veel groter dan k. Maar als A is een subgroep, elk element ervan A + A in A, inhoudende dat A + A is even groot als A zelf.

PFR beschouwt sets die niet willekeurig zijn, maar ook geen subgroepen zijn. In deze sets is het aantal elementen in A + A is enigszins klein - zeg 10kOf 100k. "Het is erg handig als je idee van structuur veel rijker is dan alleen maar een exacte algebraïsche structuur", zegt Shachar Lovett, een computerwetenschapper aan de Universiteit van Californië, San Diego.

Alle verzamelingen waarvan wiskundigen op de hoogte waren en die aan deze eigenschap voldeden, ‘komen redelijk dicht in de buurt van werkelijke subgroepen’, zei Tao. “Dat was de intuïtie, dat er geen ander soort nepgroepen rondslingerden.” Freiman had in zijn oorspronkelijke werk een versie van deze bewering bewezen. In 1999 breidde Ruzsa de stelling van Freiman uit van de gehele getallen naar het opstellen van binaire lijsten. Hij bewees dat wanneer het aantal elementen in A + A is een constant veelvoud van de grootte van A, A bevindt zich in een subgroep.

Maar de stelling van Ruzsa vereiste dat de subgroep enorm was. Martons inzicht was om te stellen dat, in plaats van opgenomen te zijn in één gigantische subgroep, A kan vervat zijn in een polynoom aantal nevenklassen van een subgroep dat niet groter is dan de oorspronkelijke verzameling A.

‘Ik ken een echt idee als ik een echt idee zie’

Rond de millenniumwisseling kwam Gowers Ruzsa’s bewijzen van de stelling van Freiman tegen terwijl hij een ander probleem bestudeerde over verzamelingen die reeksen van gelijkmatig verdeelde getallen bevatten. "Ik had zoiets als dit nodig, een soort structurele informatie verkrijgen uit veel lossere informatie over een bepaalde set", zei Gowers. “Ik had het grote geluk dat Ruzsa nog niet zo lang geleden dit absoluut schitterende bewijs produceerde.”

Gowers begon een mogelijk bewijs uit te werken voor de polynomiale versie van het vermoeden. Zijn idee was om met een set te beginnen A waarvan de som relatief klein was, en vervolgens geleidelijk manipuleerde A in een subgroep. Als hij kon bewijzen dat de resulterende subgroep vergelijkbaar was met de originele set A, kon hij gemakkelijk concluderen dat het vermoeden waar was. Gowers deelde zijn ideeën met collega's, maar niemand kon er een volledig bewijs van maken. Hoewel de strategie van Gowers in sommige gevallen succesvol was, duurden de manipulaties in andere gevallen A verder verwijderd van de gewenste conclusie van het polynoom Freiman-Ruzsa vermoeden.

Uiteindelijk ging het veld verder. In 2012, Sanders bleek bijna PFR. Maar het aantal verschoven subgroepen dat hij nodig had, lag boven het polynoomniveau, zij het slechts een klein beetje. “Toen hij dat eenmaal deed, betekende dit dat het een minder urgente zaak werd, maar nog steeds een heel leuk probleem waar ik een grote voorliefde voor heb,” zei Gowers.

Maar de ideeën van Gowers leefden voort in de herinneringen en harde schijven van zijn collega’s. ‘Daar zit een echt idee in’, zei Green, die ook een leerling van Gowers was geweest. “Ik herken een echt idee als ik een echt idee zie.” Deze zomer bevrijdden Green, Manners en Tao eindelijk de ideeën van Gowers uit hun vagevuur.

Green, Tao en Manners waren 37 pagina's diep in samenwerking voordat ze dachten terug te keren naar de twintig jaar oude ideeën van Gowers. Op 20 juni papierhadden ze met succes een concept uit de waarschijnlijkheidstheorie gebruikt, genaamd willekeurige variabelen, om de structuur van sets met kleine somsets te onderzoeken. Door deze overstap te maken, kon de groep hun sets met meer finesse manipuleren. “Omgaan met willekeurige variabelen is op de een of andere manier veel minder rigide dan het omgaan met verzamelingen,” zei Manners. Met een willekeurige variabele: “Ik kan een van de kansen een klein beetje aanpassen, en dat levert me misschien een betere willekeurige variabele op.”

Met behulp van dit probabilistische perspectief konden Green, Manners en Tao overstappen van het werken met het aantal elementen in een set naar het meten van de informatie in een willekeurige variabele, een grootheid die entropie wordt genoemd. Entropie was niet nieuw in de additieve combinatoriek. In feite Tao had geprobeerd om het concept eind jaren 2000 populair te maken. Maar niemand had nog geprobeerd het te gebruiken voor het polynoom Freiman-Ruzsa-vermoeden. Green, Manners en Tao ontdekten dat het krachtig was. Maar ze konden het vermoeden nog steeds niet bewijzen.

Terwijl de groep over hun nieuwe resultaten kauwde, realiseerden ze zich dat ze eindelijk een omgeving hadden gecreëerd waarin de sluimerende ideeën van Gowers konden floreren. Als ze de grootte van een verzameling zouden meten aan de hand van de entropie ervan, in plaats van het aantal elementen, zouden de technische details veel beter kunnen uitwerken. “Op een gegeven moment realiseerden we ons dat deze oude ideeën van Tim van twintig jaar geleden feitelijk waarschijnlijker zouden werken dan de ideeën die we probeerden,” zei Tao. “En dus hebben we Tim terug bij het project betrokken. En dan passen alle stukjes verrassend mooi in elkaar.”

Toch moesten er nog veel details worden uitgezocht voordat er een bewijs kwam. “Het was een beetje dwaas dat we alle vier ongelooflijk druk waren met andere dingen”, zei Manners. “Je wilt dit geweldige resultaat publiceren en het aan de wereld vertellen, maar je moet eigenlijk nog je midterms schrijven.” Uiteindelijk drong de groep door en op 9 november plaatsten ze hun krant. Ze bewezen dat als A + A is niet groter dan k keer de grootte van Adan A kan niet meer dan ongeveer gedekt worden k¹² verschuivingen van een subgroep die niet groter is dan A. Dit is een potentieel enorm aantal verschuivingen. Maar het is een polynoom, dus het groeit niet exponentieel sneller k wordt groter, zoals het geval zou zijn k waren in de exponent.

Een paar dagen later, Tao begon te formaliseer het bewijs. Hij leidde het formaliseringsproject gezamenlijk, waarbij hij gebruik maakte van het versiebeheerpakket GitHub om de bijdragen te coördineren 25 vrijwilligers over de hele wereld. Ze gebruikten een tool genaamd plan ontwikkeld door Patrick Massot, een wiskundige aan de Paris-Saclay Universiteit, om de inspanningen te organiseren om te vertalen van wat Tao Dit betekent dat we onszelf en onze geliefden praktisch vergiftigen. "Wiskundig Engels" in computercode. Blueprint kan onder andere een in kaart te brengen afbeelding van de verschillende logische stappen die betrokken zijn bij het bewijs. Toen alle belletjes bedekt waren met wat Tao een ‘mooie tint groen’ noemde, was het team klaar. Ze ontdekten een paar zeer kleine typefouten in de krant – op een online Bericht, merkte Tao op dat “de wiskundig meest interessante delen van het project relatief eenvoudig te formaliseren waren, maar dat het de technische ‘voor de hand liggende’ stappen waren die het langst duurden.”

Marton stierf slechts een paar jaar voordat haar beroemde vermoeden werd bewezen, maar het bewijs weerspiegelt haar levenswerk over entropie en informatietheorie. “Alles werkt veel beter als je het in dit entropieraamwerk doet dan in het raamwerk dat ik probeerde te doen,” zei Gowers. “Voor mij lijkt het nog steeds enigszins magisch.”

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.