Набор крышек - Cap set

9 точек и 12 строк ${\displaystyle \mathbb {Z} _{3}^{2}}$, и набор крышек из 4 элементов (четыре желтых точки) в этом пространстве

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

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

пример

Полный набор из 81 карты изоморфный с теми из игры Набор показаны все возможные комбинации четырех функций. Рассматривая каждую группу 3 × 3 как плоскость, выровненную в 4-мерном пространстве, набор включает 3 карты в (4-мерном) ряду с циклическим переходом. Пример 20-карточного набор крышек заштрихован желтым.

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

Один из способов создать большой набор ограничений в игровом наборе - выбрать два из трех значений для каждой характеристики и положить лицом вверх каждую из карт, в каждой из которых используется только одно из этих двух значений. В результате будет набор из 16 карточек. В более общем плане та же стратегия приведет к установлению ограничений в ${\displaystyle \mathbb {Z} _{3}^{n}}$ размера ${\displaystyle 2^{n}}$. Однако в 1971 году Джузеппе Пеллегрино доказал, что четырехмерные наборы крышек имеют максимальный размер 20. С точки зрения набора этот результат означает, что в некоторых макетах из 20 карт нет линии, которую нужно собрать, но что каждый макет из 21 карты имеет как минимум одна линия.

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

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

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

Решение Пеллегрино для четырехмерной задачи о множестве крышек также приводит к более высоким нижним оценкам, чем ${\displaystyle 2^{n}}$ для любого более высокого измерения, которые были дополнительно улучшены Эдель (2004) приблизительно ${\displaystyle 2.2174^{n}}$.^[2]

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

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

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

В 2011 году Майкл Бейтман и Нетс Кац^[14] улучшил привязку к ${\displaystyle O(3^{n}/n^{1+\varepsilon })}$ с положительной константой ${\displaystyle \varepsilon }$. Гипотеза о наборе кепок была решена в 2016 году, когда Эрни Крут, Всеволод Лев и Петер Пал Пах опубликовали препринт по тесно связанной проблеме, который был быстро использован Джордан Элленберг и Дион Гийсвейт доказать верхнюю оценку ${\displaystyle 2.756^{n}}$ по шапке поставил проблему.^{[5][6][15][16][17]} В 2019 году Сандер Дамен, Йоханнес Хёльцль и Роб Льюис формализовали доказательство этой верхней границы в Доказательство теорем бережливого производства.^[18]

Приложения

Гипотеза подсолнечника

Основная статья: Подсолнечник (математика)

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

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

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

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

Основная статья: График игр

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

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

• Нет проблем с тремя рядами, проблема исключения трех элементов в строке в двумерной сетке

Рекомендации

1. Остин, Дэвид (август 2016 г.), "Игра. НАБОР. Полином.", Столбец функций, Американское математическое общество.
2. Эдель, Ив (2004), "Расширения обобщенных ограничений продукта", Конструкции, коды и криптография, 31 (1): 5–14, Дои:10.1023 / А: 1027365901231, Г-Н  2031694.
3. См., Например, Чепмен, Т. А. (1971), "Плотные сигма-компактные подмножества бесконечномерных многообразий", Труды Американского математического общества, 154: 399–426, Дои:10.1090 / s0002-9947-1971-0283828-7, Г-Н  0283828.
4. См., Например, Минькова Р. М. (1979), "Слабые пространства Коровкина", Академия Наук Союза ССР, 25 (3): 435–443, 477, Г-Н  0534099.
5. Кларрайх, Эрика (31 мая 2016 г.), «Доказательство простой игры ошеломляет математиков», Quanta
6. Грохов, Джошуа А. (2019), "Новые приложения полиномиального метода: гипотеза о множестве крышек и не только", Бюллетень Американского математического общества, 56: 29–64, Дои:10.1090 / бык / 1648, Г-Н  3886143
7. Браун, Т. С; Бюлер, Дж. П. (1984-03-01). «Линии подразумевают пространства в теории плотности Рамсея». Журнал комбинаторной теории, серия А. 36 (2): 214–220. Дои:10.1016/0097-3165(84)90006-2.
8. Браун, Т. С; Бюлер, Дж. П. (1984-03-01). «Линии подразумевают пространства в теории плотности Рамсея». Журнал комбинаторной теории, серия А. 36 (2): 214–220. Дои:10.1016/0097-3165(84)90006-2.
9. Франкл, П.; Грэм, Р. Л.; Рёдль, В. (1987). «О подмножествах абелевых групп без трехчленной арифметической прогрессии». Журнал комбинаторной теории. Серия А. 45 (1): 157–161. Дои:10.1016/0097-3165(87)90053-7. Г-Н  0883900.
10. Алон, Нога; Дубинер, Моше (1995). «Проблема решетки и аддитивная теория чисел». Комбинаторика. 15 (3): 301–309. Дои:10.1007 / BF01299737. ISSN  0209-9683.
11. Мешулам, Рой (1995-07-01). «О подмножествах конечных абелевых групп без 3-членных арифметических прогрессий». Журнал комбинаторной теории, серия А. 71 (1): 168–172. Дои:10.1016/0097-3165(95)90024-1.
12. "Что сложного в проблеме с ограничениями?". Журнал Гауэрса. 2011-01-11. Получено 2016-11-26.
13. «Открытый вопрос: наилучшие границы для наборов ограничений». Какие новости. 2007-02-23. Получено 2016-11-26.
14. Бейтман, Майкл; Кац, Сети (2012-01-01). «Новые границы наборов шапок». Журнал Американского математического общества. 25 (2): 585–613. arXiv:1101.5851. Дои:10.1090 / S0894-0347-2011-00725-X. ISSN  0894-0347.
15. Редакция (5 июня 2016 г.), «Экспоненциальная верхняя граница для задачи ограничения», Редакция, Дискретный анализ.
16. Крут, Эрни; Лев, Всеволод; Пач, Питер (2017), «Сеты без прогресса в ${\displaystyle Z_{4}^{n}}$ экспоненциально малы ", Анналы математики, 185 (1): 331–337, arXiv:1605.01506, Bibcode:2016arXiv160501506C, Дои:10.4007 / анналы.2017.185.1.7.
17. Элленберг, Джордан С.; Gijswijt, Dion (2017), "О больших подмножествах ${\displaystyle \mathbb {F} _{q}^{n}}$ без трехчленной арифметической прогрессии ", Анналы математики, Вторая серия, 185 (1): 339–343, arXiv:1605.09223, Дои:10.4007 / анналы.2017.185.1.8, Г-Н  3583358
18. Дахмен, Сандер; Хёльцль, Йоханнес; Льюис, Роберт (2019), Формализация решения проблемы набора ограничений, arXiv:1907.01449, Дои:10.4230 / LIPIcs.ITP.2019.15.
19. Хартнетт, Кевин. «Математики начинают решать проблему дикой природы« подсолнух »». Журнал Quanta. Получено 2019-10-22.
20. Калаи, Гил (17 мая 2016 г.), «Polymath 10 Emergency Post 5: Гипотеза Эрдоша-Семереди о подсолнечнике теперь доказана», Комбинаторика и не только.
21. Блазиак, Иона; Черч, Томас; Кон, Генри; Grochow, Joshua A .; Уманс, Крис (2016), «О наборах крышек и теоретико-групповом подходе к умножению матриц», Дискретный анализ, arXiv:1605.06702, Bibcode:2016arXiv160506702B, Дои:10.19086 / da.1245.
22. Хилл, Раймонд (1978), «Заголовки и коды», Дискретная математика, 22 (2): 111–137, Дои:10.1016 / 0012-365X (78) 90120-6, Г-Н  0523299.