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

Теорема ван дер Вардена з теорії Рамсея стверджує, що для будь-яких натуральних чисел $r$ і $k$ існує таке додатне ціле число $N$, що, якщо кожне з цілих чисел $\{1,2,\dots ,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	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
6	1132	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
7	>3703	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
8	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
9	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
10	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité
11	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité	>Шаблон:Unité

Вільям Гауерс довів, що числа ван дер Вардена з $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)$.

Посилання

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