WikiDer > Штурмское слово

Sturmian word

В Слово Фибоначчи - пример штурмского слова. Начало последовательность резки здесь показано начало слова 0100101001.

В математика, а Штурмское слово (Штурмовская последовательность или же бильярдная последовательность^[1]), названный в честь Жак Шарль Франсуа Штурм, это своего рода бесконечно длинный последовательность символов. Такую последовательность можно создать, рассматривая игру Английский бильярд на квадратном столе. Ударенный мяч последовательно попадает в вертикальные и горизонтальные края, обозначенные 0 и 1, образуя последовательность букв.^[2] Эта последовательность - штурмовское слово.

Определение

Последовательности Штурма могут быть определены строго в терминах их комбинаторных свойств или геометрически как последовательность резки для линий иррационального наклона или кодировки для иррациональные вращения. Традиционно они считаются бесконечными последовательностями в алфавите двух символов 0 и 1.

Комбинаторные определения

Последовательности невысокой сложности

Для бесконечной последовательности символов ш, позволять σ(п) быть функция сложности из ш; т.е. σ(п) = количество различных смежные подслова (факторы) в ш длины п. потом ш Штурм, если σ(п) = п +1 для всехп.

Сбалансированные последовательности

Множество Икс двоичных строк называется сбалансированный если Вес Хэмминга элементов Икс принимает не более двух различных значений. То есть для любого ${ displaystyle s in X}$ |s|₁ = k или |s|₁ = k ' где |s|₁ это количество единиц в s.

Позволять ш - бесконечная последовательность нулей и единиц, и пусть ${ Displaystyle { mathcal {L}} _ {п} (ш)}$ обозначают множество всей длины-п подслова ш. Последовательность ш Штурм, если ${ Displaystyle { mathcal {L}} _ {п} (ш)}$ сбалансирован для всех п и ш в конечном итоге не является периодическим.

Геометрические определения

Последовательность резки иррационального

Позволять ш - бесконечная последовательность нулей и единиц. Последовательность ш Штурмовский, если для некоторых ${ Displaystyle х в [0,1)}$ и некоторые иррациональные ${ Displaystyle тета в (0, infty)}$ , ш реализуется как последовательность резки линии ${ Displaystyle е (т) = тета т + х}$ .

Различие последовательностей Битти

Позволять ш = (ш_п) - бесконечная последовательность нулей и единиц. Последовательность ш является штурмовским, если это разность неоднородных Битти последовательности, то есть для некоторых ${ Displaystyle х в [0,1)}$ и некоторые иррациональные ${ Displaystyle тета в (0,1)}$

{ Displaystyle w_ {п} = lfloor n theta + x rfloor - lfloor (n-1) theta + x rfloor}

для всех ${ displaystyle n}$ или же

{ Displaystyle w_ {п} = lceil п тета + х rceil - lceil (п-1) тета + х rceil}

для всех ${ displaystyle n}$ .

Кодирование иррационального вращения

Анимация, показывающая последовательность Штурма, созданную иррациональным вращением с θ ≈ 0,2882 и Икс ≈ 0.0789

За ${ Displaystyle тета в [0,1)}$ , определять ${ displaystyle T _ { theta}: [0,1) to [0,1)}$ к ${ Displaystyle т mapsto т + тета { bmod {1}}}$ . За ${ Displaystyle х в [0,1)}$ определить θ-кодирование Икс быть последовательностью (Икс_п) куда

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

Позволять ш - бесконечная последовательность нулей и единиц. Последовательность ш Штурмовский, если для некоторых ${ Displaystyle х в [0,1)}$ и некоторые иррациональные ${ Displaystyle тета в (0, infty)}$ , ш это θ-кодированиеИкс.

Обсуждение

Пример

Известный пример (стандартного) штурмианского слова - это Слово Фибоначчи;^[3] его наклон ${ displaystyle 1 / phi}$ , куда ${ displaystyle phi}$ это Золотое сечение.

Сбалансированные апериодические последовательности

Множество S конечных двоичных слов сбалансированный если для каждого п подмножество S_п слов длины п обладает тем свойством, что Вес Хэмминга слов в S_п принимает не более двух различных значений. А сбалансированная последовательность тот, для которого сбалансирован набор факторов. Сбалансированная последовательность имеет не более п+1 различные факторы длины п.^[4]^:43 An апериодическая последовательность это тот, который не состоит из конечной последовательности, за которой следует конечный цикл. Апериодическая последовательность имеет не менее п + 1 различный фактор длины п.^[4]^:43 Последовательность является штурмовской тогда и только тогда, когда она сбалансирована и апериодична.^[4]^:43

Наклон и пересечение

А последовательность ${ Displaystyle (а_ {п}) _ {п в mathbb {N}}}$ над {0,1} - штурмовское слово тогда и только тогда, когда существует два действительные числа, то склон ${ displaystyle alpha}$ и перехватить ${ displaystyle rho}$ , с ${ displaystyle alpha}$ иррациональный, так что

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

для всех ${ displaystyle n}$ .^[5]^:284^[6]^:152 Таким образом, штурмовское слово дает дискретизация прямой с уклоном ${ displaystyle alpha}$ и перехватитьρ. Без ограничения общности всегда можно предположить ${ Displaystyle 0 < альфа <1}$ , потому что для любого целого k у нас есть

{ Displaystyle lfloor ( альфа + к) (n + 1) + rho rfloor - lfloor ( alpha + k) n + rho rfloor - lfloor alpha + k rfloor = a_ {n}. }

Все штурмовские слова, соответствующие одному наклону ${ displaystyle alpha}$ одинаковый набор факторов; слово ${ displaystyle c _ { alpha}}$ соответствует перехвату ${ displaystyle rho = 0}$ это стандартное слово или же характерное слово склона ${ displaystyle alpha}$ .^[5]^:283 Следовательно, если ${ Displaystyle 0 < альфа <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}}$ .

Бесконечная последовательность слов ${ displaystyle (s_ {n}) _ {n geq 0}}$ определенная выше рекурсией, называется стандартная последовательность для стандартного слова ${ displaystyle c _ { alpha}}$ , и бесконечная последовательность d = (d₁, d₂, d₃, ...) неотрицательных целых чисел, с d₁ ≥ 0 и d_п > 0 (п ≥ 2), называется его директивная последовательность.

Штурмское слово ш над {0,1} является характеристическим тогда и только тогда, когда оба 0ш и 1ш Штурмовские.^[7]

Частоты

Если s слово бесконечной последовательности и ш - конечное слово, пусть μ_N(ш) обозначают количество вхождений ш как фактор в префиксе s длины N + |ш| - 1. Если μ_N(ш) имеет предел как N→ ∞, мы называем это частота из ш, обозначаемый μ(ш).^[4]^:73

За штурмовское слово s, каждый конечный фактор имеет частоту. В теорема о трех щелях означает, что факторы фиксированной длины п имеют не более трех различных частот, и если есть три значения, то одно является суммой двух других.^[4]^:73

Небинарные слова

Для слов, превышающих размер алфавита k больше 2, мы определяем слово Штурма как слово со сложностью п + k − 1.^[6]^:6 Их можно описать в терминах последовательностей резки для k-мерное пространство.^[6]^:84 Альтернативное определение - это слова минимальной сложности, которые в конечном итоге не являются периодическими.^[6]^:85

Связанные реальные числа

Действительное число, для которого цифры относительно некоторого фиксированного основания образуют слово Штурма, называется трансцендентное число.^[6]^:64,85

Штурмовы эндоморфизмы

Эндоморфизм свободный моноид B^∗ на двухбуквенном алфавите B является Штурм если он отображает каждый Штурмское слово к штурмовскому слову^[8]^[9] и местно штурмский если он отображает какое-нибудь штурмовское слово на штурмовское слово.^[10] Эндоморфизмы Штурма образуют подмоноид моноида эндоморфизмов B^∗.^[8]

Определим эндоморфизмы φ и ψ B^∗, куда B = {0,1}, поскольку φ (0) = 01, φ (1) = 0 и ψ (0) = 10, ψ (1) = 0. Тогда я, φ и ψ - штурмовы,^[11] и штурмовы эндоморфизмы B^∗ в точности те эндоморфизмы в подмоноиде моноида эндоморфизмов, порожденные {я, φ, ψ}.^[9]^[10]^[7]

Примитивная подстановка - штурмовская, если изображение слова 10010010100101 сбалансировано.^{[требуется разъяснение]}^[9]^[12]

История

Хотя изучение штурмских слов восходит к Иоганн III Бернулли (1772),^[13]^[5]^:295 это было Густав А. Хедлунд и Марстон Морс в 1940 году кто ввел термин Штурм для обозначения таких последовательностей,^[5]^:295^[14] в честь математика Жак Шарль Франсуа Штурм из-за связи с Теорема сравнения Штурма.^[6]^:114

Смотрите также

дальнейшее чтение

Бюжо, Ян (2012). Распределение по модулю один и диофантово приближение. Кембриджские трактаты по математике. 193. Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-11169-0. Zbl 1260.11001.
Лотэр, М. (2011). Алгебраическая комбинаторика слов. Энциклопедия математики и ее приложений. 90. С предисловием Жана Берштеля и Доминика Перрена (Перепечатка издания в твердом переплете 2002 г.). Издательство Кембриджского университета. ISBN 978-0-521-18071-9. Zbl 1221.68183.

[1] Hordijk, A .; Лаан, Д. А. (2001). «Границы для детерминированных периодических последовательностей маршрутизации». Целочисленное программирование и комбинаторная оптимизация. Конспект лекций по информатике. 2081. п. 236. Дои:10.1007/3-540-45535-3_19. ISBN 978-3-540-42225-9.

[2] Дьёри, Эрвин; Сос, Вера (2009). Последние тенденции в комбинаторике: наследие Пола Эрдеша. Издательство Кембриджского университета. п. 117. ISBN 0-521-12004-7.

[deluca1995-3] де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации. 54 (6): 307–312. Дои:10.1016 / 0020-0190 (95) 00067-М.

[Loth2002-4] а ^б ^c ^d ^е Лотэр, М. (2002). "Штурмские слова". Алгебраическая комбинаторика слов. Кембридж: Издательство Кембриджского университета. ISBN 0-521-81220-8. Zbl 1001.68093. Получено 2007-02-25.

[Allo2003-5] а ^б ^c ^d Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. ISBN 978-0-521-82332-6. Zbl 1086.11015.

[Fogg2002-6] а ^б ^c ^d ^е ^ж Пифей Фогг, Н. (2002). Берте, Валери; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.). Подстановки в динамике, арифметике и комбинаторике. Конспект лекций по математике. 1794. Берлин: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.

[BS1994-7] а ^б Berstel, J .; Себольд П. (1994). «Замечание о морфических штурмовских словах». РАИРО, Информ. Теор. Appl. 2. 8 (3–4): 255–263. Дои:10.1051 / ita / 1994283-402551. ISSN 0988-3754. Zbl 0883.68104.

[LotII83-8] а ^б Lothaire (2011 г.), п. 83)

[PF197-9] а ^б ^c Пифей Фогг (2002), п. 197)

[LotII85-10] а ^б Lothaire (2011 г.), п. 85)

[LotII84-11] Lothaire (2011 г.), п. 84)

[BS1993-12] Берстель, Жан; Себольд, Патрис (1993), "Характеристика штурмовских морфизмов", в Borzyszkowski, Andrzej M .; Соколовский, Стефан (ред.), Математические основы компьютерных наук, 1993. 18-й Международный симпозиум, MFCS'93, Гданьск, Польша, 30 августа - 3 сентября 1993 г. Труды, Конспект лекций по информатике, 711, стр. 281–290, Дои:10.1007/3-540-57182-5_20, ISBN 978-3-540-57182-7, Zbl 0925.11026

[13] Дж. Бернулли III, Sur une nouvelle espece de calc, Recueil pour les Astronomes, vol. 1, Берлин, 1772, стр. 255–284.

[14] Морс, М.; Хедлунд, Г.А. (1940). «Символическая динамика II. Штурмовские траектории». Американский журнал математики. 62 (1): 1–42. Дои:10.2307/2371431. JSTOR 2371431.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Navigation