Введение к работе
Актуальность темы
Данная диссертация посвящена изучению сложности дискретных структур.
В первых двух главах изучаются вопросы относящиеся к теории сложности конечных последовательностей, недавно построенной В.И. Арнольдом. Речь идет о последовательностях конечной длины п с элементами из 1р.
Понятие сложности конечной последовательности вводилось и ранее. Так А.Н. Колмогоров ввел понятие информационной сложности1. Простая колмогоровская сложность равна количеству информации, которая необходима, чтобы задать последовательность. При этом сложность последовательности, естественно, зависит от того каким образом (с помощью какого "алгоритма декомпрессии") последовательность восстанавливается из сжатой последовательности информации.
В 2005 году В.И. Арнольд ввел другое понятие сложности, связанное с графом разностного оператора Т>(п) : Z —> Z2'3'4. Разностный оператор Т>(п) действует на последовательность х = (жі,..., хп) длины п по следующему правилу: Т>(п)х = у = (х2 — Х\,... ,xn — xn-i, Х\ —хп). Граф разностного оператора представляет из себя ориентированный граф, вершинами которого являются все рп элементов пространства Z"-. При этом ребро из вершины и в вершину v существует в том и только том случае, когда Т>(п)и = v.
В этом направленном графе каждая компонента связности представляет из себя единственный цикл, к каждой из вершин которого "подвешено" некоторое дерево5. При этом сложность последовательности х — вершины графа, определяется длиной притягивающего цикла и расстоянием до этого цикла на соответствующем дереве.
ХВ.А. Успенский, Н.Н. Верещагин, А.Х. Шень, Колмогоровская сложность, el. print.
2В.И. Арнольд, Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств: el. print, 2005.
3V.I. Arnold, Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions// Funct. Anal, and Other Math., 2006, Vol.1, N 1, p. 1-18.
4В.И. Арнольд, Лекция: Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств, 13.05.2006г., БКЗ Академический РАН,
5Ф. Харари. Теория графов, М. Мир, 1973.
В.И. Арнольд сформулировал и доказал ряд утверждений о графе разностного оператора в случае бинарных последовательностей из Z^. В частности, им было доказано, что в бинарном случае все деревья в графе разностного оператора изоморфны и представляют собой корневое бинарное дерево, высота которого определяется длиной п последовательности. Также в своих работах В.И. Арнольд выдвинул ряд гипотез о строении графа разностного оператора, которые были основаны на проведенных им численных экспериментах для относительно малых п.
Часть гипотез Арнольда также исследовалась в работах других авторов. Так О.Н. Карпенков6 построил графы двоичных разностных операторов для всех длин последовательностей до 25 и для некоторых бесконечных серий длин. Кроме того, в той же работе поставлен ряд задач, уточняющих гипотезу Арнольда о длине максимального цикла в графе разностного оператора, которая утверждает что длина максимального цикла в графе разностного оператора всегда делится на длину п последовательности, за исключением случая п = ра.
Среди гипотез, сформулированных В.И. Арнольдом, мы выделим две следующие: гипотезу о логарифмической последовательности, которая утверждает, что логарифмическая последовательность является одной из самых сложных последовательностей. Логарифмической последовательностью I = (/i,..., ln), где п = р — 1 для некоторого простого р, называется такая бинарная последовательность, для которой /^ = 0 в случае если і является квадратичным вычетом по модулю р и li = 1 в противоположном случае. Эта последовательность называется логарифмической так как, для каждого фиксированного первообразного корня g по простому модулю р она показывает, в какую: четную или нечетную, — степень нужно возвести д, чтобы получить остаток і. Тем самым логарифмическая последовательность показывает четность логарифма остатка і по основанию д.
Вторая интересующая нас гипотеза Арнольда — это, упомянутая выше, гипотеза о длине максимального цикла.
В работах Э.Ю. Лернера7'8 сформулирован и реализован один из ал-
6O.N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets,// Funct. Anal, and Other Math., 2006, Vol.1, N 2, p. 197-202.
7Э.Ю. Лернер. Мультипликативная функция вместо логарифма, el. print, 2008.
8E.Yu. Lerner. Tables of graphs of binary and ternary sequences differentiation, el. print, 2008.
горитмов построения графа разностного оператора. В этих работах приведены графы разностного оператора при р = 2 для всех длин до 160 и при р = 3 для всех длин до 100. Также Э.Ю. Лернер модифицировал логарифмическую последовательность путем добавления нуля в начало и доказал, что такие модифицированные последовательности в большинстве случаев притягиваются лишь к максимальным циклам и находятся на максимальном или почти максимальном удалении от цикла.
Третья глава данной диссертации посвящена устройству дискретных множеств с точки зрения их билипшицевой эквивалентности.
Множество X в метрическом пространстве М называется множеством Делоне если найдутся две такие положительные константы г и Л, что открытые шары радиуса г с центрами в точках X не пересекаются, а замкнутые шары радиуса R покрывают все пространство М. Сам Б.Н. Делоне называл такие множества (г, Л)-системами9; в зарубежной литературе также можно встретить термин "separated net". Вопрос о билипшицевой эквивалентности двух множеств Делоне был поставлен М. Громовым10.
Билипшицева эквивалентность двух множеств Делоне Х\ и Х2 в двух различных метрических пространствах М\ и М2 напрямую связана с понятием квази-изометричности метрических пространств. Два метрических пространства М\ и М2 называются квази-изометричными если существует отображение (не обязательно биективное!) / : М\ —> М2 и константы L > 1 и С > 0 такие, что для любых двух точек х и у из М\ выполнено неравенство
-dMl(x,y) -С < dM2(f(x)J(y)) < LdMl(x,y) + C.
Кроме того, существует такая константа D > 0, что для любой точки и Є УІ2 найдется такая точка х Є Мі, что dM2(u} f(x)) < D.
Известно, что пространства Mi и М2 квази-изометричны в том и только том случае, когда в них существуют множества Делоне Х\ С М\ и Х2 С М-2 билипшицево эквивалентные друг другу. В случае, когда в пространствах М\ и М2 нашлась пара множеств Х\ С М\ и Х2 С М2, которые не эквивалентны друг другу, нельзя утверждать, что пространства
9Б.Н. Делоне, Геометрия положительных квадратичных форм, УМН, 1937, 3, 16-62. 10М. Gromov. Asymptotic invariants for infinite groups, // London Mathematical Society Lecture Notes, vol. 182,Geometric group theory, eels. J.A. Niblo, M.A. Roller, J.W.S. Cassels, 1993.
М\ и М^ не являются квази-изометричными. Можно говорить об отсутствии квази-изометричности в том случае, когда любые два множества Делоне в каждом из двух пространств эквивалентны между собой.
Впервые вопрос о билипшицевой эквивалентности двух различных множеств Делоне в некотором метрическом пространстве был поставлен М. Громовым в следующем виде:"Какому критерию должно удовлетворять метрическое пространство X, чтобы любые два множества Делоне в нем были билипшицево эквивалентны?"
К настоящему времени получен ряд результатов как для неевклидовых, так и для евклидовых пространств произвольной размерности. Для гиперболических пространств Ш1 О. Богопольский11 доказал билип-шицеву эквивалентность любых двух множеств Делоне. П. Папасоглу12 доказал билипшицеву эквивалентность (как метрических пространств) двух однородных деревьев валентности кип больших или равных 3. К. Уайт13 доказал, что дискретное пространство с ограниченно геометрией не является аменабельным в том и только том случае, когда все его точки можно разбить на подмножества, каждое из которых билипшицево эквивалентно метрическому пространству однородного трехвалентного дерева.
В случае евклидова пространства Kd независимо друг от друга Д. Бу-раго и Б. Кляйнер14, и К. МакМаллен15 доказали существование множества Делоне, которое не является билипшицево эквивалентным решетке IIі.
В дальнейшем Д. Бураго и Б. Кляйнер16 получили достаточное условие эквивалентности произвольного двумерного множества Делоне и решетки Z2, также с помощью этого условия была доказана эквивалентность ряда двумерных квазикристаллов и решетки.
иО.В. Богопольский, Бесконечные соизмеримые гиперболические группы билипшицево эквивалентны,/ / Алгебра и логика, т. 36, вып. 3, 1997, 259-272.
12Р. Papasoglu. Homogeneous trees are bi-Lipschitz equivalent, // Geom. Dedicata, vol. 54, 1995, 301-306.
13K. Whyte, Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture, // Duke Math. J. vol. 99, 1999, 93-112.
14D. Burago, B. Kleiner, Separated nets in Euclidean space and Jacobians of bi-Lipschitz maps, //Geom. Fund. Anal. vol. 8, 1998, 273-282.
15C. McMullen, Lipschitz maps and nets in Euclidean space, // Geom. Funct. Anal. vol. 8, 1998, 304-314.
16D. Burago, B. Kleiner, Rectifying separated nets, // Geom. and Func. Anal. vol. 12, 2002, 80-92.
Цель работы
Исследовать свойства графов разностных операторов действующих в ZJ) и, по возможности, обобщить полученные результаты на случай произвольных линейных операторов действующих также в Z"-. Применить полученную теорию к ряду гипотез о графах разностных операторов.
Исследовать множества Делоне в евклидовых пространствах произвольной размерности с точки зрения их билипшицевой эквивалентности. Получить новые необходимые и достаточные условия эквивалентности таких множеств. Построить явные примеры множеств Делоне не эквивалентных решетке.
Основные методы исследования
В первых двух главах диссертации используются методы классической линейной алгебры и теории многочленов над конечными полями. В третьей главе диссертации используются методы дискретной и комбинаторной геометрии.
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем:
Приведен алгоритм нахождения структуры графа произвольного линейного оператора, действующего на пространстве Z. Доказана гипотеза Арнольда о длине максимального цикла для произвольного простого р : длина максимального цикла в графе разностного оператора делится на длину последовательности п, если п = ра и п ф 2ра.
Показано, что доля последовательностей, притягиваемых циклами максимальной длины в графе разностного оператора, стремится к единице, если длины последовательностей пробегают только значения степеней простых чисел.
Показано, что для п = 72(р = 73) логарифмическая последовательность I находится на одном из циклов. Таким образом гипотеза Арнольда о логарифмической последовательности нуждается в уточнении.
Получен ряд достаточных условий билипшицевой эквивалентности множеств Делоне. На их основе дан ответ на ранее поставленные важные вопросы о множествах Делоне.
Для любого d построен явный пример множества Делоне в Ed, не эквивалентного решетке IIі.
Теоретическая и практическая ценность
Диссертация имеет теоретический характер. Результаты, полученные в первой части диссертации, могут быть использованы для дальнейшего исследования структуры графов линейных операторов над произвольными конечными полями. Результаты второй части диссертации могут быть использованы для исследования классов эквивалентности дискретных множеств в евклидовых пространствах произвольной размерности.
Апробация результатов
Основные результаты диссертации неоднократно докладывались на семинаре "Дискретная геометрия и геометрия чисел" под руководством Н.П. Долбилина и Н.Г. Мощевитина (мех-мат МГУ, 2006-2009 гг.); на математическом семинаре В.И. Арнольда (мех-мат МГУ, 2006 г.); на семинаре им. М.М. Постникова "Алгебраическая топология и ее приложения" под руководством В.М. Бухштабера, А.В. Чернавского, И.А. Дынникова, Л.А. Алании, Д.В. Миллионщикова и Т.Е. Панова (мех-мат МГУ, 28 апреля 2009 г.); на семинаре по геометрии им. И.Ф. Шарыгина (МЦНМО, 7 мая 2009 г.).
Также результаты диссертации докладывались на следующих международных конференциях и семинарах: International ISM Symposium: Packing and random packing, Токио, 2006; IX Международный семинар "Дискретная математика и ее приложения", посвященный 75-летию со дня рождения академика О.Б. Лупанова, Москва, 2007; 10-th International Conference on Discrete Mathematics, Дортмунд, 2007; Международная конференция "Дифференциальная геометрия и топология", посвященная 100-летию со дня рождения Л.С. Понтрягина, Москва, 2008; Российско-японская конференция "Discrete Geometry and Statistics of Configurations", Москва, 2009.
Публикации
Основные результаты диссертации опубликованы в четырех работах, список которых приведен в конце автореферата.
Структура диссертации
Диссертация состоит из введения, трех глав и списка литературы. Полный объем диссертации — 56 страниц, библиография включает 25 наименований.
