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.

De complexiteitsfunctie ${\displaystyle 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: ${\displaystyle 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.

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.

Sturmiaanse woorden kan men beschouwen als de discretisatie van een rechte lijn ${\displaystyle y=\alpha x+\rho }$ met helling ${\displaystyle \alpha }$ en intercept ${\displaystyle \rho }$, waarbij ${\displaystyle \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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ over {0,1} is een Sturmiaans woord als en slechts als er twee reële getallen ${\displaystyle \alpha }$ en ${\displaystyle \rho }$ bestaan, met ${\displaystyle \alpha }$ irrationaal, zodanig dat voor elke ${\displaystyle n}$:

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

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

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

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

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

• ${\displaystyle s_{0}=1}$
• ${\displaystyle s_{1}=0}$
• ${\displaystyle 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 ${\displaystyle (s_{n})_{n>0}}$ is een prefix van de volgende, zodat de reeks zelf convergeert naar een oneindig woord, namelijk ${\displaystyle c_{\alpha }}$.

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.^[1]

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.

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.^[1]

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