Сверхслова, меры на них и их полупрямые произведения (1104768), страница 5
Текст из файла (страница 5)
С другой стороны, ни одно из слов индекса нуль неявляется началом никакого другого. Следовательно, любое вхождение словас индексом нуль в , или корректно. База индукции доказана.Индуктивный переход: по предположению индукции любое вхождениеслова с индексом + 1 должно состоять из корректных вхождений слов с индексом . Если считать блоки , составляющие слова с индексом + 1, отдельными буквами, то слова с индексом + 1 имеют те же свойства,которые были использованы в базе индукции. А именно, каждое из слов индекса +1 начинается со слова , которое не является подсловомникакого слова с индексом + 1 (за исключением начала) и не может бытьпредставлено как конкатенация некоторого непустого конца слова с индексом+1 и некоторого начала слова с индексом +1.
Кроме того, никакое словос индексом +1 не является началом другого слова с индексом +1. Лемма1.1 доказана.Лемма 1.2. Длина слова вычисляется по формуле | | = = 10+1∏︀ .=1Кроме того, | | = | | − 1 и | | = | | + 1.Доказательство. Проверим это по индукции. При = 0 утверждениеочевидно.Индуктивный переход: +1 является конкатенацией 10+1 − 8 слов дли∏︀ны 10+1 , а также 4 слов длины на единицу меньше, и 4 слов длины=1на единицу больше. В сумме получаем как раз в 10+1 раз больше, чем напредыдущем шаге, что и требовалось.Слова +1 и +1 отличаются от +1 только заменой одного слова в кон29катенации на слово, которое на один символ короче или длиннее соответственно.1.6.
Позиции вхождений слов в сверхслово и их остаткиот деления на Нам нужно показать, что регулятор сверхслова относительно маленький, а регулятор сверхслова ⊗ Cycle — большой. Точнее, нам нужнооценить сверху или снизу значения этих функций на числе , которое мыможем выбрать по своему усмотрению. Мы выберем в качестве длинуслова 3 , равную 3 .
Таким образом, нам нужно будет показать две вещи: регулятор сверхслова принимает на 3 значение, меньшее 3+3 , арегулятор сверхслова ⊗ Cycle — большее 3+⌊/10⌋ .Мы начнём со второго. Чтобы установить это, нужно предъявить словодлины не больше 3 , которое встречается в ⊗ Cycle бесконечно многораз, но расстояния между соседними вхождениями велики. Мы будем считать, что слово Cycle записано в алфавите остатков от деления на (например, −1 и − 1 являются обозначениями одного и того же символа). Такимсловом будет произведение слова 3 и слова⌊−/2⌋, ⌊−/2⌋ + 1, .
. . , −1, 0, 1, . . . , ⌊/2⌋ . . . .Чтобы доказать, что оно встречается в ⊗ Cycle достаточно редко, намнужно понять, с каких позиций могут начинаться вхождения слова 3 вслово , и показать, что номера таких позиций, сравнимые с ⌊−/2⌋ помодулю , встречаются достаточно редко.Лемма 1.3. В любом слове с индексом + слово входит, начинаяс позиций, дающих все остатки от − до 0 по модулю (и, возможно,30другие).
При этом никакое слово с индексом (то есть , , ) невходит ни в какое слово с индексом + начиная с позиций с остатками помодулю , не лежащими от −4 до 0 (данное утверждение нетривиальнотолько при > 4).Доказательство. Докажем индукцией по . База = 1 почти очевидна: с одной стороны первое и второе вхождения в слова с индексом + 1дают остатки 0 и −1. С другой стороны, мы знаем, что все вхождения словс индексом в слова с индексом + 1 корректны. И можно непосредственноубедиться, что номера позиций начал корректных вхождений слов с индексом в слова с индексом + 1 суть 0, −1, −2, −3, −4 по модулю .Пусть для = это верно.
Рассмотрим теперь = + 1, и пусть данолюбое слово с индексом + + 1. Сначала докажем первое утверждение. Попредположению индукции в данном слове есть вхождение +1 на позиции.с остатком − по модулю +1 , а значит, и по модулю , так как +1 .. .Это вхождение +1 начинается со вхождения ; так мы получим вхождение с остатком − по модулю . Аналогичным образом доказывается существование вхождений с остатками от − + 1 до 0 по модулю . Остаток−−1 даст второе вхождение во вхождение +1 , начинающееся с позициис остатком − по модулю .Перейдем к доказательству второго утверждения. По предположениюиндукции в данном слове индекса + + 1 все вхождения слов с индексом + 1 имеют начальные позиции с остатками от −4 до 0 по модулю +1 (азначит, и по модулю ).
Рассмотрим отдельно любое из таких вхождений.Остатки от деления на позиций вхождений слов с индексом в слово синдексом + 1 относительно его начала лежат от −4 до 0, а само начало попредположению индукции имеет позицию с остатком от −4 до 0 при делениина . Складывая остатки, получаем второе утверждение леммы.311.7. Нижняя оценка на регулятор почти периодичностипрямого произведения построенного сверхслова ипериодического сверхслова.Лемма 1.4. Пусть .. и > > 100.
Тогда регулятор почти периодичности сверхслова ⊗ Cycle на принимает значение большее +⌊ ⌋ .10Более того, регулятор любого суффикса ⊗ Cycle обладает этим свойством..Доказательство. Заметим, что .. при > , и остаток от деленияпозиции на можно считать как остаток от деления на остатка от деленияна .Рассмотрим произвольное > + . По лемме 1.3 в слове естьвхождения , начинающиеся с позиций, дающих все возможные остатки отделения на , так как разность − не меньше .
В частности, там есть ивхождение с остатком ⌊/2⌋ по модулю . Заметим, что содержит бесконечно много непересекающихся вхождений . Поэтому любой суффикссверхслова ⊗ Cycle содержит вхождение прямого произведения слова и слова⌊−/2⌋, ⌊−/2⌋ + 1, . . . , −1, 0, 1, . . . , ⌊/2⌋ − 1 . . .(имеется в виду, что мы продолжаем эту последовательность с периодом ,пока её длина не станет равной длине слова ).Чтобы завершить доказательство первого утверждения леммы 1.4, покажем, что некоторое подслово длины +⌊ ⌋ в ⊗ Cycle не содержит10вхождений рассматриваемого произведения. Таким подсловом будет, например, начало этого слова длины +⌊ ⌋ .
Действительно, нетрудно убедиться,10что при > 100 выполнено неравенство |+⌊ ⌋ | > +⌊ ⌋ . Поэтому рас910сматриваемое начало является префиксом прямого произведения сверхсло32ва +⌊ ⌋ и начала сверхслова Cycle подходящей длины. По лемме 1.3 сло9во +⌊ ⌋ может содержать только вхождения , начинающиеся с позиций⌊︀ ⌋︀ 9⌊︀ ⌋︀−4 9 , . .
. , 0 по модулю . Поскольку 4 9 < ⌊/2⌋, среди этих остатковотсутствует ⌊/2⌋.Для доказательства второго утверждения леммы 1.4 осталось заметить,что слово содержит бесконечно много вхождений слова +⌊ ⌋ , начинаю9щихся в позициях, кратных (опять же по лемме 1.3).1.8. Верхняя оценка регулятора построенногосверхсловаЛемма 1.4 устанавливает нужную нижнюю оценку регулятора почти периодичности сверхслова ⊗ Cycle . Осталось получить верхнюю оценку регулятора почти периодичности самого сверхслова . Здесь мы будем использовать то обстоятельство, что слова с индексом + 2 содержат все возможныепары слов с индексом .Лемма 1.5. Любое слово, которое является подсловом конкатенации двухслов с индексом , входит в каждое слово с индексом + 2.Доказательство.
Любая комбинация рядом стоящих слов с индексом встречается хотя бы в одном из слов уровня +1. В каждом из слов +2 , +2и +2 встречается каждое из слов предыдущего уровня, что и требовалось.Заметим, что усложнив немного конструкцию слов , и , можносделать, чтобы доказанная лемма была справедлива для +1 вместо +2. Мыне делаем этого, поскольку не стремимся (пока) к уменьшению константы 30в формулировке теоремы 0.2. Как мы увидим ниже, при более аккуратнойформулировке и при немного другом условии на нижнюю оценку роста регулятора константа 30 может быть уменьшена почти до 1. Что означает “почти”33мы уточним позже.Лемма 1.6.
Сверхслово почти периодическое и регулятор его почтипериодичности можно оценить следующим образом:1+1 6 ( ) 6 2+2 + 1 < +32Доказательство. Первое неравенство: левая половина слова +1 несодержит , хотя все слово +1 содержит и встречается в сверхсловебесконечно много раз.Второе неравенство: любой участок длины 2+2 + 1 содержит целикомхотя бы одно слово уровня +2. Такое слово, как уже доказано, содержит любое слово, которое можно покрыть двумя непересекающимися словами с индексом (а участок длины не может пересекаться сразу с тремя вхождениями слов с индексом ).Поскольку любое слово, входящее в , входит и в некоторое , мы темсамым доказали и почти периодичность сверхслова .1.9. Завершение доказательстваЗакончим построение искомых сверхслова и последовательности .Пусть задана функция .
Построим последовательность 1 , 2 , . . . по формулам 1 = 3 (1), +1 = 3( + 1) ( ). В качестве возьмем = 3 .Проверим выполнение условий теоремы: +1 = 3+3 > 3+1 > (3 ) = ( ), регулятор последовательности почти периодичности сверхслова на принимает значение меньшее +1 , а при > регулятор последовательности ⊗Cycle на принимает значение, превосходящее 3+⌊ ⌋ >10+⌊ ⌋ , что и требовалось.30Замечание. Как видно из приведённых оценок, регулятор сверхслова принимает на значение, большее ( ). Поэтому возникает искуше34ние усилить утверждение теоремы 0.2, добавив условие > и заменивmax{, } на . Этого нельзя делать, поскольку мы не доказали, что неравенство > имеет место для всех аргументов.1.10. Улучшение нижней оценки теоремы 0.2В приведённой конструкции и доказательстве имеется большой запас иконстанту 30 можно понизить, существенно не меняя конструкции.В этом разделе, в качестве примера усиления оценки, будет доказанатеорема 0.3.Теорема 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
