Набор колпачков

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

В более общем смысле шапки определяются как подмножества конечного аффинного или проективного пространства без тройки в одной строке. ^[2]

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

Ссылки

^ ab Остин, Дэвид (август 2016 г.), «Игра. SET. Полиномиал.», Тематическая колонка , Американское математическое общество.
^ ab Edel, Yves (2004), «Расширения обобщенных пределов продукта», Designs, Codes and Cryptography , 31 (1): 5–14, doi :10.1023/A:1027365901231, MR 2031694.
^ См., например, Chapman, TA (1971), «Плотные сигма-компактные подмножества бесконечномерных многообразий», Transactions of the American Mathematical Society , 154 : 399–426, doi : 10.1090/s0002-9947-1971-0283828-7 , MR 0283828.
^ См., например, Минькова Р. М. (1979), "Слабые пространства Коровкина", Академия наук Союза ССР , 25 (3): 435–443, 477, MR 0534099..
^ abc Klarreich, Erica (31 мая 2016 г.), «Simple Set Game Proof Stuns Mathematicians», Quanta , заархивировано из оригинала 24 декабря 2016 г. , извлечено 2 августа 2016 г.
^ abc Grochow, Joshua A. (2019), «Новые приложения полиномиального метода: гипотеза о множестве крышек и далее», Бюллетень Американского математического общества , 56 : 29–64, doi : 10.1090/bull/1648 , MR 3886143
^ Пеллегрино, Джузеппе (1970). "Sul Massimo Ordine delle Calotte in $S_4,3$" [Максимальный порядок сферической шапки в $S_4,3$]. Le Matematiche (на итальянском языке). 25 : 149–157. ISSN 0373-3505.
^ Хилл, Р. (1983-01-01), Барлотти, А.; Чеккерини, П.В.; Таллини, Г. (ред.), «О 20-крышках Пеллегрино в S4, 3», North-Holland Mathematics Studies , Combinatorics '81 в честь Бениамино Сегре, т. 78, North-Holland, стр. 433–447 , получено 16 декабря 2023 г.
^ ab Brown, T. C ; Buhler, J. P (1984-03-01). "Линии подразумевают пространства в теории плотности Рамсея". Журнал комбинаторной теории . Серия A. 36 (2): 214–220. doi : 10.1016/0097-3165(84)90006-2 .
^ Tyrrell, Fred (2022). "Новые нижние границы для наборов крышек". Discrete Analysis . 2023 (20). arXiv : 2209.10045 . doi : 10.19086/da.91076 (неактивен 1 ноября 2024 г.) . Получено 9 января 2024 г.{{cite journal}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
^ Ромера-Паредес, Бернардино; Барекатаин, Мохаммадамин; Новиков, Александр; Балог, Матей; Кумар, М. Паван; Дюпон, Эмильен; Руис, Франциско Дж. Р.; Элленберг, Джордан С.; Ван, Пэнминг; Фаузи, Омар; Кохли, Пушмит; Фаузи, Альхуссейн (14.12.2023). «Математические открытия из программного поиска с большими языковыми моделями». Nature . 625 (7995): 468–475. doi : 10.1038/s41586-023-06924-6 . ISSN 1476-4687. PMC 10794145 . PMID 38096900.
^ Франкл, П.; Грэхем , Р.Л.; Рёдль , В. (1987). «О подмножествах абелевых групп без 3-членной арифметической прогрессии». Журнал комбинаторной теории . Серия A. 45 (1): 157–161. doi : 10.1016/0097-3165(87)90053-7 . MR 0883900.
^ Алон, Нога; Дубинер, Моше (1995). «Проблема точек решетки и аддитивная теория чисел». Combinatorica . 15 (3): 301–309. doi :10.1007/BF01299737. ISSN 0209-9683.
^ Мешулам, Рой (1995-07-01). «О подмножествах конечных абелевых групп без 3-членных арифметических прогрессий». Журнал комбинаторной теории . Серия A. 71 (1): 168–172. doi : 10.1016/0097-3165(95)90024-1 .
^ Бейтман, Майкл; Кац, Нетс (2012-01-01). «Новые границы для наборов крышек». Журнал Американского математического общества . 25 (2): 585–613. arXiv : 1101.5851 . doi : 10.1090/S0894-0347-2011-00725-X. ISSN 0894-0347.
^ "Что сложного в проблеме набора крышек?". Веблог Гауэрса . 2011-01-11 . Получено 2016-11-26 .
^ ab Tao, Terence (2007-02-23). "Открытый вопрос: лучшие границы для наборов крышек". Что нового . Получено 2016-11-26 .
^ «Экспоненциальная верхняя граница для проблемы набора крышек», редакционная статья, Дискретный анализ , 5 июня 2016 г..
^ Croot, Ernie ; Lev, Vsevolod; Pach, Peter (2017), «Progression-free sets in are exponentially small», Annals of Mathematics , 185 (1): 331–337, arXiv : 1605.01506 , Bibcode : 2016arXiv160501506C, doi : 10.4007/annals.2017.185.1.7 $Z_{4}^{n}$ .
^ Элленберг, Джордан С.; Гейсвейт, Дион (2017), «О больших подмножествах без трехчленной арифметической прогрессии», Annals of Mathematics , Вторая серия, 185 (1): 339–343, arXiv : 1605.09223 , doi : 10.4007/annals.2017.185.1.8, MR 3583358 $\mathbb {F} _{q}^{n}$
^ Дамен, Сандер Р.; Хёльцль, Йоханнес; Льюис, Роберт Ю. (2019), «Формализация решения проблемы ограничения количества», в Харрисоне, Джон; О'Лири, Джон; Толмач, Эндрю (ред.), 10-я Международная конференция по интерактивному доказательству теорем, ITP 2019, 9–12 сентября 2019 г., Портленд, Орегон, США , LIPIcs, vol. 141, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 15:1–15:19, arXiv : 1907.01449 , doi : 10.4230/LIPIcs.ITP.2019.15
^ Цзян, Чжи (2021), Явные верхние границы для проблемы набора крышек , arXiv : 2103.06481
^ Фоллетт, Майкл; Калаил, Кайл; Макмахон, Элизабет; Пелланд, Кэтрин; Вон, Роберт (2014), «Разбиения на максимальные шапки», Дискретная математика , 337 : 1–8, arXiv : 1302.4703 , doi : 10.1016/j.disc.2014.08.002 , MR 3262358 $АГ(4,3)$
^ Хартнетт, Кевин. «Математики начинают приручать дикую проблему «Подсолнух»». Журнал Quanta . Получено 22 октября 2019 г.
^ Калай, Джил (17 мая 2016 г.), «Полимат 10 Аварийный пост 5: Гипотеза Эрдеша-Семереди о подсолнухе теперь доказана», Комбинаторика и многое другое.
^ Блазиак, Джона; Чёрч, Томас; Кон, Генри; Грохоу, Джошуа А.; Уманс, Крис (2016), «О кэп-множествах и групповом теоретико-подходе к умножению матриц», Дискретный анализ , arXiv : 1605.06702 , Bibcode : 2016arXiv160506702B, doi : 10.19086/da.1245.
^ Хилл, Рэймонд (1978), «Caps and codes», Discrete Mathematics , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR 0523299.