Сверхслова, меры на них и их полупрямые произведения (1104768), страница 6
Текст из файла (страница 6)
Пусть задана возрастающая функция : N → N. Тогда найдётся почти периодическое сверхслово с регулятором почти периодичности и следующими свойствами.1) Для бесконечного количества аргументов превышает . Болеетого, эти аргументы выстроены в цепочку: существует последовательность натуральных чисел , такая что1 ( ) < +1 6 ( ) 6 +1 .62) Для любого > 2 и любого регулятор почти периодичности ⊗Cycle удовлетворяет неравенствам ⊗Cycle ( ) > +−2 > ∘−2 ( ).3) Для любого достаточно большого регулятор почти периодичности всё того же прямого произведения ⊗ Cycle на всех достаточнобольших значениях аргументов превышает ∘−3 .Доказательство. Для доказательства изменим немного конструкциюслов , , .
Слова 0 , 0 , 0 менять не будем, а +1 , +1 , +1 определим35по-другому:+1 = ( )5 ,+1 = ( )5 ,+1 = ( )5 .Из определения видно, что для любого длины слов , , отличаются на 1: как и раньше, обозначим длину через , тогда длина есть − 1, а длина есть + 1. Последовательность 1 , 2 , . .
. подберём изтого расчёта, чтобы для всех при всех достаточно больших число былократно и чтобы +1 было больше 100 ( ). Кроме того, сделаем > 100.Слова +1 , +1 , +1 выбраны такими, чтобы:(а) каждое из них содержало пары , , , и в любойсвоей четверти и конкатенация любых слов из +1 , +1 , +1 не содержаладругих пар из слов , , ;(б) в каждом из них был фрагмент длины не менее одной шестой от всегослова, не содержащий .(в) в любом начале любого из слов +1 , +1 , +1 разница между количеством и количеством принимала оба значения 0 и 1 не менее одногораза и не принимала никаких других значений;(г) в каждом из них ровно в одном месте входят + 2 копии подряд.Из-за наличия уникального фрагмента +2 в одном и том же местекаждого из слов уровня + 1 и того, что слова уровня + 1 не продолжаютдруг друга, следует аналог леммы 1.1: для всех 6 все вхождения слов , , в , , корректны.
Из свойства (в) следует такой аналоглеммы 1.3:Лемма 1.7. В любом слове с индексом + любое слово с индексом входит начиная с позиций, дающих только остатки от − до 0 по модулю36 , причём для каждого такого остатка и любого слова уровня + некоторое слово с индексом входит в это слово, начиная с позиции, дающейэтот остаток.
Слово входит во все слова с индексом + начиная с позиций, дающих только остатки от − до 0 по модулю и все остаткиреализуются (в любом слове с индексом + ).Из этой леммы следует оценка на регулятор прямого произведениясверхслова и Cycle : а именно, выполнено неравенство ( ) > +−2(для всех , для которых кратно ). В самом деле, рассмотрим прямоепроизведение слова и слова− + 1, − + 2, . . . , −1, 0, 1, .
. .Это слово входит в ⊗ Cycle . Действительно, рассмотрим любое число ,удовлетворяющее неравенству > − 1.Тогда входит в + , начиная с некоторой позиции, сравнимой с − + 1по модулю .С другой стороны, верно и обратное — если слово входит в начало+ начиная с некоторой позиции, сравнимой с − + 1 по модулю , то удовлетворяет этому неравенству. Таким образом, мы нашли слово длины ,не входящее в некоторые подслова длины +−2 .
При этом оно входит внаше сверхслово бесконечно много раз. Таким образом, значение регуляторана больше +−2 .Теперь докажем, что для регулятора сверхслова выполнено неравенство ( ) 6 +1 .37Любое слово длины (или меньше), входящее в сверхслово , покрываетсядвумя словами уровня . По первому и второму свойству любая возможная внашем сверхслове комбинация рядом стоящих слов с индексом встречаетсяв каждом из слов уровня + 1; более того, она встречается в любой четвертикаждого из слов уровня +1. Любой участок длины +1 пересекается с однимиз слов уровня + 1 хотя бы по половине его длины (возможно, минус одинили два символа), что намного больше четверти длины и включает первыйили последний из пяти повторов блока в середине слова уровня +1 целиком.Теперь установим, что1+1 6 ( ).6Слово длины −1 не встречается между своими двумя вхождениями в двасоседних повтора пятикратно повторяемого блока в середине слова уровня + 1, что позволяет указать подслово длины +1 /6 без вхождений данногослова длины − 1.Вспоминая, что ( ) < 61 +1 , мы можем заключить, что для регулятора сверхслова выполняются неравенства1 ( ) < +1 6 ( ) 6 +1 ,6при всех значениях .
Поскольку регулятор не убывает, индукцией по легко доказывается, что ∘−2 ( ) 6 +−2 , что, напомним, меньше ⊗Cycle ( ).Теперь рассмотрим произвольную длину < < +1 . Заметим, что () 6 (+1 ) 6 +2 , и при этом ⊗Cycle () > ⊗Cycle ( ) > +−2 >∘−4 (+2 ) > ∘−4 ( ()) = ∘−3 ().Таким образом, теорема 0.3 доказана полностью.Можно посмотреть на конструкцию при конкретном выборе . Длина∏︀слова равна 10 × 5 × 1 ( + 6). Пусть, скажем, +1 = × ⌈ | | ⌉. Тогдана некоторой подпоследовательности длин регулятор ведёт себя как Θ(2 ),38−3а регулятор ⊗ Cycle как Ω(2).39Глава 2Полупрямые произведения вычислимых мер насверхсловах2.1.
Основные свойства полупрямых произведений,согласованных с отношениемВ качестве примера использования определения 0.6 докажем сначаланаличие полупрямого произведения, согласованного с отношением, для двухконкретных мер. Рассмотрим меру , сконцентрированную на последовательности с периодом⊕ ⊖ ⊕ ⊖ ⊕ ⊕ ⊕ ⊖ ⊖⊖,и меру , сконцентрированную на последовательности с периодом⊕⊕⊕⊖⊕⊕⊕⊖⊖⊖.Ясно, что 6 .
Действительно, мера, сконцентрированная на последовательности с периодом⊕⊕⊕⊖⊕⊕⊕⊖⊖⊖.⊕⊖⊕⊖⊕⊕⊕⊖⊖⊖приписывает нулевую вероятность слову⊖⊕,отсутствие в сверхслове вхождений этого слова обеспечивает выполнение нестрогого покомпонентного неравенства между проекциями и имеет проекции, равные рассматриваемым мерам.Как уже было упомянуто во введении, из теоремы Форда–Фалкерсона [8]о максимальном потоке и минимальном разрезе следует простой критерийтого, что распределение находится в отношении с . Авторство данногокритерия достоверно неизвестно.40Напомним формулировку теоремы 0.4.Теорема. (0.4) Распределение находится в отношении с , тогда итолько тогда, когда не существует подмножеств ⊂ , ⊂ , такихчто все -соседи лежат в и () > ().Для полноты изложения приведём доказательство этого критерия.
Ясно, что если распределение находится в отношении с , то таких подмножеств нет. В самом деле, рассмотрим полупрямое произведение , длякоторого ( ) = 1. Предположим, что все -соседи лежат в . Тогда() = ( × ) = (( × ) ∩ ) == (( × ) ∩ ) 6 ( × ) 6 ( × ) = ().Второе равенство здесь выполнено, поскольку носитель распределения включен в , а третье — поскольку все -соседи лежат в .Теперь докажем обратное утверждение.
Для этого рассмотрим следующую сеть (рис. 2.1). Из источника выходит || рёбер, они ведут в вершины,stPXPYXYРис. 2.1. Пример сети, соответствующей заданному отношению .соответствующие элементам . Их пропускные способности равны значениям на соответствующих элементах . Рёбра, ведущие в сток , выходят извершин, соответствующих элементам , а их пропускные способности равнызначениям . Ребра сети между вершинами и соответствуют элементам бинарного отношения — их пропускные способности не ограничены.41По построению, в этой сети можно пропустить поток мощности 1 из истокав сток тогда и только тогда, когда существует полупрямое произведение ,для которого ( ) = 1: значение на паре (, ) соответствует количествужидкости, проходящей из в , наличие в сети рёбер только из ограничивает носитель распределения отношением .
Теорема Форда–Фалкерсонаутверждает, что для произвольной сети, если из источника в сток невозможно пропустить поток мощности , то к этому есть следующее препятствие:все вершины сети можно разделить на два множества , (разрез) так, чтобы исток попал в , сток попал в , и сумма пропускных способностей всехрёбер сети, ведущих из в , (величина разреза) была меньше . В нашемслучае множество , существующее по этой теореме, вместе с любой своейвершиной должно содержать и всех её соседей (иначе величина разреза будет неограниченной). Возьмем в качестве множество всех вершин из ,лежащих в , а в качестве — множество всех вершин из , лежащих в .Величина разреза равна (1−())+() (первое слагаемое равно сумме пропускных способностей ребер из источника в , а второе — сумме пропускныхспособностей ребер из в сток).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
