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

О гипотезе Келлера о полиномиальных отображениях см. «Гипотезу Якобиана» .

В этом мозаике плоскости конгруэнтными квадратами зеленые и фиолетовые квадраты встречаются от края до края, как и синие и оранжевые квадраты.

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

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

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

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

Заявление

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

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

Плитка Пифагора показывает, что неравные квадраты могут замостить плоскость, не пересекаясь от края к краю.

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

Сформулированная гипотеза не требует, чтобы все кубы в мозаике встречались лицом к лицу с другими кубами. Хотя мозаика из конгруэнтных квадратов на плоскости обладает более сильным свойством, заключающимся в том, что каждый квадрат пересекается от края до края с другим квадратом, некоторые плитки в мозаиках гиперкуба более высокой размерности могут не пересекаться лицом к лицу с какой-либо другой плиткой. Например, в трех измерениях структура тетрастикса , образованная тремя перпендикулярными наборами квадратных призм, может использоваться для построения мозаики куба, комбинаторно эквивалентной структуре Вейра-Фелана , в которой четверть кубов (тех, которые не являются частью какого-либо призма) окружены двенадцатью другими кубами, но ни один из них не встречается лицом к лицу.

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

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

Хайос (1949) впервые переформулировал гипотезу Келлера в терминах факторизации абелевых групп . Он показывает, что если существует контрпример к гипотезе, то его можно считать периодической мозаикой кубов с целой длиной стороны и целыми положениями вершин; таким образом, при изучении гипотезы достаточно рассмотреть мозаики этого специального вида. В этом случае группа целочисленных сдвигов по модулю переводов, сохраняющих разбиение, образует абелеву группу, и определенные элементы этой группы соответствуют положениям плиток. Хайос определяет семейство подмножеств A _i абелевой группы как факторизацию, если каждый элемент группы имеет уникальное выражение в виде суммы a ₀ + a ₁ + ... , где каждый a _i принадлежит A _i . С учетом этого определения переформулированная гипотеза Хайоса заключается в том, что всякий раз, когда абелева группа имеет факторизацию, в которой первый набор A ₀ может быть произвольным, но каждый последующий набор A _i принимает специальную форму {0, gi _, 2 g _i , 3 ​​g _i , ..., (| A _i | − 1) g _i } для некоторого элемента g _i of A _i , то хотя бы один элемент | А _я | g _i должен принадлежать A ₀ − A ₀ ( разностному множеству A 0 _самого себя).

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

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

Граф Келлера размерности два, изоморфный графу Клебша .

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

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

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

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

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

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

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

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

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

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

В 1975 году Людвиг Данцер и независимо Бранко Грюнбаум и Г.К. Шепард обнаружили мозаику трехмерного пространства из параллелепипедов с углами граней 60 ° и 120 °, в которых никакие два параллелепипеда не имеют общей грани.

Ссылки

• Бракензик, Джошуа; Хойле, Военно-морской флот ; Макки, Джон; Нарваес, Дэвид (2020), «Разрешение гипотезы Келлера», Пельтье, Николас; Софрони-Стоккерманс, Виорика (ред.), Автоматизированное рассуждение: 10-я Международная совместная конференция, IJCAR 2020, Париж, Франция, 1–4 июля 2020 г., Материалы, Часть I , Конспекты лекций по информатике, том. 12166, Спрингер, стр. 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), «Упаковки куба, второй момент и дырки», Европейский журнал комбинаторики , 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), «Сюр-ла-факторизация групп животных», Чехословацкая академия наук. Журнал по развитию математики , 74 : 157–162, MR   0045727 .
• Хартнетт, Кевин (19 августа 2020 г.), «Компьютерный поиск решает 90-летнюю математическую задачу» , журнал Quanta .
• Иосевич, Алекс; Педерсен, Стин (1998), «Спектральные и мозаичные свойства единичного куба», Международные уведомления о математических исследованиях , 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), «О полном заполнении пространства кубами», Журнал чистой и прикладной математики (на немецком языке), 1930 (163): 231–248, doi : 10.1515/crll.1930.163.231 , JFM   56.1120.01 , S2CID   199547028 .
• Лагариас, Джеффри С .; Ридс, Джеймс А.; Ван, Ян (2000), «Ортонормированные основы экспонент для $n$-cube», Duke Mathematical Journal , 103 (1): 25–37, CiteSeerX   10.1.1.207.4194 , doi : 10.1215/S0012-7094-00-10312-2 , MR   1758237 .
• Лагариас, Джеффри С .; Шор, Питер В. (1992), «Гипотеза Келлера о мозаике куба ложна в больших измерениях», Бюллетень Американского математического общества , New Series, 27 (2): 279–283, arXiv : math/9210222 , Bibcode : 1992math .....10222L , дои : 10.1090/S0273-0979-1992-00318-X , MR   1155280 , S2CID   6390600 .
• Лагариас, JC ; Шор, П.В. (1994), "Кубические мозаики $\mathbb {R} ^{n}$ и нелинейные коды», Дискретная и вычислительная геометрия , 11 (4): 359–391, doi : 10.1007/BF02574014 , MR   1273224 .
• Лысаковская, Магдалена; Пшеславский, Кшиштоф (2011), «О структуре мозаик кубов и нерасширяемых системах кубов малых размерностей», European Journal of Combinatorics , 32 (8): 1417–1427, doi : 10.1016/j.ejc.2011.07.003 .
• Лысаковская, Магдалена; Пшеславский, Кшиштоф (2012), «Гипотеза Келлера о существовании столбцов в мозаиках кубов $\mathbb {R} ^{n}$", Advances in Geometry , 12 (2): 329–352, arXiv : 0809.1960 , doi : 10.1515/advgeom.2011.055 , MR   2911153 , S2CID   14016886
• Макки, Джон (2002), «Куб восьмого измерения без разделения граней», Discrete and Computational Geometry , 28 (2): 275–279, doi : 10.1007/s00454-002-2801-9 , MR   1920144 .
• Перрон, Оскар (1940а), «О полном завершении $n$-мерное пространство конгруэнтными кубами», Mathematical Journal , 46 : 1–26, doi : 10.1007/BF01181421 , MR   0003041 , S2CID   186236462 .
• Перрон, Оскар (1940b), «О полном завершении $n$-мерное пространство через равные кубы. II", Mathematical Journal , 46 : 161–180, doi : 10.1007/BF01181436 , MR   0006068 , S2CID   123877436 .
• Робинсон, Рафаэль М. (1979), «Множественные мозаики $n$-мерное пространство единичными кубами», Mathematical Journal , 166 (3): 225–264, doi : 10.1007/BF01214145 , MR   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 , MR   0866636 , S2CID   120163301 .
• Сабо, Шандор (1993), «Разбиение куба как вклад алгебры в геометрию» , «Вклад в алгебру и геометрию» , 34 (1): 63–75, MR   1239279 .
• Цзун, Чуанмин (2005), «Что известно о единичных кубах», Бюллетень Американского математического общества , Новая серия, 42 (2): 181–211, doi : 10.1090/S0273-0979-05-01050-5 , MR   2133310 .