В геометрии , гипотеза Келлера является гипотеза , что в любом черепицей из п - мерного евклидова пространства с помощью идентичных гиперкубов , есть два гиперкубы , которые разделяют целой ( п - 1) -мерную грань друг с другом. Например, в любой мозаике плоскости одинаковыми квадратами некоторые два квадрата должны иметь общее ребро, как на иллюстрации.
Эта гипотеза была введена Отт-Генрихом Келлером ( 1930 ), в честь которого она названа. Прорыв Лагариаса и Шора ( 1992 ) показал, что оно ложно в десяти или более измерениях, и после последующих уточнений теперь известно, что оно истинно в пространствах размерности не более семи и ложно во всех более высоких измерениях. Доказательства этих результатов используют переформулировку проблемы в терминах кликового числа некоторых графов, теперь известных как графы Келлера .
Связанная с этим гипотеза о мозаике кубов решетки Минковского утверждает, что всякий раз, когда мозаика пространства идентичными кубами обладает дополнительным свойством, заключающимся в том, что центры кубов образуют решетку , некоторые кубы должны встречаться лицом к лицу. Это было доказано Дьёрдь Хаджошем в 1942 году.
Сабо (1993) , Шор (2004) и Зонг (2005) дают обзоры работ по гипотезе Келлера и связанным с ней проблемам.
Заявление
Тесселяции или разбиение евклидова пространства, интуитивно, семейство подмножеств , которые охватывают все пространство без перекрытия. Более формально, семейство замкнутых множеств , называемых плитками , образует мозаику, если их объединение представляет собой все пространство и каждые два различных набора в семействе имеют непересекающиеся внутренние части. Мозаика называется моноэдральной, если все плитки имеют одинаковую форму (они конгруэнтны друг другу). Гипотеза Келлера касается моноэдральных мозаик, в которых все плитки являются гиперкубами той же размерности, что и пространство. Как Сабо (1986) формулирует проблему, куб Черепица является разбиением на сравнимых гиперкуб , в котором плитка дополнительно требуется , чтобы все они переводы друг от друга без какого - либо вращения, или , что эквивалентна, чтобы все их сторон параллельна осям координат пространства. Не все мозаики конгруэнтными кубами обладают этим свойством; например, трехмерное пространство может быть выложено плиткой двухмерных листов кубов, скрученных под произвольными углами относительно друг друга. Формулируя ту же проблему, Шор (2004) вместо этого рассматривает все мозаики пространства конгруэнтными гиперкубами и без доказательства утверждает, что предположение, что кубы параллельны осям, может быть добавлено без ограничения общности.
П - мерный гиперкуб имеет 2 п граней размерности п - 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 | г я должен принадлежать к 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. Эта клика приводит к не-лицом к лицу замощению в размерности 10, и его копии можно складывать ( смещение на половину единицы в каждом координатном направлении), чтобы создавать мозаику без лицевой стороны в любом более высоком измерении. Точно так же Mackey (2002) обнаружил клику размером 2 8 в графе Келлера размерности восемь, что таким же образом приводит к мозаике без непосредственного контакта в размерности 8 и (путем укладки) в размерности 9.
Впоследствии Debroni et al. (2011) показали, что граф Келлера размерности семь имеет максимальную клику размером 124 <2 7 . Поскольку это меньше 2 7 , теоретико-графовая версия гипотезы Келлера верна в семи измерениях. Однако переход от мозаики кубов к теории графов может изменить размерность проблемы, поэтому этот результат не решает геометрическую версию гипотезы в семи измерениях. Наконец, 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 - √ n / 3 , более сильное для десяти или более измерений.
Iosevich & Pedersen (1998) и Lagarias, тростники и Ван (2000) обнаружили тесную связь между кубиком паркетами и спектральной теорией с квадратом функций , интегрируемых на кубе.
Дутур Сикирич, Ито и Поярков (2007) используют клики в графах Келлера, которые являются максимальными, но не максимальными, для изучения упаковки кубов в пространство, которые не могут быть расширены путем добавления каких-либо дополнительных кубов.
В 1975 году Людвиг Данцер и независимо друг от друга Бранко Грюнбаум и Г.К. Шепард обнаружили мозаику трехмерного пространства параллелепипедами с углами граней 60 ° и 120 °, в которых никакие два параллелепипеда не имеют общей грани. [10]
Заметки
- ^ а б в Сабо (1993) ; Шор (2004) ; Цзун (2005)
- ^ Ysakowska and Przesławski ( 2011 , 2012 ).
- ^ Conway, Burgiel & Goodman-Строс (2008) .
- ^ CORRADI & Сабо (1990) .
- ^ Brakensiek et al. (2020) .
- ^ Хартнетт (2020) .
- ↑ Johnson & Trick (1996) ; Debroni et al. (2011) , «Графы Келлера входят в эталонный набор задач клики из задачи клики DIMACS, и они кажутся особенно сложными для алгоритмов клики».
- ↑ Сабо (1993) .
- Перейти ↑ Szabó (1982) .
- ^ Грюнбаум и Шепард (1980) .
Рекомендации
- Бракензик, Джошуа; Heule, Marijn ; Макки, Джон; Нарваэс, Дэвид (2020), «Разрешение гипотезы Келлера», в Пельтье, Николас; Софрони-Стоккерманс, Виорика (ред.), Автоматизированное рассуждение: 10-я международная совместная конференция, IJCAR 2020, Париж, Франция, 1–4 июля 2020 г., Труды, часть I , Лекционные заметки по компьютерным наукам, 12166 , Springer, стр. 48 –65, arXiv : 1910.03740 , doi : 10.1007 / 978-3-030-51074-9_4 , S2CID 203951899
- Конвей, Джон Х .; Берджел, Хайди; Гудман-Штраус, Хаим (2008), «Понимание ирландских пузырей», Симметрии вещей , Уэлсли, Массачусетс: AK Peters, стр. 351, ISBN 978-1-56881-220-5, MR 2410150
- Corrádi, K .; Сабо, С. (1990), "Комбинаторный подход к гипотезе Келлера", Periodica Mathematica Hungarica. Журнал Бойяи математического общества , 21 (2): 95-100, DOI : 10.1007 / BF01946848 , МР 1070948 , S2CID 121453908.
- Деброни, Дженнифер; Эблен, Джон Д .; Лэнгстон, Майкл А .; Шор, Петр ; Мирволд, Венди ; Weerapurage Динеш (2011), "Полное решение проблемы максимальной клики Keller" (PDF) , Труды 22 - го ACM-SIAM симпозиум по дискретным алгоритмам , С. 129-135,. Дои : 10,1137 / 1.9781611973082.11 , ЛВП : 1721.1 / 81184 , S2CID 15797721.
- Дютур Сикирич, Матье; Ито, Йошиаки; Поярков, Алексей (2007), «Кубические упаковки, второй момент и дыры», Европейский журнал комбинаторики , 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 , МР 0585178.
- Hajós, G. (1949), "Sur la factorisation des groupes abéliens", Československá Akademie Věd. Časopis Pro Pěstování Matematiky , 74 : 157–162, MR 0045727.
- Хартнетт, Кевин (19 августа 2020 г.), «Компьютерный поиск решает 90-летнюю математическую проблему» , журнал Quanta.
- Иосевич Алексей; Педерсен, Стин (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 умереть lückenlose Erfüllung де Raumes Würfeln Массачусетский технологический институт", Journal für умереть Reine унд Angewandte Mathematik (на немецком языке ), 1930 (163): 231-248, DOI : 10,1515 / crll.1930.163.231 , JFM 56.1120.01 , S2CID 199547028.
- Лагариас, Джеффри К .; Ридс, Джеймс А .; Ван, Ян (2000), "Ортонормированные базисы экспонент для-куба», Герцог математический журнал , 103 (1): 25-37, CiteSeerX 10.1.1.207.4194 , DOI : 10,1215 / S0012-7094-00-10312-2 , МР 1758237.
- Лагариас, Джеффри К .; Шор, Питер У. (1992), «Гипотеза Келлера о разбиении куба неверна в больших измерениях», Бюллетень Американского математического общества , Новая серия, 27 (2): 279–283, arXiv : math / 9210222 , Bibcode : 1992math ..... 10222L , DOI : 10,1090 / S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600.
- Lagarias, JC ; Шор, PW (1994), "Кубикии нелинейные коды», Дискретные и Вычислительная геометрия , 11 (4): 359-391, DOI : 10.1007 / BF02574014 , МР 1273224.
- Лысаковская, Магдалена; Пшеславский, Кшиштоф (2011), «О структуре кубических мозаик и нерасширяемых систем кубов в малых размерностях», Европейский журнал комбинаторики , 32 (8): 1417–1427, DOI : 10.1016 / j.ejc.2011.07.003.
- Лысаковская, Магдалена; Пшеславский, Кшиштоф (2012), "Гипотеза Келлера о существовании столбцов в кубических мозаиках», Успехи в геометрии , 12 (2): 329-352, Arxiv : 0809.1960 , DOI : 10,1515 / advgeom.2011.055 , MR 2911153
- Макки, Джон (2002), "Куб черепицей размерности восемь, без facesharing", Дискретная и вычислительная геометрия , 28 (2): 275-279, DOI : 10.1007 / s00454-002-2801-9 , MR 1920144.
- Перрон, Оскар (1940a), "Über lückenlose Ausfüllung des-dimensionalen Raumes durch kongruente Würfel ", Mathematische Zeitschrift , 46 : 1–26, DOI : 10.1007 / BF01181421 , MR 0003041 , S2CID 186236462.
- Перрон, Оскар (1940b), "Über lückenlose Ausfüllung des-dimensionalen Raumes durch kongruente Würfel. II », Mathematische Zeitschrift , 46 : 161–180, DOI : 10.1007 / BF01181436 , MR 0006068 , S2CID 123877436.
- Робинсон, Рафаэль М. (1979), "Множественные мозаикимерное пространство с помощью единичных кубов», Mathematische Zeitschrift , 166 (3): 225-264, DOI : 10.1007 / BF01214145 , МР 0526466 , S2CID 123242152.
- Шор, Питер (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 , МР 0866636 , S2CID 120163301.
- Сабо, Шандор (1993), «Кубические мозаики как вклад алгебры в геометрию» , Beiträge zur Algebra und Geometrie , 34 (1): 63–75, MR 1239279.
- Цзун Chuanming (2005), "Что известно о единичных кубиков", Бюллетень Американского математического общества , Новая серия, 42 (2): 181-211, DOI : 10,1090 / S0273-0979-05-01050-5 , MR 2133310.