シュトゥルム語

数学において、シュトゥルム語（シュトゥルム列またはビリヤード列^[1]）は、ジャック・シャルル・フランソワ・シュトゥルムにちなんで名付けられた、ある種の無限に長い文字列である。このような列は、正方形のテーブルでの英国式ビリヤードのゲームを考えることによって生成することができる。打たれたボールは、0と1のラベルが付けられた垂直方向と水平方向のエッジに順番に当たり、文字の列を生成する。^[2]この列がシュトゥルム語である。

シュトゥルム数列は、組み合わせ特性の観点から厳密に定義することも、無理数傾斜の直線の切断列や無理数回転のコードとして幾何学的に定義することもできます。これらは伝統的に、2 つの記号 0 と 1 のアルファベット上の無限数列であると考えられています。

無限のシンボルシーケンスwについて、σ ( n ) をwの複雑性関数とします。つまり、σ ( n ) =長さnのw内の異なる連続するサブワード (因子)の数です。すべてのnに対してσ ( n ) =  n  + 1 である場合、 w はSturmian です。

バイナリ文字列のセットX は、 Xの要素のハミング重みが最大で 2 つの異なる値を取る場合、バランスが取れていると呼ばれます。つまり、任意の| s | ₁  =  kまたは | s | ₁  =  k'であり、 | s | _1はs内の 1 の数です。 ${\displaystyle s\in X}$

w を0 と 1 の無限シーケンスとし、wの長さn のすべてのサブワードの集合を とします。シーケンスwが Sturmian であるとは、がすべてのnに対してバランスが取れていて、w が最終的に周期的でない場合です。 ${\displaystyle {\mathcal {L}}_{n}(w)}$${\displaystyle {\mathcal {L}}_{n}(w)}$

w を0 と 1 の無限シーケンスとします。シーケンスwがシュトゥルムであるとは、ある とある無理数に対して、w が直線 の切断シーケンスとして実現される場合です。 ${\displaystyle x\in [0,1)}$${\displaystyle \theta \in (0,\infty )}$${\displaystyle f(t)=\theta t+x}$

w  = ( w _n ) を 0 と 1 の無限列とする。列wがシュトゥルム列であるとは、非同次ビーティ列の差、つまり、ある無理数とある無理数に対して、${\displaystyle x\in [0,1)}$${\displaystyle \theta \in (0,1)}$

${\displaystyle w_{n}=\lfloor n\theta +x\rfloor -\lfloor (n-1)\theta +x\rfloor }$

全員または ${\displaystyle n}$

${\displaystyle w_{n}=\lceil n\theta +x\rceil -\lceil (n-1)\theta +x\rceil }$

すべてに対して。 ${\displaystyle n}$

については、によって定義されます。 については、xのθコーディングをシーケンス ( x _n ) として定義します。ここで ${\displaystyle \theta \in [0,1)}$${\displaystyle T_{\theta }:[0,1)\to [0,1)}$${\displaystyle t\mapsto t+\theta {\bmod {1}}}$${\displaystyle x\in [0,1)}$

${\displaystyle x_{n}={\begin{cases}1&{\text{if }}T_{\theta }^{n}(x)\in [0,\theta ),\\0&{\text{else}}.\end{cases}}}$

w を0 と 1 の無限シーケンスとします。シーケンスwがシュトゥルムであるとは、ある とある無理数に対して、w がxの θコーディングである場合です。 ${\displaystyle x\in [0,1)}$${\displaystyle \theta \in (0,\infty )}$

（標準的な）シュトゥルム語の有名な例はフィボナッチ語です。^[3]その傾きは で、 は黄金比です。 ${\displaystyle 1/\phi }$${\displaystyle \phi }$

有限のバイナリワードの集合Sがバランスしているとは、各nに対して、長さnのワードの部分集合S _nが、 S _n内のワードのハミング重みが最大で 2 つの異なる値を取るという特性を持つ場合です。バランスの取れたシーケンスとは、要素の集合がバランスの取れたシーケンスです。バランスの取れたシーケンスには、長さnの異なる要素が最大でn +1 個あります。^{[4] : 43} 非周期シーケンスとは、有限シーケンスとそれに続く有限サイクルで構成されていないシーケンスです。非周期シーケンスには、長さn の異なる要素が少なくともn + 1 個あります。^{[4] : 43} シーケンスがシュトゥルム的であるためには、バランスが取れていて非周期的である必要があります。^{[4] : 43}

{0,1}上の数列が シュトゥルム語となるのは、2つの実数、傾き、切片が存在し、無理数であって、 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ ${\displaystyle \alpha }$ ${\displaystyle \rho }$${\displaystyle \alpha }$

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

全ての に対して となる。^{[5] : 284  [6] : 152}このように、シュトゥルム語は、傾きと切片 ρを持つ直線の離散化を提供する。一般性を失うことなく、任意の整数kに対して となる ため、常に と仮定することができる。${\displaystyle n}$${\displaystyle \alpha }$${\displaystyle 0<\alpha <1}$

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

同じ傾きに対応するすべてのスターム語は同じ因数集合を持ち、切片に対応する語は傾きの標準語または特性語である。^{[5] ：283}したがって、 の場合、特性語は無理数 に対応するビーティ数列の最初の差である。 ${\displaystyle \alpha }$${\displaystyle c_{\alpha }}$${\displaystyle \rho =0}$${\displaystyle \alpha }$${\displaystyle 0<\alpha <1}$${\displaystyle c_{\alpha }}$${\displaystyle \alpha }$

標準単語は、次のように再帰的に定義された単語のシーケンスの極限でもあります。 ${\displaystyle c_{\alpha }}$${\displaystyle (s_{n})_{n\geq 0}}$

を の連分数展開とし、次のように定義する。 ${\displaystyle [0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]}$${\displaystyle \alpha }$

• ${\displaystyle s_{0}=1}$
• ${\displaystyle s_{1}=0}$
• ${\displaystyle s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ for }}n>0}$

ここで、単語間の積は、それらの連結に過ぎません。シーケンス内の各単語は、次の単語の接頭辞であるため、シーケンス自体は無限の単語、つまり に収束します。 ${\displaystyle (s_{n})_{n>0}}$${\displaystyle c_{\alpha }}$

上記の再帰によって定義される単語の無限列は標準単語の標準列と呼ばれ、非負整数の無限列d = ( d ₁ , d ₂ , d _{3 , ...)（} d ₁ ≥ 0かつd _n > 0（n ≥ 2））はその指示列と呼ばれます。 ${\displaystyle (s_{n})_{n\geq 0}}$${\displaystyle c_{\alpha }}$

{0,1}上のシュトゥルム語wが特徴語となるのは、 0wと1wの両方がシュトゥルム語である場合に限ります。^[7]

s が無限列語でw が有限語である場合、長さN  + | w | − 1のsの接頭辞におけるwの出現回数をμ _N ( w ) で表す。N →∞ でμ _N ( w ) に極限がある場合、これをw の頻度と呼び、 μ ( w )で表す。^{[4] : 73}

シュトゥルム語sでは、すべての有限因子は頻度を持つ。3ギャップ定理は、固定長nの因子は最大で3つの異なる頻度を持ち、3つの値がある場合、1つは他の2つの値の合計であることを意味する。^{[4] : 73}

2より大きいサイズkのアルファベット上の単語について、複雑度関数n  +  k  − 1を持つ単語をシュトゥルム語と定義する。^{[6] : 6}これらはk次元空間 の切断列で記述できる。[6] ^{: 84} 別の定義は、究極的には周期的ではないことを条件として、複雑度が最小の単語である。^{[ 6] : 85}

ある固定された基数に対する数字がシュトゥルム語を形成する実数は超越数である。^{[6] : 64, 85}

2 文字のアルファベットB上の自由モノイド B ^∗の同型写像は、すべてのスターミアンの単語をスターミアンの単語にマッピングする場合はスターミアンであり^{[8] [9]}、一部のスターミアンの単語をスターミアンの単語にマッピングする場合は局所的にスターミアンです。 ^{[10]スターミアン同型写像は、} B ^∗ の同型写像のモノイドのサブモノイドを形成します。^[8]

B ^∗の自己準同型 φ と ψ を、B = {0,1} として、 φ(0) = 01、 φ(1) = 0 および ψ(0) = 10、 ψ(1) = 0 と定義する。このとき、I、 φ 、 ψ はシュトゥルム写像となり、^[11] B ^∗のシュトゥルム写像は、 { I 、φ、ψ}によって生成される自己準同型モノイドのサブモノイド内の自己準同型とまったく同じである。^{[9] [10] [7]}

射がシュトゥルム射であるためには、単語10010010100101の像がバランスのとれた列であることが必要である。つまり、各nに対して、長さnの部分単語のハミング重みは最大で2つの異なる値を取る。^{[9] [12]}

シュトゥルム語の研究はヨハン・ベルヌーイ（1772）にまで遡るが、 ^{[13] [5] : 295} 1940年にグスタフ・A・ヘドランドとマーストン・モースが、シュトゥルム比較定理との関係から、数学者ジャック・シャルル・フランソワ・シュトゥルムに敬意を表して、そのような列を指すためにシュトゥルム語という用語を造語した。^{[ 5] :  295  [14]}

• 切断シーケンス
• 単語（群論）
• 形態素
• リンドンの言葉

• Bugeaud, Yann (2012)。分布法 1 とディオファントス近似。ケンブリッジ数学論文集。第 193 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-11169-0.ZBL1260.11001  。​
• ロテール、M. (2011)。単語の代数的組合せ論。数学とその応用百科事典。第90巻。ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）。ケンブリッジ大学出版局。ISBN 978-0-521-18071-9.ZBL1221.68183  。​