Je leest:

Combinatorisch woordenraadsel opgelost

Combinatorisch woordenraadsel opgelost

Auteur: | 19 juni 2009

Wat is het verschil tussen rijst en couscous? Het antwoord: couscous is als woord veel interessanter, want de eerste vier en de laatste vier letters zijn hetzelfde. Dergelijke repeterende woorden staan centraal in het ‘vermoeden van Dejean’, een probleem uit de combinatoriek. Het gaat over de vraag in hoeverre het mogelijk is om repeterende woorden in een oneindige rij letters te vermijden. Deze theorie heeft zijn toepassingen in onder andere de datacompressie.

Wiskundige James Currie en informaticus Narad Rampersad, beiden verbonden aan de universiteit van de Canadese stad Winnipeg, hebben het ‘vermoeden van Dejean’ opgelost, een combinatorisch probleem uit 1972. Het probleem gaat over rijtjes letters (of cijfers) waarbij de vraag in hoeverre repeterende rijtjes letters voorkómen kunnen worden, centraal staat. Dit probleem heeft toepassingen in de informatica: het is bruikbaar bij het comprimeren van computerbestanden.

Een groot deel van het wiskundige vraagstuk was al opgelost en nu zijn ook de laatste puzzelstukjes gelegd. In het raadsel staan woorden als ‘papa’, ‘kerker’, het Engelse ‘hotshots’ en het Franse ‘chercher’ centraal. Deze vier woorden hebben een bijzondere eigenschap: het zijn zogeheten kwadraten of tweedemachten: repeterende woorden die we korter kunnen schrijven als (pa)2, (ker)2, (hots)2 en (cher)2. Overigens maken we ons er in de wiskunde niet druk om als een woord niet in de Van Dale is te vinden: ook niet-bestaande woorden tellen mee. De schrijfwijze van ‘hogeremachtswoorden’ gaat op dezelfde manier als bij kwadraten: xxx (x staat voor een rijtje letters) wordt kort geschreven als x3, xxxx als x4, enzovoorts. We zeggen dat een woord van de vorm xn een n-de macht is. Dus blablabla = (bla)3 is een derdemacht.

Het comprimeren van bestanden

Met de komst van de computer is de aandacht voor datacompressie toegenomen, dat wil zeggen, voor het compacter maken van gegevens. Mp3- en zipbestanden zijn er voorbeelden van. Er is een belangrijk verschil tussen de twee. Mp3’s bevatten niet exact dezelfde informatie als de oorspronkelijke bestanden. Er is een deel weggelaten dat je (bijna) niet hoort. Maar een bestand uit een zipbestand is wel gelijk aan het origineel. Deze vorm van comprimeren wordt wel ‘verliesloze compressie’ genoemd. Een simpele manier om verliesloos te comprimeren heet ‘run-length encoding’. Een voorbeeld:

Ongecomprimeerd: 0011100001100000100 (19 cijfers) Gecomprimeerd: 20314021501120 (14 cijfers)

Zie je wat er is gebeurd? Je vervangt een rijtje nullen of enen door de lengte van dat rijtje en een 0 of 1 daarachter. De rij van 19 cijfers is teruggebracht tot 14 cijfers, dus er is inderdaad iets gewonnen.

Het vermoeden van Dejean

Het probleem van de vrouwelijke wiskundige Françoise Dejean gaat over oneindig lange rijtjes letters, voor het gemak ‘oneindige woorden’ genoemd. In die oneindige woorden kijk je naar eindige rijtjes letters die erin voorkomen. Oneindige woorden waarin slechts twee verschillende letters voorkomen, bevatten altijd kwadraten. Dat is niet moeilijk in te zien. Maar oneindig lange woorden (met twee verschillende letters) hoeven geen derdemachten te bevatten. Dat bewees de Noorse wiskundige Axel Thue. In 1906 gaf hij een voorbeeld van een oneindig woord dat geen derdemachten bevat:

ABBABAABBAABABBABAABABBAABBABAAB…

Dit woord is als volgt geconstrueerd:

Begin met een A. De ‘tegengestelde’ van A is B. Combineer deze twee letters: AB. De ‘tegengestelde’ van AB is BA. Combineer deze twee rijtjes: ABBA. De ‘tegengestelde’ van ABBA is BAAB. Combineer deze twee rijtjes: ABBABAAB. Enzovoorts.

Het proces om Thue’s woord te construeren kan grafisch worden weergegeven; een zwart hokje stelt een A voor, een wit hokje een B.
Hier zie je Thue’s woord na een flink aantal iteraties.

In het woord van Thue komen wel kwadraten voor, zoals (BA)2 (de tweede tot en met de vijfde letter). Het woord bevat veel andere vormen xx, waarbij x een rijtje letters bestaande uit A’s en B’s is. Maar derdemachten x3, vierdemachten x4, enzovoorts, bevat het door Thue geconstrueerde woord niet. Met een 3-letter-alfabet is het zelfs mogelijk om een woord te construeren dat geen kwadraten bevat. Ook daarvan gaf Thue een voorbeeld.

Narad Rampersad bewees dat je met een 4-letter-alfabet een oneindig woord kunt construeren zonder kwadraten xx, waarbij x uit ten minste drie letters bestaat. De constructie kan op deze manier grafisch worden weergegeven, waarbij elke kleur een letter voorstelt.

Rationale machten

Thue zocht dus naar oneindige woorden waarin n-de machten voor zover mogelijk worden vermeden. Meer algemeen kun je zoeken naar oneindige woorden waarin rationale machten worden vermeden. We zeggen dat een woord w een p/q-macht is indien het kan worden geschreven als xkx’. Hierbij is x’ een beginstuk van x en de lengte van w is gelijk aan p/q maal de lengte van x. Een voorbeeld is het woord ‘koekoek’. Dit kan worden geschreven als (koe)2k. Het is een 7/3-macht; het woord heeft immers lengte 7 en het repeterende deel (koe) heeft lengte 3. Een ander voorbeeld is ‘entertainment’. Dit kan worden geschreven als (entertainm)ent; weliswaar geen kortere schrijfwijze, maar omdat de laatste drie letters een beginstuk vormen van ‘entertainm’, zit er toch een repeterend element in. Het is een 13/10-macht; het woord heeft immers lengte 13 en ‘entertainm’ bevat 10 letters. Nog twee voorbeelden: ‘abracadabra’ is een 11/7-macht en het Franse ‘entanglement’ is een 12/9-, ofwel 4/3-macht.

Dejean’s vermoeden gaat over de grootste exponent e zó, dat er geen oneindig woord bestaat in een k-letter-alfabet waarin geen exponenten groter dan e voorkomen. We noteren deze exponent als RT, waarbij RT staat voor ‘repetitive threshold’. Thue bewees dat RT = 2: in een 2-letter-alfabet bestaan geen oneindige woorden waarin tweedemachten worden vermeden. Dejean bewees zelf dat RT = 7/4. Zij construeerde in 1972 een oneindig woord dat als volgt begint:

ABCACBCABCBACBCACBA…

Dit oneindige woord bevat 7/4-machten: de tweede tot en met de achtste letter vormen het woord BCACBCA, bestaande uit 7 letters waarvan de eerste 3 en de laatste 3 letters overeenkomen. Een woord met exponent groter dan 7/4 komt in dit oneindige woord niet voor. Dejean deed verder onderzoek op dit terrein en kwam er al experimenterend achter dat RT = 7/5 en RT = k/(k – 1) voor k ≥ 5. Een bewijs van haar vermoeden kon ze echter niet geven.

In 1984 bewees Jean-Jacques Pansiot dat RT inderdaad gelijk is aan 7/5. Dat Dejean’s vermoeden voor k > 4 waar is, bleek pas later. In 1992 bewees Jean Moulin Ollagnier Thue’s vermoeden voor 5 ≤ k ≤ 11. Drie jaar geleden, in 2006, gaven M. Mohammad-Noori en James Currie het bewijs voor 12 ≤ k ≤ 14. Vlak daarna kwam een ware doorbraak: de Italiaan Arturo Carpi bewees het vermoeden voor alle k ≥ 33. Currie en Narad Rampersad wisten Carpi’s constructie uit te breiden zodat het bewijs voor alle k ≥ 27 geleverd was. Hardnekkig bleven echter de waarden 15 ≤ k ≤ 26. Maar met de technieken die Ollagnier in de jaren negentig had gebruikt wisten Currie en Rampersad ook dit laatste gat in Dejean’s vermoeden te dichten. En hiermee is opnieuw een groot wiskundig raadsel opgelost!

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 19 juni 2009
NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.