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 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: , 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 met helling en intercept , waarbij 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 over {0,1} is een Sturmiaans woord als en slechts als er twee reële getallen en bestaan, met irrationaal, zodanig dat voor elke :

is hier de entier-functie. We kunnen zonder verlies van algemeenheid aannemen dat .

Alle Sturmiaanse woorden die met dezelfde helling overeenkomen, hebben dezelfde verzameling factoren. Het woord waarvoor de intercept noemt men het standaardwoord of karakteristiek woord van de helling .

Definitie met kettingbreuk[bewerken]

Het standaardwoord kan ook gedefinieerd worden met behulp van de kettingbreukexpansie van .

Stel stelt de oneindige kettingbreuk voor van , en stel

waarbij het "product" van twee woorden hun concatenatie is. Elk woord in de rij is een prefix van de volgende, zodat de reeks zelf convergeert naar een oneindig woord, namelijk .

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]