WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

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

В параграфе 1.1 определяется граф произвольного линейного оператора A : Zn - Zn. Это направленный граф GA, вершинами которого p p являются все pn векторов пространства Zn. При этом из каждой вершиp ны u выходит ровно одно ребро в такую вершину v, для которой v = Au.

Также в этом параграфе доказывается, что построение графа GA может быть разбито на две части: построение деревьев и построение циклов. Первое представляет из себя построение графа оператора A, то есть ограничения оператора A на пространство A0, а второе построение графа оператора ограничения оператора A на пространство A.

При этом пространство A0 является ядром некоторой (достаточно большой) степени оператора A, а A образом.

В параграфе 1.2 доказано, что все деревья в графе GA изоморфны и приведен следующий индуктивный алгоритм построения дерева, притягивающегося нулевой вершиной 0. Этот алгоритм использует размеры k1 k2... km всех жордановых клеток оператора A с нулевым собственным значением (или размеры всех жордановых клеток оператора A).

m Обозначим li = min(i, kj). Тогда доказанный алгоритм построj=km ения вспомогательного дерева T 0 выглядит следующим образом, мы i будем последовательно строить деревья T 0 для всех i от 1 до km.

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

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

i-i i Для построения дерева T 0 необходимо в дереве T 0 выделить pl -li-вершин на первом уровне, при этом следует взять те вершины, из которых уже “растут” деревья до (i - 1)-го уровня, и заменить эти деревья i-2 i-вида T* на деревья T*, которые изоморфны уже построенному дереву i-T 0. При этом не имеет значения какие конкретно выбирать вершины i-на первом уровне T 0, важно только, чтобы все они имели прообразы на i - 1 уровне, в остальном все такие вершины эквивалентны.

Для получения итогового дерева притягиваемого нулевой вершиной km в графе GA нужно в построенном дереве T 0 удалить произвольную вершину на первом уровне, у которой есть прообразы на верхнем уровне.

При этом удаляются и все вершины, которые притягиваются удаленной.

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

Параграф 1.3 посвящен формулировке и доказательству алгоритма построения всех циклов графа GA. Этот алгоритм использует строение жордановой нормальной формы оператора A над полем F, которое является алгебраическим расширением Zp, содержащим все kA = deg P(z) корней характеристического многочлена P(z) оператора.

Пусть tA количество различных неприводимых над Zp делителей многочлена P(z) i Положим Si = {1,..., r } F множество сопряженных (в F) корi i ней многочлена P(z), являющиеся корнями его i-го неприводимого делителя pi(z). Здесь ri это степень неприводимого многочлена pi(z).

Всем корням из Si соответствует одинаковое количество и размеры жордановых клеток в жордановой нормальной форме оператора над полем F; пусть количество таких жордановых клеток равно i, а их разi меры равны s1 s2... s. Кроме того, положим A = max i.

i i i Также доказанный алгоритм использует следующее Определение 1.3.17. Порядком многочлена Q Zp[z], не делящегося на z, назовем минимальное натуральное q такое, что zq - 1 делится на Q. Обозначим ord Q = q.

Для каждого неприводимого делителя многочлена P(z) вида pi(z), 1 i tA обозначим через qi его порядок.

В дальнейшем доказывается, что длина цикла, которому принадлеx жит вектор x, определяется ассоциированным с ним многочленом P = itA 1 pi pi... pt и набором (i1, i2,..., it ), где ij s1 для любого j tA.

1 2 A j A Следовательно, достаточно найти соответствующую длину и количество векторов, ассоциированных с некоторым фиксированным набором.

Это можно сделать благодаря следующим двум утверждениям.

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

Утверждение 1.3.27. Количество векторов, которые соответствуitA x 1 ют многочлену P = pi pi... pt, равно произведению 1 A A A rk min(sj,ik) rk(min(sj,ik)-1) k k p j=1,sj j=1,sj k=0 k=- p.

1ktA:ik= Вторая глава данной диссертации посвящена детальному исследованию графа разностного оператора. В параграфе 2.1 формулируются результаты первой главы по отношению к графу разностного оператора D(n), который действует на последовательность x = (x1,..., xn) по правилу D(n)x = (x2 - x1, x3 - x2,..., x1 - xn). Результаты второй главы используют представление n в виде n = pM, где M не делится на p.

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

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

Следствие 2.1.9. Длина максимального цикла в графе GD(n) это по(z+1)n-рядок характеристического многочлена PD(n)(z) =.

zp Следствие 2.1.12. PD(n) = (p1p2... pt )p, где p1, p2,..., pt раз D(n) личные неприводимые многочлены. При этом PD(M) = p1p2... pt и D(n) tD(n) = tD(M).

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

Гипотеза 1. Пусть q простое число. Рассмотрим двоичную последовательность l = (l1, l2,..., ln) длины n = q - 1, которая определена следующим образом:

0, если i квадратичный вычет по модулю q li = 1, если i квадратичный невычет по модулю q Тогда последовательность l, или логарифмическая последовательность, является сложной или почти самой сложной, то есть притягивающий ее цикл в графе разностного оператора имеет максимальную длину и l расположена среди вершин, находящихся на одном из двух верхних уровней дерева.

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

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

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

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

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

Утверждение 2.2.6. Пусть q = 73, тогда последовательность l = (l1,..., l72) находится на цикле.

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

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

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

В параграфе 2.3 эта гипотеза доказана в более общем случае для произвольного p. Основной результат, подтверждающий гипотезу Арнольда о длине максимального цикла, содержит Теорема 2.3.5. Если n не равняется p и 2p, то длина максимального цикла L(n) делится на n.

Исключительные случаи это n = p или n = 2p, то есть если n = pM, то M = 1 или M = 2 (только в случае p > 2). В первом случае существует единственный цикл в графе Gn и его длина равна 1.

В случае M = 2 длина максимального цикла равна pq, где q это порядок линейного многочлена PD(2)(z) = z + 2, то есть порядок остатка -2 в мультипликативной группе Z. Число q является нечетным (случай p когда длина максимального цикла не делится на n) в том и только том случае, когда двойка имеет порядок по модулю p равный 4k + 2. Примером простых чисел, удовлетворяющим этим условиям, могут служить p = 3, 11, 19.

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

Гипотеза 3. Пусть C(n) общее количество циклов, а Cmax(n) количество циклов максимальной длины в графе GD(n). Тогда отношение Cmax(n), или доля циклов максимальной длины, стремится к единице C(n) когда n стремится к бесконечности.

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

Основным результатом этого параграфа, является доказательство частного случая гипотезы 4. Этот факт содержит Теорема 2.4.6. Если n пробегает только степени простых чисел и стремится к бесконечности, то при этом vmax(n) стремится к единице.

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

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

Определение 3.1.1. Множество A E2 называется множеством Делоне если найдутся две такие положительные константы rA и RA, что круги радиуса rA с центрами в точках множества A не пересекаются по внутренним точкам, а круги радиуса RA покрывают всю плоскость E2.

Также такое множество называется (rA, RA)-системой.

Определение 3.1.2. Пусть A и B два подмножества евклидовой плоскости E2. Отображение f : A - B называется билипшицевым если найдется число L 1 такое, что для любых двух точек x, y A выполнено двойное неравенство · d(x, y) d(f(x), f(y)) L · d(x, y), L где d(·, ·) обозначает евклидово расстояние на плоскости E2.

Определение 3.1.3. Подмножества A и B евклидовой плоскости называются билипшицево эквивалентными если существует билипшицева биекция f : A - B. Будем писать для эквивалентных множеств A B.

Lip Также в этом параграфе доказана основная Лемма 3.1.4. Пусть A и B два таких множества Делоне, что существуют такая биекция f : A - B и такая константа > 0, что для любой точки x A выполнено неравенство d(x, f(x)). Тогда A B.

Lip В параграфе 3.2 доказан ряд достаточных условий на множество C, для того чтобы множества Делоне A и A C (или A \ C) были билипшецево эквивалентны. В частности, доказано, что изменение множества Делоне в конечном числе точек не меняет его класса эквивалентности.

Основным результатом этого параграфа является следующая Теорема 3.2.3. Пусть A некоторое множество Делоне. Если множество C удовлетворяет следующим условиям:

1. A C = ;

2. B = A C является множеством Делоне;

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

то B A.

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

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

Теорема 3.3.3. Пусть A и B два множество Делоне, тогда существует множество Делоне C B такое, что A C.

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

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

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

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

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

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

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

Теорема 3.6.4. Пусть X и Y два множества Делоне на плоскости E2. Предположим, что существует такая константа D > 0, что для любого натурального N и любого квадрата N N симметрическая разность X Y содержит не более DN точек в этом квадрате. Тогда множества X и Y билипшицево эквивалентны.

Для доказательства теоремы 3.6.4 устанавливается, что существует биекция между множествами X и Y, удовлетворяющая условиям леммы 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. А.И. Гарбер, Сложные последовательности по В.И. Арнольду, // Материалы IX Международного семинара “Дискретная математика и ее приложения”, посвященного 75-летию со дня рождения академика О. Б. Лупанова, 2007, стр. 374-376.

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»