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

Московский государственный университет имени М В Ломоносова

Механико-математический факультет

На правах рукописи УДК 511 34+511 336+517 938

Шкредов Илья Дмитриевич

КОМБИНАТОРНЫЕ СВОЙСТВА ЧИСЛОВЫХ МНОЖЕСТВ БОЛЬШОЙ ПЛОТНОСТИ И ИХ ПРИЛОЖЕНИЯ

01 01 06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва 2007

003071756

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М В Ломоносова

Официальные оппоненты: доктор физико-математических наук,

чл -корр РАН,профессор В А Быковский, доктор физико-математических наук, профессор С В Конягин, доктор физико-математических наук, чл -корр РАН, профессор Д В Трещев

Ведущая организация- Институт математики

Национальной Академии наук Беларуси

Защита диссертации состоится 18 мая 2007 г в 16 часов 15 минут на заседании диссертационного совета Д 501 001 84 в Московском государственном университете им M В Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, ауд 14-08

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (главное здание, 14 этаж)

Автореферат разослан 18 апреля 2007 г

Ученый секретарь диссертационного совета Д 501 001 84 в МГУ, профессор

В H Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В 1953 году К Ф Рот4 получил замечательное обобщение теоремы Ван дер Вардена Используя классический метод теории чисел — метод Харди-Литлвуда, К Ф Рот доказал, что любое множество целых чисел положительной плотности обязательно содержит арифметическую прогрессию длины три Более того, он получил количественную оценку на плотность подмножеств {1,2, . ,N} без прогрессий длины три После работы К Ф. Рота вопросы, связанные с приложением кругового метода к задачам о множествах без арифметических прогрессий длины три, рассматривались такими известными специалистами по теории чисел, как Д Р Хиф-Браун5, Е Семереди6 и Ж Бурген7

Теоремы К Ф Рота, Д Р Хиф-Брауна, Е Семереди и Ж Бургена относятся к оценке максимальной плотности подмножества {1,2, , ,N} без

1 Von der WaerdenB L Beweis einer Baudetschen Vermutung // Nieuw Arch Wisk , 15, 1927, 212-216

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

z Грэхем Р Начала теории Рамсея / M Мир, 1984 , Graham R L , Rothschild В L , Spencer J Ramsey Theory / Wiley Interscience, Senes in Discrete Mathematics, 1980

* Roth К F On certain sets of integers (I) // J London Math Soc , 28,1953, 245-252, Roth К F On certain sets of integers (II) // J London Math Soc , 29, 1953, 20-26

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

* Szemerédi E On sets of integers containing no arithmetic progressions // Acta Math Hungax, v 56,1990,

155-158

rßours<nn J On triples m arithmetic progression // GAFA, 9, 1999, 968-984

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

Основная задача настоящей диссертации состоит в получении количественных оценок для двумерной теоремы Семереди Говоря кратко, она состоит в следующем насколько большую мощность может иметь подмножество двумерной решетки без конфигураций вида (ж,у), (х + d,y), (а:,у + d), где d > О7 Такие тройки называются уголоками или равнобедренными прямоугольными треугольниками Первый результат в этом направлении был доказан М Атаи и Е Семереди13 в 1974 году с помощью комбинаторных

sSzemer6d\E On sets of integers containing no four elements m arithmetic progression // Acta Anth Acad Sci Hungar , v 20, 1969, 89-104 , Szemeridt E On sets of integers containing no k elements m arithmetic progression // Acta Anth, 27, 1975, 299-345

'SztmeridxE Regular partitions of graphs // Colloques International* CNRS, 260 — Problems Combinatories et Thfone des Graphes, Orsay, 1976, 399-401 , Kohayakawa Y Szemeridi's regularity lemma for sparse graphs // Foundations of Computational Mathematics, Selected papers, IMPA conference, January 1997, Rio de Janeiro, Springer, 1997 , Kolmis J, SmonovitsM Paul Erdos is 80 (под редакцией D Mikl6s, V T S6s, T Szonyi) / v 2, Proc Colloq Math Soc Jinos Bolyai, 1996

10 Furstenberg H Ergodic behavior of diagonal measures and a theorem of Szemertidi on arithmetic progressions // J d'Analyse Math , v 31, 204-256, 1977

n Furstenberg В, Katznelson Y, An ergodic Szemeridi theorem for commuting transformations 11 J d'Analyse Math , V 34,275-291,1978 Furstenberg H, Katznelson Y and OmstanD The Ergodic Theoretical Proof of SzemeriSdi's Theorem // Bull Amer Math Soc , v 7, N 3, 527-552,1982

12 Furstenberg H Ergodic behavior of diagonal measures and a theorem of Szemeridi on arithmetic progressions // J d'Analyse Math , v 31, 204-256, 1977 , FurstenbergH Recurrence m ergodic theory and combinatorial number theory / Princeton (N J ), 1981 , FurstenbergH, Katznelson Y, An ergodic Szemerddi theorem for commuting transformations // J d'Analyse Math , v 34, 275-291,1978 , Furstenberg H, Katznelson Y and OrnstemD The Ergodic Theoretical Proof of Szemerfdi's Theorem // Bull Amer Math Soc , v 7, N3,527-552,1982, Bergelson V, Letbman A Polynomial extentions of van der Waerden's and Szemergdi's theorems // J Amer Math Soc, v 9, N 3,1996,725-753, Bergelson V, Leibman A Set-polynomials and polynomial extension of the Hales-Jewett theorem // Ann of Math (2), v 150, N 1, 1999, 33-75, FurstenbergH, Katznelson Y A density version of the Hales-Jewett theorem // J Analyse Math , 57, 1991, 64-119, LetbmanA Multiple recurrence theorem for measure preserving actions of a mlpotent group // Geom func anal, v 8, 1998, 853-931

13AjtaiM, SzemeridtE Sets of lattice points that form no squares // Stud Sci Math Hungar , 9, 1974,

методов Они показали, что любое подмножество двумерной решетки положительной плотности обязательно содержит уголок В 1978 году результат о равнобедренных прямоугольных треугольниках был передоказан Г Фюр-стенбергом и Я Кацнельсоном14 с помощью методов эргодической теории Доказательство M Атаи и Е Семереди дает очень слабые верхние оценки на плотность множества двумерной решетки без уголков Доказательство Фюр-стенберга и Каднельсона является неэффективными в том смысле, что оно вообще не дает никаких верхних оценок на указанную плотность В своей филдсовской работе15 В Т Гауэрс использовал оригинальные модификации классических методов теории чисел, таких как круговой метод и метод тригонометрических сумм, и получил принципиально новые количественные оценки в задачах типа теоремы Е Семереди В той же работе16 В Т Гауэрс еще раз привлек внимание к вопросу о получении эффективных оценок в задаче об уголках В диссертационной работе удалось создать оригинальные и принципиально новые теоретико-числовые конструкции, позволяющие, в отличие от эргодического и комбинаторного подходов, получать хорошие количественные оценки в рассматриваемых многомерных задачах.

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

Научная новизна работы.

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

9-11

14FurstenbergH, Katznelson Y, An ergodic Szemerédi theorem for commuting transformations // J d'Analyse Math , v 34, 275-291, 1978

15 Gowers W T A new proof of Szemerédi's theorem // Geom func anal, v 11, 2001, 465-588 и Gowers W T A new proof of Szemerédi's theorem for arithmetic progressions of length four // Geom func anal, v 8, 1998, 529-551

le Gowers W T A new proof of Szemerédi's theorem // Geom func anal, v 11, 2001, 465-588

"Ajtai M, Szemerédi E Sets of lattice points that form no squares / / Stud Sei Math Hungar , 9,1974,9-11,

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

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

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

2 Доказана структурная теорема и плотных подмножествах двумерной решетки

3 Получен критерий a-равномерности множества А в терминах матрицы смежности графа Ga, ассоциированного с Л, а также в терминах плотности А в декартовых произведениях больших подграфов графа

Ga

4 Любое множество А С {1,2, ,JV}2 мощности 7V2/(log log TV)с, где С > 0 — некоторая эффективная константа, содержит уголок

5 Получены примеры динамических систем с медленной скоростью кратного возвращения

6 Доказаны теоремы об оценке сверху для скорости многомерной возвра-щаемости

7 Построены примеры динамических систем с заданной скоростью однократного возвращения

FurstenbergH, Katznehon У, An ergodic Szemerédi theorem for commuting transformations // J d'Analyse Math , v 34, 275-291, 1978

18 Gowers W T A new proof of Szemerédi's theorem // Geom func ana! , v 11, 2001, 465-588

8 Найдена нетривиальная оценка снизу для числа решений уравнения гх+ + гь = г[ + + г'к, где все г„ г[ принадлежат множеству больших тригонометрических сумм, а также системы линейных уравнений с переменными из множества больших тригонометрических сумм

9 Получен результат, существенно улучшающий теорему Чанг о строении множества больших тригонометрических сумм

Методы доказательства утверждений, сформулированных в пунктах 1 и 4 совершенно различные Первый подход опирается на структурные результаты о плотных подмножествах двумерной решетки (пункт 2), а второй использует свойства множеств Бора Оба метода дают существенное продвижение в известной и трудной задаче о уголках Хотя в контексте данной задачи второй метод сильнее, тем не менее, он принципиально не позволяет получать, интересные сами по себе, утверждения о структуре плотных подмножеств {1,2, ., Щ2 Кроме того, второй метод использует некоторые результаты, доказанные с применением первого, более слабого, подхода

Необходимо отметить, что результаты, сформулированные в пунктах 14, а также в пунктах 8 и 9 касаются вопросов традиционно относящихся к эргодической, комбинаторной теории чисел и, так называемым, обратным задачам аддитивной теории чисел Часть результатов, например, пункт 6, являются естественной переформулировкой основных числовых теорем на языке теории динамических систем

Методы исследования.

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

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

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

Апробация работы.

Результаты настоящей диссертации неоднократно докладывались автором на многочисленных международных конференциях и семинарах Перечислим сперва конференции международная конференция "Современная теория динамических систем и ее приложения к небесной механике" (г Москва, 2002 г), пятая международная конференция "Алгебра и теория чисел современные проблемы и приложения" (г Тула, 2003 г), международная конференция "XXIII Арифметические дни" в Граце (Австрия, 2003 г), международная конференция "Диофантовый анализ, равномерное распределение и их приложения" в Минске (Беларусь, 2003 г), международная конференция "Новейшие достижения в аддитивной комбинаторике" в Пало Альто (США,

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

2005 г), международная конференция "Геометрические методы в физике" в Беловеже (Польша, 2005 г.), международная конференция "Аддитивная комбинаторика" в Бристоле (Англия, 2005 г), международная конференция "Вероятность и эргодическая теория" (США, 2006 г), международная школа и конференция "Аддитивная комбинаторика" в Монреале (Канада, 2006 г), "Аналитические и комбинаторные методы в теории чисел и геометрии" (г Москва, 2006 г), "Диофантовы и аналитические проблемы теории чисел" (г Москва, 2007 г), Ломоносовские чтения в Московском государственном университете в 2002, 2004, 2006 гг

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

Публикации.

Результаты диссертации опубликованы в 10 работах, список которых приводится в конце автореферата

Структура и объем работы.

Диссертация изложена на 173 страницах и состоит из введения, общей характеристики работы, списка использованных обозначений и сокращений, пяти глав и списка использованных источников, включающего 126 наименований

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

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

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

Содержание главы 2.

Основным результатом настоящей главы является теорема о двумерном обобщении теоремы Е Семереди (см теорему 8 ниже) Мы начнем с обзора предшествующих результатов

Пусть N — натуральное число Положим

ак(ГГ) = ^так{\А\ ЛС[1,ЛГ],

А — не содержит арифметических прогрессий длины , Используя круговой метод, К Ф Рот в 1953 году доказал теорему20

Теорема 1 (Рот). Пусть N — натуральное число, N > 3 Тогда

1

a3(N) <

log log N

Результат К Ф Рота был затем улучшен Д Р Хиф-Брауном в работе21 и Е Семереди в статье22 Независимо друг от друга оба этих автора получили следующую оценку для аз (ТУ)

Теорема 2 (Хиф-Браун, Семереди). Пусть N — натуральное число, N > 3 Тогда

<<

где константу с можно взять равной 1/20

Наилучший, на сегодняшний день, результат об оценке сверху величины аз(Аг) принадлежит Ж Бургену23

Теорема 3. (Бурген) Пусть N — натуральное число, N > 3 Тогда

20Roth K F On certain sets of integers (I) // J London Math Soc , 28, 1953, 245-252

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

21 Szerneréit E On sets of integers containing no arithmetic progressions // Acta Math Hungar , v 56,1990, 155-158

23Bonn/am J On triples in arithmetic progression // GAFA, 9, 1999, 968-984

А Беренд в работе24 получил нижнюю оценку величины аз (А'') (см также работы25) Р Ранкин в статье26 обобщил результат А Беренда на случай всех к>3

Теорема 4 (А Беренд, Р. Ранкин) Пусть е > 0 — любое действительное число и к > 3 — натуральное Тогда для всех достаточно больших выполнено

ак(М) > ехр(—(1 + е)С*(1ое М)1^),

где Ск некоторая положительная эффективная константа, зависящая только от к

Теоремы К Ф Рота, Е Семереди, Д Р Хиф-Брауна и Ж Бургена относятся к оценке величины аз(/У) Долгое время вопрос о поведении функций а (.(Л'') при к > 4 оставался открытым Лишь в 1975 году Е Семереди доказал, что о^(-Л^) —» 0 при N —> +оо для всех к > 4 (см статьи27)

Альтернативное доказательство теоремы Е Семереди было предложено Г, Фюрстенбергом в работе28 (более простое доказательство изложено в статье29) Его подход использует методы эргодической теории Г Фюрстенберг показал, что теорема Е Семереди эквивалентна утверждению о кратной воз-вращаемости для почти всех точек в произвольной динамической системе

К сожалению, методы Семереди дают очень слабые верхние оценки для йк(М) Эргодический подход вообще не дает никаких оценок Только в 2001 году В Т Гауэрс30 получил первый эффективный результат о скорости стремления к нулю величины аЦЛО для к > 4

Теорема 5. (Гауэрс) Для всех натуральных N > 3 и к > 4 справедливо неравенство

ак(И) « 1/(1о§1оёЛ0с*,

MBehrtndF A On sets of integers which contain no three terms m arithmetic progression // Proc Nat Acad Sci, 23, 1946, 331-332

25emphSalem R , Spencer D C On sets of integers which contain no three terms m arithmetical progression

// Proc Nat Acad Sa Wash , 28, 1942, 561 - 563 , Salem R , Spencer D C On sets which do not contain a

given number of terms m arithmetical progression // Nieuw Arch Wisk , 23, 1950, 561 - 563 , MoserL On non-averaging sets of integers // Canad Math J , 5,1953, 245-252

28 Rankin II 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

111 Szemerédi E On sets of integers containing no four elements in arithmetic progression // Acta Anth Acad Sci Hungar , v 20, 1969, 89-104 , SzemerédiE On sets of integers containing no k elements m arithmetic progression JI Acta Anth , 27, 1975, 299-345

23 Purstenberg H Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions 11 J d'Analyse Math , v 31, 204-256,1977

™FurstenbergH, Katznelson Y and OrnstetnD The Ergodic Theoretical Proof of Szemerédi's Theorem // Bull Amer Math Soc , v 7, N 3, 527-552, 1982

30 Gowers W T A new proof of Szemerédi's theorem for arithmetic progressions of length four // Geom func anal, v 8, 1998, 529-551 , Gowers W T A new proof of Szemerédi 's theorem / / Geom func anal, v 11, 2001, 465-588

где константа с* = 2 2t+9

Рассмотрим двумерную решетку [Лг]2 с базисом С; = (1,0) и ег = (0, —1) Пусть

А — не содержит троек вида (k, го), {к + d, то), (к, m + d), d > 0} (2)

Тройку из (2) мы будем называть уголком В работе31 М Атаи и Е Семереди доказали, что величина L{N) стремится к 0, когда N стремится к бесконечности Говоря точнее, они получили даже более сильный результат

Теорема 6. (Атаи, Семереди) Пусть 0 < 5 < 1 — действительное число, N — натуральное число и S = {(0,0), (0,1), (1,0), (1,1)} — единичный квадрат Тогда любое множество А С [N]2, \А\ > 5N2 содержит аффинный образ S, то есть множество aS + Ь, где а €Е N и b € N2

Затем теорема 6 была передоказана Г Фестенбергом в книге32

Ясно, что задача про уголки является двумерным обобщением задачи о множествах без арифметических прогрессий длины три в том смысле, что равенство 1ш1лг_оо L(N) — 0 влечет hm/v_^00a3(Ar) = 0

В Т Гауэрс (см статью33) поставил вопрос о скорости сходимости L(N) к 0 В работе34 В By, развивая подход из статьи35 предложил следующее решение этого вопроса Пусть log^j = log N и для I > 2 положим log^ N = log(log[;_j] Лг) Таким образом log^ N есть результат взятия логарифма от числа N I раз подряд Далее, пусть к — наибольшее натуральное число, такое, что log^j N >2 Тогда положим log* N = к

Теорема 7. (By)

L(N)< 100

log]/4 N

В работах36 был получен следующий результат

31AjtaiM, SzemerédiE Sets of lattice points that form no squares // Stud Sci Math Hungar , 9, 1974, 9-11

35FurstenbergH Recurrence in ergodic theory and combinatorial number theory / Princeton (N J ), 1981

33 Gowers W T A new proof of Szemerédi's theorem for arithmetic progressions of length four // Geom func anal, v 8, 1998, 529-551

34 Vu V Я On a question of Gowers // Ann of Combinatorics, 6, 2002, 229-233

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

звШкредовИ Д Об одной задаче Гауэрса // ДАН, 400, N 2, 169-172, 2005 , ШкредовИ Д Об одной задаче Гауэрса // ИАН, 200, N 2, 176-217, 2006

Теорема 8. Пусть 5 > О, N » ехрехрехр(<5~с), С > 0 — некоторая эффективная константа и А С {1, , ./V}2 — произвольное подмножество, мощности не меньше, чем 8И2. Тогда А содержит тройку вида (к,тп), (к + (1, тп), (к, тп + Л), где в, > О

Таким образом получена оценка величины ¿(/о сверху Ь{АО < 1/(1о51о§ЛГ)с\ где Сг = 1 /С

Кроме того, в этом же параграфе мы получим простейшую оценку снизу для величины Ь(М)

Теорема 9. Для любого е > 0 существует 6 М, такое что для всех натуральных N > Л^, выполнено ДЛГ) > N

Доказательство теоремы 8 содержится в параграфах 2 2, 2 3 и 2 4

Параграф 2 2 посвящен понятию «-равномерности

Пусть N — натуральное число Обозначим через = Ъ/ИХ множество вычетов по модулю N Пусть А произвольное множество из Ъ^, |Л| = ЫЯ Будем обозначать той же буквой А характеристическую функцию этого множества Функция /(я) = А(з)—5 называется балансовой функцией множества А Обозначим через В замкнутый диск на комплексной плоскости с центром в 0 и радиусом 1

Определение 1. Функция / из Ъ^ в В называется а-равномерной, если

(з)

к з

Будем говорить, что множество А является а-равномерным, если его балансовая функция а-равномерна

Пусть 2?! х Е2 некоторое подмножество и / —> В — некоторая функция Будем писать / х —► В, если вне Е\ х Ег функция / равна О

Определение 2. Пусть а любое действительное число, а € [0,1] Пусть Е\ х 1?2 — некоторое подмножество Функция / Е\ х Е2 —*► В называется а-равномерной, относительно базиса (е^ег), если

+ + < а\Е^\Е2\2 (4)

8, и Г

Пусть множество А принадлежит некоторому множеству Е\ х Е2 Определим плотности 6т = и 7* = ■ур по формулам <5т = 1/|£п| А(те2 +

pei), 7к = ££Li А{ке1+ре2) Функцию /(s) = (^(s)-im) {Ех xE2)(s)

назовем балансовой функцией множества А

Будем говорить, что множество А С Е\ х Е2 является а-равномерным, относительно базиса (е^ег), если его балансовая функция а-равномерна, относительно этого базиса

Наше первое предложение относится к ситуации, когда множество А С Е\ х Е2 является а-равномерным, относительно базиса (ех, ег), а сами множества Е\, Е2 являются а-равномерными в смысле определения 6

Теорема 10. Пусть множество А принадлежит Е\ х Е2 и имеет мощность |Л| = 5\Е\\\Е2\ Пусть |£1| = , \Е2\ — 02Ы и множества Ех,Е2 являются 10~33°/92/1/3|4£132 равномерными Пусть также А является а-равномерным, относительно базиса (е^ег), а = 10~108£44, N > Ю10(<54/31/?2)-1 и 52т 16т ~ ¿|2 < а(32М Тогда А содержит уголок

В параграфе 2 3 мы рассматриваем ситуацию когда множество А С Е\ х Е2 не является а-равномерным, & Ех, Е2 произвольны В этом случаем справедливо следующее предложение

Теорема 11 Пусть множество А С Е\ х Е2, имеет мощность |Л| = £|£а||.Е?2| Пусть а > 0 действительное число и А не а-равномерно, относительно базиса (ех, ег) Тогда существуют множества С Е\ и (?г ^ Е2 для которых выполнено

Наконец, в последнем параграфе 2 4 мы доказываем структурную теорему о декартовых произведениях плотных подмножеств [ЛГ]

Мы будем говорить, что двумерная арифметическая прогрессия Р есть правильный квадрат, если Р = Р\Х Р2, где Р\, Р2 одномерные прогрессии с одинаковыми разностями и равной мощности

Теорема 12. Пусть 0 < е <5 — некоторые числа и пусть а(в) = Кзр, К € (0,1], р > 4 Пусть множество содержится в {1, ,ЛГ}2, =

SN2 и N > (СаС1)-(1/с2)1/°, где С = 21000^ а = №р ис2 = 2~128, а а = а(е)

Тогда существуют правильные квадраты Р\, ,Рм Я {1, , /V}2 и разбиение W fia множества W П Pi, , W П Рм и В, для которых выполнено 1) Для любого г множество W является a{5ptiW))-равномерным в прогрессии Pi

ИП(Сх х G2)| > (J + 2-500a70)|G'1||G2| |Gi|, |G2| > 2-5(Wa70min{|£i|, \E2\}

и

(5)

(6)

2) Для любого г выполнено \W П Р,| > е|Р,| и \Рг\ > Nc2

3) |В| < AeN2

Из этого утверждения вытекает следующая теорема

Теорема 13. Пусть W\, W2 С Ъ^ - некоторые множества, \Wi\ = ßiN, \W2\ = ß2N, С 6 (0,1) некоторое число, a(s) = Ksp, К G (0,1], р > 4 и а = a(C,ß iß2) Предположим, что множество А содержится в W\ х W2, |Л| = í|Wi||W2| и N > (СаС1)-(1/с2)1/а, где С = 21000", Cl = 100p u С2 = 2~128 Тогда существует такой правильный квадрат Р = Р\ х Р2, |Р| > N<%° и множества RbR2, Ri С (Wi П Pi), Р2 С (W2 П Р2), |i?i х Д2| > Cßiß2\P\, обладающие следущими свойствами R\, R2 являются «(¿^(iíi))1/2, q(¿p2(P2))1^2-равномерными , соответственно, в Pi и

Р2 о > 5 - 4С

В последней части параграфа 2 4 мы объединяем теоремы 10, 11, 13 и с помощью итеративной процедуры доказываем основную теорему 8

Содержание главы 3

В главе 3 мы доказываем усиление теоремы 8 (см работы37)

Теорема 14. Пусть 6 > 0, N ехрехр(5-с), с > 0 — некоторая эффективная константа и А С. {1, ,N}2 — произвольное подмножество, мощности не меньше, чем 5N2 Тогда А содержит тройку вида (к,т), (к + d,m), (к,т + d), где d > 0

Таким образом получена оценка величины L(N) сверху L(N) l/OoglogAO0', где Ci = 1/с

Доказательство теоремы 14 содержится в параграфах 3 2, 3 3, 3 4, 3 5 и

36

Параграф 3 2 посвящен свойствам множеств Бора38 Пусть N и d натуральные числа, е > 0 — действительное число и в = (0Ь ,ed)eTd

Определение 3. Множеством Бора Л = Ag¿ji называется множество = {п е Ъ I |n| < N, ||n0J < £ для з = 1,. ,d}

31 ШкредовИ Д Об одном обобщении теоремы Семереди // ДАН, 405, N 3, 315-319, 2005 , Shkredovl D On a Generalization of Szemerédi's Theorem // Proceedings London Math Soc , 93, N 3, 723-760, 2006 ssBourgamJ On triples in arithmetic progression // GAFA, 9, 1999, 968-984

Определение 4. Пусть 0 < к < 1 — некоторое число Множество Бора Л = Ле^дг называется регулярным, если для любых е\ ТУ', таких что

1 ' кш ' юосг

выполнено

В работе39 была доказана лемма

Лемма 1. Пусть 0 < к < 1 некоторое число и Ад1С^ множество Бора Тогда существует пара (еь N1) со свойствами

£ N

-<£1<е и

такая, что множество Бора Л^^ является регулярным

Определение 5. Пусть е € (0,1] некоторое число и — множество

Бора, в = (01, ,9а) Регулярное множество Бора Л' = Л^д' называется £-сопровождающим множества Л, если в' = (61, ., 0с1+1, , ва+к), к > О, ££о/2 < с' < ££о, £N(¡/2 < Ы' < £Щ Из леммы 1 вытекает существование такого множества

В параграфе 3 3 мы даем определение (а, е)-равномерных подмножеств множеств Бора, а также множеств являющихся (а,е)-равномерными, относительно прямоугольной нормы

Пусть / — функция из Ъ в С принимающая конечное число ненулевых значений Обозначим через /(х) коэффициент Фурье функции /

/(*) = £/(* )е(-8х),

«ег

где е(х) = е2тх

Определение 6. Пусть Л — множество Бора, £? С Л, |<2| = ¿|Л|, а,£ — некоторые положительные числа и Л' есть е-сопровождающее множества Л Рассмотрим множество

В = {т 6 Л | ||(б? П (Л' + т) - 6(А' + т)Г||00 > а|Л'|}

зяBoкrga^nJ Оа 1пр1ез т апНипе^с progгessюn // САГА, 9, 1999, 968-984

Множество называется (а, е)-равномерным, если

|В|<«|Л|, (7)

(8)

' ' тел

||(дпЛ-5ЛГ||оо<а|Л| (9)

Пусть Лх, Л2 — множества Бора, е > 0 некоторое число и Л' есть е-сопровождающее множества Лх Пусть также Е\, Е2 — некоторые подмножества Ль Л2, соответственно, ^ \Е\\ = Рх\Кх\, Е2 — /?2|Л2|

Определение 7 Функция / Л1 X Л2 —» В называется (а, е)-равномерной, относительно прямоугольной нормы, если

Н/ИЬл,,, = Е Е ЕЕЛ'(™- * - -к-г)х

•еЛ1;/еЛ2 А: т,и

|ЕЛ'(^ + г-^)/(г,ш)/(г,и)|2 < а/?х/?||Л'|4|Лх|2|Л2| (10)

г

Обозначим множество Л' в формуле (10) через Лх(е)

Определение 8. Пусть А С Ех х £2, |Л| = ед/?2|Л1||Л2|, 6 > 0 и /(з) = Л (б) - 3(Е1 х Е2)(в) Пусть /¡(б) = /(й! + I, в2)Л'(в1), * € Лх Рассмотрим множество

в = {г е лх | ш^д,., > а/з2/з2|л'(£)|4|л'|2|л2|}

Множество Л называется (а, ах,е)-равномерным, относительно прямоугольной нормы, если < ах|Лх|

Первое предложение параграфа 3 3 относится к ситуации, когда множество А С Е\ х Е2 является (а, «1, е)-равномерным, относительно прямоугольной нормы, а сами множества Е2 являются (а,е)-равномерными в смысле определения 6

Пусть Л некоторое множество Бора, Л = Л^^, б € Т^ и , Е2 С Л, 1^x1 = /?х|Л|, \Е21 = /32|Л| Обозначим через V декартово произведение Е\ хЕ2

Теорема 15. Пусть множество А принадлежит ЕххЕ2 и uAteem мощность \А\ = S\Ei\\E2\ Пусть множества Ei,E2 являются (ао,2~10е2)~ равномерными, а0 = 2-тооё9в$8$8, £ = (2':mQf))/(100d) Пусть также А является (а, ах, £)-равномерным, относительно прямоугольной нормы, а == 2~ш612, ах = 2-4 и

logTVj > 210dlog— (11)

El£

Тогда А содержит тройку вида {(k, т),(к + d, т), (к, т -f d)} с d ф О

Пусть А С Ei х Е2 не содержит троек вида {(к, т), (к + d,m), (к, т + d)} cd^O В параграфе 3 4 мы доказываем следующий результат

Теорема 16. Пусть множество А принадлежит V, имеет мощность |Л| - 6\Ех\\Е2\ « не содержит троек вида {(k,m),(k -f d,m),(k,m + d)} с d ф 0 Пусть множества Ех,Е2 являются (а0,2~юе2)-равномерными, а0 = 2-2m59e/3?Pf, е = (2~ma20)/(md), е' = 2~10е2 и

log N > 210dlog — еое

Тогда существует множество Бора А и такой вектор у = (ух,У2) € Z2, что для множеств Fx С Е\ П (Л + ух), F2 С Е2 П (Л + у2), выполнено

|Fx| > 2-125i12/?x|A|, \F2\ > 2-l2412p2\h\ и (12)

sfixf№) > <5 + 2~500637 (13)

При этом для А = Agg ^ выполнено в = в, ё > 2_5е'го и N > 2~5£'N

В доказательстве последнего утверждения используется теорема 15 Сформулирем основной результат параграфа 3 5

Теорема 17. Пусть А = А(в, £q, N) некоторое множество Бора, в е Td и целый вектор s = (sx,S2) Пусть е,сг,т,5 е (0,1) — вещественные числа, Ex, Е^ некоторые множества, Ех = А|Л|, г = 1,2, Е = Ex х Е2 подмножество (Л + sx) х (Л + s2), Ас Е, 6Е{А) = 5 + т и е < к/(1СШ), к = 2_100(г/9х/92)5о"3 Предположим также, что

N > (14)

и а < 2_100г/?х/?2 Тогда существует множество Бора А' = Л(0', е7, TV'), € Т-°, £> < 23°(тРх02)~5сг~3 + d,£'> (2~we)D£o, N' > (2~w£)°N и целый

вектор t = (£1, ¿2), так что для множеств Е[ = (Е\ — ПЛ', Е'2 = (Е2 ~ ¿2) П А', Е' = Е[ х Е'2 выполнено

1) |Е'| > А/?2Т|Л'|/16,

2) Е[,Е2 являются (сг,е) — равномерными подмножествами А',

3) ¿Е'И-^ >5 + Г/16

В последнем параграфе главы 3 мы объединяем теоремы 16, 17 и с помощью итеративной процедуры доказываем основную теорему 14

Содержание главы 4.

Пусть X — некоторое множество с сигма-алгеброй его подмножеств В Пусть также Т — измеримое, сохраняющее меру /х отображение X в себя Всюду ниже будем считать, что ц(Х) = 1 Четверка (X, В, ц, Т) называется динамической системой с инвариантной мерой Хорошо известная теорема А Пуанкаре о возвращении40 утверждает, что для всякого измеримого множества Е С X, цЕ > 0 существует натуральное п > 0 такое, что ц(Е П Т~пЕ) > О

Предположим, дополнительно, что X — метрическое пространство с метрикой , ), а В — борелевская сигма-алгебра В этом случае теорема Пуанкаре может быть переформулирована следующим образом

Теорема 18. Пусть X — метрическое пространство с метрикой с1(, ) и ц — борелевская мера на X Пусть Т — отображение X в себя, сохраняющее меру [I Тогда для почти всех точек х € X выполнено

ЬтигГ ¿(Т^х^х) = 0 (15)

п—+О0

Как мы отмечали выше Г Фюрстенберг41 (см также42) обобщил теорему Пуанкаре на случай нескольких степеней отображения Т

Теорема 19. Пусть X — пространство с сигма-алгеброй измеримых множеств Виц— мера на X Пусть Т — отображение X в себя, сохраняющее меру д, и к > 3 Тогда для любого измеримого множества Е с цЕ > О существует натуральное п > 0 такое, что

ц(Е П Т-пЕ П Т~2пЕ П П Т'^-^Е) > О

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

41 PurstenbergЯ Ergodic behavior of diagonal measures and a theorem of Szemeridi on arithmetic progressions // J d'Analyse Math , v 31, 204-256, 1977

"•PurstenbergЯ Recurrence m ergodic theory and combinatorial number theory / Princeton (N J ), 1981 , FurstenbergH, Katznelson Y and OrnstemD The Ergodic Theoretical Proof of Szemeridi's Theorem // Bull Amer Math Soc , v 7, N 3, 527-552, 1982

Если X — метрическое пространство, то теорема 19 может быть переформулирована следующим образом.

Теорема 20. Пусть X — метрическое пространство с метрикой d(, •) и ¡л — борелевская мера на X Пусть Т — сохраняющее меру ц отображение X в себя и к > 3 Тогда для почти всех х € X

lim mf max^T"*, х), d(T2nx, х), , d(T(fc-1)nx, х)} = О

В работе43 Г Фюрстенберг и Я Кацнельсон перенесли теорему 19 на случай нескольких коммутирующих отображений Мы сформулируем их теорему в случае, когда X является метрическим пространством

Теорема 21. Пусть X — метрическое пространство с метрикой d( , ) и fi — борелевская мера на X Пусть к > 2 и Ti,T2, — сохраняющие

меру ¡л коммутирующие отображения X в себя Тогда для почти всех х € X выполнено

hm mf таx{d(1fx, г), d(T£x, х), , d(Tgx, х)} = О

Эквивалентность теоремы Е Семереди теоремам 19 или 20 былы доказана Г Фюрстенбергом44, что указывает на тесную связь между эргодической теорией и комбинаторными задачами об арифметических прогрессиях

Глава 4 посвящена количественным аспектам возвращаемости В ней мы получим верхние и нижние оценки скорости кратного возвращения для метрических пространств с конечной хаусдорфовой мерой В работе45 M Бошер-ницан доказал, что если в динамической системе (X, В, ¡л, Т, d) пространство X обладает конечной хаусдорфовой мерой, то теорема Пуанкаре 18 может быть значительно усилена (ниже мы сформулируем теорему Бошерницана более строго) После этого результата возникает естественный вопрос о получении аналогичных усиленных вариантов теорем 20 и 21 для пространств с конечной хаусдорфовой мерой В параграфе 4 2 мы получим такие варианты для теоремы 20 и частично теоремы 21 (случай к — 2) Наши результаты дают верхние оценки скорости кратного возвращения Б параграфе 4 3 мы

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

"Purstenbergli Recurrence in ergodic theory and combinatoria) number theory / Princeton (N J ), 1981

ibBosherntízan M Quantitative recurrence results // Inventiones mathematicae, 113, Fase 3,1993, 617-631

получим нижние оценки для скорости кратного возвращения В своем доказательстве мы применяем оценки А Беренда и Р Ранкина для величины a/c(N) (см теорему 4 выше)

Прежде чем сформулировать теорему Бошерницана и наш основной результат мы дадим несколько определений

Рассмотрим меру Hh( ) на X, определенную следующим образом

Hh{E) = limHi{E), (16)

ó—»0

где h(t) — неотрицательная (h(0) = 0) непрерывная возрастающая функция, а Яд(£) = mf{]T h(ój)}, где inf берется по не более чем счетным покрытиям Е открытыми множествами {В3}, diam{Bj) = 5j < 5

Если h(t) = ta, то получаем обычную меру Хаусдорфа, которую обозначим через На()

Внешняя мера Нн{) является сигма-аддитивной на сигма-алгебре множеств, измеримых по Каратеодори Хорошо известно46, что эта сигма-алгебра содержит все борелевские множества

Будем говорить, что меры ц н Hh согласованы, если любое /i-измеримое множество является ^-измеримым (в смысле измеримости по Каратеодори)

Определение 9. Пусть х € X Число

С(х) = Сн(х) •= lim irif{гг h(d(Tnx,x))}

n—* оо

называется константой возвращения точки х

В статье47 М Бошерницан получил первый количественный аналог теоремы 18 Похожий результат независимо доказал Н Г Мощевитин в работе48

Теорема 22 Пусть X — метрическое пространство, имеющее Hh{X) < оо, а Т — отображение X в себя, сохраняющее меру ¡л Пусть также меры ¡х и Hh согласованы Тогда для почти всех, относительно меры (i, точек х из X выполнено С(х) < оо

В работе49 М Бошерницан получил ряд приложений теоремы 22 к различным динамическим системам О приложении теоремы Бошерницана к теории цепных дробей см статью50

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

47Boshernitzan М Quantitative recurrence results // Inventiones mathematicae, 113, Fase 3,1993, 617-631

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

49Boshermtzan М Quantitative recurrence results // Inventiones mathematicae, 113, Fase 3,1993, 617-631

50ШкредовИ Д Повторяемость неполных частных у цепных дробей // УМН, т 57, N 4, 2002, с 189190

В статье51 был доказан результат, несколько усиливающий теорему 22

Теорема 23. Пусть X — метрическое пространство, имеющее Hh(X) < оо, а Т — отображение X в себя, сохраняющее меру ц Предположим, что меры ц и Нн согласованы Тогда С(х) интегрируемая (по мере ц) функция и для любого fJ,-измеримого А выполнено

J C(x)d/i < Hh(A) (17)

Если же Hh(A) = 0, то JAC(x)dfj. = 0 без условия согласованности мер ц uHh

Кроме того, в той же работе был получен результат о скорости возвращения для вполне ограниченных метрических пространств

Определение 10. Пусть G — вполне ограниченное подмножество в X е - энтропией множества G (следуя А Н Колмогорову52) называется величина He(G,X) = log2N£(G,X) , где N£(G,X) - наименьшее количество точек которое может быть ве - сети этого множества

Обозначим через NE(X) число NC(X, X)

Определение 11. Возьмем произвольное натуральное N и пусть х е X Число

CN (х) = min{ d(T"x, х) | 1 < п < N } назовем N - константой возвращаемости для точки х

Теорема 24 Пусть X — вполне ограниченное метрическое пространство с метрикой d(,-), функцией N(z) = NZ(X), diam(vt) = 1 и Т — отображение X в себя, сохраняющее меру /л

Пусть А С X — любое измеримое множество и д(х) действительная неубывающая функция, ограниченная на [0,1], такая что для любого t € (0,1] существует интеграл Стилтьеса NA.(z)dg(z), где N_a(z) — mm(fx(A),Nz(A,X)JN) Тогда выполнено следующее неравенство 1

j^g{CN{x))dii < inf{ g(t)n(A)+J NA{z)dg{z) }

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

мКолмогоров А Н О некоторых асимптотических характеристиках вполне ограниченных метрических пространств // ДАН, том 108, 3, 1956

Вернемся к теоремам 19 и 21 В параграфе 4 2 мы доказываем некоторые их количественные варианты

Пусть S и R два коммутирующих отображения пространства X, сохраняющие меру ¡1

Определение 12. Пусть х е X Число

Ссд(х) = С%л(х) = liminf {L-1(n) max{h(d(Snx,x)),h(d(Rnx,x))}} ,

' n—*oo

где L~l{n) — 1/L(n), называется константой одновременного (или кратного) возвращения точки х

Теорема 25. Пусть X — метрическое пространство, имеющее Hh{X) < оо , а S,R - коммутирующие отображения X в себя, сохраняющие меру /х. Предположим, что меры ц и Н^ согласованы Тогда Csji(x) интегрируемая (по мере ¡л) функция и для любого fi-измеримого А выполнено

f CSfi(x)dfi<Hh{A) (18)

Если же Hh(A) = 0, то fA CstR(x)dfi = 0 без условия согласованности мер ц гi Ни

По аналогии с определением 11 мы дадим определение константы возвра-щаемости точки под действием двух коммутирующих операторов

Определение 13 Возьмем произвольное натуральное N и пусть Число

CsNfl(x) = min{ max{d(Snx,x),d(RJlx,x)} \l<n<N}

назовем N — константой одновременной возвращаемости для точки х

Теорема 26. Пусть X — вполне ограниченное метрическое пространство с метрикой d( , ), функцией N(z) = NZ(X), diam(X) = 1 и S, R — отображения X в себя, сохраняющие меру ц

Пусть А С X — любое [х-измеримое множество и д(х) действительная не убывающая функция, ограниченная на [0,1], такая что для любого t € (0,1] существует интеграл Стилтьеса // NA(z)dg(z),

где Na{z) = mm(ц(А), NZ(A,X)L(N)) Тогда для всех натуральных N выполнено неравенство

Jj(C%R(x))dn < inf{ д(ЫА) + £ Na(z) dg(z) }

Итак, в теоремах 22, 23, 24, 25, 26 получены верхние оценки для интегралов от функций С(х) и Cs,r(x) В параграфе 4 3 получим нижние оценки для функции кратного возвращения в случае когда на пространстве X действует несколько степеней отображения Т Так как степени отображения Т коммутируют, то мы автоматически получаем нижнюю оценку функции кратного возвращения и в ситуации когда на X действует несколько коммутирующих отображений

Сформулируем основной результат параграфа 4 3

Пусть к — фиксированное натуральное число, к > 3 Пусть для всякого натурального N задано непустое множество С Zjv, не содержащее арифметических прогрессий длины к Обозначим плотность множества в Zjy через p(N), p(N) = \A{n)\/N Тогда р(1) — 1 По теореме Е Семереди имеем p(N) —» 0, при N —> оо

Теорема 27. Пусть ф : N —> R+ — произвольная монотонно возрастающая функция, X = [0,1], р — мера Лебега на X и — построенная выше последовательность множеств Тогда существует динамическая система (X,B,p.,T,d) такая, что р и хаусдорфова мера Н\ согласованы, Н\(Х) = 0, и для почти всех, относительно меры р, точек х из X выполнено

1дтmf •(max{d(Tnx,х), d(T2nx, х), ,d{T^nx,x)}\ > 1 (19) n~>oo p{n) J

Напоминаем, что через Hi мы обозначаем хаусдорфову меру с функцией h(t) = t

Следствие 1. Пусть к — натуральное число, к >3 ие > 0 — любое действительное число Тогда найдется динамическая система (Х,В, p,T,d), X = [0,1], р — мера Лебега, р и хаусдорфова мера Н\ согласованы, Hi(X) = О и положительная эффективная константа C'k, зависящая только от к такая, что для почти всех точек х €Е X выполнено

limmf í—^-max.{d(Tnx,x),d(T2nx,x), ,d{Tllc~iynx,x)}\>1, (20)

n-oo p(n) )

где p(n) = exp(—(1 + s^logn)1/^)

Метод, развитый для доказательства основной теоремы 27, может быть приложен к изучению функции обычной (не кратной) возвращаемости С(х) В параграфе 4.4 мы доказываем следующий результат

Теорема 28. Пусть / > 1 — любое действительное число, X = [0,1] и (1 — мера Лебега на X Тогда существует динамическая система (X, В, [х, Т, ¿) такая, что /г и хаусдорфова мера Н\ согласованы, Н\ (X) = 1 и для почти всех, относительно меры Лебега, точек х из X выполнено

С^х) .= 1ш1ш£ {гг / ¿(Г":Е,®)} = 1 (21)

Содержание главы 5.

Пусть N — натуральное число Пусть / Ъ^ —» С — произвольная функция Преобразование Фурье функции / задается формулой

/>)=ЕЛ ri)e(-nr), (22)

neZN

где e(z) = e-2mx/N для коэффициентов Фурье функции / справедливо равенство Парсеваля

£|/(г)12 = лг£1ЖН2 (23)

rezw neZjv

Пусть 6,а — действительные числа, 0<а<<5<1и пусть Л — некоторое подмножество Z^ мощности 57V Рассмотрим множество lZa больших тригонометрических сумм А

па = Па{А) = {г eZN |Л(г)| > aN } (24)

Задачу о изучении структуры множеств 7Za(A) поставил В Т Гауэрс в обзоре53

В 2002 году М - Ч Чанг доказала следующий результат54

Теорема 29. Пусть 6, а — действительные числа, 0 < а < 6 < 1, А — произвольное подмножество Z^ мощности SN и множество TLa определено равенством (24) Тогда найдется множество А = {Ai, -,А|л|} С Zjv, |Л| < 2(5/а)2 log(l/5) такое, что всякий элемент г множества ~R.a представляется в виде

|л|

г = 52г,A, (mod TV), (25)

г=1

где е, 6 {-1,0,1}

53Rough structure and classification // Geom Rinct Anal, Special Volume - GAFA2000 "Visions in Mathematics", Tel Aviv, (1999) Part I, 79-117

61 ChangM-C, A polynomial bound in Freiman'a theorem//Duke Math J 113 (2002) no 3,399-419

Развивая подход из55 (см также56) Чанг приложила свой результат к доказательству теоремы Фреймана57 о множествах с маленькой суммой Другие приложения теоремы 29 получил Б Грин в статье58 Вопрос о структуре множества Ла, когда параметр а близок к 6, изучался в работах59 60 61, см также обзор62 В другой работе63 Б Грин показал, что в некотором смысле теорема М -Ч Чанг является точной

Мы видим, что результаты о строении множества Иа являются важными для комбинаторной теории чисел В §5 2 пятой главы настоящей диссерацни мы доказываем следующую теорему

Теорема 30. Пусть 6, а — действительные числа, 0 < а < 6, А — произвольное подмножество мощности 5И, к > 2 — четное и множество 71а определено равенством (24) Пусть также В С 72.а\{0} — произвольное множество Тогда величина

П(В) =|{(г1> . ,гк,г'и ,г'к) € В2к п+ +гк = т[+ ■ +г£}| (26) не меньше, чем

5а2к:\В\2к (27)

24к62к 1

Таким образом, теорема 30 показывает, что множество Ла обладает сильной аддитивной структурой

Применяя технику норм В.Т Гауэрса (см статью64), в следующем параграфе §5 3 мы получаем обобщение теоремы 30 на системы линейных уравнений

Пусть к — натуральное число, (1>0 — целое Пусть А = (ау) — матрица

55Лиzsal Generalized arithmetic progressions and sumsets // Acta Math Hungar , 65 (1994), 379-388

ъ6Вг1и Y Structure of sets with small sumset // Structure Theory of Sets Addition, Astgnsque, Soc Math France, Montrouge, 258 (1999), 77-108

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

68 Green В Arithmetic Progressions in Sumsets // Geom Funct Anal, 12 (2002) no 3, 584-597

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

t0BesserA Sets of integers with large trigonometric sums // Astinsque 258 (1999), 35-76

" Lev V F Linear Equations over Fr and Moments of Exponential Sums // Duke Mathematical Journal 107 (2001), 239-263

иKonyagmS V, Lev V F On the distribution of exponential sums // Integers Electronic Journal of Combinatorial Number Theory 0 # A01, (2000)

63 Green В Some constructions ш the inverse spectral theory of cyclic groups // Comb Prob Comp 12 (2003) no 2, 127-138

MGowers W T A new proof of Szemeridi's theorem // Geom Funct Anal 11 (2001), 465-588

(2d+1k x (d + 1)), где элементы (ai:) матрицы А определяются по формуле

1, если в двоичном разложении (j — 1) на (г — 1)-ом месте стоит 1 и 1 < j < 2dk,

—1, если в двоичном разложении (j — 1) на (г — 1)-ом месте стоит 1

и 2 dk<j < 2 d+lk, О, иначе

Напоминаем, что двоичное разложение натурального числа п определяется по правилу п = 21-1, где I > 1 и щ € {0,1}

Теорема 31. Пусть 5, а — действительные числа, 0 < а < 5, А — произвольное подмножество Zдг мощности 6N, к — натуральное число, d> 0 — целое и множество 1Za определено равенством (24) Пусть также В С Ла \ {0} — произвольное множество Рассмотрим систему уравнений

2 *+гк

= г = 1,2, ,d+1, (28)

j=i

где элементы (atJ) матрицы А = (atJ), определены формулой выше и все r-j £ В Тогда число решений системы (28) не меньше, чем

(^1В12кУ (29)

В параграфе 5 4 мы получаем несколько приложений теоремы 30 к задачам комбинаторной теории чисел Мы выводим из теоремы 30 и неравенства В Рудина65 теорему М - Ч Чанг Более того, мы доказываем результат, усиливающий теорему 29

Теорема 32. Пусть N — натуральное число, (N, 2) = 1, S, а — действительные числа, 0 < а < Ö < 1/16, А — произвольное подмножество ZN мощности 6N и множество lZa определено равенством (24) Тогда существует множество А* С Zjv,

|Л*| < тах( 2l2(6/a)2 log(l/5), 26 log2(l/¿)) (30)

такое, что для любого вычета г е TZa существует набор Л|,. ,Х*М из не более, чем 81og(l/<5) элементов А* такой, что

м

г = Е£'Л* (modiV), (31)

t=i

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

где е, 6 {—1,0,1}

Кроме того, если число N — простое, то найдется множество Л С Zдг,

|Л| < 212(ó/a)2 log(l/5) log Iog(l/í) (32)

такое, что для любого вычета г € 7Za существует набор Ai, ,\м из не более, чем 81og(l/5) элементов Л такой, что

м

Г = ]Г£Л (moáN), (33)

t=i

где ег € {-1,0,1}

В том же параграфе мы получаем приложение теоремы 30 к уже упоминавшейся теореме Фреймана

Пусть К — произвольное подмножество Zn и е € (0 1) — любое действительное число Множеством Бора B{K,¿) в Zjv называется множество

ТХ

В(К, е) = {х eZN — < £, для всех г € К} ,

где || || — означает целую часть действительного числа О свойствах множеств Бора см статью66

Теорема 33. Пусть N — натуральное число, (-N,2) = 1, 0 < S < 2~256 — действительное число и А — произвольное подмножество Z^, |А\ = SN Тогда 2А — 2А содержит множество Бора В(К,£), где \К\ < 215<5-1 log(l/5) ue=l/(28log(l/¿))

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

""BourgamJ On triples in arithmetic progression // Geom Fbnct Ana] 9 (1999), 968-984

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ.

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

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

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 Szemerödi'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, 2006

10 ШкредовИ Д О множествах больших тригонометрических сумм// Известия Академии наук, 71, N 6, 179-199, 2007

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова,

Подписано и печать /¿7 ОЦ,О ? Формат 60x90 1/16 Уел печ л /,75 Тираж /Ой экз. Заказ /6