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

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

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

Введение

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 Системы линейных уравнений с элементами из множества больших тригонометрических сумм.

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

0.1 Введение.

В настоящей диссертации рассматривается несколько хорошо известных задач комбинаторной теории чисел. Если стремится дать достаточно короткое определение самой комбинаторной теории чисел как отдельной математической дисциплины, то следует, по-видимому, сказать так : комбинаторная теория чисел — это раздел математики, который находится на стыке комбинаторики и теории чисел, то есть раздел, основные задачи которого связаны с отысканием комбинаторных характеристик различных числовых объектов (множеств целых чисел, подмножеств групп вычетов и т.д.)

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

В 1975 году Е. Семереди [9] получил замечательное обобщение теоремы Ван дер Вардена. Он доказал, что любое множество целых чисел положительной плотности содержит арифметические прогрессии любой длины. Эта сложная работа чрезвычайно сильно повлияла на развитие комбинаторной теории чисел, а также на смежные дисциплины. Так, основной инструмент в доказательстве Семереди, так называемая лемма регулярности, стала, на сегодняшний день, одним из важнейших методов теории графов. Кроме того, через несколько лет после Семереди, Г. Фюрстенберг [22] передоказал его теорему с помощью методов эргодической теории. Фюрстенберг обнаружил связь между комбинаторными объектами и динамическими системами (так называемый принцип соответствия Фюрстенберга) и основал новую науку — комбинаторную эргодическую теорию, которая занимается различными связями между комбинаторными свойствами множеств и соответствующими характеристиками динамических систем.

Основная задача настоящей диссертации состоит в получении количественных оценок для двумерной теоремы Семереди. Говоря кратко, она состоит в следующем: насколько большую мощность может иметь подмножество двумерной решетки без конфигураций вида (х, у), (х + d, у), (х, у + d), где d > 0? Такие тройки называются уголками или равнобедренными прямоугольными треугольниками. Первый результат в этом направлении был доказан М. Атаи и Е. Семереди (см. [40]) в 1974 году с помощью комбинаторных методов. Они показали, что любое подмножество двумерной решетки положительной плотности обязательно содержит уголок. В 1978 году результат о равнобедренных прямоугольных треугольниках был передоказан Фюрстенбергом и Кацнельсоном (см. [24]) с помощью методов эргодической теории. Доказательство Атаи и Семереди дает очень слабые верхние оценки на плотность множества двумерной решетки без уголков. Доказательство Фюрстенберга и Кацнельсона является неэффективными в том смысле, что оно вообще не дает никаких верхних оценок на указанную плотность. В.Т. Гауэрс (см. [35]) в своей филдсовской работе поставил вопрос о получении количественных оценок в этой задаче.

Популярность, описанных выше задач, не вызывает сомнений: в разные годы ими занимались замечательные специалисты в области комбинаторной теории чисел и комбинаторной эргодической теории, такие как филдсовские лауреаты К.Ф. Рот, Ж. Бурген, Т.Тауэре, а также П. Эрдеш, Е. Семереди, С. Шелах, Р. Радо, В. Редл, П. Франкл, JI. Ловас, И. Ружа, C.B. Конягин, P.J1. Грэхем, П. Туран, Г. Фюрстенберг, В. Бергельсон, А. Лейбман, Б. Ост, Б. Кра, Г.А. Фрейман, Д.Р. Хиф-Браун, В. Шош, А. Балог, А. Шаркоци, Г. Элекеш, М. Атаи, Н. Кац, Б. Грин, Т. Тао, М.-Ч. Чанг, В. Ву и другие.

Диссертация делится на пять глав. В первой главе даются постановки основных проблем и излагается их история. Вторая глава посвящена получению количественных оценок в задаче о двумерном обобщении теоремы Семереди. В этой главе доказано несколько результатов о, так называемых, ^-равномерных множествах. Например, получен теоретико-графовый критерий «-равномерности множества в терминах второго собственного значения соответствующей матрицы смежности. Кроме того, в этой главе доказан новый общий результат о строении плотных подмножеств множества {1,2,. ,N}2, который вместе с полученными ранее теоремами об а-равномерных множествах, применяется при доказательстве нашего основного результата о двумерных уголках. В третьей главе к задаче об уголках применяется метод Ж. Бургена, связанный с множествами Бора. Такой подход позволяет усилить верхние оценки на плотность подмножеств

1,2,., А^}2 без равнобедренных прямоугольных треугольников, а также доказать аналогичные утверждения в произвольной конечной абелевой группе. В четвертой главе получены примеры динамических систем с медленной скоростью кратного и однократного возвращения. Доказанные результаты еще раз указывают на тесную связь между задачами комбинаторной теории чисел и эргодической теорией. В пятой главе доказано несколько теорем о множествах больших тригонометрических сумм. Такие множества появляются во всех задачах комбинаторной теории чисел, при решении которых используется метод Фурье (например, они встречаются в задачах об арифметических прогрессиях и в задачах об уголках). Поэтому, как отмечает Гауэрс в своем обзоре [90], результаты о структуре множеств больших тригонометрических сумм чрезвычайно важны. Мы доказываем, что рассматриваемые множества имеют сильные аддитивные свойства. Кроме того, в пятой главе соискателем получено несколько приложений к задачам комбинаторной теории чисел, а также установлена точность доказанных теорем.

Благодарности. Соискатель считает своим приятным долгом в первую очередь поблагодарить доктора физико-математических наук, профессора Н. Г. Мощевитина за постоянный интерес и внимание к работе. Кроме того, соискатель благодарит доктора физико-математических наук, профессора С. В. Конягина, чл.—корреспондента РАН, доктора физико-математических наук, профессора Ю.В. Нестеренко, академика РАН, доктора физико-математических наук, профессора Д.В. Аносова за неоднократную помощь и поддержку, а также доктора физико-математических наук, профессора В. В. Рыжикова за ряд ценных замечаний.

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

Актуальность темы диссертации.

В работе подробно исследуются три глубоко связанные между собой проблемы комбинаторной теории чисел и комбинаторной эргодической теории. Первая из них состоит в получении количественных оценок для двумерной теоремы Семереди. Коротко говоря, она состоит в следующем: насколько большую мощность может иметь подмножество двумерной решетки без конфигураций вида (х,у), (х + б?, у), (ж, у + <1), где в, > 0? Как мы отмечали выше, первый результат в этом направлении был доказан М. Атаи и Е. Семереди (см. [40]). Они показали, что любое подмножество двумерной решетки положительной плотности обязательно содержит уголок. В 1978 году этот результат был передоказан Фюрстенбергом и Кацнельсоном (см. [24]) с помощью методов эргодической теории. Недавно [35] В.Т. Гауэрс в своей филдсовской работе поставил вопрос о получении количественных оценок в этой задаче. Ответ на данный вопрос дается в второй и третьей главах диссертации.

Выше было рассказано о глубокой связи между комбинаторными проблемами, касающихся арифметических прогрессий и динамическими системами. Наиболее четко эта связь прослеживается в созданной Фюрстенбергом науке — комбинаторной эргодической теории. Исходя из основного принципа этого раздела математики (принципа соответствия Фюрстенберга) любому множеству целых чисел положительной плотности можно сопоставить динамическую систему с тем же множеством кратного возвращения. К сожалению, количественный аспект подобного рода вопросов на данный момент изучен слабо. Отметим, что совсем недавно появилось много работ таких математиков, как М.Д. Бошерницан, Н.Г. Мощевитин, Я. Песин, В. Афра-мович, Б. Сауссол, JI. Барейра, С. Трубецкой (см. [79, 80, 81, 82, 83, 84, 85]) в которых достаточно полно изучен вопрос о количественных характеристиках однократного возвращения. В настоящей диссертации мы впервые получаем количественные результаты, касающиеся кратного возвращения.

Третья проблема, изучаемая нами в работе, связана со строением, так называемых, множеств больших тригонометрических сумм. Такие множества появляются во всех задачах комбинаторной теории чисел, при решении которых используется метод Фурье, в том числе и в проблеме об уголках. Структура этих множеств изучалась такими математиками, как Я. Кац-нельсон, Ж.П. Кахан, Ф.Л. Назаров, К. Болл (см. [103, 104, 105]), а также Г.А. Фрейманом, А.А. Юдиным, А. Бессером, В. Львом, C.B. Конягиным (см. [99, 100, 101, 102]). Недавно интерес к рассматриваемой проблематике существенно повысился (см. работы М.-Ч. Чанг [58], Б. Грина [91, 92] и диссертанта [132, 133, 134]). Это связано, по-видимому, с появлением в последнее время новых мощных методов решения задач комбинаторной теории чисел, интенсивно использующих аппарат анализа Фурье. Мы имеем здесь в виду, прежде всего, новое доказательство Гауэрса теоремы Семереди с помощью методов анализа Фурье, в котором используются специальные множества больших тригонометрических сумм, а также недавнее доказательство М.-Ч. Чанг (см. [58] и более раннюю работу И. Ружи [57]) количественного варианта знаменитой теоремы Г.А. Фреймана [55] о множествах с маленькой суммой. Напомним, что в своем доказательстве Чанг получила и использовала новый результат о свойствах множеств больших тригонометрических сумм.

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

Наконец, важно подчеркнуть, что в разное время близкими задачами занимались Ж. Бурген, Т. Гауэрс, Е, Семереди, И. Ружа, Р. Грэхем, Г. Фюр-стенберг, В. Бергельсон, А. Лейбман, Б. Ост, Б. Кра, М. Атаи, Ж. Шоли-моши, Б. Грин, В. Ву и многие другие известные математики. Ежегодно в мире проводятся конференции и семинары по этим задачам, им посвящены специализированные журналы. Публикуются обзоры и монографии.

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

Цели и задачи исследования.

Основной целью исследования является получение результатов относительно многомерных обобщений теоремы Семереди, множеств больших тригонометрических сумм, скорости возвращения в динамических системах с сохраняющейся мерой, а также других задачах комбинаторной теории чисел и комбинаторной эргодической теории. Кроме того мы преследуем цель единого описания этих задач в терминах общих методов их решения и отыскания новых взаимосвязей между проблемами. Основными задачами являются следующие: разработка новых методов, включающих в себя теоретико-графовый подход и метод тригонометрических сумм и его применение к получению верхних оценок для плотности множества двумерной решетки, не содержащей уголков; постороение примеров динамических систем с медленной скоростью кратного возвращения, а также с заданной скоростью однократного возвращения; построение метода, позволяющего обосновать существование нетривиальных решений линейных уравнений с элементами из множества больших тригонометрических сумм и применение этого метода для получения приложений к задачам комбинаторной теории чисел.

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

Методы исследования. В работе используется метод тригонометрических сумм и анализ Фурье, комбинаторные методы, методы теории графов, методы теории динамических систем, а также методы аддитивной комбинаторной теории чисел.

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

0.3 Основные положения диссертации, выносимые на защиту.

1. Любое множество А С {1,2,., N}2 мощности N2/(log log log N)c, где с > 0 — некоторая эффективная константа, содержит уголок (теорема 2.1 из параграфа 2.1).

2. Доказана структурная теорема о плотных подмножествах {1,2,., N}2 (теорема 2.6 из параграфа 2.3).

3. Получен критерий »-равномерности множества А в терминах матрицы смежности графа Ga, ассоциированного с А, а также в терминах плотности А в декартовых произведениях больших подграфов графа Ga (лемма 2.8 и предложения 2, 3 из параграфа 2.3).

4. Любое множество А С {1,2,., А^}2 мощности TV2/(log log где С > 0 — некоторая эффективная константа, содержит уголок (теорема 3.2 из параграфа 3.1).

5. Всякое подмножество декартова квадрата G х G произвольной конечной абелевой группы G мощности. \G\2/(log log |G|)Cl, где C\ > 0 — некоторая эффективная константа, содержит уголок теорема 3.3 из параграфа 3.1).

6. Получены примеры динамических систем с медленной скоростью кратного возвращения (теорема 4.12 из параграфа 4.3).

7. Доказаны теоремы об оценке сверху для скорости многомерной воз-вращаемости (теоремы 4.10 и 4.11 из параграфа 4.2).

8. Построены примеры динамических систем с заданной скоростью однократного возвращения (теорема 4.13 из параграфа 4.4).

9. Найдена наилучшая оценка снизу для числа решений уравнения гг + • • • -f г к = г[ + • • • + г'к, где все г^ г\ принадлежат множеству больших тригонометрических сумм, а также для системы линейных уравнений с переменными из множества больших тригонометрических сумм (теоремы 5.5, 5.6 и 5.11, 5.12 из параграфов 5.2, 5.3 и 5.6, соответственно).

10. Получен результат, существенно улучшающий теорему Чанг о строении множества больших тригонометрических сумм (теоремы 5.8 и 5.9 из параграфов 5.4 и 5.5, соответственно).

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

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

Перечислим сперва конференции:

• международная конференция "Современная теория динамических систем и ее приложения к небесной механике" (г. Москва, 2002 г.);

• пятая международная конференция "Алгебра и теория чисел: современные проблемы и приложения" (г. Тула, 2003 г.);

• международная конференция "XXIII Арифметические дни" в Граце (Австрия, 2003 г.);

• международная конференция "Диофантовый анализ, равномерное распределение и их приложения" в Минске (Беларусь, 2003 г.);

• международная конференция "Новейшие достижения в аддитивной комбинаторике" в Пало Альто (США, 2004 г.);

• международная конференция "Аналитические методы в теории чисел, теории вероятностей и математической статистике" (Санкт-Петербург, 2005 г.);

• международная конференция "Геометрические методы в физике" в Бе-ловеже (Польша, 2005 г.);

• международная конференция "Аддитивная комбинаторика" в Бристоле (Англия, 2005 г.);

• международная конференция "Вероятность и эргодическая теория" (США, 2006, 2007 гг.);

• международная школа и конференция "Аддитивная комбинаторика" в Монреале (Канада, 2006 г.);

• "Аналитические и комбинаторные методы в теории чисел и геометрии" (г. Москва, 2006 г.);

• "Равномерное распределение" в Марселе (Франция, 2008 г.);

• "Наводя мосты" в Будапеште (Венгрия, 2008 г.);

• "Феномен дискретной жесткости в аддитивной комбинаторике" в Беркли (США, 2008 г.);

• Ломоносовские чтения в Московском государственном университете в 2002, 2004, 2006-2008 гг.

Перечислим теперь семинары :

• кафедральный семинар кафедры теории чисел под руководством чл-корр. РАН Ю. В. Нестеренко и д.ф.-м.н. Н. Г. Мощевитина;

• кафедральный семинар кафедры динамических систем под руководством акад. РАН Д. В. Аносова, д.ф.-м.н. В. М. Закалюкина и к.ф.-м.н. А. А. Приходько;

• семинар "Аналитическая теория чисел" под руководством д.ф.-м.н. А. А. Карацубы;

• семинар "Арифметика и геометрия" под руководством д.ф.-м.н. Н. Г. Мощевитина и д.ф.-м.н. А. М. Райгородского;

• семинар "Гамильтоновы системы и статистическая механика" под руководством акад. РАН В. В. Козлова и чл.-корр. РАН Д. В. Трещева;

• семинар "Динамические системы и эргодическая теория" под руководством акад. РАН Д.В.Аносова, д.ф.-м.н. А. М.Степина, д.ф.-м.н. Р. И. Григорчука;

• семинар "Тригонометрические суммы и их приложения" под руководством д.ф.-м.н. Н. Г. Мощевитина и к.ф.-м.н. А. В. Устинова;

• семинар "Теория функций и ее приложения" под руководством д.ф.-м.н. С. В. Конягина, к.ф.-м.н. В. Б. Демидовича и к.ф.-м.н.

A. С. Кочурова;

• семинар "Динамические системы" под руководством профессора

B. Вича;

• семинар "Эргодическая теория" под руководством акад. РАН Я. Г. Синая;

• семинар "Эргодическая теория и аддитивная комбинаторика" под руководством профессора М. Виэрдла, профессора Э. Лезинь, профессора Б.Кра,

• "Научно-исследовательский семинар по теории функций" под руководством чл.-корр. РАН Б. С. Кашина , д.ф.-м.н. С. В. Конягина, д.ф.-м.н. Б.И. Голубова и д.ф.-м.н. М.И. Дьяченко ,

• семинар "Теория функций" под руководством чл.-корр. РАН Б. С. Кашина и д.ф.-м.н. С. В. Конягина .

Опубликованность результатов диссертации. Результаты диссертации опубликованы в работах [123] — [135] списка использованных источников. Всего по теме диссертации опубликовано 12 работ.

Структура и объем работы. Диссертация изложена на 217 страницах и состоит из введения, общей характеристики работы, списка использованных обозначений и сокращений, пяти глав и списка использованных источников, включающего 135 наименований.

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

1. Van der Waerden В. L. Beweis einer Baudetschen Vermutung // Nieuw Arch. Wisk., 15, 1927, 212-216.

2. ХинчинА. Я. Три жемчужины теории чисел / M.: Едиториал УРСС, 2004.

3. Грэхем Р. Начала теории Рамсея / М.: Мир, 1984.

4. Graham R. L., Rothschild В. L., Spencer J. Ramsey Theory / Wiley Interscience, Series in Discrete Mathematics, 1980.

5. ShelahS. Primitive Recursive Bounds for van der Waerden Numbers //J. Amer. Math. Soc., v. 1, 1988, 683-697.

6. ErdôsP., TurdnP. On some sequences of integers //J. Lond. Math. Soc., 11, 1936, 261-264.

7. Heath-Brown D. R. Integer sets containing no arithmetic progressions //J. London Math. Soc. (2), v. 35, N, 3, 1987, 385-394.

8. Szemerédi E. On sets of integers containing no four elements in arithmetic progression // Acta Arith. Acad. Sci. Hungar., v. 20, 1969, 89-104.

9. Szemerédi E. On sets of integers containing no k elements in arithmetic progression // Acta Arith., 27, 1975, 299-345.

10. Szemerédi E. On sets of integers containing no arithmetic progressions // Acta Math. Hungar., v. 56, 1990, 155-158.

11. Szemerédi E. Regular partitionsof graphs // Colloques Internationaux CNRS, 260 — Problems Combinatories et Théorie des Graphes, Orsay, 1976, 399-401.

12. Kohayakawa Y. Szemerédi's regularity lemma for sparse graphs // Foundations of Computational Mathematics, Selected papers, IMPA conference, January 1997, Rio de Janeiro, Springer, 1997.

13. KolmosJ., Simonovits M. Paul Erdôs is 80 (под редакцией D. Miklos, V.T. Sôs, T. Szônyi) / v. 2, Proc. Colloq. Math. Soc. Jânos Bolyai, 1996.

14. RothK. P. On certain sets of integers (I) // J. London Math. Soc., 28, 1953, 245-252.

15. Roth К. F. On certain sets of integers (II) // J. London Math. Soc., 29, 1953,20-26.

16. BourgainJ. On triples in arithmetic progression// GAFA, 9,1999, 968-984.

17. Bourgain J. A Szemerédi type theorem for sets of positive density in // Israel Journal of Mathematics, v. 54, N. 3, 1986, 307-316.

18. Szemerédi E., Ruzsal. Triple systems with no six points carrying three triangles // Combinatorics (Keszthly, 1976), v. II, N. 11, 1978, 939-945. North-Holland, Amsterdam-New York.

19. Graham R. L., RôdlV. Numbers in Ramsey theory // Surveys in Combinatorics, London Math. Soc. Lecture Note, Series, 123, 1987, 111-155.

20. Graham R. L., GrôtschelM., Lovas L. Handbook of Combinatorics / MIT Press, Cambridge, Massachusetts, 1995.

21. Успенский В. А. Лекции о вычислимых функциях / M., 1960.

22. Furstenberg H. Ergodic behavior ,of diagonal measures and a theorem of Szemerédi on arithmetic progressions // J. d'Analyse Math., v. 31, 204256, 1977.

23. Furstenberg H. Recurrence in ergodic theory and combinatorial number theory / Princeton (N.J.), 1981.

24. Furstenberg H.; Katznelson Y., An ergodic Szemerédi theorem for commuting transformations // J. d'Analyse Math., v. 34, 275-291, 1978.

25. Furstenberg H., Katznelson Y. and OrnsteinD. The Ergodic Theoretical Proof of Szemerédi's Theorem // Bull. Amer. Math. Soc., v. 7, N.3, 527-552, 1982.

26. Tao T. A quantitative ergodic theory proof of Szemerédi's theorem // http:// www.arXiv : inath.CO/0405251, 2004.

27. Bergelson V., LeibmanA. Polynomial extentions of van der Waerden's and Szemerédi's theorems // J. Amer. Math. Soc., v.9, N.3, 1996, 725-753.

28. Bergelson V., LeibmanA. Set-polynomials and polynomial extension of the Hales-Jewett theorem // Ann. of Math. (2), v.150, N.l, 1999, 33-75.

29. Furstenberg H., Katznelson Y. A density version of the Hales-Jewett theorem // J. Analyse Math., 57, 1991, 64-119.

30. Hales А. Ж. JewettA. I. Regularity and positional games // Trans. Amer. Math. Soc., 106, 1963, 222-229.

31. LeibmanA. Multiple recurrence theorem for measure preserving actions of a nilpotent group // Georn. fune. anal., v.8, 1998, 853-931.

32. McCutcheonR. Elemental methods in ergodic Ramsey theory / Springer, Lect. Notes Math., v. 1722, 1999.

33. Host В., KraB. Nonconventional ergodic averages and nilmanifolds // Ann. Math., представлено в печать.

34. Gowers W. Т. A new proof of Szemeredi's theorem for arithmetic progressions of length four // Geom. func. anal., v.8, 1998, 529-551.

35. Gowers W. T. A new proof of Szemeredi's theorem // Geom. func. anal., v.ll, 2001, 465-588.

36. Gowers W. T. Lower bounds of tower type for Szemeredi's uniformity lemma // Geom. func. anal., v.7, N.2, 1997, 1-16.

37. NagleB., RodlV., SchachtM. The counting lemma for regular k-uniform hypergraphs // Random Structures and Algorithms, представлено в печать.

38. Gowers W. Т. Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs // Combin. Probab. Comput. 15:1-2 (2006) 143-184.

39. Gowers W. T. Hypergraph Regularity and the multidimensional Szemeredi's Theorem // представлено в печать.

40. AjtaiM., SzemerediE. Sets of lattice points that form no squares // Stud. Sci. Math. Hungar., 9, 1974, 9-11.

41. BehrendP. A. On sets of integers which contain no three terms in arithmetic progression // Proc. Nat. Acad. Sci., 23, 1946, 331-332.

42. Salem R., SpencerD. C. On sets of integers which contain no three terms in arithmetical progression // Proc. Nat. Acad. Sci. Wash., 28, 1942, 561 -563.

43. Salem R., SpencerD. C. On sets which do not contain a given number of terms in arithmetical progression // Nieuw Arch. Wisk., 23,1950, 561 563.

44. Rankin R. A. Sets of Integers Containing not more than a Given Number of Terms in Arithmetic Progression // Proc. Roy. Soc. Edinburgh, 65, N.4, Sec. A, 1961, 332-344.

45. Moser L. On non-averaging sets of integers 7 Canad. Math. J., 5, 1953, 245-252.

46. LabaL, LaceyM. On Sets of Integers Not Containing Long Arithmetic Progressions // http:// www.arXiv:math.CO/0108155, 2001.

47. Ланкастер П., Теория матриц / Москва "Наука", 1982.

48. CrootE. A Structure Theorem for Positive Density Sets Having the Minimal Number of 3-Term Arithmetic Progressions // представлено в печать.

49. CrootE. Long Arithmetic Progressions in Critical Sets // http:// www.arXiv:math.NT/0403082, 2004.

50. ChudakovN. G. On the density of the set of even numbers which are not representable as a sum of two odd primes // Izv. Akad. Nauk SSSR Ser. Mat., 2, 1938, 25-40.

51. Van der CorputJ. G. Über Summen von Primzahlen und Primzahlquadraten // Math. Ann., 116, 1939, 1-50.

52. ChowlaS. There exists an infinity of 3-combinations of primes in A.P. // Proc. Lahore Philos. Soc., 6, N. 2, 1944, 15-16.

53. Green В., TaoT. The primes contain arbitrarily long arithmetic progressions // Annals of Math., представлено в печать, http:// www.arXiv:math.NT/0404188, 2004.

54. GreenB., Roth's theorem in the primes // Annals of Math., v. 161, N.3, 1609-1636, 2005.

55. ФрейманГ. А. Основания структурной теории сложения множеств / Казанский гос. пед. инст., Казань, 1966.

56. BiluY. Structure of sets with small sumset // Structure Theory of Sets Addition, Astérisque, Soc. Math. France, Montrouge, 258 (1999) 77-108.

57. Ruzsal. Generalized arithmetic progressions and sumsets // Acta Math. Hungar., 65 (1994), 379-388.

58. ChangМ,- С. A polynomial bound in Freiman's theorem // Duke Math. J. 113 (2002) no. 3, 399-419.

59. Solymosi J. Note on a generalization of Roth's theorem // Discrete and computational geometry, 825-827, Algorithms Combin., 25, Springer, Berlin, 2003.

60. Stiredzy 'G. N., Selkow S. On a question: of Gowers concerning isosceles right-angle triangles // представлено в печать, 2003.

61. Vu V. H. On a question of Gowers // Ann. of Combinatorics, 6, 2002, 229233.

62. Chung F. R. K., Graham R. L., Wilson R. M. Quasi-random graphs // Com-binatorica 9 (4), 1989, 345-362.

63. ChungF. R. K., GrahamR. L., Quasi-random subsets of Zn // J. Combin. Theory, Ser. A, v. 64, N. 1, 1992, 64-86.

64. StircozyA. On Difference Sets of Sequences of Integers I // Acta Math. Acad. Sci. Hungar, 31, nos. 1-2, 1978, 125-149.

65. StircozyA. On Difference Sets of Sequences of Integers III // Acta Math. Acad. Sci. Hungar, 31, nos. 3-4, 1978, 355-386.

66. SrinivasanS. On a Result of Sarcozy and Furstenberg // Nieuw. Acta. Wisk. (4), v.3, N.3, 1985, 275-280.

67. PintzJ., SteigerW.L., SzemerediE. On Sets of Natural Numbers whose Difference Set Contains No Squares //J. London Math. Soc. (2), v.37, 1988, 219-231.

68. Green В. On arithmetic structures in dense sets of integers // Duke Math. Journal, v. 144, N. 2, 215-238, 2002.

69. Ruzsal. Difference Sets Without Squares // Period. Math. Hungar, v. 15, N. 3, 1984, 205-209.

70. Bourgain J. Exponential sums estimates over subgroups and almost subgroups of Z*, where q is composite with few prime factors // GAFA, представлено в печать.

71. Bourgain J., GlibichukA., KonyaginS. Estimate for the number of sums and products and for exponential sums in fields of prime order //J. London Math. Soc., представлено в печать.

72. Tao Т. Lecture notes 5 for Math 254A // UCLA, 2003, http://math.ucla.edu/ tao/2'54a.l.03w/notes5.dvi.

73. Green B. A Szemeredi-type regularity lemma abelian groups // Geom. Funct. Anal., 15, 2, 2005, 340-376.

74. Green В. Finite field models in additive number theory // Surveys in Combinatorics, LMS lecture notes, 329, 2005, 1-29.

75. Green В., Tao Т. An inverse theorem for the Gowers Ud(G) norm, with applications // http:// www.arXiv : math.NT/0503014 vl 1 Mar 2005.

76. Green В., Tao T. New bounds for Szemeredi's Theorem, I: Progressions of length 4 in finite field geometries // http:// www.arXiv : math.C0/0509560 vl 23 Sep 2005.

77. Samorodnitsky A., TrevisanL. Gowers Uniformity, Influence of Variables, and PCPs // http:// www.arXiv : math.CO/0510264 vl 12 Oct 2005.

78. Пуанкаре А. Новые методы небесной механики / Избранные труды. Т. 2. М.: Наука, 1972.

79. Boshernitzan М. Quantitative recurrence results // Inventiones mathemat-icae, 113, Fasc. 3, 1993, 617-631.

80. Мощевитин П. Г. Об одной теореме Пуанкаре // УМН, 53, вып. 1, 1998, 219-220.

81. AfraimovichV., Chazottes J. R., SaussolB. Pointwise dimensions for Poincare recurrence associated with maps and special flows // Disc. Cont. Dyn. Syst., A 9, 2003, p. 263-280.

82. BarreiraL., PesinY., SchmelingJ, Dimension and product structure of hyperbolic measures // Ann. of Math., 2, 149, 1999, p. 755-783.

83. BarreiraL., SaussolB. Hausdorff dimension of measures via Poincare recurrence // Commun. Math. Phys., 219, 2001, 443-463.

84. BarreiraL., SaussolB. Product structure of Poincare recurrence // Ergod. Th. and Dynam. Sys, 22, 2002, 33-61.

85. SaussolB., Troubetzkoy S., Vaienti S. Recurrence, dimensions and Lya-punov exponents // J. Stat. Phys., 106, 2002, p. 623-634.

86. БогачевВ. И. Основы теории меры / Москва-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2003.

87. Stewart С. L., Tijdeman R. Oil Infinite-Difference Sets // Can. J. Math. 31 (1979) no. 5, 897-910. >

88. CusickT. W., Flahive M. E. The Markoff and Lagrange Spectra / Mathematical surveys and monographs, Number 30, Published by AMS, Providence, Rhode Island.

89. Колмогоров A. H. О некоторых асимптотических характеристиках вполне ограниченных метрических пространств // ДАН 108 (1956) по. 3.

90. Gowers W. Т. Rough structure and classification // GAFA, Special Volume GAFA2000 "Visions in Mathematics", Tel Aviv, (1999) Part I, 79-117.

91. GreenB. Arithmetic Progressions in Sumsets // Geom. Funct. Anal., 12 (2002) no. 3, 584-597.

92. Green B. Some constructions in the inverse spectral theory of cyclic groups // Comb. Prob. Сотр. 12 (2003) no. 2, 127-138.

93. Green В. Spectral structure of sets of integers // Fourier analysis and convexity (survey article, Milan 2001), Appl. Numer. Harmon. Anal., Birkhauser Boston, Boston, MA (2004), 83-96.

94. Green B. Structure Theory of Set Addition // ICMS Instructional Conference in Combinatorial Aspects of Mathematical Analysis, Edinburgh March 25 April 5 2002. ^ n ^ .-.■.<;

95. Bourgain J. On Aritmetic Progressions in Sums of Sets of Integers //A Tribute of Paul Erdds, Cambridge University Press, Cambridge (1990), 105109.

96. FreimanG. A., HalberstamH., Ruzsal. Integer Sumsets Containing Long Arithmetic Progressions ■// J. London Math. Soc. 46 (1992) no. 2, 193-201.

97. CrootE., Ruzsal., TomaszS. Arithmetic progressions in sparse sumsets // представлено в печать.

98. Ruzsal. Arithmetic progressions in sumsets // Acta Arith. 60 (1991) no. 2, 191-202.

99. Юдин А. А. // Теория чисел (под ред. Т.А. Фреймана, A.M. Рубинова, Е.В. Новоселова), Калининский гос. унив., Москва (1973), 163-174.

100. BesserA. Sets of integers with large trigonometric sums // Astérisque 258 (1999), 35-76.

101. Lev V. F. Linear Equations oyer Fp and Moments of Exponential Sums // Duke Mathematical Journal 107 (2001), 239-263.

102. Назаров Ф. JI. Ударное решение задачи о коэффициентах // Алгебра и анализ 9 (1997) вып. 2, 272-287.

103. Ball К. Convex geometry and functional analysis // Handbook of the geometry of Banach spaces, vol. I, North-Holland, Amsterdam (2001), 161— 194.

104. Rudin W. Fourier analysis on groups / Wiley 1990 (репринт издания 1962 года).

105. Rudin W. Trigonometric series with gaps // J. Math. Mech. 9 (1960), 203-227.

106. Виноградов И. M. Метод тригонометрических сумм в теории чисел / М.: Наука, 1971.

107. ЛинникЮ.В, О суммах Вейля// Матем. сб. 12 (1943) вып. I, 28-39.

108. Нестеренко Ю. В. К теореме о среднем И.М. Виноградова // Труды Московского Математического общества 48 (1985), 97-105.

109. BajnokB., Ruzsal. The independence number of a subset of an abelian group // Integers: Electronic Journal of Combinatorial Number Theory 3 # A02, 2003.

110. AdhikariS. D. Aspects of Combinatorics and Combinatorial Number Theory / Norosa Publishing House, India, 2002.

111. Spencer J. Six Standard Deviations Suffice // Transactions of the American Mathematical Society 289 (1985), 679-706.

112. Bernstein S. Sur une modification de l'in6qualite de Tchebichef // Annal. Sci. Inst. Sav. Ukr. Sect. Math. I (1924).

113. Lacey M. Т., McClain W. On an argument of Shkredov on two-dimensional corners // Online Journal of Analytic Combinatorics.

114. Brown Т. C., Buhler J. C. A density version of a geometric Ramsey theorem // J. Combin. Theory Ser. A 32 (1982) 20-34.

115. Frankl P., Graham G., Rodl V. On sets of abelian groups with no 3-term arithmetic progressions //J. Combin. Theory Ser. A 45 (1987) 157-161.

116. Lev V.F. Progressions-free sets in finite abelian groups // preprint.

117. Meshulam R. On subsets of finite abelian groups with no 3-term arithmetic progressions //J. Combin. Theory Ser. A 71 (1995) 168-172.

118. ГалеевЭ.М., Тихомиров В. M. Краткий курс теории экстремальныхзадач / М.: Издательство.МГУ, 1989.,.

119. Falconer К. Fractal Geometry. Mathematical Foundations and Applications / New York: Wiley 1990.

120. Weyl H. Uber die Gleichverteilung von Zahlen mon Eins // Math. Annalen, 77, 1916, p. 313-352.

121. ШкредовИ. Д. О возвращаемости в среднем // Математические заметки, т. 72, вып. 4, 2002, с. 625-632.

122. ШкредовИ. Д. Повторяемость неполных частных у цепных дробей // Успехи мат. наук, Т. 57, N. 4, 2002, с. 189-190.

123. ШкредовИ. Д. Об одной задаче; Гауэрса // Доклады Академии наук, 400, N 2, 169-172, 2005.

124. ШкредовИ. Д. Об одной задаче Гауэрса // Известия Академии наук, 70, N 2, 176-217, 2006.

125. ShkredovI.D. On Multiple, Recurrence // http:// www.arXiv : math.DS/0406413, 2004.

126. ШкредовИ. Д. Об одном обобщении теоремы Семереди // Доклады Академии наук, 405, N 3, 315-319, 2005.

127. Shkredovl. D. On a Generalization of Szemeredi's Theorem // Proceedings London Math. Soc., 93, N 3, 723-760, 2006.

128. Shkredovl. D. О динамических системах с медленной скоростью возвращения // Математический сборник, 197, N 11, 143-158, 2006.

129. ШкредовИ. Д. Теорема Семереди и задачи об арифметических прогрессиях // Успехи мат. наук, т. 61, вып. 6, 111-178, 2006.

130. Шкредов И. Д. О множествах больших тригонометрических сумм // Доклады Академии наук, 411, N 4, 455-459, 2006.

131. Шкредов И. Д. О множествах больших тригонометрических сумм // Известия Академии наук, 72, N 1, 1-22, 2008.

132. ШкредовИ. Д. Некоторые примеры множеств больших тригонометрических сумм // Математический Сборник, 198, N 12, 105-140, 2007.

133. Шкредов И. Д. О двумерном аналоге теоремы Семереди в абелевых группах // Известия Академии наук, 73, N 5, 179-222, 2008.