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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Обозначения

На протяжении статьи для обозначения множества используется запись . Такое обозначение вполне общепринято в литературе.


Формулировка

[править | править код]
Примеры раскрасок девяти чисел в два цвета. Любая из них будет содержать одноцветную прогрессию длины 3.

У теоремы есть две эквивалентных формулировки — конечная и бесконечная[1].

Бесконечная формулировка

Для любых и функции существуют такие, что

Функцию обычно называют раскраской натуральных чисел, её значения — цветами чисел, а прогрессию одноцветной (теорема не конкретизирует, какой именно цвет имеют её элементы).

Конечная формулировка похожа на бесконечную, но рассматривает раскраску конечного множества. Она принадлежит О. Шрейеру[2].

Конечная формулировка

Для любых существует число такое, что для любой функции существуют такие, что

Числа из конечной формулировки называются числами ван дер Вардена. Для них изучаются нижние и верхние оценки.

Доказательство теоремы опубликовал Б. Л. ван дер Варден в 1927 году.

Александр Сойфер[англ.] в историческом очерке о теории Рамсея пишет, что утверждение теоремы в качестве гипотезы рассматривал ещё Шур при работе над своей теоремой о раскрасках чисел (в 1916 году), но от Шура до ван дер Вардена гипотеза не дошла, зато была независимо придумана Боде[нем.] и ван дер Варден узнал гипотезу от его учеников (Баудет к тому времени уже умер). Доказательство было придумано в гамбургском университете и представлено публике в Берлине на съезде немецкого математического общества[3].

Ван дер Варден просто не понял, насколько важный результат он доказал: он отправлял свои работы по алгебраической геометрии в самый престижный журнал, Mathematische Annalen, а это доказательство отправил в «невразумительный» журнал Nieuw Archief voor Wiskunde голландского математического общества.

В свою очередь Александр Хинчин писал, что результат был получен в Гёттингене летом 1928 за несколько дней до его приезда туда и что с гипотезой столкнулся «один местный математик […] в ходе своей научной работы»[4].

Неоднозначность происхождения изначальной гипотезы подчёркивает Рональд Грэхем в своей книге о теории Рамсея[5], однако все источники сходятся в том, что в постановке задачи, которую решал ван дер Варден, цветов было всего два, а усиление утверждения до произвольного числа цветов было добавлено в качестве инструмента доказательства.

Более простое[6][7][8] доказательство теоремы в 1948 году представила советский математик М. А. Лукомская[9].

Схема доказательства[10]

[править | править код]

В этом разделе утверждение о том, что теорема верна для цветов и длины прогрессии обозначается как .

Теорема доказывается индукцией по . База очевидна[11]. При доказательстве шага индукции обычно для удобства говорят, что предполагается доказанным для всех , хотя формально для доказательства каждого отдельного утверждения достаточно конечного числа утверждений вида , но с очень большими значениями .

Пример 3-веера при , объединяющего прогрессии (11, 12, 13), (5, 9, 13) и (3, 8, 13). В каждой прогрессии цвета первых двух элементов (то есть всех кроме последнего) одинаковы.

Чтобы гарантировать наличие одноцветной прогрессии длины , нужно переходить от рассмотрения интервала, длина которого гарантирует наличие одноцветной прогрессии длины , ко всё бо́льшим и бо́льшим интервалам, гарантирующим наличие всё более сложные структур — так называемых вееров. Для раскраски назовём -веером семейство прогрессий длины таких, что:

  • , то есть последняя точка у всех прогрессий общая;
  • , то есть у каждой прогрессии все элементы, кроме последнего, одноцветны;
  • , то есть основной цвет (всех элементов кроме последнего) у каждой прогрессии свой.
Вывод существования 2-веера для из существования прогрессий длины 3 в любых достаточно больших раскрасках.
Пример конструирования вееров из прогрессий вееров меньшего порядка для , в индукционном (по ) переходе доказательства теоремы ван дер Вардена.

Веера можно применять для доказательства шага индукции благодаря двум очевидным свойствам:

  • наличие в раскраске одноцветной прогрессии длины фактически означает наличие -веера;
  • наличие в раскраске -веера гарантирует наличие одноцветной прогрессии длины (поскольку цвета всех прогрессий различны и цветов всего , то один из них совпадает с цветом общего последнего элемента).

Поэтому достаточно доказать шаг индукции по параметру для утверждения «любая раскраска достаточно большого интервала содержит -веер или прогрессию длины ». Для этого следует:

  1. Разбить большой интервал на блоки — меньшие интервалы, но тоже достаточно большой длины (обозначим ). Величина должна быть достаточной для того, чтобы в интервалах длины (то есть в каждом блоке) был -веер (такая длина существует по предположению индукции).
  2. Назначить «гиперцветом» блока всю совокупность цветов его элементов. Число таких гиперцветов будет очень большим, но всё же конечным.
  3. Для «гиперраскраски» достаточно длинной последовательности блоков применить утверждение , то есть «найти» прогрессию из абсолютно одинаково раскрашенных блоков.

Этим будет гарантировано наличие нескольких одинаковых -вееров, отстоящих друг от друга на одинаковое расстояние (своего рода прогрессия из вееров). Если цвет центрального элемента веера отличается от цветов его прогрессий[12], то в такой конструкции можно по диагонали выделить -веер (см. картинку).

Веера и содержащие их семейства многомерных арифметических прогрессий

Анализ многомерных прогрессий

[править | править код]

При диагональном переходе от прогрессии -вееров к -вееру теряется большое количество арифметических и цветовых связей, в которых участвуют элементы, не вошедшие в -веер. Если проследить за этими элементами и их дублированием в последующих прогрессиях из -вееров, -вееров и т. д., то будет видно, что одноцветные прогрессии, исходящие из любого -веера фактически являются диагоналями одноцветных многомерных прогрессий размерности от до , в зависимости от «момента» возникновения цвета в ходе индукции. Поэтому некоторые авторы излагают доказательство в терминах поиска соответствующей комбинации многомерных прогрессий[13].

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

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

Способы обобщения

[править | править код]

По структурным условиям на конфигурацию

[править | править код]

Условие о том, что числа образуют арифметическую прогрессию, означает выполнение равенств

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

Вопрос

Для каких систем линейных уравнений (в том числе отдельных уравнений) утверждение теоремы ван дер Вардена остаётся верным при замене условия того, что элементы искомой конфигурации образуют прогрессию, на то, что они удовлетворяют заданной системе?

Кроме того, элементы прогрессии представимы в виде . Если воспринять разности как фиксированные функции от , то это приводит к полиномиальному обобщению.

Полиномиальная версия

Пусть  — многочлены с целыми коэффициентами такие, что . Тогда для любого и раскраски существуют такие, что


По размерности

[править | править код]

При обобщении теоремы на многомерные пространства вместо прогрессий рассматриваются гомотетичные образы конечного множества точек (арифметической прогрессии соответствует гомотетичный образ дискретного гиперкуба).

Многомерная версия[16]

Для любых натуральных чисел , множества и раскраски существуют такие, что

Более широкое, чисто комбинаторное, многомерное обобщение предлагает теорема Хейлса-Джеветта. Для удобства её можно понимать как теорему для раскрасок , но операции с числами в ней совсем не используются, то есть множество можно заменить на любое другое того же размера. Здесь изменяемым («достаточно большим») параметром выступает уже размерность пространства, поэтому теорема Хейлса-Джеветта имеет только конечную формулировку.

Определение

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

Теорема Хейлса-Джеветта[17]

Для любых существует число такое, что для любых в любой раскраске существует одноцветная комбинаторная прямая.


На один цвет (плотные подмножества)

[править | править код]

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

Несмотря на правдоподобность, это утверждение не следует напрямую из теоремы ван дер Вардена и доказать его намного сложнее. Чтобы формализовать его, нужно заметить, что в конечной раскраске наиболее популярный цвет имеет положительную верхнюю плотность[21]. Поэтому высказанное предположение означает наличие прогрессии в любом плотном множестве. Эта теорема названа в честь Эндре Семереди, впервые её доказавшего.

Теорема Семереди

Для любых и множества такого, что , существуют такие, что .

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

На бесконечное число цветов

[править | править код]

При счётном числе цветов, то есть раскраске , длинных одноцветных прогрессий может не быть[23]. Но если в качестве другого, также допустимого, полюса цветовой структурированности рассмотреть конфигурации, где цвета всех элементов различны, то теорема останется верной.

Это утверждение называется канонической версией теоремы ван дер Вардена.

Каноническая версия

Для любого и раскраски существуют числа такие, что:

  • либо
  • либо для любых


Сводная таблица с некоторыми результатами

[править | править код]
Арифметические условия

на искомую структуру

Область поиска Пространство
Одномерное Многомерное для конечного
Арифметические прогрессии Конечная раскраска Теорема ван дер Вардена Witt, 1952 Теорема Хейлса–Джеветта[англ.]
Бесконечная раскраска Prömel, Rödl, 1986 Теорема имеет

только конечную формулировку

Плотное подмножество Теорема Семереди

(в том числе теорема Рота)

Теорема об уголках Известны сильные

обобщения теоремы Рота

Решения линейных уравнений

или систем уравнений

Конечная раскраска Теорема Радо[англ.]

Теорема Шура

Бесконечная раскраска Lefmann, 1986 Теорема имеет

только конечную формулировку

Плотное подмножество Известны некоторые

обобщения теоремы Рота[27][28]

Значение полиномов

в разностях

Конечная раскраска Walters, 2000
Бесконечная раскраска Girão, 2020

Fox, Wigderson, Zhao, 2020

Теорема имеет

только конечную формулировку

Плотное подмножество Bergelson, Leibman, 1996
Отдельными методами доказаны

теорема Фюрстенберга — Шаркози[англ.][29]

и квадратичная теорема Рота[30]

Литература

[править | править код]
  • A. Soifer. Ramsey Theory: Yesterday, Today, and Tomorrow (англ.). — Boston: Birkhäuser, 2011. — 189 p. — ISBN 978-0-8176-8091-6.
  • А. Я. Хинчин. Три жемчужины теории чисел. — Москва: "Наука", 1979. — 66 с.
  • Р. Грэхем. Начала теории Рамсея. — Москва: "Мир", 1984. — 97 с.
  • R. L. Graham, B. L. Rothschild, J. H. Spencer. Ramsey Theory (англ.). — 2-е изд.. — A wiley-interscience publication, 1990. — 196 p. — ISBN 0-471-50046-1.
  • A. Girão. A Canonical Polynomial Van der Waerden's Theorem (англ.). — 2020. — arXiv:2004.07766.
  • J. Fox, Y. Wigderson, Y. Zhao. A short proof of the canonical polynomial van der Waerden theorem (англ.). — 2020. — arXiv:2005.04135.
  • S. Peluse, S. Prendiville. A polylogarithmic bound in the nonlinear Roth theorem (англ.). — 2020. — arXiv:2003.04122.


Примечания

[править | править код]
  1. Шкредов, 2006, с. 112—114
  2. Грэхем, 1984, с. 18.
  3. Soifer, 2011, с. 2,7.
  4. Хинчин, 1979, с. 7—8.
  5. Грэхем, 1984, с. 17.
  6. R. G. Swan. Van Der Waerden's theorem on arithmetic progressions. Дата обращения: 8 августа 2023. Архивировано 13 мая 2023 года.
  7. GILA 1: van der Waerden and all that. Дата обращения: 8 августа 2023. Архивировано 8 августа 2023 года.
  8. A. Y. Khinchin. Three Pearls of Number Theory, Dover Publications, Mineola, NY 1998.
  9. М. А. Лукомская. Новое доказательство теоремы Ван-дер-Вардена об арифметической прогрессии и некоторое обобщение этой теоремы. УМН, 3:6(28) (1948), 201—204. Дата обращения: 8 августа 2023. Архивировано 8 августа 2023 года.
  10. См. различные изложения в Хинчин, 1979, с. 9—13, Грэхем, 1984, с. 18—21, Шкредов, 2006, с. 118—119
  11. Достаточно взять чисел чтобы, по принципу Дирихле, среди них было два числа одинакового цвета.
  12. Иное означало бы наличие прогрессии длины , и тогда доказывать нечего
  13. Хинчин, 1979, с. 9—13, см. формулу (5) и следующий абзац, где происходит переход к рассмотрению -той прогрессии -веера
  14. С развитием изучения теоремы Семереди, для доказательства её полиномиальных обобщений активно применялись эффективные для этого методы эргодической теории (см. Bergelson, Leibman, 1996). Элементарное доказательство полиномиального обобщения без комбинации с обобщением по типу теоремы Семереди было опубликовано позже.
  15. Walters, 2000, см. "Induction hypotesis" на с. 3
  16. В англоязычной литературе часто называется «Gallai-Witt’s theorem»
  17. Грэхем, 1984, с. 24.
  18. Грэхем, 1984, с. 24—25.
  19. Грэхем, 1984, с. 26.
  20. Graham, Rothschild, Spencer, 1990, с. 40—41.
  21. И, более того, верхнюю плотность не менее , где  — число цветов
  22. Bergelson, Leibman, 1996.
  23. Например, можно покрасить каждое число в свой цвет, то есть назначить
  24. Erdős, Graham, 1980, с. 333, см. "The existence of is guaranted by Szemerédi's theorem."
  25. Deuber, Graham, Prömel, Voigt, 1983.
  26. Prömel, Rödl, 1986.
  27. Schoen, Shkredov, 2014.
  28. Schoen, Sisask, 2016.
  29. Lyall, 2011.
  30. Peluse, Prendiville, 2020.