Графы линейных операторов и билипишицевы классы множеств Делоне тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат физико-математических наук Гарбер, Алексей Игоревич

• Гарбер, Алексей Игоревич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Гарбер, Алексей Игоревич

Введение

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

1.1 Определение графа Сд

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

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

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

2.1 Алгоритм построения графа G-p^.

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

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

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

3 Билипшицевы классы множеств Делоне

3.1 Вспомогательные леммы.

3.2 Деформации множеств, сохраняющие билипшицев класс

3.3 Об универсальности множества Делоне.

3.4 Конструкция множества, не эквивалентного решетке.

3.5 Многомерное обобщение.

3.6 "Двумерные" результаты.

Введение диссертации (часть автореферата) на тему «Графы линейных операторов и билипишицевы классы множеств Делоне»

Данная диссертация посвящена изучению сложности дискретных структур.

В первых двух главах изучаются вопросы, относящиеся к теории сложности конечных последовательностей, недавно построенной В.И. Арнольдом [1]. Речь идет о последовательностях конечной длины п с элементами из Ър. В третьей главе изучаются равномерные дискретные множества в евклидовых пространствах, так называемые множества Делоне. Среди множеств Делоне содержится относительно простой класс — класс целочисленных решеток. Основной вопрос, который мы изучаем в этой главе — существуют ли в евклидовом пространстве множества Делоне, отличающиеся от решеток с точки зрения билипшицевой эквивалентности? — восходит к М. Громову [20].

Понятие сложности конечной последовательности вводилось и ранее. Так А.Н. Колмогоров ввел понятие информационной сложности (см. [8]). Простая колмогоровская сложность равна количеству информации, которая необходима, чтобы задать последовательность. При этом сложность последовательности, естественно, зависит от того каким образом (с помощью какого "алгоритма декомпрессии") последовательность восстанавливается из сжатой последовательности информации.

В 2005 году В.И. Арнольд ввел другое понятие сложности, связанное с графом разностного оператора T>(ri) : —У Z™ (см. [1, 2, 16]). Разностный оператор V(n) действует на последовательность х — (xi,. ,хп) длины п по следующему правилу: Т>(п)х — у — (x<i — xi,., хп — xn-i,xi — хп). Граф разностного оператора представляет из себя ориентированный граф, вершинами которого являются все рп элементов пространства Z™ при этом ребро из вершины и в вершину v существует в том и только том случае, когда Т>(п)и — v.

В этом направленном графе каждая компонента связности представляет из себя цикл, к каждой вершине которого "подвешено" дерево (см. [15, Гл. 16]). При этом сложность последовательности х — вершины графа, определяется длиной притягивающего цикла и расстоянием до этого цикла на соответствующем-дереве (см. параграф 2.1).

В.И. Арнольд в [1] сформулировал и доказал ряд утверждений о графе разностного оператора в случае бинарных последовательностей из Z£. В частности, им было доказано, что в бинарном случае все деревья в графе разностного оператора изоморфны и представляют собой корневое бииарное дерево, высота которого определяется длиной п последовательности. Также в своих работах В.И. Арнольд выдвинул ряд гипотез о строении графа разностного оператора, которые были основаны на проведенных им численных экспериментах для относительно малых п.

Часть гипотез Арнольда также исследовалась в работах других авторов. Так в работе [21] О.Н. Карпенков построил графы двоичных разностных операторов для всех длин последовательностей до 25 и для некоторых бесконечных серий длин. Кроме того, в той же работе поставлен ряд задач, уточняющих гипотезу Арнольда о максимальном цикле в графе разностного оператора, которая утверждает что длина максимального цикла в графе разностного оператора всегда делится на длину п последовательности.

Первая глава диссертации посвящена изучению графа Gд для произвольного линейного оператора Л : Z™ —у Z™ над полем Zp. Этот направленный граф определяется аналогично графу разностного оператора. В первой главе получены следующие результаты, опубликованные в [10].

В параграфе 1.2 доказано, что как и в случае бинарного разностного оператора, деревья графа Ga изоморфны между собой и структура этих деревьев определяется данным оператором, точнее количеством и размером жорда-новых клеток с нулевым собственным значением в жордановой нормальной форме оператора Л. Там же приведен алгоритм алгоритм построения этих деревьев.

В параграфе 1.3 описан алгоритм построения всех циклов графа Сд. Посредством данного алгоритма циклы графа (7д получаются из жордановой нормальной формы оператора Л над алгебраическим расширением F поля Zp, которое содержит все корни характеристического многочлена оператора

А.

Отметим, что позднее в 2008 году в работах Э.Ю. Лернера [14, 22] был сформулирован и реализован другой алгоритм построения графа разностного оператора. Так, в работе [22] приведены графы разностного оператора при р — 2 для всех длин п < 160 и при р — 3 для всех п < 100.

Вторая глава посвящена более подробному исследованию случая разностного оператора и некоторых гипотез о его графе, сформулированных В.И. Арнольдом в [1, 2, 16]. Среди этих гипотез мы выделим две: гипотезу о логарифмической последовательности, которая утверждает, что логарифмическая последовательность является одной из самых сложных последовательностей. Логарифмической последовательностью I = (li,.,ln), где п = р — 1 для некоторого простого р, называется такая бинарная последовательность, для которой k = 0 в случае, если г является квадратичным вычетом по модулю р и k = 1 в противоположном случае. Вторая гипотеза Арнольда — это гипотеза о длине максимального цикла.

В параграфе 2.1 явным образом сформулирован алгоритм нахождения структуры графа разностного оператора над Zp, который является частным случаем алгоритма построения графа произвольного линейного оператора, описанного в первой главе. Отметим, что этот специальный случай алгоритма был использован О.Н. Карпенковым в [21] для построения графов бинарных разностных операторов для ряда бесконечных серий длин.

В параграфе 2.2 доказано, что для некоторых бесконечных серий простых чисел логарифмическая последовательность расположена на дереве далеко от цикла, что соответствует предположению В.И.Арнольда. С другой стороны, при некоторых простых числах это не так, например, при q = 73(п = q — 1 = 72) логарифмическая последовательность расположена непосредственно на цикле. При этом результатов о возможной длине цикла, который притягивают логарифмическую последовательность, пока не получено.

Позднее Э.Ю. Лернер [14] модифицировал логарифмическую последовательность путем добавления нуля в начало и доказал, что такие модифицированные последовательности в большинстве случаев притягиваются лишь к максимальным циклам и находятся на максимальном или почти максимальном удалении от цикла.

В параграфе 2.3 доказана гипотеза Арнольда о максимальном цикле. А именно доказано, что для любого простого р и любого числа п, не равного ра и 2ра, длина максимального цикла в соответствующем графе разностного оператора делится на п. В случае когда п = ра, длина максимального цикла равна единице, а в случае п = 2ра длина максимального цикла делится на ра, но при этом может не делиться на 2ра (например, при р — 3 или р — 11).

В параграфе 2.4 сформулирована гипотеза, полученная автором в результате вычислений, проведенных при помощи алгоритма нахождения структуры графа бинарного разностного оператора. Согласно этой гипотезе, доля вершин графа, притягиваемых циклами максимальной длины, стремится к единице. Гипотеза доказана в более слабом варианте, а именно в случае когда длины последовательностей могут принимать значения равные только степеням простых чисел.

Третья глава данной диссертации посвящена устройству дискретных множеств с точки зрения их билипшицевой эквивалентности. Вопрос о билипши-цевой эквивалентности двух множеств Делоне впервые был поставлен М. Громовым в работе [20].

Множество X в метрическом пространстве М называется множеством Делоне если найдутся две такие положительные константы г и Л, что открытые шары радиуса г с центрами в точках X не пересекаются, а замкнутые шары радиуса R покрывают все пространство М. Сам Б.Н. Делоне называл такие множества (г, Д)-системами [13]; в зарубежной литературе также можно встретить термин "separated net". Задаче об эквивалентности множеств Делоне посвящена третья глава данной диссертации.

Билипшицева эквивалентность двух множеств Делоне Х\ и Х2 в двух различных метрических пространствах Mi и М2 напрямую связана с понятием квази-изометричности метрических пространств. Два метрических пространства Mi и М2 называются квази-изометричными, если существует отображение (не обязательно биективное!) / : Mi —> М2 и константы L > 1 и С > О такие, что для любых двух точек а; и у из М\ выполнено неравенство 1 dMl(x,y) - С < dM2(f(x), /(у)) < LdMl(x,y) + С.

Кроме того, существует такая константа D > 0, что для любой точки и 6 М2 найдется такая точка х б Mi, что dM2(u,f(x)) < Здесь через с£м(-, •) мы обозначили расстояние в соответствующем метрическом пространстве М.

Известно, что пространства Mi и М2 квази-изометричны в том и только том случае, когда в них существуют подмножества Делоне Х\ С Mi и Х2 С М2 билипшицево эквивалентные друг другу (см. [20, 17]). В случае, когда в пространствах М\ и М2 нашлась пара множеств Xi С М\ и Х2 С М2, которые не эквивалентны друг другу, нельзя утверждать, что пространства Mi и М2 не являются квази-изометричными. Можно говорить об отсутствии квази-изометричности в том случае, когда в каждом из двух пространств любые два множества Делоне эквивалентны между собой, но какая-то пара подмножеств из разных пространств не эквивалентна.

Впервые вопрос о билипшицевой эквивалентности двух различных множеств Делоне в некотором метрическом пространстве был поставлен М. Громовым в работе [20, стр. 23] в следующем виде: "Какому критерию должно удовлетворять метрическое пространство X, чтобы любые два множества Делоне в нем были билипшицево эквивалентны?"

К настоящему времени получен ряд результатов как для неевклидовых, так и для евклидовых пространств произвольной размерности. Для гиперболических пространств Hd О. Богопольский [5] доказал билипшицеву эквивалентность любых двух множеств Делоне. П. Папасоглу в работе [24] доказал билипшицеву эквивалентность (как метрических пространств) двух однородных деревьев валентности кип, больших или равных 3. К. Уайт [25] доказал, что дискретное пространство с некоторыми дополнительными условиями не является аменабельным в том и только том случае, когда все его точки можно разбить на подмножества, каждое из которых билипшицево эквивалентно метрическому пространству однородного трехвалентного дерева.

В случае евклидова пространства независимо друг от друга Д. Бураго и Б. Кляйнер (см. [17]), и К. МакМаллен (см. [23]) доказали существование множества Делоне, которое не является билипшицево эквивалентным решетке Zd.

В дальнейшем в работе [18] Д. Бураго и Б. Кляйнер получили достаточное условие эквивалентности произвольного двумерного множества Делоне в евклидовой плоскости и решетки Z2, также с помощью этого условия была доказана эквивалентность ряда двумерных квазикристаллов и решетки.

В данной диссертации приведены следующие результаты, полученные автором и опубликованные в [11].

В параграфе 3.1 приведены определения и доказана основная лемма о том, что сдвиг на ограниченное расстояние не изменяет класса эквивалентности множества Делоне.

Параграф 3.2 содержит ряд достаточных условий на множество В для билипшицевой эквивалентности множеств А и A U В в случае, если оба этих множества являются множествами Делоне.

В параграфе 3.3 доказана теорема о том, что для любых двух множеств Делоне А и В в множестве А можно выбрать подмножество Ав (также являющееся множеством Делоне), которое билипшицево эквивалентно В. Полученное свойство мы называем универсальностью множеств Делоне.

В параграфе 3.4 построен конкретный пример множества Делоне А, которое не является билипшицево эквивалентным решетке Неконструктивное доказательство существования такого множества получено в работах [17] и [23]; пример, приведенный в данной диссертации, отчасти основывается на идеях статьи Бураго и Кляйнера [17].

Заключительный параграф 3.6 третьей главы содержит достаточное условие билипшицевой эквивалентности двух множеств Делоне на плоскости Е2. Достаточные условия, изложенные в параграфе 3.2, являются следствиями этого условия. Однако отметим, что более сильное условие параграфа 3.6 установлено пока лишь для двумерного случая и не известно верен ли аналог этого условия для произвольной размерности.

Особо подчеркнем, что хотя в данной диссертации для большей наглядности изложения все результаты третьей главы доказываются для двумерного евклидова пространства Е2. При этом все они, кроме результатов параграфа 3.6, могут быть практически дословно перенесены на случай произвольного d-мерного евклидова пространства Ed. Пример такого обобщения приведен в параграфе 3.5.

Список литературы диссертационного исследования кандидат физико-математических наук Гарбер, Алексей Игоревич, 2009 год

1. В.И. Арнольд, Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств: el. print, 2005. http://mms.math-net.ru/meetings/2005/arnold.pdf

2. В.И. Арнольд, Лекция: Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств, 13.05.2006г., БКЗ Академический РАН, http://elementy.ru/lib/430178/430281

3. А.Я. Белов. Задача 11, // Задачный раздел, Матем. Проев., сер. 3, вып. 4, 2000, с. 217.

4. И.И. Богданов, Г.Р. Челноков. Решение задачи 4-И-, // Задачный раздел, Матем. Проев., сер. 3, вып. 8, 2004, 249-252.

5. О.В. Богопольский, Бесконечные соизмеримые гиперболические группы билипшицево эквивалентны,// Алгебра и логика, т. 36, вып. 3, 1997, 259-272.

6. Н. Бурбаки, Алгебра (Многочлены и поля. Упорядоченные группы), 1965.

7. О.Н. Василенко, А.И. Галочкин, Сборник задач по теории чисел, 1995.

8. Н.Н. Верещагин, В.А. Успенский, А.Х. Шень, Колмогоровская сложность, el. print, http://lj.streamclub.ru/books/complex/uspen.ps

9. А.И. Гарбер, Сложные последовательности по В.И. Арнольду, // Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007, 374-376.

10. А.И. Гарбер, Графы линейных операторов, j j Тр. МИАН, т. 263, 2008, 64-71.

11. А.И. Гарбер, О классах эквивалентности множеств Делоне, // Модел. и Анал. Инф. Сист., т. 16, вып. 2, 2009, 109-118.

12. С.Б. Гашков, В.Н. Чубариков, Арифметика. Алгоритмы. Сложность вычислений, 2000.

13. Б.Н. Делоне, Геометрия положительных квадратичных форм, УМН, 1937, 3, 16-62.

14. Э.Ю. Лернер. Мультипликативная функция вместо логарифма, el. print, 2008. http://kek.ksu.ru/kek2/MyArnold.pdf

15. Ф. Харари. Теория графов, М. Мир, 1973.

16. V.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.

17. D. Burago, B. Kleiner, Separated nets in Euclidean space and Jacobians of bi-Lipschitz maps, //Geom. Funct. Anal. vol. 8, 1998, 273-282.

18. D. Burago, B. Kleiner, Rectifying separated nets, // Geom. and Func. Anal, vol. 12, 2002, 80-92.

19. A.I. Garber, Graphs of difference operators for p-ary sequences, // Funct. Anal, and Other Math., 2006, Vol.1, N 2, p. 179-195.

20. M. Gromov. Asymptotic invariants for infinite groups, // London Mathematical Society Lecture Notes, vol. 182.Geometric group theory, eds. J.A. Niblo, M.A. Roller, J.W.S. Cassels, 1993.

21. O.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.

22. E.Yu. Lerner. Tables of graphs of binary and ternary sequences differentiation, el. print, 2008. http://arxiv.org/pdf/0704.2947vl

23. C. McMullen, Lipschitz maps and nets in Euclidean space, // Geom. Funct. Anal. vol. 8, 1998, 304-314.

24. P. Papasoglu. Homogeneous trees are bi-Lipschitz equivalent, // Geom. Dedicata, vol. 54, 1995, 301-306.

25. K. Whyte, Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture, // Duke Math. J. vol. 99, 1999, 93-112.