Комбинаторные свойства числовых множеств большой плотности и их приложения

• Автор: Шкредов, Илья Дмитриевич
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 217 с.

Содержание
Введение
0.1 Введение
0.2 Общая характеристика работы
0.3 Основные положения диссертации, выносимые на защиту
0.4 Список использованных обозначений
Глава 1. Исторический обзор
1.1 Задачи об арифметических прогрессиях
1.2 Обобщения теоремы Семереди
1.3 Двумерные обобщения теоремы Семереди
Глава 2. Двумерные обобщения теоремы Семереди
2.1 Формулировка результатов и структура доказательства
2.2 Различные определения а—равномерности
2.3 Теоретико-графовый подход
2.4 Доказательство основного результата
Глава 3. Множества Бора и задача Гауэрса
3.1 Множества Бора и задача Гауэрса
3.2 Свойства множеств Бора
3.3 ск—равномерность и множества Бора
3.4 Свойства не а—равномерных множеств
3.5 Плотные подмножества множеств Бора
3.6 Доказательство основной теоремы

Глава 4. Одномерная и многомерная возвращаемость

4.1 Постановка задач
4.2 Оценки сверху для скорости многомерной возвращаемости
4.3 Нижние оценки для кратной возвращаемости
4.4 Динамические системы с заданной скоростью возвращения
Глава 5. Множества больших тригонометрических сумм
5.1 Постановка задач и формулировка результатов
5.2 Доказательство основной теоремы
5.3 Системы линейных уравнений с элементами из множества больших тригонометрических сумм
5.4 Приложение к задачам аддитивной комбинаторики
5.5 Матричное обощение теоремы
5.6 О точности полученных результатов
5.7 Примеры множеств больших тригонометрических сумм в линейных пространствах над полем простой характеристики
Список литературы

Введение.
0.1 Введение.
В настоящей диссертации рассматривается несколько хорошо известных задач комбинаторной теории чисел. Если стремится дать достаточно короткое определение самой комбинаторной теории чисел как отдельной математической дисциплины, то следует, по-видимому, сказать так : комбинаторная теория чисел — это раздел математики, который находится на стыке комбинаторики и теории чисел, то есть раздел, основные задачи которого связаны с отысканием комбинаторных характеристик различных числовых объектов (множеств целых чисел, подмножеств групп вычетов и т.д.)
Тематика настоящей диссертации связана с замечательным результатом комбинаторной теории чисел — теоремой Б.Л. Ван дер Вардена [1], доказанной им в 1927 году. Эта теорема утверждает, что при любой раскраске множества целых чисел в конечное число цветов найдется арифметическая прогрессия произвольной длины, все элементы которой раскрашены в один и тот же цвет. Теорему Ван дер Вардена А.Я. Хинчин [2] по праву назвал жемчужиной теории чисел. Несмотря на кажущуюся простоту и естественность теорема Ван дер Вардена сыграла значительную роль в развитии двух разделов математики — аддитивной комбинаторики и комбинаторной эрго-дической теории. Отметим, что обе указанных области математики связаны между собой теснейшим образом и находятся на стыке таких наук, как аддитивная и аналитическая теория чисел, теория графов и теория динамических систем. Сама по себе теорема Ван дер Вардена является одним из фундаментальных результатов теории Рамсея (см. [3, 4]).
В 1975 году Е. Семереди [9] получил замечательное обобщение теоремы Ван дер Вардена. Он доказал, что любое множество целых чисел положительной плотности содержит арифметические прогрессии любой длины. Эта сложная работа чрезвычайно сильно повлияла на развитие комбинаторной теории чисел, а также на смежные дисциплины. Так, основной инструмент в доказательстве Семереди, так называемая лемма регулярности, стала, на сегодняшний день, одним из важнейших методов теории графов. Кроме того, через несколько лет после Семереди, Г. Фюрстенберг [22] передоказал его теорему с помощью методов эргодической теории. Фюрстенберг обнаружил связь между комбинаторными объектами и динамическими системами (так называемый принцип соответствия Фюрстенберга) и основал новую науку — комбинаторную эргодическую теорию, которая занимается различными

И 1/1 Е2 ЕтеЕ26т = 1/Щ Чк = Х |- ФунКЦИЮ /(в)
(х(8) ~ $т){Е 1 х £?2)(з) назовем балансовой функцией множества Л.
Будем говорить, что множество АС Е х Е2 является а-равномерным, относительно базиса (в!, ез), если его балансовая функция а-равномерна, относительно этого базиса. Если множества Ех и Е<х не указаны, то мы будем подразумевать, что Ех = Ъы, Дг = Zv. Заметим, что множество А может быть а-равномерным, относительно базиса (еег), но не а-равномерным относительно базиса (е2,в1).
Во введении был приведен пример а-равномерного множества в которое не является а-равномерным, относительно базиса (еез). Можно показать, что любое а-равномерное, относительно базиса (еег) множество Л С К является обычным а-равномерным двумерным множеством. Мы не доказываем здесь этого утверждения, поскольку оно нам не понадобится. Прежде всего поясним комбинаторный смысл понятия а-равномерности. Назовем черверку вида (я, Б+иег, Б + геь в+ггег+ге!) простейшим прямоугольником. Множество Л С содержит простейший прямоугольник, если оно содержит все 4 точки прямоугольника.
Лемма 2.3. Пусть мноо/сество А лежит в и имеет мощность 6И2. Тогда А содержит не менее, чем А4#4 простейших прямоугольников.
Доказательство. Пусть у(в) характеристическая функция множества Л, б = ке + тв2- Количество простейших прямоугольников в Л равно
ЕЕ х(б)х(б + шэ2) х(в -г гО| )х(б -!- ие.2 -г геД = Е1Е Х(к,т)х{к,р)|2.
в, и г т,р к
Применяя неравенство Коши-Буняковского, получаем
1хк’тк>р2 - (ЕЕ*’™)*))2
т,р к т,р к
= дд (ЕIЕ т) I2)2 (Е х(к>т))4 = №.
к т к,т
Лемма доказана. □
Введем несколько обозначений. Пусть С обозначает оператор комплексного сопряжения. Для каждого целого неотрицательного п пусть Сп означает взятие комплексного сопряжения п раз. Если х и у два вектора из С*, то мы будем обозначать их скалярное произведение как х у или как (х, у). Для £ 6 {0,1}к пусть ]е| означает Е=1е*'