гипотеза Келлера

В геометрии гипотеза Келлера — это гипотеза о том, что в любой мозаике $n$ -мерного евклидова пространства идентичными гиперкубами есть два гиперкуба, которые имеют общую целую $(n - 1)$ -мерную грань друг с другом. Например, в любой мозаике плоскости идентичными квадратами некоторые два квадрата должны иметь общую целую грань, как это сделано на иллюстрации.

Эта гипотеза была выдвинута Оттом-Генрихом Келлером (1930), в честь которого она и названа. Прорыв Лагариаса и Шора (1992) показал, что она ложна в десяти или более измерениях, и после последующих уточнений теперь известно, что она верна в пространствах размерности не более семи и ложна во всех более высоких измерениях. Доказательства этих результатов используют переформулировку проблемы в терминах кликового числа определенных графов, теперь известных как графы Келлера .

Связанная с этим гипотеза о кубической мозаике решетки Минковского утверждает, что всякий раз, когда мозаика пространства одинаковыми кубами имеет дополнительное свойство, что центры кубов образуют решетку , некоторые кубы должны встречаться лицом к лицу. Это было доказано Дьёрдем Хайошем в 1942 году.

Сабо (1993), Шор (2004) и Зонг (2005) дают обзоры работ по гипотезе Келлера и связанным с ней проблемам.

Заявление

Тесселяция или мозаика евклидова пространства, интуитивно, является семейством подмножеств, которые покрывают все пространство без перекрытия. Более формально, семейство замкнутых множеств , называемых плитками , образует мозаику, если их объединение является всем пространством и каждые два различных множества в семействе имеют непересекающиеся внутренности. Говорят, что мозаика моноэдральная , если все плитки имеют одинаковую форму (они конгруэнтны друг другу). Гипотеза Келлера касается моноэдральных мозаик, в которых все плитки являются гиперкубами той же размерности, что и пространство. Как формулирует проблему Сабо (1986), кубическая мозаика — это мозаика из конгруэнтных гиперкубов, в которой плитки дополнительно должны быть переносами друг друга без какого-либо вращения или, что эквивалентно, иметь все свои стороны параллельно осям координат пространства. Не каждая мозаика из конгруэнтных кубов обладает этим свойством; например, трехмерное пространство может быть замощено двумерными листами кубов, которые скручены под произвольными углами по отношению друг к другу. Формулируя ту же проблему, Шор (2004) вместо этого рассматривает все замощения пространства конгруэнтными гиперкубами и утверждает, без доказательства, что предположение о том, что кубы параллельны осям, может быть добавлено без потери общности.

n -мерный гиперкуб имеет $2$ $n$ граней размерности $n$ $- 1 , которые сами по себе являются гиперкубами; например, квадрат$ $имеет$ четыре ребра, а трехмерный куб имеет шесть квадратных граней. Две плитки в кубической мозаике (определенной любым из вышеперечисленных способов) встречаются лицом к лицу, если существует ( $n$ $- 1$ )-мерный гиперкуб, который является гранью их обоих. Гипотеза Келлера заключается в утверждении, что каждая кубическая мозаика имеет по крайней мере одну пару плиток, которые встречаются лицом к лицу таким образом. ^[1]

Первоначальная версия гипотезы, выдвинутая Келлером, была для более сильного утверждения: каждая кубическая мозаика имеет столбец кубов, все из которых встречаются лицом к лицу. Эта версия проблемы верна или ложна для тех же измерений, что и ее более распространенная формулировка. ^[2] Необходимой частью гипотезы является то, что все кубы в мозаике должны быть конгруэнтны друг другу, поскольку если допускаются кубы неравных размеров, то пифагорейская мозаика будет образовывать контрпример в двух измерениях.

Гипотеза в том виде, в котором она сформулирована, не требует, чтобы все кубы в мозаике встречались лицом к лицу с другими кубами. Хотя мозаики из конгруэнтных квадратов на плоскости обладают более сильным свойством, что каждый квадрат встречается ребром к ребру с другим квадратом, некоторые из плиток в мозаиках гиперкуба более высокой размерности могут не встречаться лицом к лицу ни с одной другой плиткой. Например, в трех измерениях структура тетрастикс , образованная тремя перпендикулярными наборами квадратных призм, может быть использована для построения кубической мозаики, комбинаторно эквивалентной структуре Уэйра–Фелана , в которой одна четверть кубов (те, которые не являются частью какой-либо призмы) окружены двенадцатью другими кубами, не встречаясь ни с одним из них лицом к лицу. ^[3]

Теоретико-групповая переформулировка

Гипотеза Келлера была доказана Перроном (1940a, 1940b) как верная в размерностях не более шести . Опровержение гипотезы Келлера для достаточно больших размерностей прошло через ряд редукций, которые превратили ее из проблемы геометрии мозаик в проблему теории групп и, оттуда, в проблему теории графов . ^[1]

Хайош (1949) впервые переформулировал гипотезу Келлера в терминах факторизаций абелевых групп . Он показывает, что если есть контрпример к гипотезе, то можно предположить, что это периодическая мозаика кубов с целочисленной длиной стороны и целочисленными положениями вершин; таким образом, при изучении гипотезы достаточно рассматривать мозаики этой специальной формы. В этом случае группа целочисленных переносов по модулю переносов, сохраняющих мозаику, образует абелеву группу, и некоторые элементы этой группы соответствуют положениям плиток. Хайош определяет семейство подмножеств $A i$ абелевой группы как факторизацию, если каждый элемент группы имеет уникальное выражение в виде суммы $a 0 + a 1 + ...$ , где каждый $a i$ принадлежит $A i$ . С этим определением переформулированная гипотеза Хайоша заключается в том, что всякий раз, когда абелева группа имеет факторизацию, в которой первое множество $A 0$ может быть произвольным, но каждое последующее множество $A i$ принимает специальную форму ${0, g i, 2 g i, 3 g i, ..., (| A i | - 1) g i}$ для некоторого элемента $g i$ из $A i$ , то по крайней мере один элемент $| A i | g i$ должен принадлежать $A 0 - A 0$ ( множеству разности A $0 с$ самим собой). ^[1]

Сабо (1986) показал, что любая мозаика, которая образует контрпример к гипотезе, может считаться имеющей еще более специальную форму: кубы имеют длину стороны, равную степени двойки, и целочисленные координаты вершин, и мозаика является периодической с периодом, вдвое превышающим длину стороны куба в каждом направлении координат. Основываясь на этом геометрическом упрощении, он также упростил групповую теоретико-формулировку Хайоша, показав, что достаточно рассматривать абелевы группы, которые являются прямыми суммами циклических групп четвертого порядка, с каждым $q i = 2$ .

Графики Келлера

Корради и Сабо (1990) переформулировали результат Сабо как условие о существовании большой клики в некотором семействе графов, которые впоследствии стали известны как графы Келлера . Точнее, вершинами графа Келлера размерности $n$ являются $4 n$ элементов $(m 1,..., m n),$ где каждый $m$ равен 0, 1, 2 или 3. Две вершины соединены ребром, если они отличаются по крайней мере двумя координатами и отличаются ровно на два по крайней мере одной координате. Корради и Сабо показали, что максимальная клика в этом графе имеет размер не более $2 n$ , и если существует клика такого размера, то гипотеза Келлера ложна. При наличии такой клики можно образовать покрытие пространства кубами со стороной два, центры которых имеют координаты, которые, взятые по модулю четыре, являются вершинами клики. Условие того, что любые две вершины клики имеют координату, отличающуюся на два, подразумевает, что кубы, соответствующие этим вершинам, не перекрываются. Условие того, что вершины отличаются на две координаты, подразумевает, что эти кубы не могут встретиться лицом к лицу. Условие того, что клика имеет размер $2 n,$ подразумевает, что кубы в пределах любого периода мозаики имеют тот же общий объем, что и сам период. Вместе с тем фактом, что они не перекрываются, это подразумевает, что кубы, размещенные таким образом, заполняют пространство, не встречаясь лицом к лицу. ^[4]

Лагариас и Шор (1992) опровергли гипотезу Келлера, найдя клику размера 2 ¹⁰ в графе Келлера размерности 10. Эта клика приводит к нелицевой мозаике в размерности 10, и ее копии могут быть сложены (смещены на половину единицы в каждом направлении координат) для получения нелицевой мозаики в любой более высокой размерности. Аналогично, Макки (2002) нашел клику размера 2 ⁸ в графе Келлера размерности восемь, приводящую таким же образом к нелицевой мозаике в размерности 8 и (путем сложения) в размерности 9.

Впоследствии Деброни и др. (2011) показали, что граф Келлера размерности семь имеет максимальную клику размера 124. Поскольку это меньше, чем 2 ⁷ = 128, теоретико-графовая версия гипотезы Келлера верна в семи измерениях. Однако перевод из кубических мозаик в теорию графов может изменить размерность проблемы, поэтому этот результат не решает геометрическую версию гипотезы в семи измерениях. Наконец, 200-гигабайтное компьютерное доказательство в 2019 году использовало графы Келлера, чтобы установить, что гипотеза верна в семи измерениях. ^[5] Таким образом, вопрос, поставленный Келлером, можно считать решенным: гипотеза верна в семи измерениях или меньше, но ложна, когда измерений больше семи. ^[6]

Размеры максимальных клик в графах Келлера размерностей 2, 3, 4, 5 и 6 составляют соответственно 2, 5, 12, 28 и 60. Графы Келлера размерностей 4, 5 и 6 были включены в набор «графов задач DIMACS», часто используемых в качестве эталона для алгоритмов поиска клик . ^[7]

Связанные проблемы

Как описывает Сабо (1993), Герман Минковский пришел к частному случаю гипотезы о кубической мозаике из проблемы диофантовых приближений . Одним из следствий теоремы Минковского является то, что любая решетка (нормализованная так, чтобы ее определитель был равен единице) должна содержать ненулевую точку, чебышевское расстояние которой до начала координат не превышает единицы. Решетки, не содержащие ненулевой точки с чебышевским расстоянием строго меньше единицы, называются критическими , а точки критической решетки образуют центры кубов в кубической мозаике. Минковский выдвинул гипотезу в 1900 году, что всякий раз, когда кубическая мозаика имеет свои кубы, центрированные в точках решетки таким образом, она должна содержать два куба, которые встречаются лицом к лицу. Если это верно, то (из-за симметрии решетки) каждый куб в мозаике должен быть частью столбца кубов, а поперечные сечения этих столбцов образуют кубическую мозаику на одно меньшее измерение. Рассуждая таким образом, Минковский показал, что (предполагая истинность своей гипотезы) каждая критическая решетка имеет базис, который может быть выражен как треугольная матрица с единицами на главной диагонали и числами, меньшими единицы, отстоящими от диагонали. Дьёрдь Хайош доказал гипотезу Минковского в 1942 году, используя теорему Хайоша о факторизации абелевых групп, аналогичный метод теории групп тому, который он позже применил к более общей гипотезе Келлера. ^[8]

Гипотеза Келлера является вариантом гипотезы Минковского, в которой условие, что центры кубов образуют решетку, ослаблено. Вторая связанная гипотеза, выдвинутая Фуртвенглером в 1936 году, вместо этого ослабляет условие, что кубы образуют мозаику. Фуртвенглер задался вопросом, должна ли система кубов, центрированных на точках решетки, образующих $k$ -кратное покрытие пространства (то есть все, кроме подмножества с нулевой мерой, точек в пространстве должны быть внутренними ровно для $k$ кубов), обязательно иметь два куба, встречающихся лицом к лицу. Гипотеза Фуртвенглера верна для двух- и трехмерного пространства, но Хайош нашел четырехмерный контрпример в 1938 году. Робинсон (1979) охарактеризовал комбинации $k$ и размерности $n$ , которые допускают контрпример. Кроме того, объединяя гипотезы Фуртвенглера и Келлера, Робинсон показал, что $k$ -кратные квадратные покрытия евклидовой плоскости должны включать два квадрата, которые встречаются ребром к ребру. Однако для каждого $k > 1$ и каждого $n > 2$ существует $k$ -кратная мозаика $n$ -мерного пространства кубами без общих граней. ^[9]

Как только контрпримеры к гипотезе Келлера стали известны, стало интересно спросить о максимальной размерности общей грани, которая может гарантированно существовать в кубической мозаике. Когда размерность $n$ не превышает семи, эта максимальная размерность равна просто $n - 1$ , согласно доказательствам гипотезы Келлера для этих малых размерностей, а когда $n$ не менее восьми, эта максимальная размерность равна не более $n - 2$ . Лагариас и Шор (1994) показали, что она не превышает $n - \sqrt n /3$ , что сильнее для десяти и более размерностей.

Иосевич и Педерсен (1998) и Лагариас, Ридс и Ванг (2000) обнаружили тесную связь между разбиением куба на мозаики и спектральной теорией квадратично -интегрируемых функций на кубе.

Дютур Сикирич, Ито и Поярков (2007) используют клики в графах Келлера, которые являются максимальными , но не максимальными, для изучения упаковок кубов в пространстве, которое нельзя расширить путем добавления дополнительных кубов.

В 1975 году Людвиг Данцер и независимо Бранко Грюнбаум и GC Shephard нашли мозаику трехмерного пространства параллелепипедами с углами при гранях 60° и 120°, в которой никакие два параллелепипеда не имеют общей грани. ^[10]

Примечания

^ abc Сабо (1993); Шор (2004); Зонг (2005)
^ Лысаковская и Пшеславский (2011, 2012).
^ Конвей, Берджил и Гудман-Штраус (2008).
^ Корради и Сабо (1990).
^ Бракензик и др. (2020).
^ Хартнетт (2020).
^ Джонсон и Трик (1996); Деброни и др. (2011), «Графы Келлера входят в эталонный набор задач клик из DIMACS clique challenge, и они кажутся особенно сложными для алгоритмов клик».
^ Сабо (1993).
^ Сабо (1982).
^ Грюнбаум и Шепард (1980).

Ссылки

Бракензик, Джошуа; Heule, Марин ; Макки, Джон; Нарваес, Дэвид (2020), «Разрешение гипотезы Келлера», в Пельтье, Николя; Софрони-Стоккерманс, Виорика (ред.), Автоматизированное рассуждение: 10-я Международная совместная конференция, IJCAR 2020, Париж, Франция, 1–4 июля 2020 г., Материалы, Часть I , Конспекты лекций по информатике, том. 12166, Springer, стр. 48–65, arXiv : 1910.03740 , doi : 10.1007/978-3-030-51074-9_4, ISBN 978-3-030-51073-2, S2CID 203951899
Конвей, Джон Х.; Берджил, Хайди; Гудман-Штраус, Хаим (2008), «Понимание ирландских пузырей», Симметрии вещей , Уэллсли, Массачусетс: AK Peters, стр. 351, ISBN 978-1-56881-220-5, МР 2410150
Корради, К.; Сабо, С. (1990), «Комбинаторный подход к гипотезе Келлера», Periodica Mathematica Hungarica. Журнал Математического общества Яноша Бойяи , 21 (2): 95–100, doi : 10.1007/BF01946848, MR 1070948, S2CID 121453908.
Деброни, Дженнифер; Эблен, Джон Д.; Лэнгстон, Майкл А .; Шор, Питер ; Мирволд, Венди ; Вирапурадж, Динеш (2011), «Полное разрешение проблемы максимальной клики Келлера» (PDF) , Труды 22-го симпозиума ACM-SIAM по дискретным алгоритмам , стр. 129–135, doi : 10.1137/1.9781611973082.11, hdl : 1721.1/81184 , ISBN 978-0-89871-993-2, S2CID 15797721.
Дютур Сикирич, Матье; Ито, Йошиаки; Поярков, Алексей (2007), «Упаковки кубов, второй момент и дырки», European Journal of Combinatorics , 28 (3): 715–725, arXiv : math/0509100 , doi : 10.1016/j.ejc.2006.01.008, MR 2300752, S2CID 15876010.
Грюнбаум, Бранко ; Шепард, GC (1980), «Мозаики с конгруэнтными плитками», Бюллетень Американского математического общества , 3 (3): 951–973, doi : 10.1090/S0273-0979-1980-14827-2 , MR 0585178.
Хайос, Г. (1949), «Сур ла факторизация групп животных», Ческословенская академия вед. Časopis Pro Pěstování Matematiky , 74 : 157–162, MR 0045727.
Хартнетт, Кевин (19 августа 2020 г.), «Компьютерный поиск решает 90-летнюю математическую задачу», Quanta Magazine.
Иосевич, Алекс; Педерсен, Стин (1998), «Спектральные и мозаичные свойства единичного куба», International Mathematics Research Notices , 1998 (16): 819–828, arXiv : math/0104093 , doi : 10.1155/S1073792898000506 , MR 1643694, S2CID 14232561.
Джонсон, Дэвид С.; Трик , Майкл А. (1996), Клики, раскраска и выполнимость: вторая задача по внедрению DIMACS, семинар, 11–13 октября 1993 г. , Бостон, Массачусетс, США: Американское математическое общество, ISBN 0-8218-6609-5. См., в частности, страницы 43, 114, 147, 156 и 161–163, описывающие различные результаты вычислений на графах Келлера, включенных в этот набор задач.
Келлер, О. -Х. (1930), «Über die lückenlose Erfüllung des Raumes mit Würfeln», Journal für die reine und angewandte Mathematik (на немецком языке), 1930 (163): 231–248, doi : 10.1515/crll.1930.163.231, JFM 56.1120.01 , S2CID 199547028.
Лагариас, Джеффри С .; Ридс, Джеймс А.; Ван, Ян (2000), «Ортонормированные базы экспонент для -куба », Duke Mathematical Journal , 103 (1): 25–37, CiteSeerX 10.1.1.207.4194 , doi : 10.1215/S0012-7094-00-10312- 2, МР 1758237 $n$ .
Lagarias, Jeffrey C. ; Shor, Peter W. (1992), «Гипотеза Келлера о кубической мозаике ложна в больших размерностях», Bulletin of the American Mathematical Society , New Series, 27 (2): 279–283, arXiv : math/9210222 , Bibcode :1992math.....10222L, doi :10.1090/S0273-0979-1992-00318-X, MR 1155280, S2CID 6390600.
Lagarias, JC ; Shor, PW (1994), "Кубические мозаики и нелинейные коды", Discrete and Computational Geometry , 11 (4): 359–391, doi : 10.1007/BF02574014 , MR 1273224 $\mathbb {R} ^{n}$ .
Лысаковская, Магдалена; Пржеславский, Кшиштоф (2011), «О структуре кубических мозаик и нерасширяемых систем кубов в низких размерностях», Европейский журнал комбинаторики , 32 (8): 1417–1427, doi : 10.1016/j.ejc.2011.07.003.
Лысаковская, Магдалена; Пржеславский, Кшиштоф (2012), "Гипотеза Келлера о существовании столбцов в кубических мозаиках ", Advances in Geometry , 12 (2): 329–352, arXiv : 0809.1960 , doi : 10.1515/advgeom.2011.055, MR 2911153, S2CID 14016886 $\mathbb {R} ^{n}$
Макки, Джон (2002), «Кубическая мозаика размерности восемь без общих граней», Дискретная и вычислительная геометрия , 28 (2): 275–279, doi : 10.1007/s00454-002-2801-9 , MR 1920144.
Перрон, Оскар (1940a), «Über lückenlose Ausfüllung des - Dimensionen Raumes durch kongruente Würfel», Mathematische Zeitschrift , 46 : 1–26, doi : 10.1007/BF01181421 , MR 0003041, S2CID 186236462 $n$ .
Перрон, Оскар (1940b), «Über lückenlose Ausfüllung des - Dimensionen Raumes durch kongruente Würfel. II», Mathematische Zeitschrift , 46 : 161–180, doi : 10.1007/BF01181436 , MR 0006068, S2CID 123877436 $n$ .
Робинсон, Рафаэль М. (1979), «Множественные мозаики -мерного пространства единичными кубами», Mathematische Zeitschrift , 166 (3): 225–264, doi : 10.1007/BF01214145 , MR 0526466, S2CID 123242152 $n$ .
Шор, Питер (2004), Гипотезы Минковского и Келлера о замощении куба, Конспект лекций для серии лекций по математике IAP.
Сабо, Шандор (1982), «Множественные мозаики кубами без общих граней» (PDF) , Aequationes Mathematicae , 25 (1): 83–89, doi : 10.1007/BF02189600, MR 0716380, S2CID 122364522.
Сабо, Шандор (1986), «Редукция гипотезы Келлера», Periodica Mathematica Hungarica. Журнал Математического общества Яноша Бойяи , 17 (4): 265–277, doi : 10.1007/BF01848388, MR 0866636, S2CID 120163301.
Сабо, Шандор (1993), «Разбиение куба как вклад алгебры в геометрию», Beiträge zur Algebra und Geometrie , 34 (1): 63–75, MR 1239279.
Зонг, Чуаньмин (2005), «Что известно о единичных кубах», Бюллетень Американского математического общества , Новая серия, 42 (2): 181–211, doi : 10.1090/S0273-0979-05-01050-5 , MR 2133310.