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

Математический институт им. В.А. Стеклова Российская Академия Наук

□□3487БВ7

На правах рукописи УДК 514.169, 519.173, 514.17

Гарбер Алексей Игоревич

ГРАФЫ ЛИНЕЙНЫХ ОПЕРАТОРОВ И БИЛИПИШИЦЕВЫ КЛАССЫ МНОЖЕСТВ ДЕЛОНЕ

Специальность 01.01.04 — геометрия и топология

1 О ДЕК 2009

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2009

003487667

Работа выполнена в отделе геометрии и топологии Математического института им. В.А. Стеклова РАН

Научный руководитель:

доктор физико-математических наук, профессор МГУ Николай Петрович Долбилин

Официальные оппоненты:

Ведущая организация:

Санкт-Петербургский Государственный Университет

Защита диссертации состоится 24 декабря 2009 в 14 часов на заседании диссертационного совета Д002.022.03 в Математическом институте им. В.А. Стеклова Российской Академии Наук по адресу: 119991, Москва, ул. Губкина, 8 (9 этаж).

С диссертацией можно ознакомиться в библиотеке Математического института им. В.А. Стеклова РАН.

Автореферат разослан ноября 2009 г.

доктор физико-математических наук, профессор ЯрГУ

Владимир Леонидович Дольников

кандидат физико-математических наук Илья Дмитриевич Шкредов

Председатель диссертационного совета

Д002.022.03 в МИАН член-корреспондент РАН

А. Н. Паршин

Общая характеристика работы

Актуальность темы

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

В первых двух главах изучаются вопросы относящиеся к теории сложности конечных последовательностей, недавно построенной В.И. Арнольдом. Речь идет о последовательностях конечной длины п с элементами из Zp.

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

В 2005 году В.И. Арнольд ввел другое понятие сложности, связанное с графом разностного оператора Т>(п) : Z™ —> Zp2'3'4. Разностный оператор Т>(п) действует на последовательность х = (xi,..., хп) длины п по следующему правилу: Т>(п)х = у = (х 2~xi,... ,xn — xn-i,xi — xn). Граф разностного оператора представляет из себя ориентированный граф, вершинами которого являются все рп элементов пространства Z™. При этом ребро из вершины и в вершину v существует в том и только том случае, когда Т>(п)и = v.

В этом направленном графе каждая компонента связности представляет из себя единственный цикл, к каждой из вершин которого "подвешено" некоторое дерево5. При этом сложность последовательности х — вершины графа, определяется длиной притягивающего цикла и расстоянием до этого цикла на соответствующем дереве.

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

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

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г., БКЗ Академический РАН, http: //elementy.ru/lib/430178/430281

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

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

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

Среди гипотез, сформулированных В.И. Арнольдом, мы выделим две следующие: гипотезу о логарифмической последовательности, которая утверждает, что логарифмическая последовательность является одной из самых сложных последовательностей. Логарифмической последовательностью I = (¿i ,...,!„), где п = р — 1 для некоторого простого р, называется такая бинарная последовательность, для которой Ц = 0 в случае если i является квадратичным вычетом по модулю р и Ii = 1 в противоположном случае. Эта последовательность называется логарифмической так как, для каждого фиксированного первообразного корня g но простому модулю р она показывает, в какую: четную или нечетную, — степень нужно возвести g, чтобы получить остаток г. Тем самым логарифмическая последовательность показывает четность логарифма остатка i по основанию д.

Вторая интересующая нас гипотеза Арнольда — это, упомянутая выше, гипотеза о длине максимального цикла.

В работах Э.Ю. Лернера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. http://kek.ksu.ru/kek2/MyArnold.pdf

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

горнтмов построения графа разностного оператора. В этих работах приведены графы разностного оператора прн р — 2 для всех длин до 160 и при р = 3 для всех длин до 100. Также Э.Ю. Лернер модифицировал логарифмическую последовательность путем добавления нуля в начало и доказал, что такие модифицированные последовательности в большинстве случаев притягиваются лишь к максимальным циклам и находятся на максимальном или почти максимальном удалении от цикла.

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

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

Билипшицева эквивалентность двух множеств Делоне Х\ и X2 в двух различных метрических пространствах М\ и Мг напрямую связана с понятием квази-изометричности метрических пространств. Два метрических пространства М\ и Мг называются квази-изометричными если существует отображение (не обязательно биективное!) / : М\ —У М2 и константы L > 1 и С > 0 такие, что для любых двух точек х и у из Mi выполнено неравенство

dMl{x,y) -С < dM2{f{x),f{y)) < LdMl(x,y) + С.

Кроме того, существует такая константа D > 0, что для любой точки и £ М2 найдется такая точка х 6 Mi, что ймг{и, f{x)) < D.

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

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

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

М\ и Мг не являются квази-изометричными. Можно говорить об отсутствии квази-изометричности в том случае, когда любые два множества Делоне в каждом из двух пространств эквивалентны между собой.

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

К настоящему времени получен ряд результатов как для неевклидовых, так и для евклидовых пространств произвольной размерности. Для гиперболических пространств Н^ О. Богопольский11 доказал билип-шицеву эквивалентность любых двух множеств Делоне. П. Папасоглу12 доказал билипшицеву эквивалентность (как метрических пространств) двух однородных деревьев валентности к и п больших или равных 3. К. Уайт13 доказал, что дискретное пространство с ограниченно геометрией не является аменабельным в том и только том случае, когда все его точки можно разбить на подмножества, каждое из которых билипшицево эквивалентно метрическому пространству однородного трехвалентного дерева.

• В случае евклидова пространства Е^ независимо друг от друга Д. Бу-раго и Б. Кляйнер14, и К. МакМаллен15 доказали существование множества Делоне, которое не является билипшицево эквивалентным решетке ЪА.

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

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

12Р. Papasoglu. Homogeneous trees are bi-Lipschitz equivalent, // Geom. Dedicata, vol. 54, 1995, 301306.

13K. Wliyte, 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. Funct. Anal. vol. 8, 1998, 273-282.

I5C. 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.

Цель работы

1. Исследовать свойства графов разностных операторов действующих в Zp и, по возможности, обобщить полученные результаты на случай произвольных линейных операторов действующих также в Применить полученную теорию к ряду гипотез о графах разностных операторов.

2. Исследовать множества Делоне в евклидовых пространствах произвольной размерности с точки зрения их билипшицевой эквивалентности. Получить новые необходимые и достаточные условия эквивалентности таких множеств. Построить явные примеры множеств Делоне не эквивалентных решетке.

Основные методы исследования

В первых двух главах диссертации используются методы классической линейной алгебры и теории многочленов над конечными полями. В третьей главе диссертации используются методы дискретной и комбинаторной геометрии.

Научная новизна

Основные результаты диссертации являются новыми и состоят в следующем:

1. Приведен алгоритм нахождения структуры графа произвольного линейного оператора, действующего на пространстве Доказана гипотеза Арнольда о длине максимального цикла для произвольного простого р : длина максимального цикла в графе разностного оператора делится на длину последовательности п, если п ф ра и п + 2ра.

2. Показано, что доля последовательностей, притягиваемых циклами максимальной длины в графе разностного оператора, стремится к единице, если длины последовательностей пробегают только значения степеней простых чисел.

3. Показано, что для п = 72(р — 73) логарифмическая последовательность I находится на одном из циклов. Таким образом гипотеза Арнольда о логарифмической последовательности нуждается в уточнении.

4. Получен ряд достаточных условий билиишицевой эквивалентности множеств Делоне. На их основе дан ответ на ранее поставленные важные вопросы о множествах Делоне.

5. Для любого d построен явный пример множества Делоне в не эквивалентного решетке Zd.

Теоретическая и практическая ценность

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

Апробация результатов

Основные результаты диссертации неоднократно докладывались на семинаре "Дискретная геометрия и геометрия чисел" иод руководством Н.П. Долбилина и Н.Г. Мощевитина (мех-мат МГУ, 2006-2009 гг.); на математическом семинаре В.И. Арнольда (мех-мат МГУ, 2006 г.); на семинаре им. М.М. Постникова "Алгебраическая топология и ее приложения" под руководством В.М. Бухштабера, А.В. Чернавского, И.А. Дынникова, JI.A. Алании, Д.В. Миллионщикова и Т.Е. Панова (мех-мат МГУ, 28 апреля 2009 г.); на семинаре по геометрии им. И.Ф. Шарыгина (МЦНМО, 7 мая 2009 г.).

Также результаты диссертации докладывались на следующих международных конференциях и семинарах: International ISM Symposium: Packing and random packing, Токио, 2006; IX Международный семинар "Дискретная математика и ее приложения", посвященный 75-летшо со дня рождения академика О.Б. Лупанова, Москва, 2007; 10-th International Conference on Discrete Mathematics, Дортмунд, 2007; Международная конференция "Дифференциальная геометрия и топология", посвященная 100-летию со дня рождения JI.C. Понтрягина, Москва, 2008; Российско-японская конференция "Discrete Geometry and Statistics of Configurations", Москва, 2009.

Публикации

Основные результаты диссертации опубликованы в четырех работах, список которых приведен в конце автореферата.

Структура диссертации

Диссертация состоит из введения, трех глав и списка литературы. Полный объем диссертации — 56 страниц, библиография включает 25 наименований.

Краткое содержание работы

Во введении дается обзор результатов, связанных с темой диссертации. Также формулируются основные результаты диссертации.

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

В параграфе 1.1 определяется граф произвольного линейного оператора А : Ж™ —>■ Ж™. Это направленный граф вершинами которого являются все рп векторов пространства 2™. При этом из каждой вершины и выходит ровно одно ребро в такую вершину V, для которой V = Ли.

Также в этом параграфе доказывается, что построение графа (Тд может быть разбито на две части: построение деревьев и построение циклов. Первое представляет из себя построение графа оператора А, то есть ограничения оператора А на пространство «До, а второе — построение графа оператора А — ограничения оператора А на пространство А*. При этом пространство Ао является ядром некоторой (достаточно большой) степени оператора А, а А* — образом.

В параграфе 1.2 доказано, что все деревья в графе (7д изоморфны и приведен следующий индуктивный алгоритм построения дерева, притягивающегося нулевой вершиной О. Этот алгоритм использует размеры к\<к,2< ... <кт всех жордановых клеток оператора А с нулевым собственным значением (или размеры всех жордановых клеток оператора

Обозначим и — тш(г, Тогда доказанный алгоритм постро-

ения вспомогательного дерева Т~т выглядит следующим образом, мы будем последовательно строить деревья для всех г от 1 до кт.

Вначале строим дерево для г = 1. На первом уровне дерева находится рш = р11 вершин, это прообразы нулевой последовательности.

Также отдельно построим дерево для г = 2. На втором уровне этого дерева находится р1г вершин и они должны объединяться в группы по р11, при этом вершины из одной группы имеют общий образ.

Для построения дерева Т1 необходимо в дереве Т!-1 выделить р1^-1 вершин на первом уровне, при этом следует взять те вершины, из которых уже "растут" деревья до (г — 1)-го уровня, и заменить эти деревья вида Т1~2 на деревья Т\которые изоморфны уже построенному дереву Гд-1. При этом не имеет значения какие конкретно выбирать вершины на первом уровне Т^Г1, важно только, чтобы все они имели прообразы на г — 1 уровне, в остальном все такие вершины эквивалентны.

Для получения итогового дерева притягиваемого нулевой вершиной в графе нужно в построенном дереве Т~т удалить произвольную вершину на первом уровне, у которой есть прообразы на верхнем уровне. При этом удаляются и все вершины, которые притягиваются удаленной.

Также в завершении параграфа 1.2 приведен пример построения деревьев графа в случае р = 2, т — 2, к\ = 2, кг — 4.

Параграф 1.3 посвящен формулировке и доказательству алгоритма построения всех циклов графа (?д. Этот алгоритм использует строение жордановой нормальной формы оператора Л над полем F, которое является алгебраическим расширением Ър, содержащим все = с^-Рд(^) корней характеристического многочлена -Рд(-г) оператора Л.

Пусть ¿д — количество различных неприводимых над Ър делителей многочлена Рд{г)

Положим 5г = {X}, С Р множество сопряженных (в Е) кор-

ней многочлена Рд(г), являющиеся корнями его г-го неприводимого делителя рДг). Здесь п это степень неприводимого многочлена р^г).

Всем корням из соответствует одинаковое количество и размеры жордановых клеток в жордановой нормальной форме оператора А над полем Е; пусть количество таких жордановых клеток равно оц, а их размеры равны й,1 > й? > ... > Кроме того, положим ал = шаха*. Также доказанный алгоритм использует следующее

Определение 1.3.17. Порядком многочлена <3 £ не делящегося

на г, назовем минимальное натуральное д такое, что г4 — 1 делится на (2. Обозначим огс! Q = q.

Для каждого неприводимого делителя многочлена вида р{(г),

1 < ^ < Ад обозначим через его порядок.

В дальнейшем доказывается, что длина цикла, которому принадлежит вектор х, определяется ассоциированным с ним многочленом Рх = р1±р12 ■ ■ ■ и набором ■ ■. ,цл), где г^ < я] для любого j < ¿д.

Следовательно, достаточно найти соответствующую длину и количество векторов, ассоциированных с некоторым фиксированным набором. Это можно сделать благодаря следующим двум утверждениям.

Утверждение 1.3.26. Длина цикла, которому принадлежит любой из рассматриваемых векторов, равна Где 7 — наименьшее число такое, что р7 > у для всех а с1 — наименьшее общее кратное всех чисел q■j, для которых ij > 0.

Утверждение 1.3.27. Количество векторов, которые соответствуют многочлену Рх = р^р^ ■ ■ равно произведению

П

/ аЛ

1<к<1л:гк^0

2 гк(пип(4,г'к)-1)

-Р3

=!,«■£/о

V

Вторая глава данной диссертации посвящена детальному исследованию графа разностного оператора. В параграфе 2.1 формулируются результаты первой главы по отношению к графу разностного оператора Т>(п), который действует на последовательность х = {х\,..., хп) по правилу Т>{п)х = (х2 — XI,жз — хг, ■.. ,Х1 — хп). Результаты второй главы используют представление п в виде п = раМ, где М не делится на р. В частности в этом параграфе доказываются

Утверждение 2.1.6. Все деревья в графе (>£>(„) представляют из себя полные р-ичные деревья высотой ра, у которых убрано по одному ребру выходящему из корня (вместе со всеми сходящимися к этому ребру вершинами и ребрами).

Утверждение 2.1.7. Все параметры щ равны 1.

Следствие 2.1.9. Длина максимального цикла в графе Сг>(п) это порядок характеристического многочлена Р£>(п\{%) = 1 ■

Следствие 2.1.12. Pt{n) = (pip2 ■ • ■Ptv(n))pa, где рър2, ■ ■ ■ ,pt - различные неприводимые многочлены. При этом P-ñm) = Р1Р2 ■ ■ ■ Vtvм и

В параграфе 2.2 исследуется гипотеза о логарифмической последовательности, которая формулируется следующим образом:

Гипотеза 1. Пусть д — простое число. Рассмотрим двоичную последовательность I = (¿1, ¿2,..., /„) длины п = д — 1, которая определена следующим образом:

Тогда последовательность I, или логарифмическая последовательность, является сложной или почти самой сложной, то есть притягивающий ее цикл в графе разностного оператора имеет максимальную длину и I расположена среди вершин, находящихся на одном из двух верхних уровней дерева.

Основными результатами параграфа 2.2 являются следующие три утверждения:

Утверждение 2.2.5. Если д = 4к + 3, то логарифмическая последовательность I = ... ,1п) находится на вершине дерева, то есть наиболее удалена от цикла.

Замечание. При этом дерево имеет высоту 2.

Утверждение 2.2.6. Если д = 8А; + 5, то I находится в дереве на высоте 3.

Замечание. При этом дерево имеет высоту 4.

Утверждение 2.2.6. Пусть д = 73, тогда последовательность I = (¿1,..., /72) находится на цикле.

Тем самым в некоторых случаях (когда р — 1 не делится на 8) доказано, а в некоторых случаях (например при р = 73) опровергнуто утверждение гипотезы 1, относящееся к положению логарифмической последовательности на дереве графа разностного оператора.

tv(n) — tv(M)-

0, если г — квадратичный вычет по модулю q

1, если г — квадратичный невычет по модулю q

В параграфе 2.3 доказана гипотеза Арнольда о длине максимального цикла в графе разностного оператора. При условии, что Ь(п) это длина максимального цикла в графе Ср(п), гипотеза формулируется следующим образом:

Гипотеза 2. В случае р = 2 если п не является степенью двойки, то число Цп) делится на п.

В параграфе 2.3 эта гипотеза доказана в более общем случае для произвольного р. Основной результат, подтверждающий гипотезу Арнольда о длине максимального цикла, содержит

Теорема 2.3.5. Если п не равняется ра и 2ра, то длина максимального цикла Ь{п) делится на п.

Исключительные случаи это п = ра или п — 2ра, то есть если п = раМ, то М = 1 или М = 2 (только в случае р > 2). В первом случае существует единственный цикл в графе и его длина равна 1. В случае М = 2 длина максимального цикла равна paq) где д это порядок линейного многочлена Р^^(г) = г + 2, то есть порядок остатка —2 в мультипликативной группе Ъ*р. Число д является нечетным (случай когда длина максимального цикла не делится на п) в том и только том случае, когда двойка имеет порядок по модулю р равный 4к + 2. Примером простых чисел, удовлетворяющим этим условиям, могут служить р = 3,11,19.

Параграфов 2.4 содержит две гипотезы, сформулированные на основании вычислений графов разностных операторов по алгоритму первой главы.

Гипотеза 3. Пусть С(п) общее количество циклов, а Стах(п) — количество циклов максимальной длины в графе Ср(п). Тогда отношение С™(п)>' или доля циклов максимальной длины, стремится к единице когда п стремится к бесконечности.

Гипотеза 4. Пусть ьтах(п) — доля вершин, притягиваемых циклами максимальной длины в графе (?2>(п)- Тогда утах(п) —> 1 при п —^ со.

Основным результатом этого параграфа, является доказательство частного случая гипотезы 4. Этот факт содержит

Теорема 2.4.6. Если п пробегает только степени простых чисел и стремится к бесконечности, то при этом vmax(n) стремится к единице.

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

В параграфе 3.1 даны следующие определения двумерных множеств Делоне и их билипшицевой эквивалентности:

Определение 3.1.1. Множество А с Е2 называется множеством Делоне если найдутся две такие положительные константы г а и Ra, что круги радиуса г а с центрами в точках множества А не пересекаются по внутренним точкам, а круги радиуса Ra покрывают всю плоскость Е2. Также такое множество называется (га, Ял)-системой.

Определение 3.1.2. Пусть А я В два подмножества евклидовой плоскости Е2. Отображение / : А —> В называется билипшицевым если найдется число L > 1 такое, что для любых двух точек х,у 6 А выполнено двойное неравенство

^ • d(x, у) < d(f(x),f(y)) < L ■ d(x, у),

где •) обозначает евклидово расстояние на плоскости Е2.

Определение 3.1.3. Подмножества А и В евклидовой плоскости называются билипшицево эквивалентными если существует билипшице-ва биекция / : А —> В. Будем писать для эквивалентных множеств А~ В.

Lip

Также в этом параграфе доказана основная

Лемма 3.1.4. Пусть А и В два таких множества Делоне, что существуют такая биекция f : А —> В и такая константа С > О, что для любой точки х £ А выполнено неравенство d(x, f(x)) < Тогда А ~ В.

Lip

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

Теорема 3.2.3. Пусть А — некоторое множество Делоне. Если множество С удовлетворяет следующим условиялг:

1. ЛпС = 0;

2. В = A U С является множеством Делоне;

3. Существует прямая t, натуральное Т и положительное действительное £ такие, что в любой отрезок длины £ на прямой £ проецируется не более Т точек из множества С;

то В ~ А.

Lip

и следующее

Следствие 3.2.5. Если D с А удовлетворяет условию 2 теоремы 3.2.3, то A\D ~ А.

Lip

В параграфе 3.3 доказано следующее свойство, которое мы называем свойством универсальности множества Делоне:

Теорема 3.3.3. Пусть А и В два множество Делоне, тогда существует множество Делоне С С В такое, что А ~ С.

Lip

Таким образом, каждое множество Делоне содержит в качестве собственного подмножества представителя из каждого билипшицева класса.

В параграфе 3.4 приводится явный пример множества Делоне А, которое не эквивалентно решетке Z2. Этот пример основывается на доказательстве Бураго и Кляйнера существования такого множества.

Следующее построение множества Делоне А приведено в параграфе 3.4 диссертации. Пусть С — множество всех квадратов с целыми сторонами, разбитых на клетки со стороной 1, причем в каждом квадрате отмечено несколько точек в центрах клеток таким образом, что в каждой

клетке отмечено не больше одной точки и в каждом квадрате из четырех клеток не менее одной. Два таких клеточных квадрата будем считать одинаковыми если их можно совместить параллельным переносом.

Рассмотрим клетчатую плоскость и выделим на ней попарно непересекающиеся (даже по границе) квадраты соответствующие квадратам из С. Множество Делоне А будет иметь следующий вид: в центре каждой клетки не принадлежащей ни одному из выделенных квадратов будет по одной точке, кроме того, в выделенных квадратах мы отметим точки так же как мы их отметили в аналогичных квадратах из множества С.

Теорема 3.4.3. Построенное множество А не является билипшицево эквивалентным решетке 7?.

В параграфе 3.5 приведен пример обобщения результатов третьей главы на многомерный случай. В этом параграфе приведен конкретный пример (¿-мерного множества Делоне, которое не эквивалентно решетке ЪА.

В параграфе 3.6 для двумерного случая доказаны дополнительные достаточные условия (кроме условий параграфа 3.2), чтобы два множества Делоне принадлежали одному классу эквивалентности. Основным результатом этого параграфа является следующий признак эквивалентности:

Теорема 3.6.4. Пусть X и У — два множества Делоне на плоскости Е2. Предположим, что существует такая константа Б > О, что для любого натурального N и любого квадрата N х N симметрическая разность ХАУ содержит не более БЫ точек в этом квадрате. Тогда множества X и У билипшицево эквивалентны.

Для доказательства теоремы 3.6.4 устанавливается, что существует биекция между множествами X и У, удовлетворяющая условиям леммы 3.1.4, откуда следует их билипшицева эквивалентность.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю Николаю Петровичу Долбилину за постановку задач, их обсуждение и многолетнюю поддержку. Автор выражает благодарность академику Владимиру Игоревичу Арнольду за внимание к работе и ценные замечания.

Публикации автора по теме диссертации

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

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

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

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

Введение

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.

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.