Теорема Ван дер Вардена - это теорема из раздела математики, называемого теорией Рамсея . Теорема Ван дер Вардена утверждает, что для любых заданных натуральных чисел r и k существует некоторое число N такое, что если целые числа {1, 2, ..., N } раскрашены, каждое в один из r разных цветов, то существует не менее k целых чисел в арифметической прогрессии , элементы которых одного цвета. Наименьшее из таких N - это число Ван дер Вардена W ( r , k), названный в честь голландского математика Б.Л. ван дер Вардена . [1]
Пример
Например, когда r = 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 ( r , k ) для большинства значений r и k . Доказательство теоремы дает только оценку сверху. Например, для случая r = 2 и k = 3 приведенный ниже аргумент показывает, что достаточно раскрасить целые числа {1, ..., 325} двумя цветами, чтобы гарантировать, что будет одноцветная арифметика. прогрессия длины 3. Но на самом деле граница 325 очень нечеткая; минимальное необходимое количество целых чисел - только 9. Любая раскраска целых чисел {1, ..., 9} будет иметь три равномерно расположенных целых числа одного цвета.
Для r = 3 и k = 3 оценка, данная теоремой, равна 7 (2 · 3 7 + 1) (2 · 3 7 · (2 · 3 7 + 1) + 1), или приблизительно 4,22 · 10 14616 . Но на самом деле вам не нужно столько целых чисел, чтобы гарантировать одноцветную прогрессию длины 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 . [2] Лучший верхняя граница в настоящее время известно , связано с Гауэрс , [3] , которое создает
сначала установив аналогичный результат для теоремы Семереди , которая является более сильной версией теоремы Ван дер Вардена. Ранее наиболее известная оценка была получена Сахароном Шелахом и продолжалась первым доказательством результата для теоремы Хейлса – Джеветта , которая является еще одним усилением теоремы Ван дер Вардена.
Лучшая нижняя граница, известная в настоящее время для это для всех положительных у нас есть , для всех достаточно больших . [4]
Доказательство теоремы Ван дер Вардена (в частном случае)
Следующее доказательство принадлежит Рону Грэхему и Б.Л. Ротшильду. [5] Хинчин [6] дает довольно простое доказательство теоремы без оценки W ( r , k ).
Доказательство в случае W (2, 3)
б | c ( n ): цвет целых чисел | ||||
---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 |
р | р | B | р | B | |
1 | 6 | 7 | 8 | 9 | 10 |
B | р | р | B | р | |
… | … | ||||
64 | 321 | 322 | 323 | 324 | 325 |
р | B | р | B | р |
Мы докажем упомянутый выше частный случай, что W (2, 3) ≤ 325. Пусть c ( n ) - раскраска целых чисел {1, ..., 325}. Мы найдем в арифметической прогрессии три элемента {1, ..., 325} одного цвета.
Разделите {1, ..., 325} на 65 блоков {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, таким образом, каждый блок имеет вид {5 b + 1, ..., 5 b + 5} для некоторого b в {0, ..., 64}. Поскольку каждое целое число окрашено в красный или синий цвет , каждый блок окрашивается одним из 32 различных способов. По принципу «голубятни» среди первых 33 блоков есть два идентично окрашенных. То есть есть два целых числа b 1 и b 2 , оба в {0, ..., 32}, такие, что
- c (5 b 1 + k ) = c (5 b 2 + k )
для всех k в {1, ..., 5}. Среди трех целых чисел 5 b 1 + 1, 5 b 1 + 2, 5 b 1 + 3 должно быть как минимум два одного цвета. ( Снова принцип « голубятни» .) Назовите эти 5 b 1 + a 1 и 5 b 1 + a 2 , где a i находятся в {1,2,3}, а a 1 < a 2 . Предположим (без ограничения общности), что эти два целых числа красные . (Если они оба синие , в дальнейшем просто поменяйте местами « красный » и « синий ».)
Пусть a 3 = 2 a 2 - a 1 . Если 5 б 1 + 3 является красный , то мы нашли нашу арифметическую прогрессию: 5 б 1 + я все красное .
В противном случае 5 b 1 + a 3 будет синим . Поскольку a 3 ≤ 5, 5 b 1 + a 3 находится в блоке b 1 , и поскольку блок b 2 окрашен одинаково, 5 b 2 + a 3 также является синим .
Пусть теперь b 3 = 2 b 2 - b 1 . Тогда b 3 ≤ 64. Рассмотрим целое число 5 b 3 + a 3 , которое должно быть ≤ 325. Какого цвета?
Если он красный , то 5 b 1 + a 1 , 5 b 2 + a 2 и 5 b 3 + a 3 образуют красную арифметическую прогрессию. Но если он синий , то 5 b 1 + a 3 , 5 b 2 + a 3 и 5 b 3 + a 3 образуют синюю арифметическую прогрессию. В любом случае, мы закончили.
Доказательство в случае W (3, 3)
б | c ( n ): цвет целых чисел | ||||
---|---|---|---|---|---|
0 | 1 | 2 | 3 | … | м |
грамм | р | р | … | B | |
1 | м +1 | м +2 | м +3 | … | 2м |
B | р | грамм | … | р | |
… | … | ||||
грамм | gm + 1 | гм + 2 | гм + 3 | … | (г + 1) м |
B | р | B | … | грамм |
Аналогичное рассуждение можно привести, чтобы показать, что W (3, 3) ≤ 7 (2 · 3 7 +1) (2 · 3 7 · (2 · 3 7 +1) +1). Сначала делят целые числа на 2 · 3 7 · (2 · 3 7 + 1) + 1 группы по 7 (2 · 3 7 + 1) целых чисел в каждой; из первых 3 7 · (2 · 3 7 + 1) + 1 групп две должны быть окрашены одинаково.
Разделите каждую из этих двух групп на 2 · 3 7 +1 подгруппы по 7 целых чисел в каждой; из первых 3 7 + 1 подгрупп в каждой группе две подгруппы должны быть окрашены одинаково. В каждой из этих идентичных подгрупп два из первых четырех целых чисел должны быть одного цвета, например красного ; это подразумевает либо красную прогрессию, либо элемент другого цвета, например синего , в той же подгруппе.
Поскольку у нас есть две одинаково окрашенные подгруппы, есть третья подгруппа, все еще в той же группе, которая содержит элемент, который, будь красный или синий , завершил бы красную или синюю прогрессию, по конструкции, аналогичной конструкции для W ( 2, 3). Предположим, что этот элемент зеленый . Поскольку существует группа, окрашенная одинаково, она должна содержать копии идентифицированных нами красных , синих и зеленых элементов; теперь мы можем найти пару красных элементов, пару синих элементов и пару зеленых элементов, которые «фокусируются» на одном и том же целом числе, так что независимо от его цвета, оно должно завершать прогрессию.
Доказательство в общем случае
Доказательство для W (2, 3) существенно зависит от доказательства того, что W (32, 2) ≤ 33. Мы разделим целые числа {1, ..., 325} на 65 «блоков», каждый из которых можно раскрасить в 32 цвета. разными способами, а затем покажите, что два блока из первых 33 должны быть одного цвета, а есть блок противоположного цвета. Аналогично, доказательство для W (3, 3) зависит от доказательства того, что
Путем двойной индукции по количеству цветов и длине прогрессии теорема в общем доказана.
Доказательство
Д-мерный арифметическая прогрессия (АР) состоит из чисел вида:
где a - базовая точка, s - положительные размеры шага, а i - от 0 до L-1 . D - мерное AP является однородным для некоторой раскраски , когда это все тот же цвет.
D - мерная арифметическая прогрессия с преимуществами является всеми номерами данной формы, но где вы добавляете на некоторых «границе» в арифметической прогрессии, то есть некоторые из индексов I «s может быть равно L . Стороны вы лавировать на являются те , где первым к I «s равны L , а остальной я » s меньше L .
Границами D- мерной AP с преимуществами являются эти дополнительные арифметические прогрессии размерности, вплоть до 0. 0-мерная арифметическая прогрессия - это единственная точка при значении индекса . D -мерного AP с преимуществами является однородным , когда каждая из границ индивидуальна однородные, но разные границы не должны обязательно иметь одинаковый цвет.
Затем определите количество MinN (L, D, N) как наименьшее целое число, чтобы любое присвоение N цветов интервалу длины MinN или более обязательно содержало однородную D -мерную арифметическую прогрессию с преимуществами.
Цель состоит в том, чтобы ограничить размер MinN . Обратите внимание, что MinN (L, 1, N) - это верхняя граница числа Ван дер Вардена. Есть два шага индукции, а именно:
Лемма 1 - Предположим , Minn известно для заданной длины L для всех размеров арифметических прогрессий с пользой до D . Эта формула дает ограничение на MinN, когда вы увеличиваете размерность до D + 1 :
позволять , тогда
Во- первых, если у вас есть п -раскраска интервала 1 ... I , вы можете определить блок окраски из к -размер блоков. Просто рассмотрите каждую последовательность из k цветов в каждом блоке k, чтобы определить уникальный цвет. Назовите это k -блокированием и n- раскраской. k -блокирование n раскраски длины l дает n k раскраски длины l / k .
Итак, учитывая n -краску интервала I размеравы можете M -блокировать его в n M раскраски длины. Но это означает, по определению MinN , что вы можете найти одномерную арифметическую последовательность (с преимуществами) длины L в раскраске блоков, которая представляет собой последовательность блоков, расположенных на одинаковом расстоянии друг от друга, и все они имеют одинаковый цвет блока, т.е. у вас есть группа блоков длиной M в исходной последовательности, которые расположены на одинаковом расстоянии друг от друга и имеют внутри точно такую же последовательность цветов.
Теперь, по определению M , вы можете найти d -мерную арифметическую последовательность с преимуществами в любом из этих блоков, и поскольку все блоки имеют одинаковую последовательность цветов, одна и та же d- мерная AP с преимуществами появляется во всех блоков, просто переводя его из блока в блок. Это определение d + 1- мерной арифметической прогрессии, так что у вас есть однородная d + 1- мерная AP. Новый параметр шага s D + 1 определяется как расстояние между блоками.
Но вам нужны льготы. Границы вы получите теперь все старые границы, а также их переводы на одинаково цветных блоков, потому что я D + 1 всегда меньше , чем L . Единственная граница, которая не похожа на эту, - это 0-мерная точка, когда. Это одна точка, и она автоматически однородна.
Лемма 2 - Предположим , Minn известно для одного значения L и всех возможных размеров D . Затем вы можете связать MinN на длину L + 1 .
Дан п -раскраска интервала размера Minn (л, п, п) , по определению, вы можете найти арифметическую последовательность с преимуществами размерностей п длиной L . Но теперь количество границ «выгоды» равно количеству цветов, поэтому одна из однородных границ, скажем размерности k , должна иметь тот же цвет, что и другая граница однородной выгоды, скажем, граница измерения р <к . Это позволяет построить арифметическую последовательность длины L + 1 (размерности 1), пройдя линию внутри k -мерной границы, которая заканчивается прямо на p -мерной границе, и включая конечную точку на p -мерной границе. . В формулах:
если
- имеет тот же цвет, что и
тогда
- иметь такой же цвет
- т.е. u составляет последовательность длины L +1.
Это создает последовательность размерности 1, и "преимущества" автоматические, просто добавьте еще одну точку любого цвета. Чтобы включить эту граничную точку, нужно увеличить интервал на максимально возможное значение шага, которое, безусловно, меньше размера интервала. Так что удвоение размера интервала определенно сработает, и это причина для множителя два. Это завершает индукцию по L .
Базовый случай: MinN (1, d, n) = 1 , т.е. если вам нужна однородная d -мерная арифметическая последовательность длины 1 , с преимуществами или без них, вам нечего делать. Это составляет основу индукции. Сама теорема Ван дер Вардена является утверждением конечности MinN (L, 1, N) и следует из базового случая и шагов индукции. [5]
Смотрите также
- Числа Ван-дер-Вардена для всех известных значений W ( n , r ) и наиболее известные границы для неизвестных значений.
- Игра Ван дер Вардена - игра, в которой игрок выбирает целые числа из набора 1, 2, ..., N и пытается собрать арифметическую прогрессию длины n .
- Теорема Хейлза – Джеветта
- Теорема Радо
- Теорема Семереди
- Бартель Леендерт ван дер Варден
Заметки
- ^ ван дер Варден, BL (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arch. Виск. (на немецком). 15 : 212–216.
- ^ Грэм, Рон (2007). «Некоторые из моих любимых задач по теории Рэмси» . INTEGERS: Электронный журнал комбинаторной теории чисел . 7 (2): # A15.
- ^ Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди» . Геом. Функц. Анальный . 11 (3): 465–588. DOI : 10.1007 / s00039-001-0332-9 .
- ^ Сабо, Золтан (1990). «Применение локальной леммы Ловаса - новая нижняя оценка числа Ван дер Вардена». Случайная структура. Алгоритмы . 1 (3): 343–360. DOI : 10.1002 / rsa.3240010307 .
- ^ а б Graham, RL ; Ротшильд Б.Л. (1974). «Краткое доказательство теоремы Ван дер Вардена об арифметических прогрессиях» . Proc. Амер. Математика. Soc . 42 (2): 385–386. DOI : 10.1090 / S0002-9939-1974-0329917-8 .
- ↑ Хинчин (1998 , стр. 11–17, глава 1)
Рекомендации
- Хинчин, А.Я. (1998), Три жемчужины теории чисел , Mineola, NY: Dover, стр. 11–17, ISBN 978-0-486-40026-6
Внешние ссылки
- О'Брайант, Кевин . «Теорема ван дер Вардена» . MathWorld .
- О'Брайант, Кевин и Вайсштейн, Эрик В. «Число Ван дер Вардена» . MathWorld .