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

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 15:17, 30 квітня 2020, створена BunykBot (обговорення | внесок) (автоматична заміна {{Не перекладено}} вікі-посиланнями на перекладені статті)
Перейти до навігації Перейти до пошуку

Теорема ван дер Вардена з теорії Рамсея стверджує, що для будь-яких натуральних чисел і існує таке додатне ціле число , що, якщо кожне з цілих чисел пофарбувати в один із різних кольорів, то знайдеться принаймні цілих чисел одного кольору, що утворюють арифметичну прогресію. Найменше таке називається числом ван дер Вардена . Названі на честь голландського математика ван дер Вардена.

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

Є два випадки, в яких число ван дер Вардена легко обчислити:

  1. коли число кольорів дорівнює 1, очевидно для будь-якого цілого , оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити ).
  2. якщо довжина необхідної арифметичної прогресії дорівнює 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, № 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.

Посилання