Число ван дер Вардена (Cnvlk fgu ;yj Fgj;yug)

Числом ван дер Вардена $W(r,\;k)$ называется наименьшее $N$ такое, что в любой раскраске множества $\{1,\;2,\;\ldots ,\;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	>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$ ограничиваются сверху^[1]

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

Элвин Берлекэмп доказал, что для простого числа $p$ , 2-цветное число ван дер Вардена количество ограничено снизу^[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)$ .

Примечания

↑ Gowers, Timothy^[англ.]. A new proof of Szemerédi's theorem (англ.) // Geometric and Functional Analysis : journal. — 2001. — Vol. 11, no. 3. — P. 465—588. — doi:10.1007/s00039-001-0332-9. Архивировано 26 сентября 2020 года.
↑ Berlekamp, E. A construction for partitions which avoid long arithmetic progressions (англ.) // Canadian Mathematical Bulletin : journal. — 1968. — Vol. 11. — P. 409—414. — doi:10.4153/CMB-1968-047-7.

Ссылки

[1] Gowers, Timothy^[англ.]. A new proof of Szemerédi's theorem (англ.) // Geometric and Functional Analysis : journal. — 2001. — Vol. 11, no. 3. — P. 465—588. — doi:10.1007/s00039-001-0332-9. Архивировано 26 сентября 2020 года.

[2] Berlekamp, E. A construction for partitions which avoid long arithmetic progressions (англ.) // Canadian Mathematical Bulletin : journal. — 1968. — Vol. 11. — P. 409—414. — doi:10.4153/CMB-1968-047-7.

[1]

[2]