Sturmian slovo - Sturmian word

The Fibonacciho slovo je příkladem šturmského slova. Začátek sekvence řezání zobrazený zde ilustruje začátek slova 0100101001.

v matematika, a Sturmian slovo (Sturmianova sekvence nebo kulečníková sekvence^[1]), pojmenoval podle Jacques Charles François Sturm, je určitý druh nekonečně dlouhý posloupnost znaků. Takovou sekvenci lze vygenerovat zvážením hry o Anglický kulečník na čtvercovém stole. Zasažený míč postupně zasáhne svislé a vodorovné okraje označené 0 a 1 a vytvoří posloupnost písmen.^[2] Tato posloupnost je šturmské slovo.

Definice

Sturmianovy sekvence lze definovat striktně z hlediska jejich kombinatorických vlastností nebo geometricky jako sekvence řezání pro čáry iracionálního sklonu nebo kódování pro iracionální rotace. Tradičně jsou považovány za nekonečné sekvence v abecedě dvou symbolů 0 a 1.

Kombinatorické definice

Sekvence nízké složitosti

Pro nekonečnou sekvenci symbolů w, nechť σ(n) být funkce složitosti z w; tj., σ(n) = počet odlišných souvislé podslovy (faktory) v w délky n. Pak w je Sturmian pokud σ(n) = n + 1 pro všechnyn.

Vyvážené sekvence

Sada X se nazývá binární řetězce vyrovnaný pokud Hammingova hmotnost prvků X trvá maximálně dvě odlišné hodnoty. To znamená pro všechny ${ displaystyle s v X}$ |s|₁ = k nebo |s|₁ = k ' kde |s|₁ je počet 1 s v s.

Nechat w být nekonečnou posloupností 0s a 1s a nechat ${ displaystyle { mathcal {L}} _ {n} (w)}$ označit množinu všechn podřízená slova z w. Sekvence w je Sturmian pokud ${ displaystyle { mathcal {L}} _ {n} (w)}$ je vyvážený pro všechny n a w není nakonec periodický.

Geometrické definice

Řezná sekvence iracionální

Nechat w být nekonečnou posloupností 0s a 1s. Sekvence w je pro některé Sturmian ${ displaystyle x v [0,1)}$ a některé iracionální ${ displaystyle theta in (0, infty)}$, w je realizován jako sekvence řezání linky ${ displaystyle f (t) = theta t + x}$.

Rozdíl sekvencí Beatty

Nechat w = (w_n) být nekonečná sekvence 0 s a 1 s. Sekvence w je Sturmian, je-li rozdíl nehomogenní Beatty sekvence, tedy pro některé ${ displaystyle x v [0,1)}$ a některé iracionální ${ displaystyle theta v (0,1)}$

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

pro všechny ${ displaystyle n}$ nebo

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

pro všechny ${ displaystyle n}$.

Kódování iracionální rotace

Animace zobrazující Sturmianovu sekvenci generovanou iracionální rotací s θ ≈ 0,2882 a X ≈ 0.0789

Pro ${ displaystyle theta v [0,1)}$, definovat ${ displaystyle T _ { theta}: [0,1) až [0,1)}$ podle ${ displaystyle t mapsto t + theta { bmod {1}}}$. Pro ${ displaystyle x v [0,1)}$ definovat θ-kódování X být sekvence (X_n) kde

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

Nechat w být nekonečnou posloupností 0s a 1s. Sekvence w je pro některé Sturmian ${ displaystyle x v [0,1)}$ a některé iracionální ${ displaystyle theta in (0, infty)}$, w je θ-kódováníX.

Diskuse

Příklad

Slavným příkladem (standardního) šturmského slova je Fibonacciho slovo;^[3] jeho sklon je ${ displaystyle 1 / phi}$, kde ${ displaystyle phi}$ je Zlatý řez.

Vyvážené neperiodické sekvence

Sada S konečných binárních slov je vyrovnaný pokud pro každého n podmnožina S_n slov délky n má vlastnost, kterou Hammingova hmotnost slov v S_n trvá maximálně dvě odlišné hodnoty. A vyvážená sekvence je faktor, u kterého je vyvážen soubor faktorů. Vyvážená sekvence má nanejvýš n+1 odlišné faktory délky n.^[4]:43 An neperiodická posloupnost je ten, který nespočívá v konečné posloupnosti následované konečným cyklem. Aperiodická sekvence má alespoň n + 1 výrazný faktor délky n.^[4]:43 Sekvence je Sturmian, jen když je vyvážená a neperiodická.^[4]:43

Sklon a zachycení

A sekvence ${ displaystyle (a_ {n}) _ {n in mathbb {N}}}$ nad {0,1} je Sturmianovo slovo právě tehdy, pokud existují dvě reálná čísla, sklon ${ displaystyle alpha}$ a zachytit ${ displaystyle rho}$, s ${ displaystyle alpha}$ iracionální, takový, že

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

pro všechny ${ displaystyle n}$.^{[5]:284[6]:152} Sturmianovo slovo tedy poskytuje a diskretizace přímky se sklonem ${ displaystyle alpha}$ a zachytitρ. Bez ztráty obecnosti můžeme vždy předpokládat ${ displaystyle 0 < alpha <1}$, protože pro jakékoli celé číslo k my máme

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

Všechna Sturmianova slova odpovídají stejnému sklonu ${ displaystyle alpha}$ mít stejnou sadu faktorů; slovo ${ displaystyle c _ { alpha}}$ odpovídající odposlechu ${ displaystyle rho = 0}$ je standardní slovo nebo charakteristické slovo svahu ${ displaystyle alpha}$.^[5]:283 Proto, pokud ${ displaystyle 0 < alpha <1}$, charakteristické slovo ${ displaystyle c _ { alpha}}$ je první rozdíl z Beatty sekvence odpovídající iracionálnímu číslu ${ displaystyle alpha}$.

Standardní slovo ${ displaystyle c _ { alpha}}$ je také limit posloupnosti slov ${ displaystyle (s_ {n}) _ {n geq 0}}$ definováno rekurzivně takto:

Nechat ${ displaystyle [0; d_ {1} + 1, d_ {2}, ldots, d_ {n}, ldots]}$ být pokračující zlomek expanze ${ displaystyle alpha}$a definovat

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

kde součin mezi slovy je jen jejich zřetězení. Každé slovo v pořadí ${ displaystyle (s_ {n}) _ {n> 0}}$ je předpona z dalších, takže samotná sekvence konverguje na nekonečné slovo, které je ${ displaystyle c _ { alpha}}$.

Nekonečná posloupnost slov ${ displaystyle (s_ {n}) _ {n geq 0}}$ definovaný výše uvedenou rekurzí se nazývá standardní sekvence pro standardní slovo ${ displaystyle c _ { alpha}}$a nekonečná posloupnost d = (d₁, d₂, d₃, ...) nezáporných celých čísel, s d₁ ≥ 0 a d_n > 0 (n ≥ 2), se nazývá jeho direktivní sekvence.

Sturmianovo slovo w nad {0,1} je charakteristické právě tehdy, když oba 0w a 1w jsou Sturmian.^[7]

Frekvence

Li s je nekonečné pořadové slovo a w je konečné slovo, ať μ_N(w) označují počet výskytů w jako faktor v předponě s délky N + |w| - 1. Pokud μ_N(w) má limit jako N→ ∞, říkáme tomu frekvence z w, označeno μ(w).^[4]:73

Pro šturmianské slovo s, každý konečný faktor má frekvenci. The věta o třech mezerách znamená, že faktory pevné délky n mít nanejvýš tři odlišné frekvence, a pokud existují tři hodnoty, pak jedna je součtem ostatních dvou.^[4]:73

Non-binární slova

Pro slova nad velikostí abecedy k větší než 2, definujeme Sturmianovo slovo jako slovo se složitou funkcí n + k − 1.^[6]:6 Mohou být popsány z hlediska sekvence řezání pro k-rozměrný prostor.^[6]:84 Alternativní definice je jako slova minimální složitosti s výhradou, že nebudou nakonec periodická.^[6]:85

Přidružená reálná čísla

Skutečné číslo, pro které číslice s ohledem na určitou pevnou základnu tvoří Sturmianovo slovo, je a transcendentní číslo.^[6]:64,85

Sturmianské endomorfismy

Endomorfismus volný monoid B^∗ na dvoupísmenné abecedě B je Sturmian pokud mapuje všechny Sturmian slovo na Sturmianovo slovo^[8][9] a místně Sturmian pokud mapuje nějaké šturmské slovo na šturmské slovo.^[10] Sturmianské endomorfismy tvoří submonoid monoidu endomorfismů B^∗.^[8]

Definujte endomorfismy φ a ψ B^∗, kde B = {0,1}, podle φ (0) = 01, φ (1) = 0 a ψ (0) = 10, ψ (1) = 0. Potom Já, φ a ψ jsou Sturmian,^[11] a sturmianské endomorfismy z B^∗ jsou přesně ty endomorfismy v submonoidu monomeru endomorfismu generovaného {Já, φ, ψ}.^[9][10][7]

Primitivní substitucí je Sturmian, pokud je obraz slova 10010010100101 vyvážený.^{[je zapotřebí objasnění ][9][12]}

Dějiny

Ačkoli studie o Sturmianových slovech sahá až do roku Johann III Bernoulli (1772),^[13][5]:295 to bylo Gustav A. Hedlund a Marston Morse v roce 1940, který vytvořil tento termín Sturmian odkazovat se na takové sekvence,^[5]:295[14] na počest matematika Jacques Charles François Sturm kvůli vztahu s Sturmova věta o srovnání.^[6]:114

Viz také

• Sekvence řezání
• Slovo (teorie skupin)
• Morfické slovo
• Slovo Lyndon

Reference

Další čtení

• Bugeaud, Yann (2012). Distribuce modulo one a diofantická aproximace. Cambridge Tracts v matematice. 193. Cambridge: Cambridge University Press. ISBN  978-0-521-11169-0. Zbl  1260.11001.
• Lothaire, M. (2011). Algebraická kombinatorika slov. Encyklopedie matematiky a její aplikace. 90. S předmluvou Jean Berstel a Dominique Perrin (Dotisk vázané knihy z roku 2002, ed.). Cambridge University Press. ISBN  978-0-521-18071-9. Zbl  1221.68183.