Sturmiaans woord

Een Sturmiaans woord, genoemd naar de wiskundige Jacques Charles François Sturm, is in de wiskunde een bepaalde, oneindig lange rij van symbolen (een "woord") uit een eindig alfabet. Sturmiaanse woorden kunnen op verschillende, equivalente manieren gedefinieerd worden.

Definitie met complexiteitsfunctie

De complexiteitsfunctie $C_{w}(n)$ van een woord w is het aantal verschillende factoren (substrings) van lengte n in w. Een woord w is Sturmiaans als voor elk positief natuurlijk getal n geldt: $C_{w}(n)=n+1$, dat wil zeggen dat w voor elke n exact n+1 verschillende factoren (substrings) heeft van lengte n.

Als n=1, betekent dit dat er exact twee verschillende factoren van lengte 1 zijn. Hieruit volgt dat het volledige woord bestaat uit twee verschillende symbolen uit het alfabet: Sturmiaanse woorden zijn binaire woorden. We kunnen die symbolen zonder verlies van algemeenheid aanduiden met 0 en 1.

Voorbeeld

Het Sturmiaans woord

10101001010010101001010010101001010010100 ...

heeft voor n=4 de vijf verschillende factoren: 1010, 0101, 0010, 1001, 0100.

Voor n=5 zijn de zes verschillende factoren: 10101, 01010, 10100, 00101, 10010, 01001.

Het oneindige Fibonacciwoord is een Sturmiaans woord.

Meetkundige definitie

Voorstelling van een Sturmiaans woord door een rechte vanuit de oorsprong (ρ=0); hier met helling φ-1, waarbij φ de gulden snede is en het Sturmiaans woord het Fibonacciwoord is.

Sturmiaanse woorden kan men beschouwen als de discretisatie van een rechte lijn $y=\alpha x+\rho$ met helling $\alpha$ en intercept $\rho$, waarbij $\alpha$ een irrationaal getal is. De snijpunten van de lijn met de horizontale en verticale lijnen van de gehele coördinaten duidt men aan met "1" respectievelijk met "0".

Een formele definitie luidt:

Een rij $(a_{n})_{n\in \mathbb {N} }$ over {0,1} is een Sturmiaans woord als en slechts als er twee reële getallen $\alpha$ en $\rho$ bestaan, met $\alpha$ irrationaal, zodanig dat voor elke $n$:

$a_{n}=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor -\lfloor \alpha \rfloor$

$\lfloor x\rfloor$ is hier de entier-functie. We kunnen zonder verlies van algemeenheid aannemen dat $0<\alpha <1$.

Alle Sturmiaanse woorden die met dezelfde helling $\alpha$ overeenkomen, hebben dezelfde verzameling factoren. Het woord $c_{\alpha }$ waarvoor de intercept $\rho =0$ noemt men het standaardwoord of karakteristiek woord van de helling $\alpha$.

Definitie met kettingbreuk

Het standaardwoord $c_{\alpha }$ kan ook gedefinieerd worden met behulp van de kettingbreukexpansie van $\alpha$.

Stel $[0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]$ stelt de oneindige kettingbreuk voor van $\alpha$, en stel

• $s_{0}=1$
• $s_{1}=0$
• $s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ voor }}n>0$

waarbij het "product" van twee woorden hun concatenatie is. Elk woord in de rij $(s_{n})_{n>0}$ is een prefix van de volgende, zodat de reeks zelf convergeert naar een oneindig woord, namelijk $c_{\alpha }$.

Definitie met palindromen

Een oneindig woord is Sturmiaans als en slechts als het exact één palindroom van lengte n bevat als n een even natuurlijk getal is en twee verschillende palindromen van lengte n als n een oneven natuurlijk getal is.

Voor het voorbeeld hierboven zijn dit:

• voor n = 1: 0 en 1
• voor n = 2: 00
• voor n = 3: 101 en 010
• voor n = 4: 1001
• voor n = 5: 10101 en 01010
• voor n = 6: 010010, enz.

Geschiedenis

Reeksen die in verband staan met Sturmiaanse woorden werden reeds in 1772 beschreven door de astronoom Jean Bernouilli III, uitgaande van de kettingbreukexpansie van een positief irrationaal getal. Andrej Markov bewees in 1882 de geldigheid van Bernoulli's beschrijving. De term "Sturmiaanse reeksen" werd echter gegeven door Hedlund en Morse in 1940, die deze reeksen bestudeerden in het kader van symbolische dynamica.

Zie ook

• Quasikristal: Sturmiaanse woorden zijn aperiodiek. Men kan ze interpreteren als de eenvoudigste familie van quasikristallen.
• Christoffelwoorden

Bronnen, noten en/of referenties