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.

Definition

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

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

Morse-Hedlund-Theorem

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

Mechanische Wörter

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

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

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

Ein unendliches Wort ist genau dann ein Sturmsches Wort, wenn es irrational mechanisch ist.

Balancierte Wörter

Eine Menge $X\subseteq \{a,b\}^{*}$ ist balanciert, wenn die Häufigkeit von $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 $x$ ist aperiodisch, wenn es keine Wörter $y,z$ mit $x=yz^{\omega }$ gibt, wobei $z^{\omega }$ die unendliche Konkatenation von $z$ ist.

Ein unendliches Wort ist genau dann ein Sturmsches Wort, wenn es aperiodisch und balanciert ist.

Eigenschaften

Charakterisierung des Fibonacci-Worts 0100101001… als Schnittfolge

Weil für jedes Sturmsche Wort $x$ $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.

Geschichte

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.