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

Теорема ван дер Вардена з теорії Рамсея стверджує, що для будь-яких натуральних чисел $r$ і $k$ існує таке додатне ціле число $N$, що, якщо кожне з цілих чисел $\{1,\;2,\;\ldots ,\;N\}$ пофарбувати в один із $r$ різних кольорів, то знайдеться принаймні $k$ цілих чисел одного кольору, що утворюють арифметичну прогресію. Найменше таке $N$ називається числом ван дер Вардена $W(r,\;k)$. Названі на честь голландського математика ван дер Вардена.

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

Є два випадки, в яких число ван дер Вардена $W(r,\;k)$ легко обчислити:

1. коли число кольорів $r$ дорівнює 1, очевидно $W(1,\;k)=k$ для будь-якого цілого $k$, оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити $R$).
2. якщо довжина $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	>17 705	>98 740	>98 748
6	1132	>11 191	>91 331	>540 025	>816 981
7	>3703	>48 811	>420 217	>1 381 687	>7 465 909
8	>11 495	>238 400	>2 388 317	>10 743 258	>57 445 718
9	>41 265	>932 745	>10 898 729	>79 706 009	>458 062 329
10	>103 474	>4 173 724	>76 049 218	>542 694 970	>2 615 305 384
11	>193 941	>18 603 731	>30 551 357	>2 967 283 511	>3 004 668 671

Вільям Гауерс довів, що числа ван дер Вардена з $R\geqslant 2$ обмежуються зверху

$W(r,\;k)\leqslant 2^{2^{r^{2^{2^{k+9}}}}}.$

Елвін Берлекемп довів, що для простого числа $p$, 2-колірне число ван дер Вардена обмежене знизу

$p\cdot 2^{p}\leqslant W(2,\;p+1).$

Іноді також використовується позначення $w(r;\;k_{1},\;k_{2},\;\ldots ,\;k_{r})$, яке означає найменше число $w$ таке, що будь-яке розфарбування цілих чисел $\{1,\;2,\;\ldots ,\;w\}$ в $r$ кольорів містить прогресію довжини $k_{i}$ кольору $i$, для деяких $i$. Такі числа називаються недіагональними числами ван дер Вардена.

Таким чином: $W(r,\;k)=w(r;\;k,\;k,\;\ldots ,\;k)$.

Посилання

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