Набор крышек

В аффинной геометрии набор ограничений является подмножеством $\mathbb {Z} _{3}^{n}$ (ан $n$ -мерное аффинное пространство над трехэлементным полем ), где никакие три элемента в сумме не дают нулевой вектор.Задача о наборе пределов — это проблема нахождения размера максимально возможного набора пределов в зависимости от $n$ . ^[1] Первые несколько размеров набора крышек — это 1, 2, 4, 9, 20, 45, 112, ... (последовательность A090245 в OEIS ).

Наборы ограничений могут быть определены в более общем смысле как подмножества конечных аффинных или проективных пространств без трех в строке, где эти объекты называются просто крышками. ^[2] Терминологию «ограниченного набора» следует отличать от других несвязанных математических объектов с таким же названием, в частности от множеств со свойством компактного поглощения в функциональных пространствах. ^[3] а также из компактных выпуклых ковыпуклых подмножеств выпуклого множества. ^[4]

Пример

Пример наборов крышек взят из карточной игры Set , карточной игры, в которой каждая карта имеет четыре характеристики (ее номер, символ, оттенок и цвет), каждая из которых может принимать одно из трех значений. Карты этой игры можно интерпретировать как точки четырехмерного аффинного пространства. $\mathbb {Z} _{3}^{4}$ , где каждая координата точки определяет значение одного из признаков. Линия в этом пространстве представляет собой тройку карточек, которые по каждому признаку либо одинаковы, либо отличаются друг от друга. Игровой процесс состоит из поиска и сбора линий среди карт, которые в данный момент лежат лицевой стороной вверх, а набор ограничений описывает массив открытых карт, в которых нельзя собрать ни одной линии. ^[1]^[5]^[6]

Один из способов создать большой набор ограничений в игровом наборе — это выбрать два из трех значений для каждой функции и положить лицевой стороной вверх каждую из карт, в каждой из которых используется только одно из этих двух значений. В результате получится набор из 16 карт. В более общем плане та же стратегия приведет к установлению ограничений в $\mathbb {Z} _{3}^{n}$ размера $2^{n}$ . Однако в 1970 году Джузеппе Пеллегрино доказал, что четырехмерные наборы кепок имеют максимальный размер 20. ^[7] С точки зрения набора этот результат означает, что в некоторых раскладах из 20 карт нет линии для сбора, но в каждом раскладе из 21 карты есть хотя бы одна линия. (Даты не являются опечаткой: результат набора кепок Pellegrino 1970 года действительно предшествует первой публикации игры Set в 1974 году.) ^[8]

Максимальный размер

Со времени работы Пеллегрино в 1971 году, а также Тома Брауна и Джо Бюлера, которые в 1984 году доказали, что комплекты крышек не могут составлять какую-либо постоянную долю всего пространства, ^[9] было проведено значительное исследование того, насколько большими они могут быть.

Нижние границы

Решение Пеллегрино четырехмерной задачи о множестве ограничений также приводит к более высоким нижним оценкам, чем $2^{n}$ для любого более высокого измерения, которое было дополнительно улучшено до $2.2173^{n}$ Эдель (2004) ^[2]а затем $2.2180^{n}$ Тиррелла (2022) . ^[10] В декабре 2023 года группа исследователей из Google DeepMind опубликовала статью, в которой они объединили модель большого языка (LLM) с оценщиком и сумели улучшить привязку к $2.2202^{n}$ . ^[11]

Верхние границы

В 1984 году Том Браун и Джо Бюлер ^[9] доказал, что максимально возможный размер кепки установлен в $\mathbb {Z} _{3}^{n}$ является $o(3^{n})$ как $n$ растет; Грубо говоря, это означает, что наборы ограничений имеют нулевую плотность. Петер Франкл , Рональд Грэм и Войтех Рёдль показали ^[12] в 1987 году, что результат Брауна и Бюлера легко следует из Ружи - Семереди леммы об удалении треугольника , и задался вопросом, существует ли константа $c<3$ такое, что действительно для всех достаточно больших значений $n$ , любое установленное ограничение $\mathbb {Z} _{3}^{n}$ имеет максимальный размер $c^{n}$ ; то есть, есть ли какой-либо набор в $\mathbb {Z} _{3}^{n}$ размером превышающим $c^{n}$ содержит аффинную строку. Этот вопрос также появился в статье ^[13] опубликовано Ногой Алоном и Моше Дубинером в 1995 году. В том же году Рой Мешулам доказал ^[14] чтобы размер комплекта шапок не превышал $2\cdot 3^{n}/n$ . Майкл Бейтман и Нетс Кац ^[15] улучшили привязку к $O(3^{n}/n^{1+\varepsilon })$ с положительной константой $\varepsilon$ .

Определение возможности улучшения границы Мешулама до $c^{n}$ с $c<3$ считалась одной из самых интригующих открытых проблем в аддитивной комбинаторике и теории Рамсея на протяжении более 20 лет, что подчеркивалось, например, в сообщениях в блоге по этой проблеме медалиста Филдса Тимоти Гауэрса. ^[16] и Теренс Тао . ^[17] В своем сообщении в блоге Тао называет ее «возможно, моей любимой открытой проблемой» и дает упрощенное доказательство экспоненциальной границы для наборов ограничений, а именно, для любой простой степени $p$ , подмножество $S\subset F_{p}^{n}$ который не содержит арифметической прогрессии длины $3$ имеет максимальный размер $c_{p}^{n}$ для некоторых $c_{p}<p$ . ^[17]

Гипотеза о предельном наборе была решена в 2016 году благодаря серии прорывов в полиномиальном методе. Эрни Крут , Всеволод Лев и Петер Пал Пах опубликовали препринт по связанной с этим проблеме непрогрессивных подмножеств $\mathbb {Z} _{4}^{n}$ , и этот метод использовался Джорданом Элленбергом и Дионом Гейсвейтом для доказательства верхней границы $2.756^{n}$ по поводу проблемы с набором шапок. ^[5]^[6]^[18]^[19]^[20] В 2019 году Сандер Дамен, Йоханнес Хёльцль и Роб Льюис формализовали доказательство этой верхней оценки в средстве доказательства теорем бережливого производства . ^[21]

По состоянию на март 2023 года экспоненциального улучшения верхней границы Элленберга и Гейсвейта не наблюдается. Цзян показал, что, точно исследуя полиномиальные коэффициенты, полученные из доказательства Элленберга и Гейсвейта, можно получить коэффициент ${\sqrt {n}}$ . ^[22] Эта экономия происходит по тем же причинам, что и ${1/{\sqrt {n}}}$ коэффициент центрального биномиального коэффициента .

Взаимно непересекающиеся наборы крышек

В 2013 году пять исследователей вместе опубликовали анализ всех способов, с помощью которых пространства размером до $\mathbb {Z} _{3}^{4}$ могут быть разделены на непересекающиеся наборы крышек. ^[23] Они сообщили, что можно использовать четыре разных набора крышек размера 20 в $\mathbb {Z} _{3}^{4}$ что между ними охватывают 80 различных ячеек; единственная ячейка, оставшаяся непокрытой, называется якорем каждого из четырех наборов ограничений, единственной точкой, которая при добавлении к 20 точкам набора ограничений приводит к тому, что вся сумма становится равной 0 (модуль 3). Все наборы крышек в такой непересекающейся коллекции имеют один и тот же якорь. Результаты для более крупных размеров по состоянию на 2021 год все еще открыты.

Приложения

Гипотеза о подсолнухе

Решение проблемы максимального множества можно также использовать для доказательства частичной формы гипотезы о подсолнухе , а именно: если семейство подмножеств некоторого $n$ В -элементном множестве нет трех подмножеств, все попарные пересечения которых равны, то число подмножеств в семействе не более $c^{n}$ для постоянного $c<2$ . ^[5]^[24]^[6]^[25]

Алгоритмы умножения матриц

Верхние границы ограниченных наборов подразумевают нижние границы для определенных типов алгоритмов умножения матриц . ^[26]

Сильно регулярные графы

Граф Games представляет собой строго регулярный граф с 729 вершинами. Каждое ребро принадлежит уникальному треугольнику, поэтому это локально линейный граф , самый большой из известных локально линейных сильно регулярных графов. Его конструкция основана на уникальном 56-точечном наборе ограничений в пятимерном троичном проективном пространстве (а не на аффинном пространстве, в котором обычно определяются наборы ограничений). ^[27]

См. также

Проблема «нет трех строк» — проблема исключения трех элементов в строке в двумерной сетке.
Проблема Ружи – Семереди

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Остин, Дэвид (август 2016 г.), «Игра. МНОЖЕСТВО. Полином». , Тематическая колонка , Американское математическое общество .
^ Jump up to: Перейти обратно: ^а ^б Эдель, Ив (2004), «Расширения обобщенных ограничений продукта», Designs, Codes and Cryptography , 31 (1): 5–14, doi : 10.1023/A:1027365901231 , MR 2031694 .
^ См., например, Чепмен, Т. А. (1971), «Плотные сигма-компактные подмножества бесконечномерных многообразий», Труды Американского математического общества , 154 : 399–426, doi : 10.1090/s0002-9947-1971-0283828-7 , MR 0283828 .
^ См., например, Minʹkova, R. M. (1979), "Weak Korovkin spaces", Akademiya Nauk Soyuza SSR , 25 (3): 435–443, 477, MR 0534099 .
^ Jump up to: Перейти обратно: ^а ^б ^с Кларрайх, Эрика (31 мая 2016 г.), «Простое игровое доказательство ошеломляет математиков» , Quanta , заархивировано из оригинала 24 декабря 2016 г. , получено 2 августа 2016 г.
^ Jump up to: Перейти обратно: ^а ^б ^с Грочоу, Джошуа А. (2019), «Новые применения полиномиального метода: гипотеза о наборе ограничений и не только», Бюллетень Американского математического общества , 56 : 29–64, doi : 10.1090/bull/1648 , MR 3886143
^ Пеллегрино, Джузеппе (1970). "О максимальном порядке шапочек в $S_4,3$" [Максимальный порядок сферической шапочки в $S_4,3$]. Математика (на итальянском языке). 25 : 149–157. ISSN 0373-3505 .
^ Хилл, Р. (1983-01-01), Барлотти, А.; Чеккерини, П.В.; Таллини, Г. (ред.), «О 20 шапках Пеллегрино в S4, 3» , Математические исследования Северной Голландии , Комбинаторика '81 в честь Бениамино Сегре, том. 78, Северная Голландия, стр. 433–447 , получено 16 декабря 2023 г.
^ Jump up to: Перейти обратно: ^а ^б Браун, ТК ; Бюлер, Дж. П. (1 марта 1984 г.). «Линии означают пространства в теории плотности Рамсея» . Журнал комбинаторной теории . Серия А. 36 (2): 214–220. дои : 10.1016/0097-3165(84)90006-2 .
^ Тиррелл, Фред (2022). «Новые нижние границы наборов ограничений» . Дискретный анализ . 2023 (20). arXiv : 2209.10045 . дои : 10.19086/da.91076 . Проверено 9 января 2024 г.
^ Ромера-Паредес, Бернардино; Барекатаин, Мохаммадамин; Новиков, Александр; Балог, Матей; Кумар, М. Паван; Дюпон, Эмильен; Руис, Франциско младший; Элленберг, Джордан С.; Ван, Пэнмин; Фаузи, Омар; Кохли, Пушмит; Фаузи, Аль-Хусейн (14 декабря 2023 г.). «Математические открытия в результате программного поиска с большими языковыми моделями» . Природа : 1–3. дои : 10.1038/s41586-023-06924-6 . ISSN 1476-4687 . ПМЦ 10794145 .
^ Франкл, П .; Грэм, РЛ ; Рёдль, В. (1987). «О подмножествах абелевых групп без трехчленной арифметической прогрессии» . Журнал комбинаторной теории . Серия А. 45 (1): 157–161. дои : 10.1016/0097-3165(87)90053-7 . МР 0883900 .
^ Алон, Нога; Дубинер, Моше (1995). «Задача о точках решетки и аддитивная теория чисел». Комбинаторика . 15 (3): 301–309. дои : 10.1007/BF01299737 . ISSN 0209-9683 .
^ Мешулам, Рой (1 июля 1995 г.). «О подмножествах конечных абелевых групп без 3-членных арифметических прогрессий» . Журнал комбинаторной теории . Серия А. 71 (1): 168–172. дои : 10.1016/0097-3165(95)90024-1 .
^ Бейтман, Майкл; Кац, Нетс (1 января 2012 г.). «Новые ограничения на наборы крышек». Журнал Американского математического общества . 25 (2): 585–613. arXiv : 1101.5851 . дои : 10.1090/S0894-0347-2011-00725-X . ISSN 0894-0347 .
^ «Что сложного в проблеме с набором крышек?» . Блог Гауэрса . 11 января 2011 г. Проверено 26 ноября 2016 г.
^ Jump up to: Перейти обратно: ^а ^б Тао, Теренс (23 февраля 2007 г.). «Открытый вопрос: наилучшие границы для наборов ограничений» . Что нового . Проверено 26 ноября 2016 г.
^ «Экспоненциальная верхняя граница проблемы максимального набора» , редакция журнала Discrete Analysis , 5 июня 2016 г.
^ Крут, Эрни ; Лев, Всеволод; Пах, Питер (2017), «Наборы без прогрессирования в $Z_{4}^{n}$ экспоненциально малы», Annals of Mathematics , 185 (1): 331–337, arXiv : 1605.01506 , Bibcode : 2016arXiv160501506C , doi : 10.4007/annals.2017.185.1.7 .
^ Элленберг, Джордан С .; Гейсвейт, Дион (2017), «О больших подмножествах $\mathbb {F} _{q}^{n}$ без трехчленной арифметической прогрессии», Annals of Mathematics , Second Series, 185 (1): 339–343, arXiv : 1605.09223 , doi : 10.4007/annals.2017.185.1.8 , MR 3583358
^ Дамен, Сандер Р.; Хёльцль, Йоханнес; Льюис, Роберт Ю. (2019), «Формализация решения проблемы ограничения количества», в Харрисоне, Джон; О'Лири, Джон; Толмач, Эндрю (ред.), 10-я Международная конференция по интерактивному доказательству теорем, ITP 2019, 9–12 сентября 2019 г., Портленд, Орегон, США , LIPIcs, vol. 141, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 15:1–15:19, arXiv : 1907.01449 , doi : 10.4230/LIPIcs.ITP.2019.15
^ Цзян, Чжи (2021), Явные верхние границы для задачи о наборе ограничений , arXiv : 2103.06481
^ Фоллетт, Майкл; Калаил, Кайл; МакМахон, Элизабет; Пелланд, Кэтрин; Вон, Роберт (2014), «Разделы $AG(4,3)$ на максимальные ограничения», Дискретная математика , 337 : 1–8, arXiv : 1302.4703 , doi : 10.1016/j.disc.2014.08.002 , MR 3262358
^ Хартнетт, Кевин. «Математики начинают приручать дикую задачу о «подсолнухе»» . Журнал Кванта . Проверено 22 октября 2019 г.
^ Калай, Гил (17 мая 2016 г.), «Экстренный пост Polymath 10 5: гипотеза Эрдоша-Семереди о подсолнухе теперь доказана» , Комбинаторика и многое другое .
^ Блазиак, Иона; Черч, Томас; Кон, Генри; Грочоу, Джошуа А.; Уманс, Крис (2016), «О наборах ограничений и теоретико-групповом подходе к умножению матриц», Discrete Analysis , arXiv : 1605.06702 , Bibcode : 2016arXiv160506702B , doi : 10.19086/da.1245 .
^ Хилл, Рэймонд (1978), «Шапики и коды», Дискретная математика , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR 0523299 .

[austin-1] Jump up to: Перейти обратно: ^а ^б Остин, Дэвид (август 2016 г.), «Игра. МНОЖЕСТВО. Полином». , Тематическая колонка , Американское математическое общество .

[edel-2] Jump up to: Перейти обратно: ^а ^б Эдель, Ив (2004), «Расширения обобщенных ограничений продукта», Designs, Codes and Cryptography , 31 (1): 5–14, doi : 10.1023/A:1027365901231 , MR 2031694 .

[3] См., например, Чепмен, Т. А. (1971), «Плотные сигма-компактные подмножества бесконечномерных многообразий», Труды Американского математического общества , 154 : 399–426, doi : 10.1090/s0002-9947-1971-0283828-7 , MR 0283828 .

[4] См., например, Minʹkova, R. M. (1979), "Weak Korovkin spaces", Akademiya Nauk Soyuza SSR , 25 (3): 435–443, 477, MR 0534099 .

[quanta-5] Jump up to: Перейти обратно: ^а ^б ^с Кларрайх, Эрика (31 мая 2016 г.), «Простое игровое доказательство ошеломляет математиков» , Quanta , заархивировано из оригинала 24 декабря 2016 г. , получено 2 августа 2016 г.

[bulletin-6] Jump up to: Перейти обратно: ^а ^б ^с Грочоу, Джошуа А. (2019), «Новые применения полиномиального метода: гипотеза о наборе ограничений и не только», Бюллетень Американского математического общества , 56 : 29–64, doi : 10.1090/bull/1648 , MR 3886143

[7] Пеллегрино, Джузеппе (1970). "О максимальном порядке шапочек в \(S_4,3\)" [Максимальный порядок сферической шапочки в \(S_4,3\)]. Математика (на итальянском языке). 25 : 149–157. ISSN 0373-3505 .

[8] Хилл, Р. (1983-01-01), Барлотти, А.; Чеккерини, П.В.; Таллини, Г. (ред.), «О 20 шапках Пеллегрино в S4, 3» , Математические исследования Северной Голландии , Комбинаторика '81 в честь Бениамино Сегре, том. 78, Северная Голландия, стр. 433–447 , получено 16 декабря 2023 г.

[Brown_214–220-9] Jump up to: Перейти обратно: ^а ^б Браун, ТК ; Бюлер, Дж. П. (1 марта 1984 г.). «Линии означают пространства в теории плотности Рамсея» . Журнал комбинаторной теории . Серия А. 36 (2): 214–220. дои : 10.1016/0097-3165(84)90006-2 .

[tyrrell-10] Тиррелл, Фред (2022). «Новые нижние границы наборов ограничений» . Дискретный анализ . 2023 (20). arXiv : 2209.10045 . дои : 10.19086/da.91076 . Проверено 9 января 2024 г.

[11] Ромера-Паредес, Бернардино; Барекатаин, Мохаммадамин; Новиков, Александр; Балог, Матей; Кумар, М. Паван; Дюпон, Эмильен; Руис, Франциско младший; Элленберг, Джордан С.; Ван, Пэнмин; Фаузи, Омар; Кохли, Пушмит; Фаузи, Аль-Хусейн (14 декабря 2023 г.). «Математические открытия в результате программного поиска с большими языковыми моделями» . Природа : 1–3. дои : 10.1038/s41586-023-06924-6 . ISSN 1476-4687 . ПМЦ 10794145 .

[12] Франкл, П .; Грэм, РЛ ; Рёдль, В. (1987). «О подмножествах абелевых групп без трехчленной арифметической прогрессии» . Журнал комбинаторной теории . Серия А. 45 (1): 157–161. дои : 10.1016/0097-3165(87)90053-7 . МР 0883900 .

[13] Алон, Нога; Дубинер, Моше (1995). «Задача о точках решетки и аддитивная теория чисел». Комбинаторика . 15 (3): 301–309. дои : 10.1007/BF01299737 . ISSN 0209-9683 .

[14] Мешулам, Рой (1 июля 1995 г.). «О подмножествах конечных абелевых групп без 3-членных арифметических прогрессий» . Журнал комбинаторной теории . Серия А. 71 (1): 168–172. дои : 10.1016/0097-3165(95)90024-1 .

[15] Бейтман, Майкл; Кац, Нетс (1 января 2012 г.). «Новые ограничения на наборы крышек». Журнал Американского математического общества . 25 (2): 585–613. arXiv : 1101.5851 . дои : 10.1090/S0894-0347-2011-00725-X . ISSN 0894-0347 .

[16] «Что сложного в проблеме с набором крышек?» . Блог Гауэрса . 11 января 2011 г. Проверено 26 ноября 2016 г.

[tao-17] Jump up to: Перейти обратно: ^а ^б Тао, Теренс (23 февраля 2007 г.). «Открытый вопрос: наилучшие границы для наборов ограничений» . Что нового . Проверено 26 ноября 2016 г.

[18] «Экспоненциальная верхняя граница проблемы максимального набора» , редакция журнала Discrete Analysis , 5 июня 2016 г.

[19] Крут, Эрни ; Лев, Всеволод; Пах, Питер (2017), «Наборы без прогрессирования в $Z_{4}^{n}$ экспоненциально малы», Annals of Mathematics , 185 (1): 331–337, arXiv : 1605.01506 , Bibcode : 2016arXiv160501506C , doi : 10.4007/annals.2017.185.1.7 .

[20] Элленберг, Джордан С .; Гейсвейт, Дион (2017), «О больших подмножествах $\mathbb {F} _{q}^{n}$ без трехчленной арифметической прогрессии», Annals of Mathematics , Second Series, 185 (1): 339–343, arXiv : 1605.09223 , doi : 10.4007/annals.2017.185.1.8 , MR 3583358

[21] Дамен, Сандер Р.; Хёльцль, Йоханнес; Льюис, Роберт Ю. (2019), «Формализация решения проблемы ограничения количества», в Харрисоне, Джон; О'Лири, Джон; Толмач, Эндрю (ред.), 10-я Международная конференция по интерактивному доказательству теорем, ITP 2019, 9–12 сентября 2019 г., Портленд, Орегон, США , LIPIcs, vol. 141, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 15:1–15:19, arXiv : 1907.01449 , doi : 10.4230/LIPIcs.ITP.2019.15

[22] Цзян, Чжи (2021), Явные верхние границы для задачи о наборе ограничений , arXiv : 2103.06481

[disjoint-23] Фоллетт, Майкл; Калаил, Кайл; МакМахон, Элизабет; Пелланд, Кэтрин; Вон, Роберт (2014), «Разделы $AG(4,3)$ на максимальные ограничения», Дискретная математика , 337 : 1–8, arXiv : 1302.4703 , doi : 10.1016/j.disc.2014.08.002 , MR 3262358

[24] Хартнетт, Кевин. «Математики начинают приручать дикую задачу о «подсолнухе»» . Журнал Кванта . Проверено 22 октября 2019 г.

[25] Калай, Гил (17 мая 2016 г.), «Экстренный пост Polymath 10 5: гипотеза Эрдоша-Семереди о подсолнухе теперь доказана» , Комбинаторика и многое другое .

[26] Блазиак, Иона; Черч, Томас; Кон, Генри; Грочоу, Джошуа А.; Уманс, Крис (2016), «О наборах ограничений и теоретико-групповом подходе к умножению матриц», Discrete Analysis , arXiv : 1605.06702 , Bibcode : 2016arXiv160506702B , doi : 10.19086/da.1245 .

[27] Хилл, Рэймонд (1978), «Шапики и коды», Дискретная математика , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR 0523299 .

[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]

[27]