Теорема Хейлса–Джветта
В математике теорема Хейлза -Джеветта [1] — это фундаментальный комбинаторный результат теории Рэмсея, названный в честь Альфреда В. Хейлза и Роберта И. Джуэтта , касающийся степени, в которой многомерные объекты обязательно должны демонстрировать некоторую комбинаторную структуру.
Неформальная геометрическая формулировка теоремы состоит в том, что для любых целых положительных чисел n и c существует число H такое, что если клетки H -мерного куба размером n × n × n ×...× n раскрасить в c цветов, то должна быть одна строка, столбец или определенная диагональ (подробнее ниже) длины n, все ячейки которой имеют один и тот же цвет. Другими словами, предполагая, что n и c фиксированы, многомерное многопользовательское обобщение игры « крестики-нолики» с c игроками не может закончиться ничьей, независимо от того, насколько крупной является игра « крестики-нолики». n — независимо от того, сколько людей c что он разыгрывается на доске достаточно большого размера H. играет и какой игрок играет каждый ход, при условии , Таким образом, с помощью стандартного аргумента о краже стратегии можно заключить, что если два игрока чередуются, то первый игрок имеет выигрышную стратегию, когда H достаточно велико, хотя практический алгоритм получения этой стратегии неизвестен.
Официальное заявление
[ редактировать ]
Пусть W ЧАС
n — множество слов длины H в алфавите из n букв; то есть набор последовательностей {1, 2, ..., n } длины H . Этот набор образует гиперкуб, являющийся предметом теоремы. Переменное слово w ( x ) над W ЧАС
n по-прежнему имеет длину H , но включает специальный элемент x вместо хотя бы одной буквы. Слова w (1), w (2), ..., w ( n ), полученные заменой всех экземпляров специального элемента x на 1, 2, ..., n , образуют комбинаторную линию в пространстве W ЧАС
п ; комбинаторные линии соответствуют строкам, столбцам и (некоторым) диагоналям гиперкуба . Теорема Хейлса-Джеветта затем утверждает, что для данных положительных целых чисел n и c существует целое положительное число H , зависящее от n и c , такое, что для любого разделения W ЧАС
n на c частей, найдется хотя бы одна часть, содержащая целую комбинаторную прямую.
Например, возьмем n = 3, H = 2 и c = 2. Гиперкуб W ЧАС
н в этом случаеЭто стандартная доска для игры в крестики-нолики с девятью позициями:
| 11 | 12 | 13 |
| 21 | 22 | 23 |
| 31 | 32 | 33 |
Типичная комбинаторикастрока будет словом 2x, что соответствует строке 21, 22, 23; другая комбинаторная линия — это xx, то есть линия11, 22, 33. (Обратите внимание, что линия 13, 22, 31, хотя и является допустимой линией для игры «крестики-нолики» , не считается комбинаторной линией.) В этом конкретном случае теорема Хейлза-Джеветта не действует. применять; можно разделить доску для игры в крестики -нолики на два набора, например {11, 22, 23, 31} и {12, 13, 21, 32, 33}, ни один из которых не содержиткомбинаторная линия (и будет соответствовать ничьей в игре в крестики-нолики ). С другой стороны, если мы увеличим H до, скажем, 8 (так что доска теперь восьмимерная, с 3 8 = 6561 позиция) и разделите эту доску ничья невозможна на два набора («нолики» и «крестики»), то один из двух наборов должен содержать комбинаторную линию (т.е. в этом варианте крестиков-ноликов ). Доказательство см. ниже.
Доказательство теоремы Хейлса–Джеветта (в частном случае)
[ редактировать ]Теперь мы докажем теорему Хейлса–Джеветта в частном случае n = 3, c = 2, H = 8, обсуждавшемся выше. Идея состоит в том, чтобысвести эту задачу к доказательству более простых версий теоремы Хейлза–Джеветта (в данном конкретном случае к случаям n = 2, c = 2, H = 2 и n = 2, c = 6, H = 6). Общий случай теоремы Хейлса–Джеветта можно доказать аналогичными методами, используя математическую индукцию .
Каждый элемент гиперкуба W 8
3 — это строка из восьми чисел от 1 до 3, например 13211321 — это элемент гиперкуба. Мы предполагаем, что этот гиперкуб полностью заполнен «нолями» и «крестиками». Мы воспользуемся доказательством от противного и предположим, что ни множество нулей, ни множество крестиков не содержат комбинаторной прямой. Если зафиксировать первые шесть элементов такой цепочки и оставить изменяться двум последним, то получится обычная доска для игры в крестики-нолики , например «132113??» дает такую доску. Для каждой такой доски «abcdef??» считаем позиции«abcdef11», «abcdef12», «abcdef22». Каждый из них должен быть заполнен либо нулем, либо крестиком, поэтому по принципу ячейки два из них должны быть заполнены одним и тем же символом. Поскольку любые две из этих позиций являются частьюкомбинаторной линии, третий элемент этой строки должен быть занят противоположным символом (поскольку мы предполагаем, что ни в одной комбинаторной строке все три элемента не заполнены одним и тем же символом). Другими словами, для каждого выбора «abcdef» (который можно рассматривать как элемент шестимерного гиперкуба В 6
3 ), существует шесть (перекрывающихся) возможностей:
- abcdef11 и abcdef12 — нули; abcdef13 — крест.
- abcdef11 и abcdef22 — нули; abcdef33 — крест.
- abcdef12 и abcdef22 — нули; abcdef32 — крест.
- abcdef11 и abcdef12 — кресты; abcdef13 — это ноль.
- abcdef11 и abcdef22 — кресты; abcdef33 — это ноль.
- abcdef12 и abcdef22 — кресты; abcdef32 — это ноль.
Таким образом, мы можем разбить шестимерный гиперкуб W 6
3 на шесть классов, соответствующих каждой из шести вышеуказанных возможностей. (Если элемент abcdef подчиняется нескольким возможностям, мы можем выбрать один произвольно, например, выбрав самый высокий из приведенного выше списка).
Теперь рассмотрим семь элементов 111111, 111112, 111122, 111222, 112222, 122222, 222222 в W. 6
3 . По принципу «ячейки» два из этих элементов должны относиться к одному и тому же классу. Предположим, например111112 и 112222 относятся к классу (5), поэтому 11111211, 11111222, 11222211, 11222222 — крестики, а 11111233, 11222233 — нолики. Но теперь рассмотрим позицию 11333233, которую необходимо заполнить либо крестиком, либо нулём. Если она заполнена крестиком, то комбинаторная строка 11xxx2xx целиком заполнена крестиками, что противоречит нашей гипотезе. Если вместо этого она будет заполнена нулём, то комбинаторная строка 11xxx233 будет полностью заполнена нулями, что снова противоречит нашей гипотезе. Аналогично, если любые другие два из семи вышеупомянутых элементов W 6
3 относятся к одному классу. Поскольку во всех случаях мы имеем противоречие, исходная гипотеза должна быть ложной; таким образом, должна существовать хотя бы одна комбинаторная линия, состоящая целиком из нулей или целиком из крестиков.
Приведенный выше аргумент был несколько расточительным; на самом деле та же самая теорема верна и для H = 4. [2] Если распространить приведенный выше аргумент на общие значения n и c , то H будет расти очень быстро; даже когда c для двух игроков = 2 (что соответствует игре в крестики-нолики ), H, заданный приведенным выше аргументом, растет так же быстро, как функция Аккермана . Первая примитивно-рекурсивная граница принадлежит Сахарону Шелаху , [3] и до сих пор является наиболее известной оценкой числа Хейлса–Джеветта H = H ( n , c ).
Связи с другими теоремами
[ редактировать ]Заметьте, что приведенный выше аргумент также дает следующее следствие: если мы позволим A быть множеством всехвосьмизначные числа, все цифры которых равны 1, 2, 3 (таким образом, A содержит такие числа, как 11333233),и раскрасим A в два цвета, тогда A содержит хотя бы одну арифметическую прогрессию длины три, все элементы которой одного цвета. Это просто потому, что все комбинаторные линии, встречающиеся в приведенном выше доказательстве теоремы Хейлса-Джеветта, также образуют арифметические прогрессии в десятичной записи . Более общую формулировку этого аргумента можно использовать, чтобы показать, что теорема Хейлса-Джеветта обобщает теорему Ван дер Вардена . Действительно, теорема Хейлса-Джеветта является существенно более сильной теоремой.
Так же, как теорема Ван дер Вардена имеет более сильную версию плотности в теореме Семереди , теорема Хейлса-Джеветта также имеет версию плотности. В этой усиленной версии теоремы Хейлса–Джеветта вместо раскраски всего гиперкуба W ЧАС
n на c цветов, дано произвольное подмножество A гиперкуба W ЧАС
n с некоторой заданной плотностью 0 < δ < 1. Теорема утверждает, что если H достаточно велико в зависимости от n и δ, то множество A обязательно должно содержать целую комбинаторную прямую.
Теорема Хейлса-Джеветта о плотности была первоначально доказана Фюрстенбергом и Кацнельсоном с использованием эргодической теории . [4] В 2009 году проект Polymath разработал новое доказательство. [5] [6] теоремы Хейлса–Джеветта о плотности, основанной на идеях доказательства теоремы об углах . [7] Додос, Канеллопулос и Тирос предложили упрощенную версию доказательства Полимата. [8]
Теорема Хейлза-Джеветта обобщается теоремой Грэма-Ротшильда более высокой размерности о комбинаторных кубах .
Ссылки
[ редактировать ]- ^ Хейлз, Альфред В.; Джуэтт, Роберт И. (1963). «Регулярность и позиционные игры» . Пер. амер. Математика. Соц. 106 (2): 222–229. дои : 10.1090/S0002-9947-1963-0143712-1 . МР 0143712 .
- ^ Хиндман, Нил ; Тресслер, Эрик (2014). «Первое нетривиальное число Хейлса-Джеветта равно четырем» (PDF) . Арс Комбинатория . 113 : 385–390. МР 3186481 .
- ^ Шела, Сахарон (1988). «Примитивно-рекурсивные оценки чисел Ван дер Вардена» . Дж. Амер. Математика. Соц. 1 (3): 683–697. дои : 10.2307/1990952 . JSTOR 1990952 . МР 0929498 .
- ^ Фюрстенберг, Гилель ; Кацнельсон, Ицхак (1991). «Плотная версия теоремы Хейлза – Джуэтта». Журнал Математического Анализа . 57 (1): 64–119. дои : 10.1007/BF03041066 . МР 1191743 . S2CID 123036744 .
- ^ DHJ Полимат (2012). «Новое доказательство теоремы Хейлса – Джуитта о плотности» . Анналы математики . 175 (3): 1283–1327. дои : 10.4007/анналы.2012.175.3.6 . МР 2912706 .
- ^ Гауэрс, Уильям Тимоти (2010). «Эрудит и теорема Хейлса-Джветта о плотности». В Барани Имре; Солимоси, Йожеф (ред.). Нестандартный ум . Общество математических исследований Боляи. Том 21. Будапешт: Математическое общество Яноша Бойяи. стр. 659–687. дои : 10.1007/978-3-642-14444-8_21 . ISBN 978-963-9453-14-2 . МР 2815619 .
- ^ Айтай, Миклош; Семереди, Эндре (1974). «Наборы точек решетки, не образующие квадратов». Стад. Научная математика. Венгерский . 9 :9–11. МР 0369299 .
- ^ Додос, Панделис; Канеллопулос, Василис; Тирос, Константинос (2014). «Простое доказательство теоремы Хейлса – Джуэтта о плотности». Межд. Математика. Рез. Нет. ИМРН . 2014 (12): 3340–3352. arXiv : 1209.4986 . дои : 10.1093/imrn/rnt041 . МР 3217664 .
Внешние ссылки
[ редактировать ]- Полное доказательство HJT – начинается на слайде 57.
- Статья в Science News о совместном доказательстве теоремы Хейлса-Джеветта о плотности
- Сообщение в блоге Стивена Ландсбурга, в котором обсуждается, как доказательство этой теоремы было улучшено совместно в блоге.
- Многомерные крестики-нолики | Бесконечный сериал от PBS
