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

Перейти к навигации Перейти к поиску

Числом ван дер Вардена называется наименьшее такое, что в любой раскраске множества в цветов найдётся одноцветная арифметическая прогрессия длины . Существование этих чисел гарантирует теорема ван дер Вардена из теории Рамсея.

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

[править | править код]

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

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

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

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

В приведенной ниже таблице приведены точные значения и границы значений .

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

Уильям Гауэрс доказал, что числа ван дер Вардена с ограничиваются сверху[1]

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

Иногда также используется обозначение , которое означает наименьшее число такое, что любая раскраска целых чисел с цветами содержит прогрессию длины цвета , для некоторых . Такие числа называются недиагональными числами ван дер Вардена.

Таким образом: .

Примечания

[править | править код]
  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.