Sturmiaans woord

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

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[bewerken]

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\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[bewerken]

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[bewerken]

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.

Geschiedenis[bewerken]

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 Sr. 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]

Zie ook[bewerken]

Bronnen, noten en/of referenties