Слово Штурма (последовательность Штурма или биллиардная последовательность), названная в честь французского математика Жака Шарля Франсуа Штурма — это некоторого рода бесконечно длинная последовательность символов. Такая последовательность может быть получена при рассмотрении английского бильярда на квадратном столе. Удар по шару приведёт к последовательным столкновениям с вертикальными и горизонтальными краями, обозначенными цифрами 0 и 1, что породит последовательность букв. Эта последовательность и есть слово Штурма.

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

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

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

Сбалансированные последовательности Множество X двоичных строк называется сбалансированным, если вес Хэмминга элементов X принимает максимум два различных значения. То есть, для любого или где |s|1 — число единиц в s.

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

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

Последовательность пересечений наклона Пусть w бесконечной последовательностью нулей и единиц. Последовательность w есть последовательность Штурма, если для некоторого и некоторого иррационального w, если она является прямой .

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

для всех или

для всех .

Двоичное кодирование траектории точки на окружности

Пусть , определим функцию , которая отображает . Для определим θ-кодирование x как последовательность (xn), где

Пусть w будет бесконечной последовательностью нулей и единиц. Последовательность w является последовательностью Штурма, если для некоторого и некоторого иррационального w является θ-кодированием x.

Обсуждение

Пример Знаменитым примером (стандартного) слова Штурма является слово Фибоначчи. Наклон прямой этого слова (см. Последовательность пересечений наклона выше) равен , где  — золотое сечение.

Сбалансированные апериодические последовательности Множество S конечных бинарных слов называется сбалансированным, если для каждого n подмножество Sn слов длины n обладает свойством, что веса Хэмминга слов в Sn принимают не более двух различных значений. Сбалансированная последовательность — это последовательность, в которой все подпоследовательности сбалансированы. Сбалансированная последовательность имеет не более n+1 различных подпоследовательностей длины n. Апериодическая последовательность — это последовательность, которая не состоит из конечной последовательности, за которой следует конечный цикл. Апериодическая последовательность имеет не менее n + 1 различных подпоследовательностей длины n. Последовательность является последовательностью Штурма тогда и только тогда, когда она сбалансирована и апериодична.

Наклон и точка пересечения Последовательность из нулей и единиц является словом Штурма тогда и только тогда, когда существуют два вещественных числа — наклон и точка пересечения , причём иррационально, такие что

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

Все слова Штурма, соответствующие одному и тому же наклону имеют один и тот тоже набор факторов (подмножеств). Слово , соответствующее точке пересечения является стандартным словом или характеристическим словом наклона . Следовательно, если , характеристическое слово является последовательности Битти, соответствующей иррациональному числу .

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

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

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

Бесконечная последовательность слов определённая вышеуказанной рекурсией, называется стандартной последовательностью для стандартного слова , и бесконечная последовательность неотрицательных целых чисел, где и , называется направляющей последовательностью.

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

Частота Если s является бесконечным словом, а w является конечным словом, то μN(w) обозначает число вхождений слова w в префикс слова s длины N + |w| − 1. Если μN(w) имеет предел при N→∞, мы называем его частотой слова w и обозначаем μ(w) .

Для слова Штурма s любое конечное подслово имеет частоту. Из следует, что подслова фиксированной длины n имеют максимум три частоты, и если есть три значения, то одно из низ является суммой двух других.

Недвоичные слова Для слов над алфавитом размера k, большего 2, мы определяем слово Штурма как слово с функцией сложности . Они могут быть описаны в терминах последовательности пересечений для k-мерного пространства. Альтернативное определение — это слова минимальной сложности при условии, что они не являются в конечном итоге периодическими.

Ассоциированные вещественные числа Вещественное число, для которого запись по некоторому основанию образует слово Штурма, является трансцендентным числом.

Эндоморфизмы Штурма Эндоморфизм B∗ на двухбуквенном алфавите B есть эндоморфизм Штурма, если он переводит каждое слово Штурма в слово Штурма и локальный эндоморфизм Штурма, если он переводит только часть слов Штурма в слова Штурма. Эндоморфизмы Штурма образуют подмоноид автоморфизмов B∗.

Определим эндоморфизмы φ и ψ на B∗, где B = {0,1}, следующим образом: φ(0) = 01, φ(1) = 0 и ψ(0) = 10, ψ(1) = 0. Обозначим через E тривиальный морфизм, обменивающий буквы 0 и 1. Тогда E, φ и ψ являются зндоморфизмами Штурма и эндоморфизмами Штурма моноида B∗ являются в точности те эндоморфизмы в подмоноиде моноида автоморфизмов, которые порождены {E,φ,ψ}

История Хотя изучение слов Штурма началось с работ Иоганн III Бернулли а 1772 году, сам термин ввели и Марстон Морс в 1940 году. Они назвали слова в честь математика Жакп Шарля Франсуа Штурма, учитывая их связь с теоремой сравнения Штурма .

См. также

Слово Линдона

Примечания

Литература

Дополнительная литература

Категория:Комбинаторика слов Категория:Ряды и последовательности