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

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

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

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

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

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

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

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

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

Пусть w - бесконечная последовательность нулей и единиц, и пусть обозначает множество подслов всей длины n в w . Последовательность w является штурмовской, если она сбалансирована для всех n, а w в конечном итоге не периодична.

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

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

Пусть w - бесконечная последовательность нулей и единиц. Последовательность ш штурмова , если для некоторых и некоторых иррациональных , ш реализуются как последовательность резки линии .

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

Пусть w  = ( w n ) - бесконечная последовательность нулей и единиц. Последовательность w является штурмовской, если она является разностью неоднородных последовательностей Битти , т.е. для некоторых и некоторых иррациональных

для всех или

для всех .

Кодирование иррационального вращения [ править ]

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

Для определения по . Для определения θ- кодирования x как последовательности ( x n ), где

Пусть w - бесконечная последовательность нулей и единиц. Последовательность ш штурмова , если для некоторых и некоторых иррациональных , ш является θ -coding из  х .

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

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

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

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

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

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

Последовательность над {0,1} является штурмова слово тогда и только тогда , когда существуют два вещественных числа , по склону и перехватывать , с иррациональным , так что

для всех . [5] : 284 [6] : 152 Таким образом, слово Штурма обеспечивает дискретизацию прямой с наклоном и  точкой пересечения ρ . Без ограничения общности мы всегда можем предположить , потому что для любого целого k мы имеем

Все слова Штурма, соответствующие одному и тому же наклону, имеют одинаковый набор факторов; слово, соответствующее перехвату, является стандартным словом или характеристическим словом наклона . [5] : 283 Таким образом, если , характерное слово , это первое отличие от последовательности Beatty , соответствующей иррационального числа .

Стандартное слово также является пределом последовательности слов, рекурсивно определяемой следующим образом:

Пусть - разложение в цепную дробь , и определим

где произведение между словами - это просто их конкатенация . Каждое слово в последовательности является префиксом следующих, так что сама последовательность сходится к бесконечному слову, которое есть .

Бесконечная последовательность слов, определенная вышеупомянутой рекурсией, называется стандартной последовательностью для стандартного слова , а бесконечная последовательность d = ( d 1 , d 2 , d 3 , ...) неотрицательных целых чисел, где d 1 ≥ 0 и d n > 0 ( n ≥ 2), называется его директивной последовательностью .

Штурмово слово 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

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

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

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

  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.
  3. ^ де Лука, Альдо (1995). «Свойство деления слова Фибоначчи». Письма об обработке информации . 54 (6): 307–312. DOI : 10.1016 / 0020-0190 (95) 00067-M .
  4. ^ а б в г д Лотэр, М. (2002). «Штурмские слова» . Алгебраическая комбинаторика слов . Кембридж: Издательство Кембриджского университета . ISBN 0-521-81220-8. Zbl  1001.68093 . Проверено 25 февраля 2007 .
  5. ^ a b c d Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl  1086.11015 .
  6. ^ Б с д е е Pytheas Фоггом, N. (2002). Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Берлин: Springer-Verlag . ISBN 3-540-44141-7. Zbl  1014.11015 .
  7. ^ a b Berstel, J .; Себольд П. (1994). «Замечание о морфических словах Штурма» . РАИРО, Информ. Теор. Прил. 2 . 8 (3–4): 255–263. DOI : 10.1051 / ITA / 1994283-402551 . ISSN 0988-3754 . Zbl 0883.68104 .  
  8. ^ a b Lothaire (2011 , с. 83)
  9. ^ a b c Пифей Фогг (2002 , стр.197)
  10. ↑ a b Lothaire (2011 , с. 85)
  11. ^ Lothaire (2011 , стр. 84)
  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 . 

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

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