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

Для доказательства полиномиальной версии также могут использоваться веера, но с соответствующими полиномиальными разностями. Например, при доказательстве наличия в произвольной раскраске одноцветной пары ${\displaystyle a,a+d^{2},\ a,d\in {\mathbb {N} }}$ промежуточным шагом является доказательство наличия чисел ${\displaystyle x_{0},x_{1},\dots ,x_{s}}$ таких, что ${\displaystyle x_{1},\dots ,x_{s}}$ имеют разные цвета и ${\displaystyle x_{1}-x_{0},\dots ,x_{s}-x_{1}}$ являются квадратами[11].

В основе доказательства теоремы Хейлса–Джеветта лежит та же индукция через веера. Для вектора ${\displaystyle {\vec {a}}\in A^{n}}$ рассматривается разбиение координат ${\displaystyle {\vec {a}}=({\vec {a_{1}}},{\vec {a_{2}}})\in A^{n_{1}}\times A^{n_{2}},\ n_{1}+n_{2}=n}$. В гиперраскраске ${\displaystyle A^{n_{1}}}$, где гиперцветом вектора ${\displaystyle {\vec {a_{1}}}\in A^{n_{1}}}$ является комбинация цветов всех точек вида ${\displaystyle ({\vec {a_{1}}},{\vec {a_{2}}}),\ {\vec {a_{2}}}\in A^{n_{2}}}$, при достаточно большом ${\displaystyle n_{1}}$ можно, по предположение индукции (с ${\displaystyle k'=k-1}$), найти комбинаторную прямую, где все элементы кроме одного будут одноцветны. Для раскраски ${\displaystyle A^{n}}$ это будет означать наличие такой "прямой" из одинаково раскрашенных подпространств размерности ${\displaystyle n_{2}}$. А при большом ${\displaystyle n_{2}}$ гарантировано наличие аналогичной прямой в каждом из этих подпространств. Получается "прямая из прямых", каждая из которых имеет одинаковое продолжение. Эта конструкция похожа на конструкцию обобщённых прогрессий из доказательство теоремы ван дер Вардена и может быть использована для построения вееров таким же образом, как там[14].

Теорема ван дер Вардена следует из теоремы Хейлса–Джеветта, поскольку преобразование из ${\displaystyle [k]^{n}}$ в ${\displaystyle [k^{n}]}$, соответствующее интерпретации координат как цифр в ${\displaystyle k}$-ричной системе счисления, отображает комбинаторные прямые в арифметически прогрессии[15]. Многомерную теорему ван дер Вардена можно вывести аналогично, зафиксировав любую нумерацию элементов ${\displaystyle K}$ и рассмотрев теорему Хейлса–Джеветта для ${\displaystyle k=|K|}$[16].

Многомерную теорему можно доказывать и напрямую, без теоремы Хейлса–Джеветта. Действительно, если она доказана для подмножества ${\displaystyle K'\subset K\subset {\mathbb {R} }^{t}}$, содержащего ${\displaystyle t}$ аффинно-независимых точек, то можно применить индукцию от ${\displaystyle K'}$ до ${\displaystyle K}$ с помощью вееров из теорем ван дер Вардена, но с разбиением на многомерные блоки. Значит, достаточно предъявить способ перехода от утверждения для ${\displaystyle {\mathbb {R} }^{t-1}}$ к утверждению для множества ${\displaystyle K\subset {\mathbb {R} }^{t}}$ из ${\displaystyle t}$ аффинно-независимых точек. В качестве примера такого ${\displaystyle K}$ можно взять уголок, то есть точки вида

${\displaystyle (a_{1},a_{2},\dots ,a_{t})}$

${\displaystyle (a_{1}+d,a_{2},\dots ,a_{t})}$

${\displaystyle (a_{1},a_{2}+d,\dots ,a_{t})}$

${\displaystyle \dots }$

${\displaystyle (a_{1},a_{2},\dots ,a_{t}+d)}$

Наличие ${\displaystyle (t-1)}$-мерного уголка в гиперплоскости ${\displaystyle {\mathbb {R} }^{t}}$ с условием ${\displaystyle a_{1}+\dots +a_{t}=N}$ (которое гарантировано при достаточно большом ${\displaystyle N}$) означает наличие в ${\displaystyle {\mathbb {R} }^{t}}$ уголка, у которого все точки, кроме центральной, одноцветны. Далее, разбивая числа на многомерные блоки и применяя к ним ту же процедуру, можно построить сколь угодно большие веера из таких уголков.

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

Для доказательства наиболее широких обобщений (с добавлением полиномиальности разностей и многомерности пространства) хорошо работают методы эргодической теории, но они не дают никаких количественных оценок для конечных формулировок[18].

Иллюстрация наличия одноцветной прогрессии когда второй и четвёртый элемент одноцветны в прогрессиях с индексами ${\displaystyle (a+3D,d)}$, ${\displaystyle (a+2D,d+D),(a+D,d+2D),(a,d+3D)}$ (одноцветный образ квадрата в ${\displaystyle c'}$ имеет разность ${\displaystyle D}$)

Эрдёш и Грэхем первыми заметили, что каноническая версия следует из теоремы Семереди[20]. Впоследствии эту идею обобщили на многомерный случай[21]. Однако сама теорема Семереди доказывается сложно, поэтому позже было найдено другое, элементарное доказательство канонической версии через многомерную версию обычной теоремы ван дер Вардена[22].

По раскраске ${\displaystyle c:{\mathbb {N} }\to {\mathbb {N} }}$ можно построить раскраску плоскости ${\displaystyle c'}$, где цвет пары ${\displaystyle (a,d)\in {\mathbb {N} }^{2}}$ связан с прогрессией ${\displaystyle a,a+d,\dots ,a+(k-1)d}$, а именно – соответствует разбиению прогрессии ${\displaystyle (c(a),c(a+d),\dots ,c(a+(k-1)d))}$ по одинаковости цветов. Например, пары, для которых соответствующие прогрессии покрашены в цвета (красный, красный, зелёный) и (синий, синий, жёлтый) будут иметь одинаковый цвет в ${\displaystyle c'}$. Важно, что количество цветов в ${\displaystyle c'}$ конечно.

Если в ${\displaystyle c}$ нет разноцветных прогрессий длины ${\displaystyle k}$, то в любой прогрессии есть хотя бы два элемента одинакового цвета. По многомерной теоремой ван дер Вардена, в раскраске ${\displaystyle c'}$ есть одноцветный гомотетичный образ ${\displaystyle [(k-1)^{2}]^{2}}$. Прогрессии, соответствующие точкам этого образа, будут пересекаться таким образом, что, комбинируя эти равенства, можно показать одноцветность элементов из разных прогрессий, причём их будет так много, что эти элементы образуют свою прогрессию длины ${\displaystyle k}$, полностью одноцветную, что и требуется по условию.