스터미어

수학에서 자크 샤를 프랑수아 스투름의 이름을 딴 스터미어 단어(Sturmian sequence 또는 당구 순서^[1])는 어떤 종류의 무한히 긴 문자 순서다.네모난 테이블 위에서 영국 당구 경기를 생각하면 이런 순서가 나올 수 있다.스트라이크 볼은 0과 1로 표시된 수직 및 수평 가장자리에 연속적으로 부딪혀 일련의 문자를 생성한다.^[2]이 순서는 스터미어어다.

정의

스터미어 시퀀스는 결합 특성 측면에서 엄격하게 정의하거나 비합리적인 기울기의 선이나 비합리적인 회전을 위한 코딩의 절단 시퀀스로 기하학적으로 정의할 수 있다.그것들은 전통적으로 두 기호 0과 1의 알파벳에 무한 시퀀스로 받아들여진다.

결합 정의

복잡성이 낮은 순서

기호 w의 무한 순서인 경우, σ(n)을 w의 복잡함수가 되게 한다. 즉, σ(n) = 길이가 n인 구별되는 연속 하위 단어(요인)의 수입니다.그러면 w는 모든 n에 대해 σ(n) = n + 1이면 스터미안이다.

균형 시퀀스

이항 문자열의 집합 X는 X 원소의 해밍 가중치가 최대 두 개의 구별되는 값을 갖는다면 균형이라고 불린다.즉, $s{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle s\in$ X$}$ = k 또는 s = k'에 대해 s는 1초의 수입니다.

${\displaystyle w_{}}$를 0과 1의 무한 시퀀스로 하고 L $n{\displaystyle {\mathcal{}}_{}}$ (${\displaystyle {}_{}w}$ $){\displaystyle {\mathcal{L}_{n}(w)}$이 w의 모든 length-n 하위 워드의 집합을 나타내도록$$ 한다.$L{\displaystyle {\mathcal{}}_{}}$ ${\displaystyle n_{}}$( ${\displaystyle w}$) ${\displaystyle {\mathcal{L}_{n}(w)}$이(가) 모든 n에 대해 균형잡히고$$ w가 결국 주기적이지 않으면 시퀀스 w는 스터미안이다.

기하학적 정의

비합리성의 절단 순서

w는 0초와 1초의 무한 시퀀스가 되도록 하자.The sequence w is Sturmian if for some ${\displaystyle x\in [0,1)}$ and some irrational ${\displaystyle \theta \in (0,\infty )}$, w is realized as the cutting sequence of the line ${\displaystyle f(t)=\theta t+x}$.

비트티 시퀀스의 차이

w = (w_n) 0과 1의 무한 시퀀스가 되게 한다.순서 w가 비균형 Beatty 시퀀스의 차이인 경우, 즉 일부 ${\displaystyle \mathrm{x}}$ ${\displaystyle \in }$[ 0 , ${\displaystyle 1}$) ${\displaystyle x\in[0,1$)과$$ 일부 비합리적인 $\theta {\displaystyle }$(${\displaystyle 0}$, 1${\displaystyle }$) ${\displaysty \theta \in (0,1$)의 경우 순서 w는 Sturmian이다.

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

$모든{\displaystyle }$ n ${\displaystyle n}$ 또는$$

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

$모든{\displaystyle }$ n ${\displaystyle n}$에 대해$.$

비이성 회전 부호화

For ${\displaystyle \theta \in [0,1)}$, define ${\displaystyle T_{\theta }:[0,1)\to [0,1)}$ by ${\displaystyle t\mapsto t+\theta {\bmod {1}}}$. For ${\displaystyle x\in [0,1)}$ define the θ-coding of x to be the sequence (x_n) where

${\displaystyle x_{n}={\begin{case}1&{\text}{{}t_{\teta }^{n(x)\in[0,\theta ])\\\0&{\text{else}}}.\end{case}}}$

w는 0초와 1초의 무한 시퀀스가 되도록 하자.sequence w는 sturmian이며, 일부 $x{\displaystyle }$ ${\displaystyle \in }$[${\displaystyle 0}$, 1${\displaystyle }$) ${\displaystyle x\in [0,$ ${\displaystyle \infty ]}$에 대한 비합리적인 $irrational{\displaystyle }$(${\displaystyle 0}$, ${\displaystyle \theta \in (0,\infty$ $)\},$ w는 x의 θ-코딩이다.

토론

예

(표준) 스터미어 단어의 유명한 예로는 피보나치어(^[3]Fibonacci word)가 있다. 그 경사는 $1{\displaystyle \mathrm{}}$ /${\displaystyle \varphi }$ ${\displaystyle 1/\pi }$이며$,$ 여기서 $\varphi {\displaystyle }$ ${\displaysty \pi }$은 황금 비율이다.

균형잡힌 주기적 시퀀스

길이 n의 각 부분집합_n S가 최대_n 두 개의 구별되는 값을 갖는 S 단어의 해밍 가중치를 갖는다면 유한 이항 단어의 집합 S는 균형을 이룬다.균형잡힌 순서는 요인 집합이 균형잡힌 순서 중 하나이다.균형 잡힌 시퀀스는 최대 n+1의 길이 n의 구별되는 인자를 가진다.^{[4]: 43} 주기적 시퀀스는 유한 시퀀스와 유한 사이클로 구성되지 않는 시퀀스다.주기적 시퀀스에는 길이 n에 대한 최소 n + 1의 구별되는 요인이 있다.^{[4]: 43} 순서는 균형잡히고 주기적인 경우에만 스터미언이다.^{[4]: 43}

경사 및 절편

A sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ over {0,1} is a Sturmian word if and only if there exist two real numbers, the slope ${\displaystyle \alpha }$ and the intercept ${\displaystyle \rho }$, with ${\displaystyle \alpha }$ irrational, such that

${\displaystyle a_{n}=\lfloor \loor \loor \loor \loor \loor \loor \lloor \lloor \lloor }}$

$모든{\displaystyle }$ n ${\displaystyle n}$에 대해$.$^{[5]: 284 [6]: 152} 따라서 스터미어 단어는 경사 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$과(와) 절편 ρ으로 직선의 분석을 제공한다.일반성의 상실 없이, 우리는 항상 < < 1 ${\displaystyle$ 0$<\alpha <$1}을$($를) 가정할 수 있다 왜냐하면 어떤 정수 k에 대해서도 우리가 가지고 있기 때문이다.

$\displaystyle \llloor (\floor (\floor +k)(n+1)+\rho \lloor -\llloor -\llloor =a_{n}.}$

{\displaystyle \alpha}요인 같은 표준 군이 모두Sturmian 단어를 똑같이 비탈 면에 α, 그 단어 c({\displaystyle c_{\alpha}}은 요격 ρ에 해당하는)0{\displaystyle\rho =0}은 표준 단어나 경사의 특징 말 α{\displaystyle \alpha}.[5]:283그래서다. 0<>α<> ${\displaystyle 0<\alpha <1$ 특징적인 단어 ${\displaystyle {c\alpha }_{}}$ ${\$은 비합리적인 숫자 $\alpha {\displaystyle }$ ${\displaystyle \alpha$}에 해당하는 Beatty 시퀀스의 첫 번째 차이점이다$.$

표준단어$${\$displaystyle c_{\alpha$ ${\displaystyle {\}\}}_{}}$은(${\displaystyle {}_{}}$ n ) n words 0 $displaystyle (s_{n})_{n\geq$ 0$}}}$은 다음과 같이 재귀적으로 정의된 일련의$$ 단어의 한계이기도 하다$$.

$[{\displaystyle }$ ${\displaystyle 0;}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$+ ${\displaystyle 1}$,${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle d_{}}$ n ,${\displaystyle ]}$ ${\displaystyle [0;d_{1}+1,d_{2},\ldots,d_{n},\$$ldots ]}$을(를$)$ $\alpha$의 지속적인 부분 확장이 되게$$ 하고 정의한다$.$

• ${\displaystyle s_{0}=1}$
• ${\displaystyle s_{1}=0}$
• ${\displaystyle s_{n+1}=s_{n}^{d_{n}s_{n-1}{{n-1}{\text{{{n}}의 경우$

말 사이의 산물은 단지 그들의 결합일 뿐이다.시퀀스 n)> 0{\$displaystyle (s_{n}_{n>0}}}$의 모든 단어는 다음 단어의 접두사여서 시퀀스 자체가 무한단어로 수렴되는데, 이는 ${\displaystyle {c\alpha }_{}}$ ${\$이다$.$

단어의(sn)n그 무한 수열 ≥ 0{\displaystyle(s_{n})_{0n\geq}}위의 반복으로 명시한 표준 워드 c({\displaystyle c_{\alpha}}, 비음의 정수의 무한한 시퀀스 d)(1, d2, 음,...), 1≥ 0과dn하고, 0(n≥ 2), d라는 표준 계열이라고 불린다irective 순서를 정하다

{0,1}을(를) 초과하는 스터미어 단어는 0w와 1w가 모두 스터미어인 경우에만 특성이 있다.^[7]

주파수

s가 무한 시퀀스 워드이고 w가 유한한 워드라면 μ_N(w)는 길이 N + w - 1의 s 접두사 인자로 w의 발생 횟수를 나타내도록 한다. μ_N(w)가 N→10으로 한도가 있으면 이를 μ(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]

Define endomorphisms φ and ψ of B^∗, where B = {0,1}, by φ(0) = 01, φ(1) = 0 and ψ(0) = 10, ψ(1) = 0. Then I, φ and ψ are Sturmian,^[11] and the Sturmian endomorphisms of B^∗ are precisely those endomorphisms in the submonoid of the endomorphism monoid generated by {I,φ,ψ}.^[9][10][7]

형태론은 10010010100101이라는 단어의 이미지가 균형 잡힌 순서인 경우에만 스터미언이다. 즉, 각 n에 대해 길이의 하위 단어들인 해밍 가중치는 최대 두 개의 뚜렷한 값을 취한다.^[9][12]

역사

스투르미아의 단어에 대한 연구는 요한 3세 베르누이(1772년)로 거슬러 올라가지만,^{[13][5]: 295} 구스타프 A였다. 1940년 슈투르미안(Sturmian)이라는 용어를 만들어 수학자 자크 샤를 프랑수아 스투름(Jacques Charles Francois Sturm)을 기리는 의미에서 슈투르미안(Sturm)이라는 용어를 만든 헤들룬드와 마스턴 모스(Morse)는 슈투르엠 비교 정리와의 관계 때문에 이런 서열을 가리켰다.^{[5]: 295 [14][6]: 114}

참고 항목

• 절삭순서
• 단어(그룹 이론)
• 형태어
• 린든어

참조

추가 읽기

• Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl 1260.11001.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.