Sturmsches Wort

Ein Sturmsches Wort ist in der Kombinatorik auf Wörtern ein unendliches Wort, das so wenige verschiedene Faktoren wie möglich hat, ohne periodisch zu sein. Jedes Sturmsche Wort besteht aus genau zwei verschiedenen Buchstaben. Es ist benannt nach Charles-François Sturm.

Sei ${\displaystyle P}$ die Komplexitätsfunktion, die einem unendlichen Wort und einer Zahl ${\displaystyle n\in \mathbb {N} _{0}}$ die Anzahl der verschiedenen Faktoren der Länge ${\displaystyle n}$ im Wort zuordnet.

Ein Sturmsches Wort ist ein unendliches Wort ${\displaystyle x}$ mit ${\displaystyle P(x,n)=n+1}$ für alle ${\displaystyle n\in \mathbb {N} _{0}}$.^[1]

Nach dem Morse-Hedlund-Theorem lassen sich Sturmsche Wörter auch als mechanische Wörter und über die Balance von Wörtern definieren.^[1]

Für ${\displaystyle \alpha ,\rho \in \mathbb {R} }$ mit ${\displaystyle 0\leq \alpha \leq 1}$ sind die unendlichen Wörter ${\displaystyle s_{\alpha ,\rho },s'_{\alpha ,\rho }:\mathbb {N} _{0}\to \{0,1\}}$ wie folgt definiert: ${\displaystyle s_{\alpha ,\rho }(n)=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor }$

${\displaystyle s'_{\alpha ,\rho }(n)=\lceil \alpha (n+1)+\rho \rceil -\lceil \alpha n+\rho \rceil }$

${\displaystyle s_{\alpha ,\rho }}$ wird unteres und ${\displaystyle s'_{\alpha ,\rho }(n)}$ oberes mechanisches Wort genannt. Ein mechanisches Wort ist irrational, wenn ${\displaystyle \alpha }$ irrational ist.

Ein unendliches Wort ist genau dann ein Sturmsches Wort, wenn es irrational mechanisch ist.^[1]

Eine Menge ${\displaystyle X\subseteq \{a,b\}^{*}}$ ist balanciert, wenn die Häufigkeit von ${\displaystyle a}$ sich in allen Wörtern gleicher Länge um höchstens 1 unterscheidet. Ein unendliches Wort ist balanciert, wenn die Menge seiner Faktoren balanciert ist.

Ein unendliches Wort ${\displaystyle x}$ ist aperiodisch, wenn es keine Wörter ${\displaystyle y,z}$ mit ${\displaystyle x=yz^{\omega }}$ gibt, wobei ${\displaystyle z^{\omega }}$ die unendliche Konkatenation von ${\displaystyle z}$ ist.

Ein unendliches Wort ist genau dann ein Sturmsches Wort, wenn es aperiodisch und balanciert ist.^[1]

Weil für jedes Sturmsche Wort ${\displaystyle x}$ ${\displaystyle P(x,1)=1+1=2}$ gilt, besteht es stets aus genau zwei Buchstaben.

Ein Beispiel für ein Sturmsches Wort ist das Fibonacci-Wort.

Ein Suffix eines Sturmschen Worts ist selbst ein Sturmsches Wort.

Jedes Sturmsche Wort lässt sich auch als Schnittfolge einer Geraden mit einem Koordinatengitter charakterisieren. Das Gitter besitzt dabei Linien an allen ganzzahligen, positiven Koordinaten. Das Sturmsche Wort besteht dann aus einer 0 für jeden Schnitt mit einer vertikalen Linie und einer 1 für jeden Schnitt mit einer horizontalen Linie, nach aufsteigenden Koordinaten geordnet.^[1]

Die Geschichte der Sturmschen Wörter reicht zurück bis zu Johann III Bernoulli im Jahre 1772. Das erste umfassende Werk über Sturmsche Wörter wurde 1940 von Gustav Hedlund und Harold Calvin Marston Morse veröffentlicht. Von ihnen stammt auch die Benennung nach Charles-François Sturm.^[1]

1. ↑ ^{a b c d e f} M. Lothaire: Algebraic Combinatorics on Words. Cambridge University Press, S. 40 ff.