Hoe groot kan een chaos zijn zonder dat er een bepaalde regelmaat in voorkomt? Op deze fundamentele wiskundevraag breken onderzoekers al decennia lang hun hoofd. Vier informaticastudenten maakten opeens een sprong richting de oplossing.
Share
Als je twee rijen van een ruitjespapier neemt en je kleurt in elke kolom precies een hokje, dan kun je maximaal acht kolommen kleuren voordat een patroon zich drie keer herhaalt. Als je nog een hokje in de negende kolom kleurt, ontstaat altijd een drievoudig herhaald patroon, oftewel een rekenkundige reeks met lengte drie.
Op basis van dit kleurexperiment stelde de Amsterdamse wiskundige Bartel Leendert van der Waerden in 1927 een theorie op voor de maximale grootte van een chaotische verzameling. Van der Waerden bewees dat voor de combinatie van elk gegeven getallenpaar, van positieve en natuurlijke getallen, een constante bestaat, het Van der Waerdengetal, dat deze chaosgrens weergeeft. Het Van der Waerdengetal voor de getalcombinatie uit het voorbeeld, 2 rijen en 3 herhalingen, is 9.
Van der Waerdens theorie leverde nog niet direct het gezochte antwoord. Want er bestaat geen formule om voor een willekeurig getallenpaar het Van der Waerdengetal te vinden. Door alle mogelijke patronen uit te tekenen, zijn tot nu toe slechts vijf Van der Waerdengetallen met zekerheid vast gesteld. Voor de grotere getallen is alleen een minimale waarde bepaald, doordat het aantal mogelijke kleurcombinaties simpelweg te groot is.
Vier informaticastudenten, Anne-Aimee Bun, Paul Herwig, Martijn van Lambalgen en Michel Meulpolder, gingen voor het vak ‘vervulbaarheidstheorie’ de uitdaging aan om twee van de ondergrenzen te verbeteren. Van Lambalgen: “Wij wilden voor twee getalcombinaties een langer patroon vinden, dan tot nu toe bekend was.”
Promovendus ir. Marijn Heule (EWI) had hen de tip gegeven om vooral naar symmetrische oplossingen te zoeken, omdat de vijf bekende Van der Waerdengetallen ook symmetrisch waren. Toen ze zelf de vijf exacte oplossingspatronen uitgebreid bestudeerden viel hun nog iets anders op. Het was al bekend dat de oplossingen soms bestonden uit meerdere blokken, met een lengte van een priemgetal, die een paar keer als geheel terugkwamen. Maar de studenten ontdekten dat een blok ook in ritsvorm terugkwam. Van Lambalgen: “Een patroonblok komt soms later in de reeks weer terug, maar dan om en om afgewisseld met een kopie van zichzelf.”
Gek
Ze leerden de computer deze ‘zipp-truc’. Herwig: “Je trekt bijvoorbeeld een oplossing van 11 hokjes uit elkaar, en dan verspreid je die over de even plekken van de volgende 22 hokjes. Datzelfde doe je op de oneven plekken, waardoor je nieuwe oplossing twee keer zolang is. De twee blokken worden eigenlijk in elkaar geritst.”
Zo vonden ze zeven nieuwe, grotere oplossingen. De ondergrens voor het Van der Waerdengetal W(4,5), met vier rijen en maximaal vier herhalingen, verhoogden ze bijvoorbeeld van 10437 naar 17705.
Hun begeleider, dr. Hans van Maaren (EWI), zegt dat de studenten daardoor ‘eindelijk weer schot in de zaak’ hebben gebracht. “Veel onderzoekers houden zich bezig met dit probleem, maar de afgelopen twintig jaar zijn er slechts twee nieuwe ondergrenzen gevonden. Zij hebben er nu in een keer zeven aanzienlijk verhoogd.”
De nieuwe truc geeft gek genoeg alleen verbeterde resultaten bij de getallen met een even aantal rijen. Herwig: “Dat heeft waarschijnlijk iets te maken met dat we alleen naar symmetrische oplossingen kijken.”
De studenten ontwikkelden ook een nieuwe manier om de patronen uit te tekenen. Van Lambalgen: “Een patroon van vier rijen en tienduizenden kolommen is niet te overzien. Daarom tekenen wij de getallen in lijnen uit.”
Herwig: “Bij vier rijen gebruiken we vier richtingen in ons figuur. Als in kolom één het bovenste hokje is gekleurd, trekken wij een lijntje naar boven. Als het volgende hokje in de tweede rij staat, gaat de lijn naar links, enzovoort.” Het resultaat zijn mooie symmetrische vormen waardoor de studenten vermoeden dat ze in een aantal gevallen de exacte waarde hebben gevonden. Ze kunnen dat alleen niet bewijzen. Volgens Heule zitten ze er in elk geval heel dichtbij.
Als je twee rijen van een ruitjespapier neemt en je kleurt in elke kolom precies een hokje, dan kun je maximaal acht kolommen kleuren voordat een patroon zich drie keer herhaalt. Als je nog een hokje in de negende kolom kleurt, ontstaat altijd een drievoudig herhaald patroon, oftewel een rekenkundige reeks met lengte drie.
Op basis van dit kleurexperiment stelde de Amsterdamse wiskundige Bartel Leendert van der Waerden in 1927 een theorie op voor de maximale grootte van een chaotische verzameling. Van der Waerden bewees dat voor de combinatie van elk gegeven getallenpaar, van positieve en natuurlijke getallen, een constante bestaat, het Van der Waerdengetal, dat deze chaosgrens weergeeft. Het Van der Waerdengetal voor de getalcombinatie uit het voorbeeld, 2 rijen en 3 herhalingen, is 9.
Van der Waerdens theorie leverde nog niet direct het gezochte antwoord. Want er bestaat geen formule om voor een willekeurig getallenpaar het Van der Waerdengetal te vinden. Door alle mogelijke patronen uit te tekenen, zijn tot nu toe slechts vijf Van der Waerdengetallen met zekerheid vast gesteld. Voor de grotere getallen is alleen een minimale waarde bepaald, doordat het aantal mogelijke kleurcombinaties simpelweg te groot is.
Vier informaticastudenten, Anne-Aimee Bun, Paul Herwig, Martijn van Lambalgen en Michel Meulpolder, gingen voor het vak ‘vervulbaarheidstheorie’ de uitdaging aan om twee van de ondergrenzen te verbeteren. Van Lambalgen: “Wij wilden voor twee getalcombinaties een langer patroon vinden, dan tot nu toe bekend was.”
Promovendus ir. Marijn Heule (EWI) had hen de tip gegeven om vooral naar symmetrische oplossingen te zoeken, omdat de vijf bekende Van der Waerdengetallen ook symmetrisch waren. Toen ze zelf de vijf exacte oplossingspatronen uitgebreid bestudeerden viel hun nog iets anders op. Het was al bekend dat de oplossingen soms bestonden uit meerdere blokken, met een lengte van een priemgetal, die een paar keer als geheel terugkwamen. Maar de studenten ontdekten dat een blok ook in ritsvorm terugkwam. Van Lambalgen: “Een patroonblok komt soms later in de reeks weer terug, maar dan om en om afgewisseld met een kopie van zichzelf.”
Gek
Ze leerden de computer deze ‘zipp-truc’. Herwig: “Je trekt bijvoorbeeld een oplossing van 11 hokjes uit elkaar, en dan verspreid je die over de even plekken van de volgende 22 hokjes. Datzelfde doe je op de oneven plekken, waardoor je nieuwe oplossing twee keer zolang is. De twee blokken worden eigenlijk in elkaar geritst.”
Zo vonden ze zeven nieuwe, grotere oplossingen. De ondergrens voor het Van der Waerdengetal W(4,5), met vier rijen en maximaal vier herhalingen, verhoogden ze bijvoorbeeld van 10437 naar 17705.
Hun begeleider, dr. Hans van Maaren (EWI), zegt dat de studenten daardoor ‘eindelijk weer schot in de zaak’ hebben gebracht. “Veel onderzoekers houden zich bezig met dit probleem, maar de afgelopen twintig jaar zijn er slechts twee nieuwe ondergrenzen gevonden. Zij hebben er nu in een keer zeven aanzienlijk verhoogd.”
De nieuwe truc geeft gek genoeg alleen verbeterde resultaten bij de getallen met een even aantal rijen. Herwig: “Dat heeft waarschijnlijk iets te maken met dat we alleen naar symmetrische oplossingen kijken.”
De studenten ontwikkelden ook een nieuwe manier om de patronen uit te tekenen. Van Lambalgen: “Een patroon van vier rijen en tienduizenden kolommen is niet te overzien. Daarom tekenen wij de getallen in lijnen uit.”
Herwig: “Bij vier rijen gebruiken we vier richtingen in ons figuur. Als in kolom één het bovenste hokje is gekleurd, trekken wij een lijntje naar boven. Als het volgende hokje in de tweede rij staat, gaat de lijn naar links, enzovoort.” Het resultaat zijn mooie symmetrische vormen waardoor de studenten vermoeden dat ze in een aantal gevallen de exacte waarde hebben gevonden. Ze kunnen dat alleen niet bewijzen. Volgens Heule zitten ze er in elk geval heel dichtbij.
Comments are closed.