Русская Википедия:Теорема ван дер Вардена
Теорема ван дер Вардена — классический результат комбинаторной теории чисел об одноцветных арифметических прогрессиях в раскрасках натуральных чисел. Теорема является типичным утверждением теории Рамсея, а также предтечей теоремы Семереди, которая положила начало большой ветви аддитивной комбинаторики.
Шаблон:Рамка Обозначения
На протяжении статьи для обозначения множества <math>\{ 1, \dots, N \}</math> используется запись <math>[N]</math>. Такое обозначение вполне общепринято в литературе. Шаблон:Конец рамки
Формулировка
У теоремы есть две эквивалентных формулировки — конечная и бесконечная[1].
Шаблон:Рамка Бесконечная формулировка
Для любых <math>r, k \in {\mathbb N}</math> и функции <math>c : {\mathbb N} \to [r]</math> существуют <math>a, d \in {\mathbb N}</math> такие, что
- <math>c(a) = c(a+d) = \dots = c(a+(k-1)d)</math>
Функцию <math>c</math> обычно называют раскраской натуральных чисел, её значения — цветами чисел, а прогрессию <math>a, a+d, \dots, a+(k-1)d</math> одноцветной (теорема не конкретизирует, какой именно цвет имеют её элементы).
Конечная формулировка похожа на бесконечную, но рассматривает раскраску конечного множества. Она принадлежит О. ШрейеруШаблон:Sfn.
Шаблон:Рамка Конечная формулировка
Для любых <math>r, k \in {\mathbb N}</math> существует число <math>N=N(r,k)</math> такое, что для любой функции <math>c : [N] \to [r]</math> существуют <math>a, d \in {\mathbb N}</math> такие, что
- <math>c(a) = c(a+d) = \dots = c(a+(k-1)d)</math>
Числа <math>N(r,k)</math> из конечной формулировки называются числами ван дер Вардена. Для них изучаются нижние и верхние оценки.
История
Доказательство теоремы опубликовал Б. Л. ван дер Варден в 1927 году.
Шаблон:Iw в историческом очерке о теории Рамсея пишет, что утверждение теоремы в качестве гипотезы рассматривал ещё Шур при работе над своей теоремой о раскрасках чисел (в 1916 году), но от Шура до ван дер Вардена гипотеза не дошла, зато была независимо придумана Шаблон:Iw и ван дер Варден узнал гипотезу от его учеников (Баудет к тому времени уже умер). Доказательство было придумано в гамбургском университете и представлено публике в Берлине на съезде немецкого математического обществаШаблон:Sfn.
Шаблон:Начало цитаты Ван дер Варден просто не понял, насколько важный результат он доказал: он отправлял свои работы по алгебраической геометрии в самый престижный журнал, Mathematische Annalen, а это доказательство отправил в «невразумительный» журнал Nieuw Archief voor Wiskunde голландского математического общества. Шаблон:Оригинальный текст Шаблон:Конец цитаты
В свою очередь Александр Хинчин писал, что результат был получен в Гёттингене летом 1928 за несколько дней до его приезда туда и что с гипотезой столкнулся «один местный математик […] в ходе своей научной работы»Шаблон:Sfn.
Неоднозначность происхождения изначальной гипотезы подчёркивает Рональд Грэхем в своей книге о теории РамсеяШаблон:Sfn, однако все источники сходятся в том, что в постановке задачи, которую решал ван дер Варден, цветов было всего два, а усиление утверждения до произвольного числа цветов было добавлено в качестве инструмента доказательства.
Более простое[2][3][4] доказательство теоремы в 1948 году представила советский математик М. А. Лукомская[5].
Схема доказательства[6]
В этом разделе утверждение о том, что теорема верна для <math>r</math> цветов и длины прогрессии <math>k</math> обозначается как <math>\mbox{W}(r,k)</math>.
Теорема доказывается индукцией по <math>k</math>. База <math>k=2</math> очевидна[7]. При доказательстве шага индукции обычно для удобства говорят, что <math>\mbox{W}(r,k')</math> предполагается доказанным для всех <math>k' < k,\ r \in {\mathbb N}</math>, хотя формально для доказательства каждого отдельного утверждения <math>\mbox{W}(r,k)</math> достаточно конечного числа утверждений вида <math>\mbox{W}(r', k-1), r' \in {\mathbb N}</math>, но с очень большими значениями <math>r'</math>.
Чтобы гарантировать наличие одноцветной прогрессии длины <math>k</math>, нужно переходить от рассмотрения интервала, длина которого гарантирует наличие одноцветной прогрессии длины <math>k-1</math>, ко всё бо́льшим и бо́льшим интервалам, гарантирующим наличие всё более сложные структур — так называемых вееров. Для раскраски <math>c</math> назовём <math>s</math>-веером семейство <math>(\vec{P}_i)_{i=1}^{s}</math> прогрессий длины <math>k</math> таких, что:
- <math>\vec{P}_1(k) = \vec{P}_2(k) = \dots = \vec{P}_s(k)</math>, то есть последняя точка у всех прогрессий общая;
- <math>c(\vec{P}_i(1)) = c(\vec{P}_i(2)) = \dots = c(\vec{P}_i(k-1)),\ i=1,\dots,s</math>, то есть у каждой прогрессии все элементы, кроме последнего, одноцветны;
- <math>i \not = j \Rightarrow c(\vec{P}_i(1)) \not = c(\vec{P}(1))</math>, то есть основной цвет (всех элементов кроме последнего) у каждой прогрессии свой.
Веера можно применять для доказательства шага индукции благодаря двум очевидным свойствам:
- наличие в раскраске одноцветной прогрессии длины <math>k-1</math> фактически означает наличие <math>1</math>-веера;
- наличие в раскраске <math>r</math>-веера гарантирует наличие одноцветной прогрессии длины <math>k</math> (поскольку цвета всех прогрессий различны и цветов всего <math>r</math>, то один из них совпадает с цветом общего последнего элемента).
Поэтому достаточно доказать шаг индукции по параметру <math>s</math> для утверждения «любая раскраска достаточно большого интервала содержит <math>s</math>-веер или прогрессию длины <math>k</math>». Для этого следует:
- Разбить большой интервал на блоки — меньшие интервалы, но тоже достаточно большой длины (обозначим <math>M</math>). Величина <math>M</math> должна быть достаточной для того, чтобы в интервалах длины <math>M</math> (то есть в каждом блоке) был <math>(s-1)</math>-веер (такая длина существует по предположению индукции).
- Назначить «гиперцветом» блока всю совокупность цветов его элементов. Число таких гиперцветов <math>r^M</math> будет очень большим, но всё же конечным.
- Для «гиперраскраски» достаточно длинной последовательности блоков применить утверждение <math>\mbox{W}(r^M, k-1)</math>, то есть «найти» прогрессию из абсолютно одинаково раскрашенных блоков.
Этим будет гарантировано наличие нескольких одинаковых <math>s</math>-вееров, отстоящих друг от друга на одинаковое расстояние (своего рода прогрессия из вееров). Если цвет центрального элемента веера отличается от цветов его прогрессий[8], то в такой конструкции можно по диагонали выделить <math>(s+1)</math>-веер (см. картинку).
Анализ многомерных прогрессий
При диагональном переходе от прогрессии <math>s</math>-вееров к <math>(s+1)</math>-вееру теряется большое количество арифметических и цветовых связей, в которых участвуют элементы, не вошедшие в <math>(s+1)</math>-веер. Если проследить за этими элементами и их дублированием в последующих прогрессиях из <math>(s+1)</math>-вееров, <math>(s+2)</math>-вееров и т. д., то будет видно, что одноцветные прогрессии, исходящие из любого <math>s</math>-веера фактически являются диагоналями одноцветных многомерных прогрессий размерности от <math>1</math> до <math>s</math>, в зависимости от «момента» возникновения цвета в ходе индукции. Поэтому некоторые авторы излагают доказательство в терминах поиска соответствующей комбинации многомерных прогрессий[9].
Обобщения
Для теоремы ван дер Вардена изучено множество обобщений по разным аспектам формулировки утверждения. Разные типы обобщений могут комбинироваться в одном утверждении.
В данном разделе приведены только бесконечные формулировки обобщённых утверждений, хотя для большинства из них существуют конечные аналоги, построенные по тому же принципу, что и для основной теоремы.
Способы обобщения
По структурным условиям на конфигурацию
Условие о том, что числа <math>x_1, \dots, x_k</math> образуют арифметическую прогрессию, означает выполнение равенств
- <math>x_i - x_{i-1} = x_{i+1} - x_i,\ i=2,\dots,k-2</math>
Один из способов обобщения состоит в том, чтобы заменить эти условия на другие, тоже линейные.
Шаблон:Рамка Вопрос
Для каких систем линейных уравнений (в том числе отдельных уравнений) утверждение теоремы ван дер Вардена остаётся верным при замене условия того, что элементы искомой конфигурации образуют прогрессию, на то, что они удовлетворяют заданной системе? Шаблон:Конец рамки
Кроме того, элементы прогрессии представимы в виде <math>a, a+d, a+2d, \dots, a+(k-1)d</math>. Если воспринять разности <math>d, 2d, \dots, (k-1)d</math> как фиксированные функции от <math>d</math>, то это приводит к полиномиальному обобщению.
Шаблон:Рамка Полиномиальная версия
Пусть <math>p_1, \dots, p_k</math> — многочлены с целыми коэффициентами такие, что <math>p_i(0)=0,\ i \in [k]</math>. Тогда для любого <math>r \in {\mathbb N}</math> и раскраски <math>c : {\mathbb N} \to r</math> существуют <math>a, d \in {\mathbb N}</math> такие, что
- <math>c(a) = c(a + p_1(d)) = c(a + p_2(d)) = \dots = c(a + p_k(d))</math>
По размерности
При обобщении теоремы на многомерные пространства вместо прогрессий рассматриваются гомотетичные образы конечного множества точек (арифметической прогрессии соответствует гомотетичный образ дискретного гиперкуба).
Шаблон:Рамка Многомерная версия[10]
Для любых натуральных чисел <math>r, t \in {\mathbb N}</math>, множества <math>K \subset {\mathbb N}^t</math> и раскраски <math>c : {\mathbb N}^t \to \{ 1, \dots, r \}</math> существуют <math>\vec{a} \in {\mathbb N}^t, d \in {\mathbb N}</math> такие, что
- <math>c(\vec{a}) = c(\vec{a} + \vec{k} d)\ \forall\ \vec{k} \in K</math>
Более широкое, чисто комбинаторное, многомерное обобщение предлагает теорема Хейлса-Джеветта. Для удобства её можно понимать как теорему для раскрасок <math>[k]^n</math>, но операции с числами в ней совсем не используются, то есть множество <math>[k]</math> можно заменить на любое другое того же размера. Здесь изменяемым («достаточно большим») параметром выступает уже размерность пространства, поэтому теорема Хейлса-Джеветта имеет только конечную формулировку.
Шаблон:Рамка Определение
Для множества <math>A</math> комбинаторной прямой в <math>A^n</math> называется диагональ любого нетривиального подкуба, то есть множество всех векторов, где часть координат может быть фиксирована, а остальные (ненулевое количество) всегда одинаковы и пробегают все значения <math>a \in A</math>.
Теорема Хейлса-ДжеветтаШаблон:Sfn
Для любых <math>k, r \in {\mathbb N}</math> существует число <math>n_0 = n_0(r, k)</math> такое, что для любых <math>n > n_0,\ |A|=k</math> в любой раскраске <math>c : A^n \to [r]</math> существует одноцветная комбинаторная прямая. Шаблон:Конец рамки
На один цвет (плотные подмножества)
Из эмпирических соображений естественно полагать, что искомая одноцветная конфигурация чисел в большинстве случаев будет иметь наиболее популярный цвет, ведь чем больше чисел того или иного цвета, тем больше может возникнуть интересных конфигураций между ними.
Несмотря на правдоподобность, это утверждение не следует напрямую из теоремы ван дер Вардена и доказать его намного сложнее. Чтобы формализовать его, нужно заметить, что в конечной раскраске наиболее популярный цвет имеет положительную верхнюю плотность[11]. Поэтому высказанное предположение означает наличие прогрессии в любом плотном множестве. Эта теорема названа в честь Эндре Семереди, впервые её доказавшего.
Шаблон:Рамка Теорема Семереди
Для любых <math>\delta \in (0;1), k \in {\mathbb N}</math> и множества <math>A</math> такого, что <math>\lim \limits_{N \to \infty} {\frac{|A \cap [N]|}{N}} > \delta</math>, существуют <math>a, d \in {\mathbb N}</math> такие, что <math>a, a+d, \dots, a+(k-1)d \in A</math>. Шаблон:Конец рамки
По аналогии с числами ван дер Вардена, для конечной версии теоремы Семереди изучаются нижние и верхние оценки на <math>N(\delta, k)</math>, достаточное для того, чтобы множество <math>A \subset [N]</math> с условием <math>|A| > \delta N</math> всегда содержало прогрессию длины <math>k</math>. Получение таких оценок в случае <math>k \ge 4</math> значительно сложнее, чем в случае <math>k=3</math>.
На бесконечное число цветов
При счётном числе цветов, то есть раскраске <math>c : {\mathbb N} \to {\mathbb N}</math>, длинных одноцветных прогрессий может не быть[12]. Но если в качестве другого, также допустимого, полюса цветовой структурированности рассмотреть конфигурации, где цвета всех элементов различны, то теорема останется верной.
Это утверждение называется канонической версией теоремы ван дер Вардена.
Шаблон:Рамка Каноническая версия
Для любого <math>k \in {\mathbb N}</math> и раскраски <math>c : {\mathbb N} \to {\mathbb N}</math> существуют числа <math>a, d \in {\mathbb N}</math> такие, что:
- либо <math>c(a) = c(a+d) = \dots = c(a+(k-1)d)</math>
- либо <math>c(a+id) \not = c(a+jd)</math> для любых <math>0 \le i < j < k</math>
Сводная таблица с некоторыми результатами
| Арифметические условия
на искомую структуру |
Область поиска | Пространство | ||
|---|---|---|---|---|
| Одномерное | Многомерное | <math>A^n</math> для конечного <math>A</math> | ||
| Арифметические прогрессии | Конечная раскраска | Теорема ван дер Вардена | Шаблон:Sfn0 | Шаблон:Iw |
| Бесконечная раскраска | Шаблон:Sfn0 | Теорема имеет
только конечную формулировку | ||
| Плотное подмножество | Теорема Семереди
(в том числе теорема Рота) |
Теорема об уголках | Известны сильные | |
| Решения линейных уравнений
или систем уравнений |
Конечная раскраска | Шаблон:Iw | ||
| Бесконечная раскраска | Шаблон:Sfn0 | Теорема имеет
только конечную формулировку | ||
| Плотное подмножество | Известны некоторые
обобщения теоремы РотаШаблон:SfnШаблон:Sfn |
|||
| Значение полиномов
в разностях |
Конечная раскраска | Шаблон:Sfn0 | ||
| Бесконечная раскраска | Шаблон:Sfn0 | Теорема имеет
только конечную формулировку | ||
| Плотное подмножество | Шаблон:Sfn0 | |||
| Отдельными методами доказаны
и квадратичная теорема РотаШаблон:Sfn |
||||
Литература
Примечания
- ↑ Шаблон:Sfn0, с. 112—114
- ↑ R. G. Swan. Van Der Waerden's theorem on arithmetic progressions
- ↑ GILA 1: van der Waerden and all that
- ↑ A. Y. Khinchin. Three Pearls of Number Theory, Dover Publications, Mineola, NY 1998.
- ↑ М. А. Лукомская. Новое доказательство теоремы Ван-дер-Вардена об арифметической прогрессии и некоторое обобщение этой теоремы. УМН, 3:6(28) (1948), 201—204
- ↑ См. различные изложения в Шаблон:Sfn0, Шаблон:Sfn0, Шаблон:Sfn0
- ↑ Достаточно взять <math>r+1</math> чисел чтобы, по принципу Дирихле, среди них было два числа одинакового цвета.
- ↑ Иное означало бы наличие прогрессии длины <math>k</math>, и тогда доказывать нечего
- ↑ Шаблон:Sfn0, см. формулу (5) и следующий абзац, где происходит переход к рассмотрению <math>r</math>-той прогрессии <math>s</math>-веера
- ↑ В англоязычной литературе часто называется «Gallai-Witt’s theorem»
- ↑ И, более того, верхнюю плотность не менее <math>1/r</math>, где <math>r</math> — число цветов
- ↑ Например, можно покрасить каждое число в свой цвет, то есть назначить <math>c(x):=x</math>
