Теорема Ван дер Варденса - Van der Waerdens theorem - Wikipedia

Теорема Ван дер Вардена это теорема из ветви математика называется Теория Рамсея. Теорема Ван дер Вардена утверждает, что для любого данного положительного целые числа р и k, есть номер N такие, что если целые числа {1, 2, ..., N} раскрашены, каждый с одним из р разных цветов, то есть хотя бы k целые числа в арифметическая прогрессия элементы которого одного цвета. Наименее таких N это Число Ван дер Вардена W(р, k), названный в честь голландского математика Б. Л. ван дер Варден.^[1]

Пример

Например, когда р = 2, у вас есть два цвета, скажем красный и синий. W(2, 3) больше 8, потому что вы можете раскрасить целые числа из {1, ..., 8} следующим образом:

1	2	3	4	5	6	7	8
B	р	р	B	B	р	р	B

и никакие три целых числа одного цвета не образуют арифметическая прогрессия. Но вы не можете добавить девятое целое число в конец, не создав такую прогрессию. Если вы добавите красный 9, то красный 3, 6, и 9 находятся в арифметической прогрессии. В качестве альтернативы, если вы добавите синий 9, то синий 1, 5, и 9 находятся в арифметической прогрессии.

На самом деле невозможно раскрасить от 1 до 9 без создания такой прогрессии (это можно доказать на примерах). Следовательно, W(2, 3) равно 9.

Открытая проблема

Это открытая проблема - определить значения W(р, k) для большинства значений р и k. Доказательство теоремы дает только оценку сверху. В случае р = 2 и k = 3, например, приведенный ниже аргумент показывает, что достаточно раскрасить целые числа {1, ..., 325} двумя цветами, чтобы гарантировать, что будет одноцветная арифметическая прогрессия длины 3. Но на самом деле, граница 325 очень рыхлая; минимальное необходимое количество целых чисел - только 9. Любая раскраска целых чисел {1, ..., 9} будет иметь три равномерно расположенных целых числа одного цвета.

За р = 3 и k = 3, оценка теоремы равна 7 (2 · 3⁷ + 1)(2·3^{7·(2·3⁷ + 1)} + 1), или примерно 4,22 · 10¹⁴⁶¹⁶. Но на самом деле вам не нужно столько целых чисел, чтобы гарантировать одноцветную прогрессию длины 3; вам нужно всего 27. (И можно раскрасить {1, ..., 26} тремя цветами, чтобы не было одноцветной арифметической прогрессии длины 3; например:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
р	р	грамм	грамм	р	р	грамм	B	грамм	B	B	р	B	р	р	грамм	р	грамм	грамм	B	р	B	B	грамм	B	грамм

.)

Любой, кто сможет уменьшить общую верхнюю границу до любой «разумной» функции, может выиграть крупный денежный приз. Рональд Грэм предложил приз в АМЕРИКАНСКИЙ ДОЛЛАР$ 1000 за показ W(2,k)<2^k².^[2] Наилучшая известная в настоящее время верхняя граница обусловлена Тимоти Гауэрс,^[3] кто устанавливает

{ Displaystyle W (г, к) leq 2 ^ {2 ^ {г ^ {2 ^ {2 ^ {k + 9}}}}},}

установив сначала аналогичный результат для Теорема Семереди, которая является более сильной версией теоремы Ван дер Вардена. Ранее наиболее известная оценка была связана с Сахарон Шелах и продолжил через первое доказательство результата для Теорема Хейлза – Джеветта, что является еще одним усилением теоремы Ван дер Вардена.

Лучшая нижняя граница, известная в настоящее время для ${ Displaystyle W (2, к)}$ это для всех положительных ${ displaystyle varepsilon}$ у нас есть ${ Displaystyle W (2, k)> 2 ^ {k} / k ^ { varepsilon}}$ , для всех достаточно больших ${ displaystyle k}$ .^[4]

Доказательство теоремы Ван дер Вардена (в частном случае)

Следующее доказательство принадлежит Рон Грэм и Б. Ротшильд.^[5] Хинчин^[6] дает довольно простое доказательство теоремы без оценки W(р, k).

Доказательство в случае W (2, 3)

W (2, 3) стол
б	c(п): цвет целых чисел
0	1	2	3	4	5
0	р	р	B	р	B
1	6	7	8	9	10
1	B	р	р	B	р
…	…
64	321	322	323	324	325
64	р	B	р	B	р

Мы докажем упомянутый выше частный случай, что W(2, 3) ≤ 325. Пусть c(п) раскраска целых чисел {1, ..., 325}. Мы найдем три элемента {1, ..., 325} в арифметической прогрессии одного цвета.

Разделите {1, ..., 325} на 65 блоков {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, таким образом, каждый блок имеет вид {5б + 1, ..., 5б + 5} для некоторых б в {0, ..., 64}. Поскольку каждое целое число окрашено либо красный или же синий, каждый блок раскрашивается одним из 32 различных способов. Посредством принцип голубятни, среди первых 33 блоков есть два идентично окрашенных. То есть есть два целых числа б₁ и б₂, оба в {0, ..., 32}, такие что

c(5б₁ + k) = c(5б₂ + k)

для всех k в {1, ..., 5}. Среди трех целых чисел 5б₁ + 1, 5б₁ + 2, 5б₁ + 3, должно быть как минимум двое одного цвета. (The принцип голубятни снова.) Назовите эти 5б₁ + а₁ и 5б₁ + а₂, где а_я находятся в {1,2,3} и а₁ < а₂. Предположим (без ограничения общности), что эти два целых числа являются красный. (Если они оба синийпросто обменяйкрасный' и 'синий'в дальнейшем.)

Позволять а₃ = 2а₂ − а₁. Если 5б₁ + а₃ является красный, то мы нашли нашу арифметическую прогрессию: 5б₁ + а_я все красный.

В противном случае 5б₁ + а₃ является синий. С а₃ ≤ 5, 5б₁ + а₃ находится в б₁ блок, и поскольку б₂ блок окрашен одинаково, 5б₂ + а₃ это также синий.

Теперь позвольте б₃ = 2б₂ − б₁. потом б₃ ≤ 64. Рассмотрим целое число 5б₃ + а₃, которое должно быть ≤ 325. Какого цвета?

Если это красный, то 5б₁ + а₁, 5б₂ + а₂, и 5б₃ + а₃ сформировать красный арифметическая прогрессия. Но если это синий, то 5б₁ + а₃, 5б₂ + а₃, и 5б₃ + а₃ сформировать синий арифметическая прогрессия. В любом случае, мы закончили.

Доказательство в случае W (3, 3)

W (3, 3) стол
*грамм*=2·3^{7·(2·3⁷ + 1)} ,
м=7(2·3⁷ + 1)
б	c(п): цвет целых чисел
0	1	2	3	…	м
0	грамм	р	р	…	B
1	м+1	м+2	м+3	…	2м
1	B	р	грамм	…	р
…	…
грамм	gm + 1	гм + 2	гм + 3	…	(г + 1) м
грамм	B	р	B	…	грамм

Аналогичный аргумент может быть выдвинут, чтобы показать, что W(3, 3) ≤ 7(2·3⁷+1)(2·3^{7·(2·3⁷+1)}+1). Сначала делят целые числа на 2 · 3.^{7·(2·3⁷ + 1)} + 1 группа по 7 человек (2 · 3⁷ + 1) целые числа каждый; из первых 3^{7·(2·3⁷ + 1)} +1 группа, две должны быть окрашены одинаково.

Разделите каждую из этих двух групп на 2 · 3⁷+1 подгруппа по 7 целых чисел в каждой; из первых 3⁷ + 1 подгруппа в каждой группе, две из подгрупп должны быть окрашены одинаково. В каждой из этих идентичных подгрупп два из первых четырех целых чисел должны быть одного цвета, например красный; это означает либо красный прогрессия или элемент другого цвета, скажем синий, в той же подгруппе.

Поскольку у нас есть две подгруппы одинакового цвета, существует третья подгруппа, все еще в той же группе, которая содержит элемент, который, если либо красный или же синий, завершит красный или же синий прогрессии по конструкции, аналогичной конструкции для W(2, 3). Предположим, что этот элемент зеленый. Поскольку существует группа, окрашенная одинаково, она должна содержать копии красный, синий, и зеленый элементы, которые мы определили; теперь мы можем найти пару красный элементы, пара синий элементов, и пара зеленый элементы, которые «фокусируются» на одном и том же целом числе, так что независимо от его цвета, оно должно завершать последовательность.

Доказательство в общем случае

Доказательство W(2, 3) существенно зависит от доказательства того, что W(32, 2) ≤ 33. Мы делим целые числа {1, ..., 325} на 65 «блоков», каждый из которых можно раскрасить 32 различными способами, а затем показываем, что два блока из первых 33 должны быть того же цвета, а есть блок противоположного цвета. Аналогично доказательство для W(3, 3) зависит от доказательства того, что

{ displaystyle W (3 ^ {7 (2 cdot 3 ^ {7} +1)}, 2) leq 3 ^ {7 (2 cdot 3 ^ {7} +1)} + 1.}

Двойным индукция о количестве цветов и длине прогрессии теорема в общем доказана.

Доказательство

А D-мерная арифметическая прогрессия (AP) состоит из чисел вида:

{ displaystyle a + i_ {1} s_ {1} + i_ {2} s_ {2} + cdots + i_ {D} s_ {D}}

куда $а$ это базовая точка, $s$ - положительные размеры шага, а $я$ диапазон от 0 до $L-1$ . А $d$ -мерная AP однородный для некоторой окраски, когда все одного цвета.

А $D$ -мерная арифметическая прогрессия с пользой - это все числа указанной выше формы, но если вы добавляете некоторую "границу" арифметической прогрессии, то есть некоторые индексы $я$ может быть равно $L$ . Стороны, к которым вы прикрепляете, - это те, где $k$ $я$ равны $L$ , а остальные $я$ меньше чем $L$ .

Границы $D$ -размерная AP с преимуществами - это дополнительные арифметические прогрессии размерности ${ Displaystyle d-1, d-2, d-3, d-4}$ , до 0. 0-мерная арифметическая прогрессия - это единственная точка при значении индекса ${ Displaystyle (L, L, L, L, cdots, L)}$ . А $D$ -мерная AP с преимуществами есть однородный когда каждая из границ индивидуально однородна, но разные границы не обязательно должны иметь одинаковый цвет.

Затем определите количество $MinN (L, D, N)$ быть наименьшим целым числом, чтобы любое присвоение $N$ цвета в интервале длины $МинН$ или более обязательно содержит однородный $D$ -мерная арифметическая прогрессия с пользой.

Цель состоит в том, чтобы ограничить размер $МинН$ . Обратите внимание, что $MinN (L, 1, N)$ является верхней границей числа Ван дер Вардена. Есть два шага индукции, а именно:

Лемма 1. — Предполагать $МинН$ известен для данной длины $L$ для всех измерений арифметических прогрессий с преимуществами до $D$ . Эта формула дает оценку $МинН$ когда вы увеличиваете размер до $Д + 1$ :

позволять ${ Displaystyle M = { mathrm {M} inN} (L, D, n)}$ , тогда

{ Displaystyle { mathrm {M} inN} (L, D + 1, n) leq M cdot { mathrm {M} inN} (L, 1, n ^ {M})}

Доказательство —

Во-первых, если у вас есть $п$ -раскрашивание интервала 1 ... $я$ , вы можете определить раскраска блока из $k$ -размерные блоки. Просто рассмотрите каждую последовательность $k$ цвета в каждом $k$ блок для определения уникального цвета. Назовите это $k$ -блокировка ан $п$ -раскрашивание. $k$ -блокирование $п$ раскраска длины $л$ производит $п k$ раскраска длины $л / к$ .

Итак, учитывая $п$ -раскрашивание интервала $я$ размера ${ Displaystyle M cdot MinN (L, 1, n ^ {M}))}$ Вы можете $M$ -блокировать его в $п M$ раскраска длины ${ displaystyle MinN (L, 1, n ^ {M})}$ . Но это означает, что по определению $МинН$ , что вы можете найти одномерную арифметическую последовательность (с преимуществами) длины $L$ в раскраске блока, которая представляет собой последовательность блоков, расположенных через равные промежутки времени, которые все одного цвета блока, т.е. у вас есть группа блоков длины $M$ в исходной последовательности, которые расположены через равные промежутки времени, внутри которых находится точно такая же последовательность цветов.

Теперь по определению $M$ вы можете найти $d$ -мерная арифметическая последовательность с преимуществами в любом из этих блоков, и поскольку все блоки имеют одинаковую последовательность цветов, одинаковую $d$ -размерная точка доступа с преимуществами появляется во всех блоках, просто переводя ее из блока в блок. Это определение $d + 1$ размерная арифметическая прогрессия, поэтому у вас есть однородная $d + 1$ габаритная АП. Новый параметр шага $s Д + 1$ определяется как расстояние между блоками.

Но вам нужны преимущества. Границы, которые вы получаете сейчас, - это все старые границы плюс их переводы в блоки одинакового цвета, потому что $я Д + 1$ всегда меньше чем $L$ . Единственная граница, которая отличается от этой, - это 0-мерная точка, когда ${ Displaystyle i_ {1} = i_ {2} = cdots = i_ {D + 1} = L}$ . Это одна точка, и она автоматически однородна.

Лемма 2 — Предполагать $МинН$ известен одним значением $L$ и все возможные размеры $D$ . Затем вы можете связать MinN по длине $L + 1$ .

{ Displaystyle { mathrm {M} inN} (L + 1,1, n) leq 2 { mathrm {M} inN} (L, n, n)}

Доказательство —

Учитывая $п$ -раскрашивание интервала размера $MinN (L, n, n)$ , по определению, вы можете найти арифметическую последовательность с преимуществами размерности $п$ длины $L$ . Но теперь количество границ «преимущества» равно количеству цветов, поэтому одна из однородных границ, скажем, размерности $k$ , должна иметь тот же цвет, что и другая из однородных границ полезности, скажем, граница измерения $р <к$ . Это позволяет длину $L + 1$ арифметическая последовательность (размерности 1), которую нужно построить, пройдя линию внутри $k$ -мерная граница, которая заканчивается прямо на $п$ -мерной границы, включая конечную точку в $п$ -мерная граница. В формулах:

если

{ Displaystyle а + Ls_ {1} + Ls_ {2} + cdots + Ls_ {D-k}}

имеет тот же цвет, что и

{ Displaystyle а + Ls_ {1} + Ls_ {2} + cdots + Ls_ {D-p}}

тогда

{ Displaystyle а + L cdot (s_ {1} + cdots + s_ {D-k}) + u cdot (s_ {D-k + 1} + cdots + s_ {p})}

иметь такой же цвет

{ Displaystyle и = 0,1,2, cdots, L-1, L}

т.е.

ты

делает последовательность длины

L

+1.

Это создает последовательность размерности 1, и «преимущества» автоматические, просто добавьте еще одну точку любого цвета. Чтобы включить эту граничную точку, нужно увеличить интервал на максимально возможное значение шага, которое, безусловно, меньше размера интервала. Таким образом, удвоение размера интервала определенно сработает, и это причина для множителя два. Это завершает индукцию по $L$ .

Базовый вариант: $MinN (1, d, n) = 1$ , т.е. если вам нужна однородная длина 1 $d$ -мерная арифметическая последовательность, с пользой или без, вам нечего делать. Это составляет основу индукции. Сама теорема Ван дер Вардена - это утверждение, что $MinN (L, 1, N)$ конечна и следует из базового случая и шагов индукции.^[5]

Смотрите также

Числа Ван дер Вардена для всех известных значений для W(п,р) и наиболее известные оценки неизвестных значений.
Игра Ван дер Вардена - игра, в которой игрок выбирает целые числа из множества 1, 2, ..., N, и пытается собрать арифметическую прогрессию длины п.
Теорема Хейлза – Джеветта
Теорема Радо
Теорема Семереди
Бартель Леендерт ван дер Варден

Примечания

^ ван дер Варден, Б. Л. (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arch. Виск. (на немецком). 15: 212–216.
^ Грэм, Рон (2007). «Некоторые из моих любимых задач по теории Рэмси». INTEGERS: Электронный журнал комбинаторной теории чисел. 7 (2): # A15.
^ Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди». Геом. Функц. Анальный. 11 (3): 465–588. Дои:10.1007 / s00039-001-0332-9.
^ Сабо, Золтан (1990). «Применение локальной леммы Ловаса - новая оценка снизу для числа Ван дер Вардена». Случайная структура. Алгоритмы. 1 (3): 343–360. Дои:10.1002 / rsa.3240010307.
^ ^а ^б Грэм, Р. Л.; Ротшильд, Б. Л. (1974). «Краткое доказательство теоремы ван дер Вардена об арифметических прогрессиях». Proc. Амер. Математика. Soc. 42 (2): 385–386. Дои:10.1090 / S0002-9939-1974-0329917-8.
^ Хинчин (1998 г., стр. 11–17, глава 1)

внешняя ссылка

О'Брайант, Кевин. "Теорема ван дер Вардена". MathWorld.
О'Брайант, Кевин и Вайсштейн, Эрик В. «Число Ван дер Вардена». MathWorld.

[1] ван дер Варден, Б. Л. (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arch. Виск. (на немецком). 15: 212–216.

[2] Грэм, Рон (2007). «Некоторые из моих любимых задач по теории Рэмси». INTEGERS: Электронный журнал комбинаторной теории чисел. 7 (2): # A15.

[3] Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди». Геом. Функц. Анальный. 11 (3): 465–588. Дои:10.1007 / s00039-001-0332-9.

[4] Сабо, Золтан (1990). «Применение локальной леммы Ловаса - новая оценка снизу для числа Ван дер Вардена». Случайная структура. Алгоритмы. 1 (3): 343–360. Дои:10.1002 / rsa.3240010307.

[Graham1974-5] а ^б Грэм, Р. Л.; Ротшильд, Б. Л. (1974). «Краткое доказательство теоремы ван дер Вардена об арифметических прогрессиях». Proc. Амер. Математика. Soc. 42 (2): 385–386. Дои:10.1090 / S0002-9939-1974-0329917-8.

[6] Хинчин (1998 г., стр. 11–17, глава 1)

[1]

[2]

[3]

[4]

[5]

[6]