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, waarin hij voor twee onderling ondeelbare gehele getallen $a$ en $b$ het verloop van de rij:

$r_{1}=\ a{\pmod {b}}$

$r_{2}=2a{\pmod {b}}$

$r_{3}=3a{\pmod {b}}$

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 $b;$ alleen de eerste $b$ symbolen zijn nodig. Voor bijvoorbeeld $a=4$ en $b=11$ 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 $a$ en $b$ kon afleiden: $a$ is het aantal symbolen d in de rij en $b$ is de lengte van de rij. Hij gebruikte deze rijen om de kettingbreukontwikkeling van de breuk $a/b$ af te leiden.

Men kan overigens ook niet modulair tewerk gaan en beginnend bij 0 stappen ter grootte $a$ maken tot men aankomt in een veelvoud van $b$. Vanwege de onderlinge ondeelbaarheid is dat het kleinste gemene veelvoud $ab$. Bij het passeren en aankomen in een veelvoud van $b$ noteert men een d, anders een c. Duidelijk is dat het aantal symbolen, dus het aantal stappen, gelijk is aan $a$. En het aantal symbolen d is gelijk aan het aantal veelvouden van $b$, dus het getal $a.$ 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

Constructie van het christoffelwoord C(7,5)

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 $a$ en $b$ zijn twee gehele getallen die onderling ondeelbaar zijn. Trek het lijnstuk van $(0,0)$ naar $(a,b)$ en teken een pad van $(0,0)$ naar $(a,b)$ in het geheeltallig rooster $\mathbb {Z} \times \mathbb {Z}$ dat bestaat uit een opeenvolging van horizontale en verticale lijnstukken zodanig dat:

1. het pad volledig onder het lijnstuk ligt;
2. het gebied dat omsloten wordt door het lijnstuk en het pad geen punten uit het rooster $\mathbb {Z} \times \mathbb {Z}$ bevat buiten de punten op het pad zelf.

Het pad bestaat uit een opeenvolging van stappen in de $x$-richting van een punt $(i,j)$ naar het punt $(i+1,j)$ of in de $y$-richting van een punt $(i,j)$ naar een punt $(i,j+1).$ 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 $x$-richting noteert men een x, en voor een stap in de $y$-richting een y. Dit geeft het (beneden-)christoffelwoord met helling $b/a$: $C(b,a).$ Dit woord heeft de lengte $n=a+b$ en er komt $a$ maal een x en $b$ maal een y in voor.

In het voorbeeld hiernaast is $a=5$ en $b=7$ 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 $C(a,b).$

Rekenkundige definitie

Stel $a$ en $b$ zijn twee onderling ondeelbare positieve gehele getallen en $n$ is $a+b.$ Er is een alfabet {x,y} met twee symbolen. Het christoffelwoord $C(b,a)=c_{1}c_{1}c_{2}{\ldots }c_{n}$ over dit alfabet wordt gedefinieerd als volgt:

$c_{i}={\text{x}}$, als $\ ib\!\!{\pmod {n}}>(i-1)b\!\!{\pmod {n}}$

$c_{i}={\text{y}}$, als $\ ib\!\!{\pmod {n}}<(i-1)b\!\!{\pmod {n}}$

voor $i=1,2,\ldots ,n.$ 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 $b/a$ 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 $w,$ dit is de concatenatie $ww$ 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 $p.$ Het christoffelwoord is ${\text{x}}p{\text{y}}$ (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 $w$ bestaat uit een aantal woorden $(w_{1},w_{2},\ldots )$ waarvan de concatenatie gelijk is aan $w.$: $w=w_{1}w_{2}\ldots$. Men schrijft hiervoor: $w=(w_{1},w_{2},\ldots )$

Borel en Laubie bewezen dat elk niet-triviaal christoffelwoord $w$ een unieke factorisatie $w=(w_{1},w_{2})$ heeft, waarin $w_{1}$ en $w_{2}$ zelf christoffelwoorden zijn.

Dit volgt uit de vaststelling dat, voor onderling ondeelbare gehele getallen $a$ en $b,$ er een uniek roosterpunt op het christoffelpad van $(0,0)$ naar $(a,b)$ is waarvoor de afstand tot het lijnstuk het kleinste is (de uiteinden niet meegerekend, waar de afstand nul is). De standaardfactorisatie $w=(w_{1},w_{2})$ bestaat dan uit het deel van het christoffelwoord $C(b,a)$ dat het pad codeert van $(0,0)$ tot dit punt, en het deel dat het pad codeert vanaf dit punt tot $(a,b).$

In de voorbeeldfiguur ligt het punt $(3,4)$ het dichtst bij het lijnstuk en de factorisatie van het christoffelwoord xyxyxyyxyxyy is (xyxyxyy, xyxyy). xyxyxyy is het christoffelwoord $C(4,3)$ en xyxyy is $C(3,2).$ Algemeen geldt: als het punt op het christoffelpad dat het dichtst bij het lijnstuk ligt het punt $(i,j)$ is, dan bestaat de standaardfactorisatie van $C(b,a)$ uit het christoffelwoord met helling $j/i$ en het christoffelwoord met helling $(b-j)/(a-i).$

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 $(0,0),\ (3,4)$ en $(5,7)$, bevat buiten deze drie punten geen andere roosterpunten. De oppervlakte $A$ van deze driehoekde volgt uit de formule van Pick: $A=i+{\tfrac {1}{2}}o-1.$ Daarin is $i=0$ het aantal ingesloten roosterpunten en $o=3$ het aantal hoekpunten, zodat $A=1/2.$

De matrix: ${\begin{bmatrix}i&j\\a-i&b-j\end{bmatrix}}$

behoort tot de speciale lineaire groep $\operatorname {SL} _{2}(\mathbb {Z} )$ van geheeltallige 2×2-matrices waarvan de determinant gelijk is aan 1. Dit betekent ook dat de Farey-afstand tussen de breuken $i/j$ en $(a-i)/(b-j)$ gelijk is aan 1. De breuken $(a-i)/(b-j),\ a/b$ en $i/j$ zijn opeenvolgende breuken in de Farey-rij $\mathrm {F} _{b}$ (in ons voorbeeld: 2/3, 5/7 en 3/4 in $\mathrm {F} _{7}$) en vormen een driehoek in de Farey-graaf. Er bestaat dus een verband tussen christoffelwoorden en de voorstelling van rationale getallen door kettingbreuken.

Bronnen, noten en/of referenties

• Jean Berstel, Aaron Lauve, Christophe Reutenauer, Franco V. Saliola. Combinatorics on Words: Christoffel Words and Repetitions in Words. American Mathematical Society, 2009. ISBN 9780821844809