Je leest:

Partitiegetallen gedragen zich als fractals

Partitiegetallen gedragen zich als fractals

Het lijkt een kinderspelletje: op hoeveel manieren kun je een gegeven aantal knikkers verdelen in kleinere groepjes? Achter deze vraag gaat echter diepe wiskunde schuil. Amerikaanse wiskundigen hebben een eindige formule gevonden om de zogeheten partitiegetallen te berekenen. Een enorme doorbraak, want het gerucht gaat dat dit werk een Fieldsmedaille waard is; de belangrijkste onderscheiding die een wiskundige kan krijgen.

Small

Al eeuwenlang proberen de knapste wiskundekoppen grip te krijgen op de zogeheten partitiefunctie. Deze functie geeft aan op hoeveel manieren een aantal knikkers kan worden opgedeeld in groepjes. Zo kun je 5 knikkers bijvoorbeeld verdelen in vier groepjes: één groepje van 2 en drie groepjes van 1. Als som kun je dit schrijven als 5 = 2 + 1 + 1 + 1. Een andere partitie is 5 = 3 + 2 (twee groepjes). Ook 5 = 1 + 1 + 1 + 1 + 1 (vijf groepjes) en 5 = 5 (één groepje) zijn partities. In totaal zijn er 7 partities van 5; je ziet ze in de figuur hiernaast. We noteren dat als p(5) = 7.

In het algemeen geven we het aantal partities van n aan met p(n). De rij partitiegetallen is de rij p(1), p(2), p(3), p(4), p(5) enzovoorts. Die rij ziet er zo uit: 1, 2, 3, 5, 7, 11, 15, 22, …. De getallen in die rij worden al snel ongelofelijk groot, zoals figuur 2 laat zien. Zo is p(20) = 627 en p(100) is al meer dan 190 miljoen.

Medium
De waarden van p(n) nemen snel toe.

Grote namen als Euler en Ramanujan hebben diepe inzichten verkregen in de theorie van partities. Hoewel zij met hun berekeningen veel vragen konden beantwoorden, riepen hun berekeningen uiteindelijk nog meer vragen op, waarop ook zij het antwoord schuldig moesten blijven.

Wiskundige Ken Ono heeft met een aantal collega’s nieuwe grote vorderingen gemaakt op het gebied van partities. Het team onder leiding van Ono wist te bewijzen dat de partitiegetallen zich in zekere zin gedragen als fractals, een resultaat dat niemand eerder voor mogelijk had gehouden. Zij hebben deelbaarheidseigenschappen van partities ontrafeld en een theorie ontwikkeld die de ‘oneindig herhalende’ structuur verklaart. Bovendien hebben ze de eerste eindige formule opgesteld om partitiegetallen te berekenen. “Adembenemende doorbraken”, noemt George Andrews, professor aan de Pennsylvania State University en tot 31 januari van dit jaar voorzitter van de American Mathematical Society, de resultaten.

Medium
Ken Ono geeft een voordracht over partitiegetallen.

“We hebben bewezen dat partitiegetallen een ‘fractale structuur’ hebben voor elk priemgetal. Deze getallen zijn ‘zelfherhalend’ in a shocking way”, aldus Ono. “Met onze methode hebben we een antwoord gevonden op diverse vragen die tot nu toe nog open stonden.” Ongetwijfeld zullen de nieuwe resultaten leiden tot veranderingen in hoe wiskundigen partities bestuderen.

Ono, professor aan zowel de Emory universiteit van Atlanta als de universiteit van Wisconsin in Madison, leidde een team bestaande uit Jan Bruinier van de Technische Universiteit van Darmstadt in Duitsland, Amanda Folsom van Yale University en Zach Kent, fellow aan Emory.

Small
Leonhard Euler (1707–1783).

Geschiedenis

Het werk van de achttiende-eeuwse wiskundige Leonhard Euler leidde tot de eerste recursieve techniek voor het berekenen van partitiegetallen. De methode was echter langzaam en – in een tijd zonder computers – erg onpraktisch voor grote aantallen. Honderdvijftig jaar lang kon de methode alleen toegepast worden om de eerste 200 partitiegetallen te berekenen.

In het begin van de twintigste eeuw werden nieuwe resultaten geboekt door de wiskundigen Srinivasa Ramanujan en G.H. Hardy. Met hun cirkelmethode konden grotere partitiegetallen uitgerekend worden. Zij moesten echter genoegen nemen met een benadering. Het lukte hen niet om een formule te vinden die het exacte aantal partities van een groot getal kan berekenen.

In een van zijn notebooks schreef Ramanujan in 1919: “Schijnbaar zijn er overeenkomstige eigenschappen waarin de moduli van partitiegetallen machten van een van de priemgetallen 5, 7 of 11 zijn… En die eigenschappen zijn er niet voor andere priemgetallen.” Een jaar later overleed Ramanujan en de wiskundewereld bleef zitten met een boel ondoorgrondelijke aantekeningen, waaronder deze.

Medium
Al wandelend door het bos kregen Ken Ono (links) en Zach Kent hun eerste eureka-moment.

In 1937 werd een nieuwe grote stap voorwaarts gezet. In dat jaar vond Hans Rademacher een exacte formule om partitiegetallen te berekenen. Hoewel de methode een grote verbetering was ten opzichte van de exacte, maar trage formule van Euler, had ook deze formule zo zijn beperkingen: er moesten oneindig veel getallen met oneindig veel decimalen bij elkaar opgeteld worden.

Fractal

De term fractal werd bedacht door Benoît Mandelbrot. Hij doelde hiermee op een figuur die oneindig gedetailleerd is en op elk niveau gelijk is aan de oorspronkelijke figuur: een fractal bestaat in feite uit oneindige gelijkenissen van zichzelf. Mandelbrot nam zelf als voorbeeld graag een bloemkool, die is opgebouwd uit roosjes die elk de vorm van een bloemkool hebben. De roosjes zijn op hun beurt wéér opgebouwd uit bloemkoolvormige delen, enz…

Eureka in het bos

In de daaropvolgende decennia werden opnieuw diepe inzichten verkregen, maar die staan nu allemaal in de schaduw van de doorbraak van Ono en zijn collega’s. Maandenlang heeft het team van Ono eraan gewerkt. “Alles wat we probeerden, bleek niet te werken”, aldus Ono. Het eureka moment kwam in september vorig jaar. Ono en Kent wandelden door de bossen van Tallulah Falls in de Amerikaanse staat Georgia. “We stonden op een grote rots, keken uit over de vallei en hoorden de waterval, toen we ons realiseerden dat partitiegetallen een fractale structuur hebben”, zegt Ono. “Allebei begonnen we te lachen.”

De wandeling van Ono en Kent leidde tot een nieuwe klasse van fractals. De mysterieuze zin van Ramanujan kan verklaard worden met behulp van hun ‘fractaltheorie’. Bovendien toonden de wiskundigen aan dat de deelbaarheidseigenschappen van partitiegetallen een ‘fractale structuur’ hebben voor elk priemgetal vanaf 5. De rijen zijn periodiek; ze herhalen zichzelf om de zoveel tijd. “Het is alsof je inzoomt op de Mandelbrotverzameling”, zegt Ono, doelend op de beroemde ‘kevervormige’ fractal van Mandelbrot (zie het Youtube-filmpje hieronder).

De fractale structuur van de partitiefunctie

Het team van Ken Ono vond de volgende formule die geldt voor het aantal partities van het getal 133n + 1007:

p(133n + 1007) ≡ 6p(13n + 6) (mod 13).

Deze formule gaat uit van het priemgetal 13 en genereert een rij van eenvoudige lineaire combinaties van partitiegetallen deelbaar door 13. Het ‘fractale’ zit hem in het feit dat als je inzoomt op die rij, je een deelrij vindt waarvan lineaire combinaties van partitiegetallen deelbaar zijn door 132:

p(134n + 27371) ≡ 45p(132n + 162) (mod 132).

En als je nog verder inzoomt, levert dat iets soortgelijks voor 133, enzovoorts.

In dit voorbeeld werd een formule met priemgetal 13 genomen. De wiskundigen bewezen een algemene stelling die zegt dat zulke formules bestaan voor élk priemgetal dat groter dan of gelijk is aan 5. Voor de priemgetallen 5, 7, 11 is het resultaat van Ramanujan. Voor priemgetallen 13 en groter is het resultaat van Folsom, Kent en Ono nieuw. Hoewel hun resultaat het bestaan van dergelijke formules garandeert, hebben ze geen algoritme gevonden om die formules te genereren. Of zo’n algoritme bestaat, is weer een andere vraag.

Voor technische details: volg deze link (pdf).

Nog meer succes

Alsof de gevonden fractale structuur nog niet genoeg was, hebben Ono en de zijnen nog een ander succes geboekt. Terwijl Ono en Bruinier in de auto aan het chatten waren, vastzittend in het verkeer op “Spaghetti Junction”, hadden ze hun finale ‘eureka moment’. Ze kwamen op een idee om de oneindig complexe structuur van de formule van Rademacher aanzienlijk te vereenvoudigen. Het lukte hen om een formule te vinden om partitiegetallen uit te rekenen, waarbij slechts eindig veel getallen opgeteld hoeven te worden.

Medium
De aantekeningen die leidden tot de uiteindelijke doorbraak over partitiegetallen.

“We hebben een functie P gevonden, een soort magical oracle”, zegt Ono. “Ik kan nu een willekeurig getal nemen; je stopt hem in P en na een beetje rekenwerk heb ik het aantal partities van dat getal. De functie P gebruikt geen gruwelijke getallen met oneindig veel decimalen. Het is een eindige, algebraïsche formule. Het is dátgene, waar we al heel lang naar zochten.”

Het werk van Ono en zijn collega’s resulteerde in twee publicaties die beschikbaar zijn op de site van het American Institute of Mathematics:

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 27 januari 2011

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE