Теорема Семереди и динамические системы [1] Владимир Успенский

Теорема Семереди ( ранее известная как гипотеза Эрдёша — Турана ) об арифметических прогрессиях была доказана в 1969 году крупнейшим специалистом по комбинаторике, замечательным венгерским математиком Эндре Семереди, который в 2012 году получил за доказательство этого результата самую престижную математическую награду — премию Абеля. Если разбить натуральный ряд на конечное число частей, то в одной из этих частей содержатся сколь угодно длинные арифметические прогрессии ( теорема ван дер Вардена ).

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

1. Влияние теоремы Семереди на другие теории

Почему эта теорема — отдельный комбинаторный факт — заслужила самую престижную математическую премию? Теорема Семереди — это пример утверждения, которое повлияло сразу на несколько математических областей. Более того, из теоремы Семереди возникло и новое направление — комбинаторная эргодическая теория. Эта математическая область, смесь комбинаторики и эргодической теории, была создана Фюрстенбергом в 70-е годы вскоре после публикации теоремы Семереди. Результат Семереди также связан и с теорией графов. Один частный инструмент доказательства Семереди, так называемая лемма регулярности Семереди, является сейчас основным инструментом исследования в теории плотных графов. С теоремой Семереди связана и теория чисел, например, потрясающий результат Грина — Тао, который утверждает, что простые числа содержат прогрессии любой длины. Теорема Семереди также связана и с гармоническим анализом, и с другими науками. Аналитическое доказательство теоремы Семереди было получено в 1998 году Гауэрсом, за что ему присудили Филдсовскую премию.

2. Теорема ван дер Вардена

Прежде чем сформулировать теорему Семереди, мы начнем с некоторого более простого вопроса, а именно с теоремы, доказанной ван дер Варденом в 1927 году. Предположим, что у нас имеется ряд натуральных чисел, который раскрашен в два цвета: черный и белый. Таким образом, каждому числу приписан либо белый, либо черный цвет. В натуральных числах есть арифметические прогрессии — последовательности чисел, которые находятся на одинаковом расстоянии (например, 5-10-15, 1-2-3-4-5). Ясно, что мы можем найти бесконечно много таких прогрессий. Усложним вопрос: верно ли, что если натуральные числа раскрашены в два цвета, то всегда можно утверждать, что можно обнаружить прогрессию, состоящую сплошь из чисел одного цвета, то есть либо белую, либо черную? Еще раз: верно ли, что, как бы мы ни раскрашивали натуральные числа в два цвета, всегда можно найти некоторые числа, находящиеся на одинаковом расстоянии, причем имеющие один и тот же цвет? Положительный ответ на этот вопрос и составляет предмет теоремы ван дер Вардена. Более того, оказывается, что как бы мы ни раскрашивали натуральные числа — в 2, или в 10, или 100 цветов, — все равно можно найти прогрессию произвольной длины, состоящую из элементов одного цвета.

3. Гипотеза Эрдеша — Турана

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

Можно переформулировать эту задачу и так: предположим, у нас есть бесконечное множество натуральных чисел. Определим плотность этого множества. Для этого возьмем отрезок натурального ряда от 1 до N, посчитаем, сколько в этот отрезок попало точек из множества, поделим результат на N и возьмем верхний предел. В этих терминах гипотеза Эрдеша и Турана будет звучать так: верно ли, что если плотность множества положительная, например если множество (цвет) составляет 1% от всех натуральных чисел, то тогда можно найти одноцветную прогрессию, состоящую только из точек этого множества (цвета)?

Несмотря на то, что частный случай гипотезы Эрдеша — Турана, а именно случай прогрессий длины три, был доказан в 1953 году Клаусом Ротом (английский математик, филдсовский лауреат), ситуация с прогрессиями длины три особая, поскольку здесь можно применить известный классический подход Виноградова, связанный с тригонометрическими суммами. Но уже с прогрессий длины четыре начинаются проблемы.

4. Влияние на комбинаторную теорию чисел и смежные дисциплины

В 1969 году Эндре Семереди, используя глубокие комбинаторные рассуждения, получил доказательство гипотезы Эрдеша — Турана. Его аргументы носили чисто комбинаторный характер, без всякой аналитики, причем доказательство занимало примерно 50 страниц сложного, запутанного текста.

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

В 70-е годы в данном направлении был достигнут определенный успех, когда Хиллель Фюрстенберг доказал, что теорема Семереди эквивалентна некоторому непрерывному динамическому результату — теореме о кратной возвращаемости. Затем теорема Семереди была передоказана методами теории гиперграфов. Наконец, в 1998 году Гауэрс получил аналитическое доказательство теоремы. Тем не менее мы должны признать, что, несмотря на все эти попытки, реальная причина, почему этот факт имеет место, остается не до конца осознанной.

5. Общая идея

На самом деле все эти доказательства, которые проходят на совершенно разных языках и используют методы разных наук, по сути одинаковы. Как бы мы ни рассуждали — в терминах теории динамических систем, на языке теории графов или на аналитическом языке, — на каждом шаге теоремы Семереди (а доказательство теоремы Семереди всегда состоит из некоторой последовательности шагов) происходят схожие вещи. На каждом шаге наших рассуждений мы исследуем некоторый объект, например динамическую систему, граф или тригонометрическую сумму (это зависит от языка), на случайность. Иными словами, мы берем некий тест и, используя его, проверяем, выполнен ли он для нашего объекта или нет, похоже ли наше множество, или граф, или еще что-то на случайное или же нет. Если этот тест выполнен, то есть наш объект случаен в смысле теста, то тогда (так уж устроен тест) мы находим в нем арифметическую прогрессию, да и вообще в состоянии ответить на все вопросы, которые нас интересуют, поскольку случайное множество/граф/система — это очень просто, оно в некотором смысле единственно, а уж с одним множеством человечество способно справиться. А если нет? Тогда мы находим более структурированный подобъект, например подграф, в котором несколько больше ребер (это и означает большую структурированность), чем в исходном графе, и далее рассматриваем этот подграф уже сам по себе, снова тестируя его на случайность. Если он случаен внутри себя, то все хорошо (он случаен и, значит, содержит прогрессии), а если нет — мы еще увеличиваем плотность. И так далее. В итоге, в результате, так сказать, процесса кристаллизации мы получим что-то очень хорошее: либо плотный подграф с большим числом ребер, либо какую-то просто устроенную динамическую систему, либо множество с малыми тригонометрическими суммами. А это уже позволяет нам положительно ответить на вопрос о существовании арифметических прогрессий в произвольном множестве.

6. Главное достижение Семереди

Главное достижение Семереди, с моей точки зрения, состоит в том, что он предложил некую новую идеологию. До Семереди наука занималась либо чисто случайными объектами, как, скажем, теория вероятностей, либо структурированными объектами. Семереди сказал, что не нужно бояться и промежуточных ситуаций: если у нас нет случайности, то это неплохо, это значит, что имеется структура, но небольшая. Если же у нас нет структуры, то это тоже хорошо, потому что тогда у нас есть случайность и старые вероятностные методы будут работать. Получается, что в любом случае мы что-то да выигрываем. В конечном итоге выходит так, что произвольное множество, или граф, или динамическая система обязательно обладают какой-то внутренней структурой, каким-то внутренним законом, какими-то внутренними взаимосвязями (стоит отметить также работы Клауса Рота 1953–1954 годов, где похожие мысли содержались неявно).

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

Комментарии: