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

Вид бесконечно длинной последовательности символов.

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обсуждение

Пример

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

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

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

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

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

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

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

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

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

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

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

Частоты

Если s — бесконечное последовательное слово, а w — конечное слово, пусть μ _N ( w ) обозначает количество вхождений w как множителя в префикс s длины N  + | w | − 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}

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

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

Ссылки

1. Хордейк, А.; Лаан, Д.А. (2001). "Границы для детерминированных периодических последовательностей маршрутизации". Целочисленное программирование и комбинаторная оптимизация . Конспект лекций по информатике. Том 2081. стр. 236. doi :10.1007/3-540-45535-3_19. ISBN 978-3-540-42225-9.
2. Дьёри, Эрвин; Сос, Вера (2009). Последние тенденции в комбинаторике: наследие Пола Эрдеша . Издательство Кембриджского университета. п. 117. ИСБН 978-0-521-12004-3.
3. de Luca, Aldo (1995). "Свойство деления слова Фибоначчи". Information Processing Letters . 54 (6): 307–312. doi :10.1016/0020-0190(95)00067-M.
4. Лотер, М. (2002). "Sturmian Words". Алгебраическая комбинаторика в словах . Кембридж: Cambridge University Press . ISBN 0-521-81220-8. Збл  1001.68093 . Проверено 25 февраля 2007 г.
5. Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл  1086.11015.
6. Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьян; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7. Збл  1014.11015.
7. Berstel, J.; Séébold, P. (1994). «Замечание о морфических словах Штурма». RAIRO, Inform. Théor. Appl. 2 . 8 (3–4): 255–263. doi : 10.1051/ita/1994283-402551 . ISSN  0988-3754. Zbl  0883.68104.
8. Лотер (2011, стр. 83)
9. Пифей Фогг (2002, стр. 197)
10. Лотер (2011, стр. 85)
11. Лотер (2011, стр. 84)
12. Berstel, Jean; Séébold, Patrice (1993), "A characterization of Sturmian morphisms", в Borzyszkowski, Andrzej M.; Sokołowski, Stefan (eds.), Mathematical Foundations of Computer Science 1993. 18-й Международный симпозиум, MFCS'93 Гданьск, Польша, 30 августа–3 сентября 1993 г. Труды , Lecture Notes in Computer Science, т. 711, стр. 281–290, doi :10.1007/3-540-57182-5_20, ISBN 978-3-540-57182-7, ЗБЛ  0925.11026
13. Дж. Бернулли III , Sur une nouvelle espece de Calcul, Recueil pour les Astronomes, vol. 1, Берлин, 1772 г., стр. 255–284.
14. Морс, М .; Хедлунд, Джорджия (1940). «Символическая динамика II. Штурмианские траектории». Американский журнал математики . 62 (1): 1–42. дои : 10.2307/2371431. JSTOR  2371431.

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

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