Графы линейных операторов и билипишицевы классы множеств Делоне

• Автор: Гарбер, Алексей Игоревич
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 56 с. : ил.

Содержание
Введение

1 Графы линейных операторов

1.1 Определение графа (ЗД

1.2 Построение деревьев

1.3 Алгоритм построения циклов

2 Граф разностного оператора

2.1 Алгоритм построения графа Сррц

2.2 Логарифмическая последовательность

2.3 Длина максимального цикла

2.4 О количестве максимальных циклов

3 Билипшицевы классы множеств Делоне 40:
3.1 Вспомогательные леммы
3.2 Деформации множеств, сохраняющие билипшицев класс
3.3 Об универсальности множества Делоне
3.4 Конструкция множества, не эквивалентного решетке
3.5 Многомерное обобщение
3.6 “Двумерные” результаты
Список литературы

Список иллюстраций
1.1 Пример графа линейного оператора
1.2 Дерево ТІ в случае р — 2, т = 2, к = 2, к%
1.3 Дерево в случае р = 2, т — 2, = 2, к>2
1.4 Дерево Ті в случае р — 2, т = 2, А:і = 2, &2
1.5 Дерево ТІ в случае р — 2, ш = 2, А;і = 2, /с2
1.6 Дерево, притягиваемое каждой вершиной, в случае р = 2,
тп — 2, = 2
2.1 Пример дерева в графе разностного оператора при р = 5. :
2.2 Граф оператора Т>(6) при р
3.1 Биекция / : В —у А из леммы
3.2 Иллюстрация к доказательству теоремы

Введение
Данная диссертация посвящена изучению сложности дискретных структур.
В первых двух главах изучаются вопросы, относящиеся к теории сложности конечных последовательностей, недавно построенной В.И. Арнольдом [1]. Речь идет о последовательностях конечной длины п с элементами из Ър. В третьей главе изучаются равномерные дискретные множества в евклидовых пространствах, так называемые множества Делоне. Среди множеств Делоне содержится относительно простой класс — класс целочисленных решеток. Основной вопрос, который мы изучаем в этой главе — существуют ли в евклидовом пространстве множества Делоне, отличающиеся от решеток с точки зрения билипшицевой эквивалентности? — восходит к М. Громову [20].
Понятие сложности конечной последовательности вводилось и ранее. Так А.Н. Колмогоров ввел понятие информационной сложности (см. [8]). Простая колмогоровская сложность равна количеству информации, которая необходима, чтобы задать последовательность. При этом сложность последовательности, естественно, зависит от того каким образом (с помощью какого “алгоритма декомпрессии”) последовательность восстанавливается из сжатой последовательности информации.
В 2005 году В.И. Арнольд ввел другое понятие сложности, связанное с графом разностного оператора Т)[п) : 2" —У ТП™ (см. [1, 2, 16]). Разностный оператор Т>(п) действует на последовательность х — (хг
В этом направленном графе каждая компонента связности представляет из себя цикл, к каждой вершине которого “подвешено” дерево (см. [15, Гл. 16]). При этом сложность последовательности х — вершины графа, определяется длиной притягивающего цикла и расстоянием до этого цикла на соответствующем, дереве (см. параграф 2.1).
В.И. Арнольд в [1] сформулировал и доказал ряд утверждений о графе разностного оператора в случае бинарных последовательностей из . В частности, им было доказано, что в бинарном случае все деревья в графе разностного оператора изоморфны и представляют собой корневое бинарное дерево, высота которого определяется длиной п последовательности. Также в своих работах В.И. Арнольд выдвинул ряд гипотез о строении графа разностного оператора, которые были основаны на проведенных им численных экспериментах для относительно малых п.

В правой части равенства также записана одна из сумм 5* (возможно с противоположным знаком), причем она не делится на р, так как равна б'о-Следовательно, в арифметической прогрессии вида к + 1 — пх, при некотором натуральном х, встретится 0 или 1.
Предположим, что к + 1 = пх. Распишем 51 аналогично 50:
*=(7)-Г™)+-+(-1)*Ч пж /)=»
1 / 1 + п) пх — п + 1)
= (’»*')_(' « 1)+... + (-1Г1(“1)=±8
пх — 1) пх — гг — 1/ n-lj
Но последнее равенство невозможно, так как 5х не делится на р, а 5П_1 — делится, в силу того, что п > 2. Следовательно к + 1 = пх + 1, а значит к делится на п. □
"Утверждение 2.3.4. Если т не является степенью числа р, то имеет место равенство Ь(рт) = рЬ(т).
Доказательство. По следствию 2.1.9, длина цикла определяется характеристическим многочленом оператора. Достаточно с помощью утверждений 2.1.10 и 2.1.11 записать разложение на неприводимые этих многочленов, а затем с помощью лемм 1.3.18 и 1.3.21 получить требуемое соотношение. □
Теорема 2.3.5. Если п не равняется ра и 2ра, то длина максимального цикла Ь{п) делится на п.
Доказательство. По утверждению 2.3.4, нам достаточно доказать теорему только для п > 2, не делящихся на р. Длина максимального цикла это порядок многочлена Рщп)(г) — т0 есть минимальное к такое, что Нр, Пг)
делит гк — 1. По лемме 2.3.3 любое к, удовлетворяющее этому условию, делится на п. □
Исключительный случай в лемме 2.3.3 это п = р° или п = 2ра, то есть если п = раМ, то М = 1 или М = 2 (только в случае р > 2). В первом случае, согласно утверждению 2.1.3, существует единственный цикл в графе Сп и его длина равна 1. В случае М = 2 длина максимального цикла, согласно следствию 2.3.4, равна р“д, где д это порядок линейного многочлена Рщ2)(7) = -г + 2, то есть порядок остатка —2 в мультипликативной группе 2*. Число д является нечетным (случай когда длина максимального цикла не делится на п) в том и только том случае, когда двойка имеет порядок по модулю р равный 4/с + 2 для некоторого неотрицательного целого к. Примером простых чисел, удовлетворяющим этим условиям, могут служить р — 3,11,19.
Например, в случае р = 3ии-6 = 2-31 граф разностного оператора выглядит следующим образом (при этом мы приведем только одно дерево, а все остальные ему изоморфны):