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

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

Определение [ править ]

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

Комбинаторные определения [ править ]

Последовательности низкой сложности [ править ]

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

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

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

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

Геометрические определения [ править ]

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

Пусть w — бесконечная последовательность нулей и единиц. Последовательность w является штурмовой, если для некоторого $x\in [0,1)$ и немного иррационально $\theta \in (0,\infty )$ , w реализуется как последовательность разрезов линии $f(t)=\theta t+x$ .

в Битти Разница последовательностях

Пусть w = ( w _n ) — бесконечная последовательность нулей и единиц. Последовательность w называется Штурмовой, если она является разностью неоднородных последовательностей Битти , т. е. для некоторого $x\in [0,1)$ и немного иррационально $\theta \in (0,1)$

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

для всех $n$ или

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

для всех $n$ .

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

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

Для $\theta \in [0,1)$ , определять $T_{\theta }:[0,1)\to [0,1)$ к $t\mapsto t+\theta {\bmod {1}}$ . Для $x\in [0,1)$ определим θ -кодирование x как последовательность ( x _n ), где

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

Пусть w — бесконечная последовательность нулей и единиц. Последовательность w является штурмовой, если для некоторого $x\in [0,1)$ и немного иррационально $\theta \in (0,\infty )$ , w — θ -кодирование x .

Обсуждение [ править ]

Пример [ править ]

Известным примером (стандартного) слова Штурма является слово Фибоначчи ; ^[3] его наклон $1/\phi$ , где $\phi$ это золотое сечение .

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

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

Наклон и перехват [ править ]

Последовательность $(a_{n})_{n\in \mathbb {N} }$ над {0,1} является словом Штурма тогда и только тогда, когда существуют два действительных числа , наклон $\alpha$ и перехват $\rho$ , с $\alpha$ иррационально , такое, что

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

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

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

Все слова Штурма, соответствующие одному и тому же наклону $\alpha$ иметь одинаковый набор факторов; слово $c_{\alpha }$ соответствующий перехвату $\rho =0$ стандартное слово или характерное слово наклона $\alpha$ . ^[5]^: 283 Следовательно, если $0<\alpha <1$ , характерное слово $c_{\alpha }$ — первая разность последовательности Битти, соответствующая иррациональному числу $\alpha$ .

Стандартное слово $c_{\alpha }$ также является пределом последовательности слов $(s_{n})_{n\geq 0}$ определяется рекурсивно следующим образом:

Позволять $[0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]$ быть непрерывным дробным расширением $\alpha$ и определить

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

где произведение слов — это просто их конкатенация . Каждое слово в последовательности $(s_{n})_{n>0}$ является префиксом следующих, так что сама последовательность сходится к бесконечному слову, то есть $c_{\alpha }$ .

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

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

Частоты [ править ]

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

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

Небинарные слова [ править ]

Для слов в алфавите размера k больше 2 мы определяем слово Штурма как слово с функцией сложности n + 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. Тогда I , φ и ψ являются штурмовскими, ^[11] и штурмиовы эндоморфизмы B ^∗ являются в точности теми эндоморфизмами в подмоноиде моноида эндоморфизмов, порожденного { I ,φ,ψ}. ^[9]^[10]^[7]

Морфизм является штурмовским тогда и только тогда, когда образ слова 10010010100101 представляет собой сбалансированную последовательность ; то есть для каждого n подслов веса Хэмминга длины n принимают не более двух различных значений. ^[9]^[12]

История [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ Хордейк, А.; Лаан, Д.А. (2001). «Границы для последовательностей детерминированной периодической маршрутизации». Целочисленное программирование и комбинаторная оптимизация . Конспекты лекций по информатике. Том. 2081. с. 236. дои : 10.1007/3-540-45535-3_19 . ISBN 978-3-540-42225-9 .
^ Дьёри, Эрвин; Сос, Вера (2009). Последние тенденции в комбинаторике: наследие Пола Эрдеша . Издательство Кембриджского университета. п. 117. ИСБН 978-0-521-12004-3 .
^ де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации . 54 (6): 307–312. дои : 10.1016/0020-0190(95)00067-М .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Лотер, М. (2002). «Штурмовские слова» . Алгебраическая комбинаторика слов . Кембридж: Издательство Кембриджского университета . ISBN 0-521-81220-8 . Збл 1001.68093 . Проверено 25 февраля 2007 г.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6 . Збл 1086.11015 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7 . Збл 1014.11015 .
^ Jump up to: Перейти обратно: ^а ^б Берстель, Дж.; Себольд, П. (1994). «Замечание о морфных словах Штурма» . РАЙРО, Информ. Теор. Прил. 2 . 8 (3–4): 255–263. дои : 10.1051/ita/1994283-402551 . ISSN 0988-3754 . Збл 0883.68104 .
^ Jump up to: Перейти обратно: ^а ^б Лотарь (2011 , стр. 83)
^ Jump up to: Перейти обратно: ^а ^б ^с Пифей Фогг (2002 , стр. 197)
^ Jump up to: Перейти обратно: ^а ^б Лотарь (2011 , стр. 85)
^ Лотарь (2011 , стр. 84)
^ Берстель, Жан; Себольд, Патрис (1993), «Характеристика морфизмов Штурма», в Боржишковском, Анджей М.; Соколовский, Стефан (ред.), Математические основы информатики, 1993 г. 18-й международный симпозиум, MFCS'93, Гданьск, Польша, 30 августа – 3 сентября 1993 г., Труды , конспекты лекций по информатике, том. 711, стр. 281–290, номер документа : 10.1007/3-540-57182-5_20 , ISBN. 978-3-540-57182-7 , Збл 0925.11026
^ Дж. Бернулли III , О новом виде вычислений, Recueil pour les Astronomes, vol. 1, Берлин, 1772, стр. 255–284
^ Морс, М .; Хедлунд, Джорджия (1940). «Символическая динамика II. Штурмианские траектории». Американский журнал математики . 62 (1): 1–42. дои : 10.2307/2371431 . JSTOR 2371431 .

Дальнейшее чтение [ править ]

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

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

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

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

[Loth2002-4] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Лотер, М. (2002). «Штурмовские слова» . Алгебраическая комбинаторика слов . Кембридж: Издательство Кембриджского университета . ISBN 0-521-81220-8 . Збл 1001.68093 . Проверено 25 февраля 2007 г.

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

[Fogg2002-6] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7 . Збл 1014.11015 .

[BS1994-7] Jump up to: Перейти обратно: ^а ^б Берстель, Дж.; Себольд, П. (1994). «Замечание о морфных словах Штурма» . РАЙРО, Информ. Теор. Прил. 2 . 8 (3–4): 255–263. дои : 10.1051/ita/1994283-402551 . ISSN 0988-3754 . Збл 0883.68104 .

[LotII83-8] Jump up to: Перейти обратно: ^а ^б Лотарь (2011 , стр. 83)

[PF197-9] Jump up to: Перейти обратно: ^а ^б ^с Пифей Фогг (2002 , стр. 197)

[LotII85-10] Jump up to: Перейти обратно: ^а ^б Лотарь (2011 , стр. 85)

[LotII84-11] Лотарь (2011 , стр. 84)

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

[13] Дж. Бернулли III , О новом виде вычислений, 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]