Русская Википедия:Гипотеза Келлера
Гипотеза Келлера — выдвинутая Шаблон:IwШаблон:Sfn гипотеза о том, что в любой мозаике в евклидовом пространстве, состоящей из одинаковых гиперкубов, найдутся два куба, соприкасающиеся грань-к-грани. Например, как показано на рисунке, в любой мозаике на плоскости из одинаковых квадратов какие-то два квадрата должны соприкасаться ребро-к-ребру. Перрон доказал, что это верно в размерностях до 6Шаблон:SfnШаблон:Sfn; Бракензик с соавторами доказали верность гипотезы для размерности 7Шаблон:Sfn. Однако для бо́льших размерностей это неверно, как показали Лагариас и Шор для размерностей 10 и вышеШаблон:Sfn, Макей для размерностей 8 и вышеШаблон:Sfn, для чего использовали переформулировку задачи в терминах кликового числа некоторых графов, известных теперь как графы Келлера.
Связанная гипотеза Минковского о решётке кубической мозаики утверждает, что при заполнении пространства одинаковыми кубами с дополнительным свойством, что центры кубов образуют решётку, некоторые кубы должны соприкасаться грань-к-грани. Гипотеза была доказана Хайошем в 1942 году.
Определения
Семейство замкнутых множеств, называемых плитками, образует паркет или мозаику в евклидовом пространстве, если их объединение полностью заполняет пространство и любые два различных множества в семействе имеют непересекающиеся внутренние части. Говорят, что мозаика моноэдрична, если все её плитки конгруэнтны. Гипотеза Келлера относится к моноэдрическим мозаикам, в которых все плитки являются гиперкубами. Как сформулировал СабоШаблон:Sfn, кубическая мозаика — это мозаика из конгруэнтных гиперкубов, в которой требуется, чтобы все плитки являлись параллельным переносом друг друга без вращений, или, эквивалентно, все рёбра плиток должны быть параллельны осям координат. Не любая мозаика из конгруэнтных кубов имеет такое свойство. Например, трёхмерное пространство может быть замощено слоями кубов, которые повёрнуты относительно друг друга под произвольным углом. ШорШаблон:Sfn, напротив, определяет кубическую мозаику как произвольное замощение пространства гиперкубами и утверждает без доказательства, что параллельность сторон осям может быть потребована без потери общности.
Гиперкуб в n-мерном пространстве имеет 2n граней размерности n − 1, которые сами являются гиперкубами. Например, квадрат имеет четыре ребра, а трёхмерный куб имеет шесть квадратных граней. Две плитки в кубической мозаике (определённой любым из выше указанных способов) соприкасаются грань-к-грани, если существует (n − 1)-мерный гиперкуб, являющийся гранью обоих плиток. Гипотеза Келлера утверждает, что любая кубическая мозаика содержит по меньшей мере одну пару плиток, соприкасающихся грань-к-грани таким способом.
Оригинальная версия гипотезы, высказанная Келлером, содержала более сильное утверждение, что любая кубическая мозаика имеет столбец кубов, соприкасающихся грань-к-грани. Оно верно в тех же размерностях, что и более слабое утверждение, которое обычно рассматривается исследователямиШаблон:SfnШаблон:Sfn.
Существенным требованием гипотезы является требование конгруэнтности плиток друг другу. Для подобных, но не конгруэнтных кубов возможна пифагорова мозаика, что служит тривиальным контрпримером в двумерном пространстве.
Теоретико-групповая формулировка
Опровержение гипотезы Келлера для достаточно высоких размерностей шло через последовательность приведений, которые преобразуют задачу из геометрии мозаик в задачу теории групп, а из неё в задачу теории графов.
ХайошШаблон:Sfn первым сформулировал гипотезу Келлера в терминах факторизации абелевых групп. Он показал, что если существует контрпример гипотезе, то можно считать его периодической мозаикой кубов с целочисленной длиной стороны и с целочисленными координатами вершин. Таким образом, при изучении гипотезы достаточно рассматривать мозаики специального вида. В этом случае группа целочисленных параллельных переносов, сохраняющих мозаику, образует абелеву группу, а элементы группы соответствуют позициям плиток мозаики. Хайош определил семейство подмножеств Ai абелевой группы как факторизацию, если каждый элемент группы имеет единственное выражение в виде суммы a0 + a1 + ..., где каждое ai принадлежит Ai. Согласно этому определению Хайош переформулировал гипотезу — если абелева группа имеет факторизацию, в которой первое множество A0 может быть произвольным, а каждое последующее множество Ai имеет специальный вид {0, gi, 2gi, 3gi, ..., (qi − 1)gi}, то по меньшей мере один из элементов qigi должен принадлежать A0 − A0 (разность Минковского A0 с самим собой).
СабоШаблон:Sfn показал, что любая мозаика, образующая контрпример гипотезе, должна иметь даже более специфичный вид — длина стороны куба равна степени двойки, вершины имеют целочисленные координаты, мозаика периодична с периодом, равным удвоенной длине стороны куба по каждой координате. Основываясь на этом геометрическом упрощении, он упростил теоретико-групповую формулировку Хайоша, показав, что достаточно рассматривать абелевы группы, являющиеся прямыми суммами циклических групп порядка четыре с qi = 2.
Графы Келлера
Корради и СабоШаблон:Sfn переформулировали результат Сабо в виде условия о существовании большой клики в некотором семействе графов, которые впоследствии стали называться графами Келлера. Точнее, вершины графа Келлера размерности n — это 4n элементов (m1,...,mn), где каждое число m равно 0, 1, 2 или 3. Две вершины связаны ребром, если они отличаются по меньшей мере в двух координатах и отличаются на два по меньшей мере в одной координате. Корради и Сабо показали, что наибольшая клика в этом графе имеет размер, не превосходящий 2n, и если существует клика такого размера, то гипотеза Келлера не верна. Если такая клика задана, можно сформировать пространство кубов со стороной два, центры которых имеют координаты, которые, если брать по модулю четыре, являются вершинами клики. Из условия, что любые две вершины клики имеют координаты, отличающиеся на два, следует, что кубы, соответствующие этим вершинам, не накладываются. Из условия, что клика имеет размер 2n, вытекает, что кубы внутри любого периода мозаики имеют один и тот же объём, что и сам период. Вместе с фактом, что плитки не накладываются, это даёт следствие, что кубы замощают пространство. Однако из условия, что вершины любых двух клик отличаются по меньшей мере в двух координатах, следует, что никакие два куба не имеют общих граней.
Лагариас и Шор в работе 1992 годаШаблон:Sfn опровергли гипотезу Келлера, найдя клику размера 210 в графе Келлера размерности 10. Эти клики приводят к мозаике в размерности 10 без общих граней (соприкосновений грань-к-грани), и копии плиток могут быть помещены в пространстве (со смещением на половину единицы в каждом координатном направлении), создавая мозаику без соприкосновений грань-к-грани в любой более высокой размерности. Подобным же образом МакейШаблон:Sfn уменьшил размерности, в которых найдены контрпримеры, обнаружив клику размера 28 в графе Келлера размерности восемь.
Деброни, Эблен, Лангстон и ШорШаблон:Sfn показали, что граф Келлера размерности семь имеет наибольшую клику размера 124 < 27. Таким образом, в этой размерности не удалось найти контрпример к гипотезе Келлера тем же способом, что и в размерностях 10 и 8 ранее. Позже было показано, что если клики размера 27 нет в определённом графе, родственном графу Келлера, то гипотеза верна в размерности 7. Отсутствие такой клики в этом графе было показано в работе Бракензика и др., опубликованной на arXiv.org в 2019 году и в трудах конференции в 2020 году. Условие отсутствия клики было записано в виде пропозициональной формулы, упрощено с помощью специальной программы, его невыполнимость была доказана с помощью автоматического SAT-решателя, после чего доказательство было дополнительно программно формально верифицированоШаблон:Sfn[1].
Размеры наибольших клик графов Келлера в малых размерностях 2, 3, 4, 5 и 6 равны, соответственно, 2, 5, 12, 28 и 60. Графы Келлера размерностей 4, 5 и 6 были включены в набор «тестовых графов DIMACS», часто используемых в качестве тестов производительности для алгоритмов поиска кликШаблон:Sfn.
Связанные проблемы
Как пишет СабоШаблон:Sfn, Герман Минковский пришёл к частному случаю гипотезы о кубической мозаике из задачи о диофантовом приближении. Одно из следствий теоремы Минковского — что любая решётка (нормализованная, чтобы иметь определитель, равный единице) должна содержать ненулевую точку, расстояние Чебышёва, от которой до начала координат не превосходит единицы. Решётки, которые не содержат ненулевых точек с расстоянием Чебышёва, строго меньшим единицы, называются критическими и точки критической решётки образуют центры кубов кубической мозаики. Минковский в 1900 году предположил, что если кубическая решётка имеет такое расположение центров, она должна содержать два куба, соприкасающихся грань-к-грани. Если это верно, то (ввиду симметрии решётки) каждый куб в этой мозаике должен быть частью столбца кубов и пересечения этих кубов должны образовать кубическую мозаику меньшей размерности. Рассуждая таким образом, Минковский показал, что (в предположении верности гипотезы) любая критическая решётка имеет базис, который может быть выражен треугольной матрицей с единицами на главной диагонали и числами, меньшими единицы вне диагонали. Дьёрдь Хайош доказал гипотезу Минковского в 1942 году, используя теорему Хайоша о факторизации абелевых групп, теоретико-групповой подход, который он позднее применил для более общей гипотезы Келлера.
Гипотеза Келлера является вариантом гипотезы Минковского, в которой ослаблено условие, что центры кубов образуют решётку. Другая связанная гипотеза, выдвинутая Фюртванглером в 1936 году, вместо этого ослабляет условие, что кубы образуют решётку. Фюртванглер спрашивал, должна ли система кубов с центрами в решётке, образующая k-кратное покрытие пространства (то есть любая точка пространства, за исключением точек подмножества меры ноль, должна принадлежать внутренностям в точности k кубов), содержать два куба, соприкасающихся грань-к-грани. Гипотеза Фюртванглера верна для размерностей два и три, а вот для четырёхмерного пространства Шайош в 1938 году нашёл контрпример. РобинсонШаблон:Sfn описал комбинации числа кубов k и размерности n, для которых возможны контрпримеры. Кроме того, комбинируя гипотезы Фюртванглера и Келлера, Робинсон показал, что k-кратной квадратное покрытие евклидовой плоскости должно содержать два квадрата, соприкасающихся ребро-к-ребру. Однако для любого k > 1 и n > 2 существует k-кратное замощение n-мерного пространства кубами, не имеющими общих гранейШаблон:Sfn.
Как только стали известны контрпримеры гипотезе Келлера, появился вопрос о максимальной размерности граней, существование которых гарантируется у кубов в кубической мозаике. Если размерность n не превосходит шести, максимальная размерность равна n − 1 согласно доказательству Перрона гипотезы Келлера для малых размерностей, а при n не меньших восьми максимальная размерность не превосходит n − 2. Лагариас и ШорШаблон:Sfn дали более строгую оценку сверху, n − Шаблон:Sqrt/3.
Иосевич и ПедерсенШаблон:Sfn, а также группа в составе Лагариаса, Рида и ВангаШаблон:Sfn, нашли тесную связь между кубическими мозаиками и спектральной теорией Шаблон:Не переведено 5 на кубе.
Дютур-Сикирич, Ито и ПоярковШаблон:Sfn использовали клики графов Келлера, которые максимальны, но не являются наибольшими, для изучения упаковки кубов в пространство, к которым нельзя добавить дополнительный куб.
В 1975 Людвиг Данцер и, независимо, Бранко Грюнбаум и Шепард нашли мозаику трёхмерного пространства параллелепипедамии с наклоном граней в 60° и 120°, в которой никакие два параллелепипеда не имеют общей граниШаблон:Sfn.
Примечания
Литература
- Шаблон:Публикация
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
