Комбинаторные свойства числовых множеств большой плотности и их приложения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Шкредов, Илья Дмитриевич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2009
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
Санкт-Петербурскпй государственный университет
На правах рукописи
Шкредов Ил1.я Дмитриевич
КОМБИНАТОРНЫЕ СВОЙСТВА ЧИСЛОВЫХ МНОЖЕСТВ БОЛЬШОЙ ПЛОТНОСТИ И ИХ ПРИЛОЖЕНИЯ
01.01.ОС — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации гга соискание ученой степени доктора физико-математических наук
г0
Санкт-Петербург 2009
003471414
Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.
Официальные оппоненты: доктор физико-математических наук,
профессор A.M. Вершик, доктор физико-математических наук, профессор В.Г. Журавлев, доктор физико-математических наук, профессор C.B. Конягин
Ведущая организация: Хабаровское отделение Института
прикладной математики ДВО РАН
Защита диссертации состоится "^т? " . ^гЧ^^... 2009 г. в 1G часов на заседании совета Д.212.232.29 по защите докторских и кандидатских диссертаций при Санкт Петербургском государственном университете, по адресу : 198504, Саикт Петербург, ст. Петергоф. Университетский просп., 28.
С диссертацией можно ознакомиться в Научной библиотеке Саикт Петербургского государственного университета по адресу : 199034. Саикт Петербург, Университетская наб., 7/9.
Защита будет проходить в Петербургском отделении Математического института им. В.А. Стеклова РАН по адресу : 191023, Санкт-Петербург, Наб. реки Фонтанки, 27. ауд. 311.
Автореферат разослан . .I^Vv..... 2009 г.
Ученый секретарь диссертационного совета доктор физ. мат. наук, профессор
В.М. Нежинский
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
В настоящей диссертации рассматривается несколько хорошо известных задач комбинаторной теории чисел. Тематика нашей работы связана с замечательным результатом комбинаторной теории чисел — теоремой Б.Л. Ван дер Вардепа1, доказанной им п 1027 году. Эта теорема утверждает, что при любой раскраске множества целых чисел в конечное число цветов найдется арифметическая прогрессия произвольной длины, все элементы которой раскрашены в один и тот же, цвет. Теорему Б.Л. Ван дер Вардена А.Я. Хин-чин2 по праву назвал жемчужиной теории чисел. Несмотря на кажущуюся простоту и естественность теорема Ван дер Вардена сыграла значительную роль в развитии двух разделов математики — аддитивной комбинаторики и комбинаторной эргодической теории. Отметим, что обе указанные области математики связаны между собой теснейшим образом и находятся на стыке таких наук, как аддитивная и аналитическая теория чисел, теория графов и теория динамических систем. Сама по себе теорема Б.Л. Ban дер Вардена является одним из фундаментальных результатов теории Рамеея (см., например, книги3).
В 1953 году К.Ф. Рот4 получил замечательное обобщение теоремы Ван дер Вардена. Используя классический метод теории чисел — метод Харди-Литлвуда, К.Ф. Рот доказал, что любое множество целых чисел положительной плотности обязательно содержит арифметическую прогрессию длины три. Более того, он получил количественную оценку на плотность подмножеств {1,2,..., iV} без прогрессий длины три. После работы К.Ф. Рота вопросы, связанные с приложением кругового метода к задачам о множествах без арифметических прогрессий длины три, рассматривались такими известными специалистами по теории чисел, как Д.Р. Хиф-Браун0, Е. Семереди6 и Ж. Бургсн'.
Теоремы К.Ф. Рота, Д.Р. Хиф-Брауна, Е. Семереди и Ж. Бургспа относятся к оценке максимальной плотности подмножества {1,2,..., N} без
1 Van dur WaentenB. L. Brovis «srar Baudetschen Vermutung ,// Nieuw Aich. Wisk., 15, 1.927, 212-21G.
-ХинчьнА. Я. Три жеичужокм теории насел : М.: Едиторкал УРСС, 2004.
:!ГрзгшР. Начала теории Рамсея / М.: Мир, 1984.; GnhamR.L., RathsduMB. £., SprnrrrJ. Ramsey Theory Wiley Interscience, Series, ir. Discrete Mathematics, 1980.
*RathK. F. On certain sets of integers (I) .1. London Math. Soc., 28, 1953, 243-252; Roth К. F. On certain sets of integers (II) // J. London Math. Soc., 29, 1953, 20-20.
''Heath-Brown D. R. Integer sets containing no arithmetic progressions / .' .1. London Math. Soc. (2), v. 35, N. 3, 1987, 385-394.
6Szrmcré.di E. On sets of integers conf air.ing no arithmetic progressions // Acta .Math. Hurigar., v. 5G, 199Û, 155-158.
7BourgainJ. On triples in arithmetic progression // GAFA, 9, 1999, 9G8-9S4.
прогрессий длины три. Только в 1975 году Е. Семсреди8 , отвечая на известный вопрос Эрдеша и Турана, и используя совершенно другой метод, доказал, что любое множество целых чисел положительной плотности содержит арифметические прогрессии любой длимы. Эта сложная работа чрезвычайно сильно повлияла на развитие комбинаторной теории чисел, а также на смежные дисциплины. Так, основной инструмент в доказательстве Семсреди, так называемая лемма регулярности, стала, на сегодняшний день, одним из важнейших методов теории графов (см. работы3). Кроме того, через несколько лет после Семсреди, Г. Фюрстснбсрг10 передоказал его теорему с помощью методов эргодической теории. Г. Фюрстснбсрг обнаружил связь между комбинаторными объектами и динамическими системами (так называемый принцип соответствия Фюрстснберга11) и основал новую пауку — комбинаторную зргодическую теорию, которая занимается различными связями между комбинаторными свойствами множеств и соответствующими характеристиками динамических систем (см., например, работы12).
Основная задача настоящей диссертации состоит в получении количественных оценок для двумерной теоремы Семсреди. Говоря кратко, она состоит в следующем: насколько большую мощность может иметь подмножество двумерной решетки без конфигураций вида (х,у), (х + d,y), (х,у + d), где d > 0? Такие тройки называются уголками или равнобедренными прямоугольными треугольника,ми. Первый результат в этом направлении был доказан М. Атаи и Е. Семсреди13 в 1974 году с помощью комбинаторных
яSzemcredi Е. On sets of integers containing no four elements in arithmetic progression /7 Acta Arith. Acad. Sci. Hangar., v. 20, 19G9, 89-104 ; SzemercdiE. On sets of integers containing no k elements in arithmetic progression // Acta Arith., 27, 1973, 299-343.
9SzemerediE. Regular partitions of graphs // Colloques Internat.ionaux CNRS, 2G0 — Problems Combinatories et Theorie des Graphes, Orsay, 197G, 399-401 ; Kohoyako,wa Y. Szemeredi's regularity lemma for sparse graphs ; Foundations of Computational Mathematics, Selected papers, IMPA conference, January 1997, Rio de Janeiro, Springer, 1997 ; KolmosJ., Simonovits M. Paul Erdos is SO (под редакцией D. Miklos, V.T. S6s, T. Szonyi) / v. 2, Proc. Colloq. Math. Soc. Janos Bolyai, 199G.
10 Furstenberg H. Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions // J. (ГAnalyse Math., v. 31, 204-25G, 1977.
11 Furst.enbergH., K'i.izv..chaii Г., An ergodic Szemeredi theorem for commuting transformations // J. ¿'Analyse Math., v. 34, 275-291, 1978. Fwatenberg[{., Katmelson Y. ami OrnstcmD. The Ergodic Theoretical Proof of Szemeredi's Theorem // Bull. Amer. Math. Soc., v. 7, N.3, 527-532, 1982.
vl Furstenberg H. Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions //' J. d'Analyse Math., v. 31, 204-25G, 1977 ; FvrstfnbcrgH. Recurrence in ergodic theory and combinatorial number theory / Princeton (N.J.), 1981 ; FvrstcnbergF{., Kotznelson K., An ergodic Szemeredi theorem for commuting transformations // J. d'Anaivse Math., v. 34, 275-291, 1978 ; Fur.stenberg H., Katznelson Y. and OrnsteinD. The Ergodic Theoretical Proof of Szemeredi's Theorem // Bull. Amer. Math. Soc., v. 7, N.3, 527552, 1982; Bergelson V., Leibman A. Polynomial extent.ions of van der Waerden's and Szemeredi's theorems // J. Amer. Math. Soc., v.9, N.3, 199G, 723-753 ; Bergelson V., Leibman A. Set-polynomials and polynomial extension of the Hales-Jewett theorem // Ann. of Math. (2), v. 150, N.l, 1Э9Э, 33-75; Furstenberg H., Katznebon Y. A density version of the Hales-Jewett theorem // J. Analyse Math., 57, 1991, 64-119; LcibmanA. Multiple recurrence theorem for measure preserving actions of a nilpotent group // Geom. func. anal., v.8, 1998, 853-031.
i3AjtaiM., Szemeredi E. Sets of lattice points that form no squares // Stud. Sci. Math. Hungar., 9, 1974,
методов. Они показали, что любое подмножество двумерной решетки положительной плотности обязательно содержит уголок. В 1978 году результат о равнобедренных прямоугольных треугольниках был передоказан Г. Фюр-стенбергом и Я. Кацпельсопом14 с помощью методов эргодической теории. Доказательство М. Атан и Е. Семередн дает очень слабые; верхние оценки на плотность множества дпумерной решетки без уголков. Доказательство Фюр-стенберга и Кацпельсона является неэффективными в том смысле, что оно вообще не даст никаких верхних оценок на указанную плотность. В своей филдсовской работе10 В.Т. Гауэрс попользовал оригинальные модификации классических методов теории чисел, таких как круговой метод и метод тригонометрических сумм, и получил принципиально новые количественные оценки в задачах типа теоремы Б. Семередн. В той же работе10 В.Т. Гауэрс еще раз привлек внимание к вопросу о получении эффективных оценок в задаче об уголках. В диссертационно» работе удалось создать оригинальные и принципиально новые теоретико-числовые конструкции, позволяющие, в отличие от эргодичсского и комбинаторного подходов, получать хорошие количественные оценки в рассматриваемых многомерных задачах.
В настоящее время популярность тематики, связанной с описанными выше задачами, достаточно велика: в разные годы ими занимались замечательные специалисты в области теории чисел, комбинаторной теории чисел и комбинаторной эргодической теории, такие как филдсовские лауреаты К.Ф. Рот, Ж. Бургсн, Т. Гауэрс, Т. Тао, а также П. Эрдеш, Е. Семередн, С. Шел ах, Р. Радо, В. Редл, П. Франкл, Л. Ловас, И. Р.ужа, С.В. Копягип, Р.Л. Грэхем, П. Туран, Г. Фюрстепберг, Я. Кацпельсоп, В. Бергельсон, А. Лейбман, Б. Ост, Б. Кра, Г.А. Фреймаи, Д.Р. Хиф-Браун, В. Шопг, А. Балог, А. Шаркоци, Г. Элекеш, М. Атаи, Н. Кац, Б. Грин, М.-Ч. Чапг, В. By и другие.
Научная новизна работы.
В настоящей диссертации удалось создать оригинальные методы и применить принципиально новые модификации классических методов теории чисел, позволяющие, в отличие от использующихся ранее эргодичсского и комбинаторного подходов, получать хорошие количественные оценки в задаче об уголках. Основной результат о двумерном обобщении теоремы Е. Семереди является решением достаточно давно стоявшей задачи17, впервые сформули-
9-11.
11 Furstenberg]L, Katmelson У., An ergodic Szemeredi theorem for commuting transformations // J.
¿•Analyse Math., v. 34, 275-291, 1978.
wCoecr»W. T. A new proof of Szemeredi's theorem // Geom. func. ati.il., r.ll, 2001, 405-588. и Gnw-
crs W. T. A new proof of Szemeredi's theorem for arithmetic progressions of length four // Geom. func. anal.,
v.S, 1998, 529-551
16Cowers W. T. A new proof of Szemeredi's theorem // Geom. func. anal., v.ll, 2001, 403-588.
17 AjtaiM., SzemerediE. Sets of lattice points that form no squares // Stud. Sci. Math. Hungar., S, 1374, 9-11;
рованой специалистами по эргодической комбинаторике, а затем упомянутой В.Т. Гауэрсом (см. работу18), в контексте появившихся оригинальных вариантов использования в подобных задачах классических тсоротико-числовах методов. Доказанные результаты являются новыми, полученными автором самостоятельно. Кроме того, новыми являются не только сами результаты, по и методы их обоснования. Так, впервые метод тригонометрических сумм соединен с теоретико-графовым подходом, что привело к получению наилучшего на сегодняшний день результата о множествах, не содержащих уголков. Новыми являются конструкции построения динамических систем с медленной скоростью кратного возвращения, а также метод доказательства существования нетривиальных решений линейных уравнений с элементами из множества больших тригонометрических сумм. Подход, связанный с построением динамических систем с медленной скоростью однократного возвращения существенно видоизменен и нетривиально доработан.
Основные результаты диссертации состоят в следующем :
1. Любое множество А С {1,2,... ,N}2 мощности Ar~/(logloglogгде с > 0 — некоторая эффективная константа, содержит уголок.
2. Доказана структурная теорема о плотных подмножествах {1,2,..., iV}-'.
3. Получен критерий о-равпомерпости множества А в терминах матрицы смежности графа G¿, ассоциированного с /I, а также в терминах плотности А в декартовых произведениях больших подграфов графа
С.4.
4. Любое множество А С {1,2,..., vY}2 мощности iV2/(loglog Лг)с, где С > 0 — некоторая эффективная константа, содержит уголок.
5. Всякое подмножество декартова квадрата G х G произвольной конечной абелевой группы G мощности |G]2/(loglog |G|)fl, где С\ > 0 — некоторая эффективная константа, содержит уголок.
6. Получены пример!,i динамических систем с медленной скоростью кратного возвращения.
7. Доказаны теоремы об оценке сверху для скорости многомерной возвра-щаемости.
Furst.e.nberg Н., Katzne.Uon У", An orgodic. Szemerédi theorem for commuting transformations ; / .1. d'Analyse Math., v. 34, 275-231, 1978.
1Gomas W. T. A new proof of Szemerédi's theorem // Geom. func. anal., v. 11, 2001, 4G,"i--j8S.
8. Построены примеры динамических систем с заданной скоростью однократного возвращения.
9. Найдена наилучшая оценка снизу для числа решений уравнения 7Д
----Ь г к = г[ + - - • + г'к, где все г.. г' принадлежат множеству больших
тригонометрических сумм, а также для системы линейных уравнений с переменными из множества больших тригонометрических сумм.
10. Получен результат, существенно улучшающий теорему Чанг о строении множества больших тригонометрических сумм.
Методы доказательства утверждении, сформулированных в пунктах 1 и 4 совершенно различные. Первый подход опирается на структурные результаты о плотных подмножествах двумерной решетки (пункт 2), а второй использует свойства множеств Бора. Оба метода дают существенное продвижение в известной и трудной задаче о уголках. Хотя в контексте данной задачи второй метод сильное, тем не менее, он принципиально не позволяет получать, интересные сами по себе, утверждения о структуре плотных подмножеств {1,2,..., .¿V}2. Кроме того, второй метод использует некоторые результаты, доказанные с применением первого, более слабого, подхода.
Необходимо отметит!), что результаты, сформулированные в пунктах 14, а также в пунктах 8 и 9 касаются вопросов традиционно относящихся к зргодической, комбинаторной теории чисел и, так называемым, обратным задачам аддитивной теории чисел. Часть результатов, например, пункт 0, являются естественной переформулировкой основных числовых теорем па языке теории динамических систем.
Методы исследования.
В работе используется метод тригонометрических сумм и анализ Фурье, комбинаторные методы, методы теории графов, методы теории динамических систем, а также методы аддитивной комбинаторной теории чисел.
Теоретическая и практическая ценность.
Диссертация носит теоретический характер. Методы, разработанные в ней, могут быть полезны при дальнейшем исследовании задач о двумерных и многомерных обобщениях теоремы Семереди, а также могут применяться при решении других проблем комбинаторной теории чисел и аддитивной комбинаторики. Ее результаты могут быть использованы в зргодической теории, метрической теории чисел и аддитивной теории чисел. Разделы диссертации могут составить содержание специальных курсов для студентов и аспирантов, обучающихся по специальности математика.
Апробация работы.
Результаты настоящей диссертации неоднократно докладывались автором на многочисленных международных конференциях и семинарах. Перечислим сперва конференции: международная конференция "Современная теория динамических систем и ее приложения к небесной механике'' (г. Москва, 2002 г.); пятая международная конференция "Алгебра и теория чисел: современные проблемы и приложения" (г. Тула, 2003 г.); международная конференция "XXIII Арифметические дни" в Граце (Австрия, 2003 г.); международная конференция "'Диофантопый анализ, равномерное распределение и их приложения" в Минске (Беларусь, 2003 г.); международная конференция "Новейшие достижения в аддитивной комбинаторике" в Пало Альто (США,
2004 г.); международная конференция "Аналитические методы в теории чисел, теории вероятностей и математической статистике" (Санкт-Петербург,
2005 г.); международная конференция "Геометрические методы в физике' в Бело веже (Польша, 2005 г.); международная конференция "Аддитивная комбинаторика" в Бристоле (Англия, 2005 г.); международная конференция "Вероятность и зргодическая теория" (США, 2006 г.); международная школа и конференция "Аддитивная комбинаторика" в Монреале (Канада, 2000 г.); "Аналитические и комбинаторные методы в теории чисел и геометрии" (г. Москва, 2006 г.); "Диофантовы и аналитические проблемы теории чисел" (г. Москва, 2007 г.); "Равномерное распределение" в Марселе (Франция, 2008 г.); "Наводя мосты" в Будапеште (Венгрия, 2008 г.); "Феномен дискретной жесткости в аддитивной комбинаторике" в Беркли (США, 2008 г.); Ломоносовские чтения в Московском государственном университете г. 2002, 2004, 2000-2008 гг.
Перечислим теперь семинары : кафедральный семинар кафедры теории чисел под руководством чл.-корр. РАН Ю. В. Нсстсронко и д.ф.-M.it. Н. Г. Мощевитииа; кафедральный семинар кафедры динамических систем под руководством акад. РАН Д. В. Аносова, д.ф.-м.н. В. М. Закалюкина и к.ф.-м.н. А. А. Приходько; семинар "Аналитическая теория чисел" под руководством д.ф.-м.гг. А. А. Карапубьг; общеипститутский математический семинар ПОМИ РАН под руководством д.ф.-м.н. А. М. Воришка, акад. РАН И. А. Ибрагимова, чл.-корр. РАН С. В. Кислякова, акад. РАН К). В. Матияссвича; Санкт-Петербургский семинар по теории представлений и динамическим системам под руководством д.ф.-м.н. А. М. Вершика; Санкт-Петербургский алгебраический семинар им. Д.К. Фадеева под руководством д.ф.-м.н. А. В. Яковлева; семинар "Арифметика и геометрия" под руководством д.ф.-м.н. Н. Г. Мощевитииа и д.ф.-м.н. А. М. Рай городского; семинар "Гамильтоновы системы и статистическая механика" под руководством акад. РАН В. В. Козлова и чл.-корр. РАН Д. В. Трещева; семинар
"Динамические системы и зргодичсская теория" под руководством акад. РАН Д. В. Аносова, д.ф.-м.п. А. М. Стопина, д.ф.-м.н. Р. И. Григорчука; семинар "Тригонометрические суммы и их приложения" под руководством д.ф,-м.н. Н. Г. Мощевитина и к.ф.-млт. А. В. Устинова; семинар "Теория функции и ее приложения" под руководством д.ф.-м.н. С. В. Конягина, к.ф.-м.н. В. Б. Демидовича и к.ф.-м.н. А. С. Кочурова, семинар "Динамические системы" под руководством профессора В. Бича, семинар "Эргодпческая теория" под руководством акад. РАН Я. Г. Синая, семинар "Эргодпческая теория и аддитивная комбинаторика" под руководством профессора М. Виэрдла, профессора Э.Лезинь, профессора Б.Кра, "Научно-исследовательский семинар по теории функций" под руководством чл.-корр. РАН Б. С. Кагпипа , д.ф.-м.н. С. В. Конягина, д.ф.-м.н. Б.И. Голубова и д.ф.-м.н. М.И. Дьяченко, семинар "Теория функций" под руководством чл.-корр. РАН B.C. Кашина и д.ф.-м.н. С. В. Копягипа.
Публикации.
Результаты диссертации опубликованы в 12 работах, список которых приводится в конце автореферата. Все работы опубликованы в журналах, входящих в действующий перечень ВАК.
Структура и объем работы.
Диссертация изложена па 217 страницах и состоит из введения, общей характеристики работы, списка использованных обозначений и сокращений, пяти глав и списка использованных источников, включающего 135 наименований.
КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ.
Диссертация делится на пять глав. В первой главе даются постановки основных проблем и излагается их история. Вторая глава посвящена получению количественных оценок в задаче о двумерном обобщении теоремы Се-мереди. В этой главе доказало несколько результатов о, так называемых, а-равиомерных множествах. Например, получен теоретико-графовый критерий а-равпомерпооти множества в терминах второго собственного значения соответствующей матрицы смежности. Кроме того, в этой главе доказан новый общий результат о строении плотных подмножеств множества {1,2,... , Лг}~, который вместе с полученными ранее теоремами об а-равномерных множествах, применяется при доказательстве нашего основного результата о двумерных уголках. В третьей главе к задаче об уголках применяется метод Ж. Бургена, связанный с множествами Бора. Такой подход позволяет усилит!, верхние оценки на плотность подмножеств {1,2,..., А}2 без равнобедренных прямоугольных треугольников. В четвертой главе получены примеры динамических систем с медленной скоростью кратного и однократного возвращения. Доказанные результаты еще раз указывают на тесную связь между задачами комбинаторной теории чисел и зргодической теорией. В пятой главе доказано несколько теорем о множествах больших тригонометрических сумм. Такие множества появляются во всех задачах комбинаторной теории чисел, при решении которых используется метод Фурье (например, они встречаются в задачах об арифметических прогрессиях и в задачах об уголках). Поэтому, как отмечает Гауэрс в своем обзоре 19, результаты о структуре множеств больших тригонометрических сумм чрезвычайно важны. Мы доказываем, что рассматриваемые множества имеют сильные аддитивные свойства. Кроме того, в пятой главе соискателем получено несколько приложений к задачам комбинаторной теории чисел.
Содержание главы 2.
Основным результатом настоящей главы является теорема о двумерном обобщении теоремы Е. Семереди (см. теорему 8 ниже). Мм начнем с обзора предшествующих результатов.
Пусть N — натуральное число. Положим
rtl (/V) = шах{|Л( : А С [I, ;Vj ,
А — не содержит арифметических прогрессий длины А;} ,
Используя круговой метод, К.Ф. Рот в 1953 году доказал теорему20.
"Oowert w. Г. Rough S«ructu№ *ul classification // GAFA, Special Volume - GAFA2000 "Visions in Mathematics", Tel Aviv, (1999) Part I, 79-117.
mRothK. F. On certain sets of integers (I) // J. London Math. Soc., 28, 1953, 245-252.
Теорема 1 (Рот). Пусть N — натуральное число, N > 3. Тогда
1
a,(N) «
log log Ar
Результат К.Ф. Рота был затем улучшен Д.Р. Хиф-Браупом в работе21- и Е. Семереди в статье22. Независимо друг от друга оба этих автора получили следующую оценку для flj(jV).
Теорема 2 (Хиф-Браун, Семереди). Пусть N — натуральное число, N > 3. Тогда
«7—--,
(log jV)'
где константу с молено взять равной 1/20.
Наилучший, на сегодняшний день, результат об оценке сверху величины ci:\(N) принадлежит Ж. Бургспу23.
Теорема 3. (Бурген) Пусть N — натуральное число, N > 3. Тогда
[Осг 10сг /V
111
А. Берепд в работе24 получ[гл нижнюю оценку величины аз(ЛГ) (см. также работы20). Р. Ранкип в статье20 обобщил результат А. Беренда на случай всех к > 3.
Теорема 4 (А. Беренд, Р. Ранкин). Пусть е > 0 — любое действительное чисм> и к >3 — натуральное. Тогда для всех достаточно больших N. выполнено
о,(ЛТ) >ехр(-(1+5)С,(1о8-Лг)1/('-1)),
где Си некоторая положжтельная эффективная константа, зависящая только от к.
il'-ith -!'tu11:11 !'). 11. I::Tt'p>': sets routair.ing no arithmetic progressions / .1. London Math. Soc. (2), v. 33, N. 3, 1987, 385-391.
--Szfmcrf*!!.! E. On sets of integers containing no arithmetic progressions // Acta Math. Hangar., v. 3G, 1990, 153-158.
nBo«rgainJ. On triples it! arithmetic progression .•/GAFA, 9, 1999, 9G8-984.
24 BehrendF. A. On sets o: integers wrriidi contain no three terms in arithmetic progression // Proc. Nat. Acad. Sci., 23, 194G, 331-332.
-'emphSalemR., SpeucerD.C. On sets of integers which contain no three terms in arithmetical progression / Proc. Nat. Acad. Sci, Wash., 28. 1942, 5G1 - 3G3 ; SalemR., SpencerD. C. On sets which do not, contain a given number of terms in arithmetical progression 7 Nieuw Arch. Wisk., 23, 1950, 5G1 - 5G3 ; Mover L. On non-averaging sets of integers Canad. Math. .J., 3, 1933, 245-252.
Rn,iij.in II. A. Sets of Integers Containing not more than a Given Number of Terms in Arithmetic Progression // Proc. Roy. Soc. Edinburgh, Go, N.4, Sec. A, 1961, 332-344.
Теоремi.r К.Ф. Рота, Е. Семерсди, Д.Р. Хиф-Браупа и Ж. Бургена относятся к оценке величины О/ДА). Долгое время вопрос о поведении функций ak(N) при к >4 оставался открытым. Лишь в 1975 году Б. Семерсди доказал, что сц-(М) —> 0 при N —> +оо для всех к > 4 (см. статг.и27).
Альтернативное доказательство теоремы Е. Семерсди было предложено Г. Фюрстенбергом в работе21* (более простое доказательство изложено в статье23). Его подход использует методы зргодической теории. Г. Фюрстепберг показал, что теорема Е. Семерсди эквивалентна утверждению о кратной воз-вращаемости для почти всех точек в произвольной динамической системе.
К сожалению, методы Семерсди дают очень слабые верхние оценки для a¡f{N). Эргодический подход вообще не дает никаких оценок. Только в 2001 году В.Т. Гауэрс30 получил первый эффективный результат о скорости стремления к пулю величины a¿(Ar) для к > 4.
Теорема 5. (Гауэрс) Для всех натуральных N > 3 и к > 4 справедливо неравенства
ak(N) « l/(loglogA7\
где. константа Cf- = 2~2
Рассмотрим двумерную решетку [Аг]2 с базисом с; = (1,0) и е2 = (0, —1). Пусть
ЦА')=~шах{ |Л| : .4C[l,Af и
А — не содержит троек вида (fc,m), (к + d, т), (к, т + <í), d > 0}. (2)
Тройку из (2) мы будем называть уголком.. В работе31 М. Атаи и Е. Семерсди доказали, что величина L(N) стремится к 0, когда N стремится к бесконечности. Говоря точнее, они получили даже более сильный результат.
Теорема ß. (Атаи, Семереди) Пусть 0 < д < 1 — действительное число, N — натуральное число « S = {(0,0), (0,1), (1,0), (1,1)} — единичный квадрат. Тогда любое множество А С [А']2, \А\ > SN- содержит аффинный аврал S, то есть множество aS + 6. где a € N w 6 € N2.
~7Szp.mp.rédi. E. On sets of integers no four elements in arithmetic progr ession ; Arta Arith. Acad.
Sri. Hungar., v. 20, 19G9, 89-104 ; Szcmercdi E. On sets of integers containing no k elements in arithmetic progression /• Acta Arith., 27, 1975, 299-340.
Furstenbrrg If. Ergodic behavior of diagonal measures and a theorem of Szemeredi on. arithmetic progressions .7 J. (¡'Analyse Math., v. 31, 204-25G, 1977.
Fursteiíberg H., Katznchon Г. and Onistein D. The Ergodic Theoretical Proof of Szemerédi's Theorem // Dull. Am«. Math. Soc., v. 7, N.3, 527-552, 1982.
1:1 IV. T. A new proof of Szemerédi's theorem for arithmetic progressions of length four // Geom.
func. anal., v.8, 1998, 529-551 : Gowrrs 1Г. T. A new proof of S7.emerédí's theorem // Geom. func. anal., v.11, 2001, 405-588.
AjiaiM.. Szf.meráUE. Sets of lattice points that, form no squares /7 Stud. Sei. Math. ilungar., 9, 1974, 9-11.
Затем теорема С была передоказапа Г. Феетенбергом в книге32.
Ясно, что задача про уголки является двумерным обобщением задачи о множествах без арифметических прогрессий длины три в том смысле, что равенство 1тгдг_х £(ЛГ) = 0 влечет Шил--,«- я.з(ЛГ) = 0.
В.Т. Гауэрс (см. статью33) поставил вопрос о скорости сходимости L(N) к 0. В работе31 В. By, развивая подход из статьи30 предложил следующее решение этого вопроса. Пусть logjjj = log А' и для I > 2 положим log;,] N = log(log[jr_1] N). Таким образом logr/j Л7" есть результат взятия логарифма от числа N I раз подряд. Далее, пусть к — наибольшее натуральное число, такое, что logjy N > 2. Тогда положим log, N = к.
Теорема 7. (By)
L(N) < 1Ш
1о8^/4 N '
В работах30 был получен следующий результат.
Теорема 8. Пусть & > 0, N » ехрехрехр(<5~с), С > 0 — некоторая .эффективная, константа и АС {1,... , Лг}~' — произвольное подмножество, мощности, не .меньше, -ч.е.и дЛг'. Тогда А содержит тройку вида (к, и».), (к~ Л,т), (к,т + с1). где (I > 0.
Таким образом получена оценка величины Ь(Аг) сверху Ь{Аг) <С 1/(1оё1о5Л0с', где С! =" 1/С.
Кроме того, п этом же параграфе мы получим простейшую оценку снизу для величины ¿(Аг).
Теорема 9. Для любого е > 0 существует М- 6 N. такое что для всех
1.18 2 Н-г
натуральных Аг > АГ£. выполнено ЦЛГ) > N ■"«»«л*.
Доказательство теоремы 8 содержится в параграфах 2.2, 2.3 и 2.4. Параграф 2.2 посвящен понятию а-равномерности. Пусть N — натуральное число. Обозначим через Ъц = Ъ)ЫЪ множество вычетов по модулю N. Пусть А произвольное множество из Жд', \А\ = 5А1. Будем обозначать той же буквой А характеристическую функцию этого множества. Функция /(«) = А(а) — д называется балансовой функцией множества
31 Furstenberg If. Recurrence in ergodic theory and combinatorial number theory / Princeton (N..I.), 19S1.
33 Cowers [V. T. A new proof of Szemeredi's theorem for arithmetic progressions of length four /'/ Geom.
func. anal., v.8, 1098, 523-551.
34 Vu V. ff. On a question of Gowers // Ann. of Combinatorics, G, 2002, 229-233.
31 Solymosi J. Note on a generalization of Roth's theorem /'/ Discrete and computational geometry, 825-827, Algorithms Combin., 25, Springer, Berlin, 2003.
m Шкрсдав If. Д. Об одной задаче Гауэрса // ДАН, 400, N 2, 109-172, 2005 ; ШщкдавИ. Д. Об одной задаче Гауэрса Ц ИАК, 200, N 2, 17G-217, 200G.
А. Обозначим черта В замкнутый дпек на комплексной плоскости с центром в 0 и радиусом 1.
Определение 1. Функция / из Zд- в В называется а -равномерной, если £|£/(я)Д^|2<оЛг'!. (3)
к н
Будем говорить, что множество А является а-рашгомерньш, если его балансовая функция о—равномерна.
Пусть Е\ х E-i некоторое подмножество Z2V и / : T?N —> D — некоторая функция. Будем писать / : х Е2 —► D, если вне Е\ х Ео функция / равна 0.
Определение 2. Пусть а любое действительное число, а € [0,1]. Пусть Е\ х El — некоторое подмножество IrN. Функция / : Е\ х Ei —> В называется а-равномерной, относите.,гьно ба.тса (ei,e2), если
J^TV^)f(s + ue2 +rGl) < |2|£2|2. (4)
S.B 7'
Пусть множество Л принадлежит некоторому множеству Е\ х Еп. Определим плотности Sm = и 7/,. = по формулам 6т = l/|£i| Л(?не2-(-
Pd), 77, = l/l^l-Eili ^(tci+pco). Функцию /(s) = назовем балансовой функцией множества Л.
Будем говорить, что множество А С х E-i является а-равномерным, относительно базиса (е^ео), если его балансовая функция а-рашюмерпа, отпосителг.но этого базиса.
Наше первое, предложение относится к ситуации, когда множество А С Ei х Е-2 является а-ратю.мери.ы.м, относительно базиса (ei,c->), я сами лто-жества £1, £л> являются а-равномерными в смысле определения 6.
Теорема 10. Пусть множество А принадлежит Ei х Еу и им,ест мощность |Л| = ¿|£i||£2¡- Пусть \Е\\ = PiN, |Ег| = Д>N и множества E¡,E2 являются 10'3iO>3f4^.?4(5132 равномерными. Пусть также А является а-равномерным., относительно базиса, (е^ео), а = 10_Ш8б44, N > Ю10(0%/32)-1 и I5« - 5|2 ^ afcN. Тогда А содерэ/сит уголок.
В параграфе 2.3 мы рассматриваем ситуацию когда множество А С Ei х Е2 не является а-равномерным, а Е2 произвольны. В этом случаем справедливо следующее предложение.
Теорема 11. Пусть множество А С Е\ х Е%, имеет мощность |Л| = <5|£,1||£о|. Пусть о- > 0 действительное число и А не а-равномерно, относительно ба.гит (е^ез). Тогда существуют множества С Е\ и бг С Е2
для которых выполнено
ИП«?: х С,)| > (д + 2-5Ша70)|С1||<32| и (5)
1^1,1021 > 2-500а70тт{]Е1|)|£2|}. (С)
Наконец, в последнем параграфе 2.4 мы доказываем структурную теорему о декартовых произведениях плотных подмножеств [Лг].
Мы будем говорить, что двумерная арифметическая прогрессия Р есть правильный квадрат, если Р = Р\ х Р2, где Р\, Р2 одномерные прогрессии с одинаковыми разностями и равной мощности.
Теорема 12. Пусть 0 < е < 6 — некоторые числа и пусть а(б) = К$р, К € (0,1], р > 4. Пусть множество IV содержится в {1,...,ЛГ}2. |1У| = Й"ЛГ- и N > (Саг')-(1/Г2,1/", где. С = 21Ш0'\ с; = 100/; и с2 = 2~ш. а а = а(е). Тогда существуют правильны,е квадраты Рь ..., Рц С {1,..., Л'}2 и разбиение Ц' на множества П ..., IV П Рц/ и В, для которых выполнено
1) Для .любого г. .множество XV является, а^р^М1))-равномерным в прогрессии Р,;.
2) Для любого г выполнено (IV П Р,\ > е|Р,-| и \р\ > .
3) |В| < 4еЛ'2.
Из этого утверждения вытекает следующая теорема.
Теорема 13. Пусть И^, И/Г2 С 2.у - некоторые множества, (И^! = ,3^, |Н'2| = &Л', С ^ (ОД) некоторое число, а (в) = К и'', К 6 (0,1], р > 4 и а = а(С%Ъ). Предположим, что .множество А содержится в И^ X \А\ = ¿"1 |(11^21 и N > (Сас,)-М<*У/\ где С = 2ШЮ", а = 100/; и с2 = 2"128. Тогда существует такой правильный квадрат Р = Р\ х Р2, \Р\ > №*" и .множества ЦЬЯ2, Яг С (1^ П Р:), Д2 £ (№2 П Р2), |/?1 х Д2| > (ъ3\1-32|Р|: обладающие следущими свойствами : Дь Д2 являются, а{5рх(П\))112, а(др2(П2))1^2-равно.м,ерньш,и, , соответственно, в Р\ и
Р-2 ибп^пМ) ><5-4С."
В последней части параграфа 2.4 мы объединяем теоремы 10, 11, 13 и с помощью итеративной процедуры доказываем основную теорему 8.
Содержание главы 3.
В главе 3 мы доказываем усиление теоремы 8 (см. работы3').
Теорема 14. Пусть 6 > О, N ехрехр((^с), с > 0 — некоторая эффективная константа и А С {1,...,УУ}2 — произвольное подмножество, мощности не меньше, чем 8М2. Тогда, А содержит тройку вида (к, т), (к + (I, т), (к, т + й), где. д. > 0.
Таким образом получена оценка величины Ь(М) сверху ¿(Ло « 1/(1оё1оёЛ0с', где С\ = \/с.
Доказательство теоремы 14 содержится в параграфах 3.2, 3.3, 3.4, 3.5 и
3.6.
Параграф 3.2 посвящен свойствам множеств Бора35.
Пусть N и (I натуральные числа, е > 0 — действительное число и в =
Определение 3. Множеством Вора Л = Ля.г,дг называется множество
А,;, л- = {п е 1 | И < Дг, \\n9jW < £ для ] = 1,..., <1} .
Определение 4. Пусть 0 < к < 1 — некоторое число. Множество Бора Л = Л^дг называется регулярным, если для любых е', Л", таких что
1 1 1(Ш 1 1 100(1
выполнено
1 - к < .У'" < 1 + п.
|Лв.с-Д'|
В работе33 была доказана лемма.
Лемма 1. Пусть 0 < к < 1 некоторое число и Ад^х множество Бора. Тогда существует пара (ei.Ni) со свойствами,
£ АГ ,г л.
-<£!<£ « J<N{<N такая, что .множество Вора Л^л', являет,ея регулярным,.
37 ШкрсдовИ.Д. 05 одном обобщении теоремы Семереди //ДАН, 405, N3, 315-319, 2005 ; SliMovf. D. On a Generalization of Szemeredi's Theorem // Proceedings London Math. Soc., 93, N 3, 723-7G0, 200G.
38Bourgain J. On triples in arithmetic progression // GAFA, 9, 1999, 908-981. Dourgain J. On triples in arithmetic progression ,/,/ GAFA, 9, 1999, 908-984.
Определение 5. Пусть е S (0,1] некоторое число и А(У.£(),а-0 — множество Бора, 9 = (01,..., 0<i). Регулярное множество Бора А' = Л^ ^дт' называется е-сопровождающим множества Л, если 0' = (0¡,..., 6(i, 0г/+ь... , 0,1+к), к > О, его/2 < с' < £f(¡, eNo/2 < Аг' < гЛГ(). Из леммы 1 вытекает существование такого множества.
В параграфе 3.3 мы даем определение (а, £)-равномерных подмножеств множеств Бора, а также множеств являющихся (а, г)-равномерными, относительно прямоугольной нормы.
Пусть / — функция из Z в С принимающая конечное число непулевых значений. Обозначим через /(.г) коэффициент Фурье функции /
sez
где е(лг) = е2ст1.
Определение 6. Пусть Л — множество Бора, Q С Л, ]<3| = ¿|Л|, q,е — некоторые положительные числа и Л' есть ¿-сопровождающее множества Л. Рассмотрим множество
В = {т е Л I II(д П (А' + т) - ¿(Л' + > <*|Л'|}.
Множество Q называется (а\ е) -равномерным, если
|Я|<а|Л|, (7)
тт7 Е - óf < а2 • (8)
и
||(<?пл-глг||х <«|Л|. (9)
Пустг. Ai, Ао — множества Бора, е > 0 некоторое число и Л' есть е-сопровождающее множества Aj. Пусть также E¡, Е2 — некоторые подмножества Ai, Л2, соответственно, и |Ei| = /3i|Ai|, £9 = i А 21 -
Определение 7. Функция / : Ai х A¿ —> В) называется (а,е)-равномерной, относительно прямоугольной нормы, если
II/iií.xa,, = Е Е Е Е Л'(™ -к - г)л'(« -к -г)х
ieAtjeA2 к »¡.и
| Е + г — j)/(r, m)f(r, и)|2 < a/?2/?||A'|4|Ai|2|A2|. (10)
Обозначим множество Л' в формуле (10) через Ai(e).
Определение 8. Пусть АС£,х Е2, |Л| = <5/?i/?2|Ai | |Л2|, S > 0 и /(s) = A(s) - 5(£i х Е2)(s). Пусть fi(s) = ¡(si + l,s2)A'(si), ¿ £ Ль Рассмотрим множество
В = е Ai ¡ ||/г||л.хл2.г > I Л' (е) 141 A' 121 Лг I} .
Множество А называется (ct, сц, e)-равномерным, относительно прямоугольной нормы, если |В| < Qi|Ai|.
Первое предложение параграфа 3.3 относится к ситуации, когда множество А С Ei х Ei является (о,оi,e)-равномерным, относительно прямоугольной нормы, а сами множества Еi, E¿ являются (а, г)-равномерным,и в смысле определения б.
Пусть А некоторое множество Бора, А = Ag.^jv,, в G Т'1 и Е\,Ео Q A, |£i| = /3i|A|, |F2| = ,?2¡A|. Обозначим через V декартово произведение. Ех х Е2.
Теорема 15. Пусть множество А принадлежит Е\ х E¡ и имеет мощность \А\ = 6\Ei\\Ek\. Пусть множества Е\,Ег являются («о,2-10£2)-равномерными, о() = е = (2~тщ)/{\Ш). Пусть также
А является {cx,ai,e)-равномерным., относительно прямоугольной нормы, а = 2~10()<512, а-! = 2~7S и
log Ni > 21(V/log — . (11)
£¡£
Тогда А содержит тройку вида, {(к, т), (к -г d, т), (к, т + г/)} с d, ф 0.
Пусть А С Ei х Ео не содержит троек вида {(к,т), (k + d,m), (k,m + d)} с d ф 0. В параграфе. 3.4 мы доказываем следующий результат.
Теорема 16. Пусть .множество А принадлежит, V, им,ест, мощность |Л| = ál-EiH-EsI и не содержит, троек вида {(к, т), (к + d, т), (к, т + d)} с. d Ф 0. Пусть множества Ei,E¿ являются (a<o,2~w£~)-равномерным,и. О0 = 6 = (2-lo°fl-g)/(100d), е' - 2"1(V и
log Аг > 210dlog —.
£а£
Тогда существует множество Бора А и такой вектор у = (2/1,2/2) G Z", что для, Muooicecme Fi С Ei П (А + yi), F¿ Q Е? П (Л + у?), выполнено
\Fi\ >2~lVÍ5nfa\h\, |F2| > 2"125¿12/?2|A| и (12)
5р1хГг{А)>6 + 2'Ш6Х!. (13)
При этом для А = Л^ ? д, вы,пол,паю в = в, ё > 2"5г'го и N > 2~ъе'М.
В доказательстве последнего утверждения используется теорема 15. Сформулнрем основной результат параграфа 3.5.
Теорема 17. Пусть А = А(9,£«, Лг) некоторое множество Бора, в £ Т'' и целый вектор в = (в^в-)). Пусть е,а,т,5 £ (0,1) — вещественные числа, Е\, Е-2 некоторые множества, Е, = Д|Л|, г = 1,2, Е = Е\ х £2 подмножество (Л + 51) х (Л + вг), А С Е, ¿е(^) = 6 + т и е < к/(1(Ш), к = 2-100(гА^)5^. Предположим также, что
N > . (14)
н а < 2~Ш)тРф2- Тогда существует мноэ/сество Вора, Л' = А(в\ е', М'), в' £Т°, 0< 2ж\т13и32)~5а^ + (I, е' > (2'и)£)Вс0, Лг' > (2-шг)0ЛГ н целый вектор Ь = £2)- ншк ,<шо .атожеств Е[ = (£1 —¿1) П Л'. .К = (^2 — /2) П Л', Е' = х Е!2 выполнено
1) |Е'( >
2) Е[,Е'-, являются (а, е) — равномерными, подмножествами Л';
3) 1) > й + т/16.
В последнем параграфе главы 3 мы объединяем теоремы 16, 17 и с помощью итеративной процедуры доказываем основную теорему 14.
Содержание главы 4.
Пуст!» Л' — некоторое множество с сигма-алгеброй его подмножеств В. Пусть также Т — измеримое, сохраняющее меру /х отображение X в себя. Всюду ниже будем считать, что /¿(Л") = 1. Четверка (X, В,[1,Т) называется динам.ичсской системой с инвариантной .мерой. Хорошо известная теорема А. Пуанкаре о возвращении40 утверждает, что для всякого измеримого мггожества Е С X, цЕ > 0 существует натуральное п > 0 такое, что
/|(£ПГ»В)> 0.
Предположим, дополнительно, что X — метрическое пространство с метрикой с!{-, •), а В — борелевская сигма-алгебра. В этом случае теорема Пуанкаре может быть переформулирована следующим образом.
Теорема 18. Пусть X ~ метрическое пространство с метрикой <!(•,■) и (г — борелевская мера на X. Пусть Т — отображение X в себя, сохраняющее меру р>. Тогда для почти всех точек х £ X выполнено
НттГ 6(Т"х,х) =0. (15)
п—»СО
40Пуанкаре А. Новые методы небесной механики / Избранные труды. Т. 2. М.: Наука, 1972.
Как мы отмечали выше Г. Фюрстепберг41 (см. также42) обобщил теорему Пуанкаре па случаи нескольких степеней отображения Т.
Теорема 19. Пусть X — пространство с сигма-алгеброй измеримых множеств В и /х — мера на X. Пусть Т — отображение X в себя, сохраняющее меру /1, и к > 3. Тогда для любого измеримого .множества Е с цЕ > О существует натуральное п > 0 та,кое, что
ц{Е П Т~"Е П Т'~"Е п • • ■ П Т~{к~1)"Е) > 0.
Если X — метрическое пространство, то теорема 19 может быть переформулирована следующим образом.
Теорема 20. Пусть X — метрическое пространство с метрикой (!(■,•) и ц — борелевска.я, мера на X. Пусть Т — сохраняющее меру /< отображение X в себя и к > 3. Тогда, для, почти всех х € X
Нт 1п1 тах{(1{Тпх,х),с1{Т2"х,х),...,с1(Т{к~х]"х,х)} = 0.
В работе43 Г. Фюрстепберг и Я. Кацнельеоп перенесли теорему 19 на случаи нескольких коммутирующих отображений. Мы сформулируем их теорему в случае, когда X является метрическим пространством.
Теорема 21. Пусть X — метрическое пространство с метрикой с1(-,-) и ц — борелевсхая мера на X. Пусть к >2 и Ту, То,..., 7). — сохраняющие меру /I коммучпирующие отображения X в себя. Тогда для, почти всех х, € X выполнено
Нтт! т&х{с1{Т{'х,х),(1{Т.?х,х),... ,с1{Т[!х,.х)} = 0.
11 Furstenherg H. Ergodic behavior of diagonal rne/A.surw and a theorem DÎ Szetnorédi on arithmetic progressions // J. d'Analyse Math., v. 31, 204-25G, 1977.
42FurstenhergH. Recurrence in ergodic theory and combinatorial number theory / Princeton (N.J.), 1931 ; Furstenherg IL, Katznclson Y. and OrnsteinD. The Ergodic Theoretical Proof of Szemerédi's Theorem /'/ Bull. Amer. Math. Soc., v. 7, N.3, 527-552, 19S2.
^ Furstenherg H., KatznelsonY., An ergodic Szemerédi theorem for commuting transformations // J. d'Analyse Math., v. 31, 275-291, 1978.
Эквивалентность теоремы Е. Сомореди теоремам 19 или 20 былы доказана Г. Фюрстенбсргом44, что указывает на тесную связь между эргодической теорией и комбинаторными задачами об арифметических прогрессиях.
Глава 4 посвящена количественным аспектам возвращаемости. В ней мы получим верхние и ггижшге оценки скорости кратного возвращения для метрических пространств с конечной хаусдорфовой мерой. В работе41* M. Вошср-пицан доказал, что если в динамической системе (X, В, /£, Т, d) пространство X обладает конечной хаусдорфовой мерой, то теорема Пуанкаре 18 может быть значительно усилена (ниже мы сформулируем теорему Боптерницапа более строго). После этого результата возникает естественный вопрос о получении аналогичных усиленных вариантов теорем 20 и 21 для пространств c, конечной хаусдорфовой мерой. В параграфе 4.2 мы получим такие варианты для теоремы 20 и частично теоремы 21 (случай к = 2). Наши результаты дают верхние оценки скорости кратного возвращения. В параграфе 4.3 мы получим нижние оценки для скорости кратного возвращения. В своем доказательстве мы применяем оценки А. Берепда и Р. Ранкина для величины а/,.(Аг) (см. теорему 4 выше).
Прежде чем сформулировать теорему Вошерницапа и наги основной результат мы дадим несколько определений.
Рассмотрим меру Я/Д-) на X, определенную следующим образом
Hh(E) = lim Н[(Е), (16)
Л—>о
где h(t) — неотрицательная (k(0) = 0) непрерывная возрастающая функция, a Hft(E) — inf{£ h{àj)}, где inf берется по не более чем счетным покрытиям Е открытыми множествами {Я,}, diam(Bj) = Sj < 5.
Если h(t) = t'\ то получаем обычную меру Хаусдорфа, которую обозначим через //„(•).
Внешняя мера Hi,(-) является сигма-аддитивной на сигма-алгебре множеств, измеримых по Каратеодори. Хороню известно40, что эта сигма-алгебра содержит все борелевские множества.
Будем говорить, что меры /t и #/, согласованы, если любое //-измеримое множество является Я/,-измеримым (в смысле измеримости по Каратеодори).
Определение 9. Пусть х е X. Число
ОД = С'Чх) := lim inf {п • h{d{T"x,x))}
'1 Fnrstc.nbe.rg fi. Récurrence in ergodic fheory and combinat.oriai numb^r îheory . Princeton (N.J.), 1981.
47 Boshertiitzan Kf. QuantiUrive récurrence resuh.s /■' Inventiones '.nathemat icae, 113, Fasc. 3, 1993, G17-C31.
Богачев В. //. Основы теориии меры / Москва-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2003.
начинается константой возвращения точки х.
В статье4' М. Боигсрницан получил первый количественный аналог теоремы 18. Похожий результат независимо доказал Н.Г. Мощевитии в работе48.
Теорема 22. Пусть X — метрическое пространство, имеющее Н/,(Х) < ос, а Т — отображение X в себя, сохраняющее меру ц. Пусть также мери ц. и H¡, согласованы. Тогда для, почти всех, относительно меры р, точек х из X выполнено С(х) < оо.
В работе49 М. Боигсрницан получил ряд приложений теоремы 22 к различным динамическим системам. О приложении теоремы Богиерницана к теории цепных дробей см. статью00.
В статье01 был доказан результат, несколько усиливающий теорему 22.
Теорема 23. Пусть X — метрическое пространство, имеющее Hj,{X) < оо, а Т — отобраэ1Сение X в себя, сохраняющее .меру //,. Предположим, что меры /л и H¡t согласованы. Тогда С(х) интегрируемая, (по мере ц) функция, и для, любого //-измеримого А выполнено
[ C-{x)dfi < Н/,(А). (17)
Ja
Если же Hi,(A) = 0, то fAC(x)d/i = 0 без условия согласованности .мер ¡i и //,„
Кроме того, в той же работе был получен результат о скорости возвращения для вполне ограниченных метрических пространств.
Определение 10. Пусть G — вполне ограниченное подмножество в Л', г - энтропией множества G (следуя А.Н. Колмогорову02) называется величина H£(G, X) = log2 NC-{G, Л') , где N;(G, X) - наименьшее количество точек которое может быть не - сети этого множества.
Обозначим через N€(X) число N:(X,X).
17 Bosli.rrmt.znn М. Quaiit.itative rerjrrence results Invení iones mathematicae, 113, Fase. 3. 1993, 017-031.
^ШтгвшттН. Г. Об одной теореме Пуанкаре • УМН, 33, вьгп. 1, 1998, 219-220.
Boshcrn.ii.zan.М. Quantitative recurrence resuits /7 Inventiones mathematicae, 113, Fase. 3, 1993, G17-G31.
10 UlK]>rj)aeIf. Д. Повторяемость неполных частных у цепных дробей // УМН, т. о7, N. 1. 2002, с. 189190.
11 Шкрр.ОовИ.Д. О вогр.ратаемости в среднем ; Мат. заметки, т. 72, вып. 4, 2002, G2.j-G.32.
колмогоров а. //. О некоторых асимптотических характеристиках вполне ограниченных .метрических
пространств /7 ДАН, том 108, 3, 1930.
Определение 11. Возьмем произвольное натуральное N и пусть х 6 X. Число
CN{x) = min{ d(T"x, х) I 1 <n<N} назовем N - константой возвращаемое.™ для точки х.
Теорема 24. Пусть X — вполне ограниченное метрическое пространство с метрикой </(-,•), функцией N(z) = N.(X), diam(X) = 1 и Т — отображение X в себя, сохраняющее меру р.
Пусть А С X — ллобое р-из.неримое множество и д(х) действительная неубывающая функция, ограниченная на [О, I], такая что для любого t € (0, lj существует интеграл Стилтьеса f^ N¿(z)dg(z), где N¿(z) = mm(n(A),Nz(A,X)/N). Тогда выполнено следующее неравенство ^
J g{Cs(x))d» < mf{ ЖЫА) + J ЛШ dg(z) } .
Вернемся к теоремам 19 и 21. В параграфе 4.2 мы доказываем некоторые их количественные варианты.
Пусть S и R два коммутирующих отображения пространства X, сохраняющие меру ц.
Определение 12. Пусть х е X. Число
Cs.r(x) = C'¿„(х) := liminf {L~l(u) ■ uuix{li(d(S"x,x)),h(d(R"x,x))}},
íl —*0C
где L~l(n) = l/L(n), называется константой одновременного (или кратного) возвращения точки х.
Теорема 25. Пусть X — метрическое пространство, имеющее ¡{¡¡(Х) < оо , a S,R, - коммутирующие отображения X в себя, сохраняющие меру р. Предположим, что меры ц и H¡, согласованы. Тогда C$,r{x) интегрируемая (по мере р) функция и для любого р-измеримого А выполнено
JcsM[x)dp < И,: А). (18)
Если ж:с Hi,(A) = 0. то f4 Cs./?(x)d/i = 0 бел условия согласованности м.ер р. и Н),.
По аналогии с определением 11 мы дадим определение константы возвращаемости точки под действием двух коммутирующих операторов.
Определение 13. Возьмем произвольное натуральное. N и пусть х £ X. Число
С^'(х) = min{ max{d(S"x,x),d(R"x,x)} | 1 < п < N } назовем А' — константой одновременной возвращаемости для точки х.
Теорема 26. Пусть X — вполне ограниченное метрическое пространство с метрикой d(-,-), функцией N(z) = NZ(X), diam(X) = 1 и S,R — отображения X в себя, сохраняющие меру /<.
Пусть А С X — любое /i-илмеримос множество и д(х) действительная не убывающая ¡функция, ограниченная на [0,1], такая что для, .любого t 6 (0,1] cyitificmeyem интеграл Стилтьеса J^ NA(z)dg(z),
где Na(z) = mm(fi(A), N:{A, X)L(N)). Тогда для всех натуральны,х N выполнено неравенство
J 9{C?vR{x))dii < mf{ g{t)p{A) + £ NA(z)dg(z) } .
Итак, в теоремах 22, 23, 24, 25, 20 получены верхние оценки для интегралов от функции С(х) и Cs.n(x). В параграфе 4.3 получим нижние оценки для функции кратного возвращения в случае когда на пространстве X действует несколько степеней отображения Т. Так как степени отображения Т коммутируют, то мы автоматически получаем нижнюю оценку функции кратного возвращения и в ситуации когда на X действует несколько коммутирующих отображений.
Сформулируем основной результат параграфа 4.3.
Пусть к — фиксированное натуральное число, к > 3. Пусть для всякого натурального N задано непустое множество С Zft, не содержащее арифметических прогрессий длины к. Обозначим плотность множества А^^ в Z,v через p(N), p{N) = |A(jV)|/Ar. Тогда р{ 1) = 1. По теореме Е. Семсрсди имеем p{N) —> 0, при N —> оо.
Теорема 27. Пусть ф : N —» R+ — произвольная, .монотонно возрастающая функция, X = [0,1], /í — мера Лебега, на X и — построенная выше последовательность множеств. Тогда существует динимическая система (АГ, В, д, Т, d) такая, что р и хаусдорфова мера Н\ согласованы, Н\{Х) = 0, и для почти всех, относительно меры, ц. точек х из X выполнено
liminf {^max{d(T"x,x),d{T'2"x,x),... ,d(T(í:-1!"2',:r)}) > 1. (19) n.->00 [ P(n) J
Напоминаем, что через Н\ мы обозначаем хаусдорфоп.у меру с функцией h(t) = t.
Следствие 1. Пусть к — натуральное, число, к > 3 и £ > 0 — любое действительное число. Тогда найдется динамическая система (X,B,fi,T,d), X = [0,1 ], ¡i — м.ера Лебега, //, и ха.усдорфова .мера Нi согласованы, Hi(X) = О и положительная, эффективная константа С/,-, зависящая только от к такая, что для почти всех точек х (Е X выполнено
limiuf /тл\{д(Тпх, х), <[(Т2"х,х),..., х)} 1 > 1, (20)
»-ос {р(п) J
где p(n) = ехр(-(1 +£)Cfc(log/í)1/(A-1').
Метод, развитый для доказательства основной теоремы 27, может быть приложен к изучению функции обычной (не кратной) нозвращасмости С(х). В параграфе 4.4 мы доказываем следующий результат.
Теорема 28. Пусть f > 1 — любое действительное число, X = [0,1] и [L — мера Лебега на X. Тогда существует динамическая система (X,B,fi,T,d) такая, что ц и хаусдорфова м.ера H¡ согласованы. Нi(X) = 1 и для почти всех, относительно меры Лебега, точек х из X выполнено
Cf(x) := limiaf {n • J ■ d{T"x,x)} = 1. (21)
Содержание главы 5.
Пусть N — натуральное число. Пусть / : Z,v —> С — произвольная функция. Преобразование Фурье функции / задается формулой
/>) = £ /(u)e(-nr), (22)
NcZ.V
где е{х) = e~'ll[iIlN. Для коэффициентов Фурье функции / справедливо равенство Парсеваля
£|Лг)|2 = Л']Г|/(п)|2. (23)
r€Zдг h
Пусть 5,а — действительные числа, 0 < а < 6 < 1 и пусть А — некоторое подмножество Z,y мощности SN. Рассмотрим множество 7Za больших тригонометрических сумм А
По = Па(А) = {reZlV : |Л(г)| > aN } . (24)
Задачу о изучении структуры множеств 71а(А) поставил В.Т. Гауэрс в обзоре53.
В 2002 году М.-Ч. Чанг доказала следующий результат'14.
Теорема 29. Пусть 6, а — действительные числа,. 0<о<(5<1, -4 — произвольное подмножеств о мощности 8Ы и множество %а определено равенством (21)). Тогда найдется множество Л = {Аь ..., А|д|} С 2д',
где ег G {-1,0,1}.
Развивая подход из00 (см. такжеоС) Чанг приложила свой результат к доказательству теоремы Фрсймана0' о множествах с маленькой суммой. Другие приложения теоремы 29 получил Б. Грин в статье08. Вопрос о структуре множества И<и когда параметр а близок к й, изучался в работах09 00 01, см. также обзор02. В другой работе63 Б. Грин показал, что в некотором смысле теорема М.-Ч. Чанг является точной.
Мы видим, что результаты о строении множества 7Zn являются важными для комбинаторной теории чисел. В §5.2 пятой главы настоящей диссерации мы доказываем следующую теорему (которая затем обобщается в §5.3).
Теорема 30. Пусть 6, а — действительные чиыа, 0 < а < 6, А — произвольное подмножество Z.y мощности. 6N. к >2 — четное и множество
'''Ro:;gh structure and cla-ssineation // Geom. FUnct. Anal., Special Volume - GAFA20D0 "Visions in Mathematics", Tel Aviv, (1993) Part I, 79-117.
M Chang U.-C., A polynomial bound in Freiman's theorem // Duke Math. J. 113 (2002) т.о. 3, 399-419.
"Ли»«/. Generalized arithmetic progressions and sunrsets // Acta Math. Hunger., 05 (1994), 379-388.
^Вйи У. Structure of sets with small sumset // Structure Theory of Sets Addition, Astérisque, Soc. Math. France, Mont.rouge, 258 (1999), 77-108.
1,7ФреймомГ. A. Основания структурной теории сложения множеств / Казанский гос. пед. инст., Казань, 19GG.
r's Green В. Arithmetic Progressions in Sumsets // Geom. Funct. Anal., 12 (2002) no. 3, 584-597.
'''[О-Ъ.и.Л. A. // Теория чисел (под ред. Г.А. Фреймана, A.M. Рубинова, Е.В. Новоселова), Калининский гос. унив., Москва (1973), 103-174.
Rn Besser A. Sets of integers with large trigonometric sums // Astérisque 258 (1999), 35-70.
61 Lev V. F. Linear Equations over fr, and Moments of Exponential Sums // Duke Mathematical Journal 107 (2001), 239-203.
62 KonyaginS. VLeu V. F. On the distribution of exponential sums // Integers-. Electronic Journal of Combinatorial Number Theory 0 # A01, (2000).
63 Green B. Some constructions in the inverse spectral theory of cyclic groups // Comb. Prob. Сотр. 12 (2003) no. 2, 127-138.
(mod N) ,
(25)
1ZU определено равенством (24). Пусть также В С 7£„\{0} — произвольное .множество. Тогда величина
Tk(B):=\{(ru...,rkyb...,r'k)eB2k : п +■ ■ ■ +rk = г[ + ■ ■ ■ +r[: }| (2G) не меньше, чем
\Щ ■ (27)
Таким образом, теорема 30 показывает, что множество 1Zn обладает сильной аддитивной структурой. Как показывают результаты параграфов 5.6-5.7 последняя теорема является точной.
Применяя технику норм В.Т. Гауэрса (см. статью04), в следующем параграфе §5.3 мы получаем обобщение теоремы 30 на системы линейных уравнений.
Пусть к — натуральное число, d > 0 — целое. Пусть А = (a,-¿) — матрица (2',лЛк х (d-г 1)), где элементы (ч;,) матрицы А определяются по формуле
( 1, если в двоичном разложении (j — 1) на (i — 1)-ом месте стоит 1 и 1 <j< 2dk,
— 1, если в двоичном разложении (j — 1) на (г — 1)-ом месте стоит 1
и 2''к < j < 2d+lk, 0, иначе.
Напоминаем, что двоичное разложение натурального числа п определяется по правилу п = Ylni ' где I > 1 и щ 6 {0, 1}.
Теорема 31. Пусть д, а — действительные числа. 0 < а < ô. А — произвольное подмножество 2,у мощности SN, к — натуральное число, rf > 0 — целое и множество 7¿n определено равенством, (24). Пусть также В С Tín \ {0} — произвольное .множество. Рассмотрим систему уравнений
Т'^Ч:
Y2a'.irj= г = 1,2,.... ci + 1, (28)
j=i
где элементы (a¡¡) матрицы, А = («</), определены формулой выше и все r¡ 6 В. Тогда, число решений системы (28) не меньше, чем,
fÓa'2 . (29)
\2uS2k'
«'GWeralV. Т. A new proof oí Szemerédí's theorem // Geom. Ftote», Anal. 11 (2001), 4C5-588.
В параграфе 5.4 мы получаем несколько приложений теоремы 30 к задачам комбинаторной теории чисел. Мы выводим из теоремы 30 и неравенства В. Рудииа0'' теорему М.-Ч. Чанг. Более того, мы доказываем результат, усиливающий теорему 29.
Теорема 32. Пусть N — натуральное число. (N,2) = 1, Л, п — действительные. числа, 0 < о < 6 < 1/16. А — произвольное подмножество Ък мощности ¿¡\7 и .множество Пп определено равенством (24). Тогда существует .множество Л* С Ък,
|Л*| < тах( 2п(5/а)21о§(1 /2°1ое2(1/^)) (30)
такое, что для любого вычета г £ 7Zn существует набор А],..., ил не бол,се, ч.ем, 81о§( 1/(5) элементов Л* такой, что
м
г = (тос1 Аг), (31)
! = 1
^£¿£{-1,0,1}.
Кроме того, если, число N — простое, то найдется множество А С Ъц,
|Л| < 2,2(Д/а)21о6(1М)1оё1о5(1/<5) (32)
такое, что для любого вычета г £ Лп существует набор Ах,..., Ад/ ил не. более, чел(, 8log(l/д) элементов А такой, что
М
г = (той А), (33)
)=1
гдее,, 6 {-1,0,1}.
В том же параграфе мы получаем приложение теоремы 30 к уже упоминавшейся теореме Фреймана.
Пусть К — произвольное подмножество Ъх и £ 6 (0,1) — любое действительное число. Множеством Бора В(К, е) в называется множество
ГХ I
В(К, с) = {.г д? : < £ , для всех г е А'} ,
где || -11 — означает целую часть действительного числа. О свойствах множеств Бора см. статью00.
а'liti'hn. IV. Fourier analysis on groups / Wiley 1990 (репринт издания 19G2 года).
f'f'Emirqam J. On triples in arithmetic progression // Geom. Funct. Anal. 9 (1999), 9GS-9S4.
Теорема 33. Пусть N — натуральное число, {N,2) = 1, 0 < 6 < 2"250 — действительное, число и А — произвольное под.миоэ/сество |Л| = 6М. Тогда 2А — 2А содержит множество Бора В(К,е), где \К\ < 21ад-1 «5 = 1/(281О8(1М)).
Соискатель считает своим приятным долгом в первую очередь поблагодарить доктора физико- математических паук, профессора Н. Г. Мощевитина за постоянный интерес и внимание к работе. Кроме того, соискатель благодарит академика РАН, профессора Д. В. Аносова, чл.-корр. РАН, профессора Ю. В. Нестсрснко, доктора физико-математических наук, профессора С.В. Копягшга за неоднократную помощь и поддержку, а также доктора физико-математических наук, профессора В. В. Рыжикова за ряд ценных замечаний.
РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ.
1. О возвращаемости в среднем /'/' Математические заметки, т. 72, вып. 4, 625-632, 2002.
2. Повторяемость неполных частных у цепных дробей // Успехи мат. наук, 57, N 4, 189-190, 2002.
3. Об одной задаче Гаузрса /,/ Доклад!,т Академии паук, 400, N 2, 169-172,
2005.
4. Об одной задаче Гауэрса /,/ Известия Академии паук, 70, N 2, 176-217,
2006.
5. Об одном обобщении теоремы Семереди /'/' Доклады Академии наук, 405, N 3, 315-319, 2005.
6. On a Generalization of Szcmcredi's Theorem // Proceedings London Math. Soc., 93, N 3, 723-760. 2006.
7. О динамических системах с медленной скоростью возвращения // Математический сборник, 197, N 11, 143-158, 2006.
8. Теорема Семереди и задачи об арифметических прогрессиях //' Успехи мат. наук, т. 61, вып. 6, 111-178, 2006.
9. О множествах больших тригонометрических сумм /;' Доклады Академии паук, 411, N 4, 455-459, 200G.
10. О множествах больших тригонометрических сумм/;' Известия Академии наук, 72, N 1, 1-22, 2008.
11. Некоторые примеры множеств больших тригонометрических сумм // Математический Сборник, 198, N 12, 105-140, 2007.
12. О двумерном аналоге теоремы Семереди в абсловьгх группах // Известия Академии наук, 73, N 5, 179-222, 2008.
Подписано к печати 19.02.09. Формат 60 х 84 /is. Бумага офсетная. Гарнитура Times. Печать цифровая. Псч. л. 2,0. Тираж 100 экз. Заказ 4395.
Отпечатано в Отделе оперативкой полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.. 26 Тел.: (812)428-4043,428-6919
Введение
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 наименований.
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.
