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

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

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

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

1. коли число кольорів ${\displaystyle r}$ дорівнює 1, очевидно ${\displaystyle W(1,\;k)=k}$ для будь-якого цілого ${\displaystyle k}$, оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити ${\displaystyle R}$).
2. якщо довжина ${\displaystyle K}$ необхідної арифметичної прогресії дорівнює 2, то ${\displaystyle W(r,\;2)=r+1}$, оскільки можна побудувати розфарбування, уникаючи арифметичних прогресій довжини 2, використовуючи кожен колір не більше одного разу, але використання будь-якого кольору двічі створює арифметичну прогресію довжини 2. (Наприклад, для ${\displaystyle r=3}$ найдовшим розфарбуванням, за якого не утворюється арифметична прогресія довжини 2, є RGB.)

Є тільки сім інших чисел ван дер Вардена, які відомі точно.

У таблиці наведено точні значення та межі значень ${\displaystyle 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

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

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

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

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

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

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

Примітки

1. Gowers, Timothy. A new proof of Szemerédi's theorem : ( )[англ.] //  : journal. — 2001. — Vol. 11, № 3. — С. 465—588. — DOI:10.1007/s00039-001-0332-9.
2. Berlekamp, E. A construction for partitions which avoid long arithmetic progressions : ( )[англ.] // Canadian Mathematical Bulletin : journal. — 1968. — Vol. 11. — С. 409—414. — DOI:10.4153/CMB-1968-047-7.

Посилання

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