Christoffelwoord
Christoffelwoorden zijn genoemd naar de Duitse wiskundige Elwin Bruno Christoffel (1829-1900). De term Christoffelwoord werd ingevoerd door Jean Berstel in 1990, maar de theorie was reeds in ontwikkeling sedert het einde van de negentiende eeuw. Christoffelwoorden zijn de eindige versie van de Sturmiaanse woorden.
Oorsprong
E.B. Christoffel schreef in 1864 een artikel in het Latijn in Annali di Matematica Pura ed Applicata,[1] waarin hij voor twee onderling ondeelbare gehele getallen en het verloop van de rij:
- enz.
onderzocht. Hij maakte een corresponderende rij met de symbolen c en d, waarin hij een c noteerde als de volgende rest in de rij groter was dan de huidige (crescit), en een d als de volgende rest in de rij kleiner was (decrescit). De rij is periodiek met periode alleen de eerste symbolen zijn nodig. Voor bijvoorbeeld en vond hij de rijen:
4 8 1 5 9 2 6 10 3 7 0 [4 8...] c d c c d c c d c d c [c...]
Christoffel observeerde dat men uit het "woord" 'cdccdccdcdc' de getallen en kon afleiden: is het aantal symbolen d in de rij en is de lengte van de rij. Hij gebruikte deze rijen om de kettingbreukontwikkeling van de breuk af te leiden.[2]
Men kan overigens ook niet modulair tewerk gaan en beginnend bij 0 stappen ter grootte maken tot men aankomt in een veelvoud van . Vanwege de onderlinge ondeelbaarheid is dat het kleinste gemene veelvoud . Bij het passeren en aankomen in een veelvoud van noteert men een d, anders een c. Duidelijk is dat het aantal symbolen, dus het aantal stappen, gelijk is aan . En het aantal symbolen d is gelijk aan het aantal veelvouden van , dus het getal Het bovenstaande voorbeeld wordt dan:
[4 8 1 5 9 2 6 10 3 7 0 (mod 11)] 4 8 12 16 20 24 28 32 36 40 44 c d c c d c c d c d
Meetkundige definitie
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bb/Christoffelwoord.png/260px-Christoffelwoord.png)
Een christoffelwoord kan op meetkundige wijze gedefinieerd worden, als discretisatie van een lijnstuk met een helling die een rationaal getal is, door een pad in het rooster van gehele getallen. Stel en zijn twee gehele getallen die onderling ondeelbaar zijn. Trek het lijnstuk van naar en teken een pad van naar in het geheeltallig rooster dat bestaat uit een opeenvolging van horizontale en verticale lijnstukken zodanig dat:
- het pad volledig onder het lijnstuk ligt;
- het gebied dat omsloten wordt door het lijnstuk en het pad geen punten uit het rooster bevat buiten de punten op het pad zelf.
Het pad bestaat uit een opeenvolging van stappen in de -richting van een punt naar het punt of in de -richting van een punt naar een punt Men noemt dit een christoffelpad.
De opeenvolgende stappen van het pad kunnen voorgesteld worden als een woord over een binair alfabet met twee symbolen, bijvoorbeeld x en y. Voor een stap in de -richting noteert men een x, en voor een stap in de -richting een y. Dit geeft het (beneden-)christoffelwoord met helling : Dit woord heeft de lengte en er komt maal een x en maal een y in voor.
In het voorbeeld hiernaast is en en is dat woord xyxyxyyxyxyy.
N.B. Als men de definitie wijzigt en eist dat het pad volledig boven het lijnstuk ligt, krijgt men een bovenchristoffelwoord. Dit is in het voorbeeld yyxyxyyxyxyx, het omgekeerde van
Rekenkundige definitie
Stel en zijn twee onderling ondeelbare positieve gehele getallen en is Er is een alfabet {x,y} met twee symbolen. Het christoffelwoord over dit alfabet wordt gedefinieerd als volgt:
- , als
- , als
voor Dit is in essentie de methode die Christoffel gebruikte.
Voorbeelden
Enkele bijzondere christoffelwoorden zijn:
- Het (triviale) christoffelwoord met helling 0 is x.
- Het (triviale) christoffelwoord met helling oneindig is y.
- Het christoffelwoord met helling 1 is xy.
Eigenschappen
- Christoffelwoorden zijn eindige Sturmiaanse woorden. In plaats van een lijnstuk met helling definieert men Sturmiaanse woorden aan de hand van een oneindige halve rechte vanuit (0,0) die een irrationale helling heeft.
- Christoffelwoorden zijn primitieve woorden. Het kwadraat van een christoffelwoord dit is de concatenatie is geen christoffelwoord. En een christoffelwoord kan nooit het kwadraat van een ander christoffelwoord zijn; want dan zou het aantal symbolen x en y in het woord wel onderling deelbaar zijn.
- Indien men de volgorde van de snijpunten van het lijnstuk met de horizontale en verticale lijnen van het rooster codeert met een y voor een snijpunt met een horizontale en x voor een snijpunt met een verticale, verkrijgt men een palindroom Het christoffelwoord is (in de figuur hiernaast is dat palindroom yxyxyyxyxy).
Standaardfactorisatie
De standaardfactorisatie van christoffelwoorden werd ingevoerd door Jean-Pierre Borel en François Laubie in 1993. Een factorisatie van een woord bestaat uit een aantal woorden waarvan de concatenatie gelijk is aan : . Men schrijft hiervoor:
Borel en Laubie bewezen dat elk niet-triviaal christoffelwoord een unieke factorisatie heeft, waarin en zelf christoffelwoorden zijn.
Dit volgt uit de vaststelling dat, voor onderling ondeelbare gehele getallen en er een uniek roosterpunt op het christoffelpad van naar is waarvoor de afstand tot het lijnstuk het kleinste is (de uiteinden niet meegerekend, waar de afstand nul is). De standaardfactorisatie bestaat dan uit het deel van het christoffelwoord dat het pad codeert van tot dit punt, en het deel dat het pad codeert vanaf dit punt tot
In de voorbeeldfiguur ligt het punt het dichtst bij het lijnstuk en de factorisatie van het christoffelwoord xyxyxyyxyxyy is (xyxyxyy, xyxyy). xyxyxyy is het christoffelwoord en xyxyy is Algemeen geldt: als het punt op het christoffelpad dat het dichtst bij het lijnstuk ligt het punt is, dan bestaat de standaardfactorisatie van uit het christoffelwoord met helling en het christoffelwoord met helling
Elk christoffelwoord kan aldus op een unieke manier uitgedrukt worden als het product van twee christoffelwoorden. Deze eigenschap kan men gebruiken om een oneindig grote, complete binaire boom te maken die alle christoffelwoorden bevat.
De driehoek in het voorbeeld, gevormd door de punten en , bevat buiten deze drie punten geen andere roosterpunten. De oppervlakte van deze driehoekde volgt uit de formule van Pick: Daarin is het aantal ingesloten roosterpunten en het aantal hoekpunten, zodat
De matrix:
behoort tot de speciale lineaire groep van geheeltallige 2×2-matrices waarvan de determinant gelijk is aan 1. Dit betekent ook dat de Farey-afstand tussen de breuken en gelijk is aan 1. De breuken en zijn opeenvolgende breuken in de Farey-rij (in ons voorbeeld: 2/3, 5/7 en 3/4 in ) en vormen een driehoek in de Farey-graaf. Er bestaat dus een verband tussen christoffelwoorden en de voorstelling van rationale getallen door kettingbreuken.
- Jean Berstel, Aaron Lauve, Christophe Reutenauer, Franco V. Saliola. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Society, 2009. ISBN 9780821844809