Число ван дер Вардена

Числом ван дер Вардена $W(r,k)$ называется наименьшее $N$ такое, что в любой раскраске множества $\{1,2,\dots ,N\}$ в $r$ цветов найдётся одноцветная арифметическая прогрессия длины $k$. Существование этих чисел гарантирует теорема ван дер Вардена из теории Рамсея.

Оценка чисел ван дер Вардена

Есть два случая, в которых число ван дер Вардена $W(r,k)$ легко вычислить:

Во-первых, когда число цветов $r$ равно 1, очевидно $W(1,k)=k$ для любого целого $k$, так как один цвет производит только тривиальные раскраски RRRR…RRR (для одного цвета, обозначаемого $R$).

Во-вторых, если длина $K$ требуемой арифметической прогрессии равна 2, то $W(r,2)=r+1$, так как можно построить раскраску, которая избегает арифметических прогрессий длины 2, используя каждый цвет не более одного раза, но используя любой цвет дважды, создает арифметическую прогрессию длины 2. (Например, для $r=3$ самой длинной раскраской, избегающей арифметической прогрессии длины 2, является RGB.)

Есть только семь других чисел ван дер Вардена, которые известны точно.

В приведенной ниже таблице приведены точные значения и границы значений $W(r,k)$.

k\r	2 цвета	3 цвета	4 цвета	5 цветов	6 цветов
3	9	27	76	>170	>223
4	35	293	>1048	>2254	>9778
5	178	>2173	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
6	1132	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
7	>3703	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
8	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
9	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
10	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num
11	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num	>Шаблон:Num

Уильям Гауэрс доказал, что числа ван дер Вардена с $R⩾2$ ограничиваются сверху

$W(r,k)⩽2^{2^{r^{2^{2^{k+9}}}}}.$

Элвин Берлекэмп доказал, что для простого числа $p$, 2-цветное число ван дер Вардена количество ограничено снизу

$p\cdot 2^p⩽W(2,p+1).$

Иногда также используется обозначение $w(r;k_1,k_2,\dots ,k_r)$, которое означает наименьшее число $w$ такое, что любая раскраска целых чисел $\{1,2,\dots ,w\}$ с $R$ цветами содержит прогрессию длины $k_i$ цвета $i$, для некоторых $i$. Такие числа называются недиагональными числами ван дер Вардена.

Таким образом: $W(r,k)=w(r;k,k,\dots ,k)$.

Ссылки

• Задачи типа Ван Дер Варден
• Теория Рамсея