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

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

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

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

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

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

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

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

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

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

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

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

Режущая последовательность иррационального [ править ]

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

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

Пусть w = ( w _n ) - бесконечная последовательность нулей и единиц. Последовательность w является штурмовской, если она является разностью неоднородных последовательностей Битти , т.е. для некоторых и некоторых иррациональных ${\ 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 и x ≈ 0,0789

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

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

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

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

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

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

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

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

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

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

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

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

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

Все слова Штурма, соответствующие одному и тому же наклону, имеют одинаковый набор факторов; слово, соответствующее перехвату, является стандартным словом или характеристическим словом наклона . ^[5]^:²⁸³ Таким образом, если , характерное слово , это первое отличие от последовательности Beatty , соответствующей иррационального числа . $\alpha$ $c_{\alpha }$ $\rho =0$ $\alpha$ $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 }$

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

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

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

Если s - бесконечное слово-последовательность, а w - конечное слово, пусть μ _N ( w ) обозначает количество вхождений w как множителя в префиксе s длины N + | w | - 1. Если μ _N ( ш ) имеет предел при N → ∞, мы называем это частоту из ш , обозначаемый ц ( ш ). ^[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 сбалансировано. ^{[ требуется разъяснение ]}^[9]^[12]

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

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

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

Последовательность резки
Слово (теория групп)
Морфическое слово
Линдон слово

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

^ Hordijk, A .; Лаан, Д.А. (2001). «Границы для детерминированных периодических последовательностей маршрутизации». Целочисленное программирование и комбинаторная оптимизация . Конспект лекций по информатике. 2081 . п. 236. DOI : 10.1007 / 3-540-45535-3_19 . ISBN 978-3-540-42225-9.
^ Дьёри, Эрвин; Сос, Вера (2009). Последние тенденции в комбинаторике: наследие Пола Эрдеша . Издательство Кембриджского университета. п. 117. ISBN 0-521-12004-7.
^ де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации . 54 (6): 307–312. DOI : 10.1016 / 0020-0190 (95) 00067-M .
^ а б в г д Лотэр, М. (2002). «Штурмские слова» . Алгебраическая комбинаторика слов . Кембридж: Издательство Кембриджского университета . ISBN 0-521-81220-8. Zbl 1001.68093 . Проверено 25 февраля 2007 .
^ a b c d Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
^ Б с д е е Pytheas Фоггом, N. (2002). Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Берлин: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .
^ a b Berstel, J .; Себольд П. (1994). «Замечание о морфических словах Штурма» . РАИРО, Информ. Теор. Прил. 2 . 8 (3–4): 255–263. DOI : 10.1051 / ITA / 1994283-402551 . ISSN 0988-3754 . Zbl 0883.68104 .
^ a b Lothaire (2011 , с. 83)
^ a b c Пифей Фогг (2002 , стр.197)
↑ a b Lothaire (2011 , с. 85)
^ Lothaire (2011 , стр. 84)
^ Berstel, Жан; Себольд, Патрис (1993), "Характеристика морфизмов Штурма", у Borzyszkowski, Andrzej M .; Соколовский, Стефан (ред.), « Математические основы компьютерных наук», 1993. 18-й Международный симпозиум, MFCS'93, Гданьск, Польша, 30 августа - 3 сентября 1993 г., Материалы лекций по информатике, 711 , стр. 281–290, doi : 10.1007 / 3-540-57182-5_20 , ISBN 978-3-540-57182-7, Zbl 0925,11026
↑ J. Bernoulli III , Sur une nouvelle espece de calc, Recueil pour les Astronomes, vol. 1, Берлин, 1772, стр. 255–284.
^ Морс, М .; Хедлунд, Джорджия (1940). «Символическая динамика II. Штурмовские траектории». Американский журнал математики . 62 (1): 1–42. DOI : 10.2307 / 2371431 . JSTOR 2371431 .

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

Буджо, Янн (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. DOI : 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. DOI : 10.1016 / 0020-0190 (95) 00067-M .

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

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

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

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

[LotII83-8] Lothaire (2011 , с. 83)

[PF197-9] Пифей Фогг (2002 , стр.197)

[LotII85-10] Lothaire (2011 , с. 85)

[LotII84-11] Lothaire (2011 , стр. 84)

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

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

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

[1]