WikiSort.ru - Не сортированное

В геометрии гипотеза Келлера — это высказанная Отт-Генрихом Келлером^[en][1] гипотеза о том, что в любой мозаике в евклидовом пространстве, состоящей из однинаковых гиперкубов, найдутся два куба, соприкасающиеся грань-к-грани. Например, как показано на рисунке, в любой мозаике на плоскости из одинаковых квадратов, какие-то два квадрата должны соприкасаться ребро-к-ребру. Перрон доказал, что это верно в размерностях до 6^[2][3]. Однако для больших размерностей это неверно, как показали Лагарис и Шор для размерностей 10 и выше^[4] и Макей для размерностей 8 и выше^[5], для чего использовали переформулировку задачи в терминах кликового числа некоторых графов, известных теперь как графы Келлера. Хотя эта версия гипотезы в терминах теории графов доказана для любой размерности, оригинальная гипотеза кубической мозаики остаётся открытой для размерности 7.

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

Шабо, Шор и Цонг^[6] дали обзор работ по гипотезе Келлера и связанных проблемах.

Определения

Семейство замкнутых множеств, называемых плитками, образует паркет или мозаику в Евклидовом пространстве, если их объединение полностью заполняет пространство и любые два различных множества в семействе имеют непересекающиеся внутренние части. Говорят, что мозаика моноэдрична, если все её плитки конгруэнтны. Гипотеза Келлера относится к моноэдрическим мозаикам, в которых все плитки являются гиперкубами. Как сформулировал Шабо^[7], кубическая мозаика — это мозаика из конгруэнтных гиперкубов, в которой требуется, чтобы все плитки являлись параллельным переносом друг друга без вращений, или, эквивалентно, все рёбра плиток должны быть параллельны осям координат. Не любая мозаика из конгруэнтных кубов имеет такое свойство. Например, трёхмерное пространство может быть замощено слоями кубов, которые повёрнуты относительно друг друга под произвольным углом. Шор^[8], напротив, определяет кубическую мозаику как произвольное замощение пространства гиперкубами и утверждает без доказательства, что параллельность сторон осям может быть потребована без потери общности.

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

Оригинальная версия гипотезы, высказанная Келлером, содержала более строгое утверждение, что любая кубическая мозаика имеет столбец кубов, соприкасающихся грань-к-грани. Как и более слабое утверждение, которое обычно рассматривается исследователями, утверждение верно для размерностей вплоть до шести, неверно для размерностей восемь и выше, и остаётся открытой проблемой для размерности семь^[9][10].

Существенным требованием гипотезы является требование конгруэнтности плиток друг другу. Для подобных, но не конгруэнтных кубов возможна пифагорова мозаика, что служит тривиальным контрпримером в двумерном пространстве.

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

Опровержение гипотезы Келлера для достаточно высоких размерностей шло через последовательность приведений, которые преобразуют задачу из геометрии мозаик в задачу теории групп, а из неё в задачу теории графов.

Хайош^[11] первым сформулировал гипотезу Келлера в терминах факторизации абелевых групп. Он показал, что если существует контрпример гипотезе, то можно считать его периодической мозаикой кубов с целочисленной длиной стороны и с целочисленными координатами вершин. Таким образом, при изучении гипотезы достаточно рассматривать мозаики специального вида. В этом случае группа целочисленных параллельных переносов, сохраняющих мозаику, образует абелеву группу, а элементы группы соответствуют позициям плиток мозаики. Хайош определил семейство подмножеств A_i абелевой группы как факторизацию, если каждый элемент группы имеет единственное выражение в виде суммы a₀ + a₁ + ..., где каждое a_i принадлежит A_i. Согласно этому определению Хайош переформулировал гипотезу — если абелева группа имеет факторизацию, в которой первое множество A₀ может быть произвольным, а каждое последующее множество A_i имеет специальный вид {0, g_i, 2g_i, 3g_i, ..., (q_i − 1)g_i}, то по меньшей мере один из элементов q_ig_i должен принадлежать A₀ −A₀ (разность Минковского A₀ с самим собой).

Шабо^[7] показал, что любая мозаика, образующая контрпример гипотезе, должна иметь даже более специфичный вид — длина стороны куба равна степени двойки, вершины имеют целочисленные координаты, мозаика периодична с периодом, равным удвоенной длине стороны куба по каждой координате. Основываясь на этом геометрическом упрощении, он упростил теоретико-групповую формулировку Хайоша, показав, что достаточно рассматривать абелевы группы, являющиеся прямыми суммами циклических групп порядка четыре с q_i = 2.

Графы Келлера

Корради и Шабо^[12] переформулировали результат Шабо в виде условия о существовании большой клики в некотором семействе графов, которые впоследствии стали называться графами Келлера. Точнее, вершины графа Келлера размерности n — это 4ⁿ элементов (m₁,...,m_n), где каждое число m равно 0, 1, 2 или 3. Две вершины связаны ребром, если они отличаются по меньшей мере в двух координатах и отличаются на два по меньшей мере в одной координате. Корради и Шабо показали, что наибольшая клика в этом графе имеет размер, не превосходящий 2ⁿ, и если существует клика такого размера, то гипотеза Келлера не верна. Если такая клика задана, можно сформировать пространство кубов со стороной два, центры которых имеют координаты, которые, если брать по модулю четыре, являются вершинами клики. Из условия, что любые две вершины клики имеют координаты, отличающиеся на два, следует, что кубы, соответствующие этим вершинам, не накладываются. Из условия, что клика имеет размер 2ⁿ, вытекает, что кубы внутри любого периода мозаики имеют один и тот же объём, что и сам период. Вместе с фактом, что плитки не накладываются, это даёт следствие, что кубы замощают пространство. Однако из условия, что вершины любых двух клик отличаются по меньшей мере в двух координатах, следует, что никакие два куба не имеют общих граней.

Лагариас и Шор^[4] опровергли гипотезу Келлера, найдя клику размера 2¹⁰ в графе Келлера размерности 10. Эти клики приводят к мозаике в размерности 10 без общих граней (соприкосновений грань-к-грани), и копии плиток могут быть помещены в пространстве (со смещением на половину единицы в каждом координатном направлении), создавая мозаику без соприкосновений грань-к-грани в любой более высокой размерности. Подобным же образом Маклей^[5] уменьшил размерности, в которых найдены контрпримеры, обнаружив клику размера 2⁸ в графе Келлера размерности восемь.

Наконец, Деброни, Эблен, Лангстон и Шор^[13] показали, что граф Келлера размерности семь имеет наибольшую клику размера 124 <  2⁷. Таким образом, тот же подход не ведёт к контрпримеру в этой размерности. Однако сведение задачи от кубической мозаики к кликам может повлечь увеличение размерности, так что остаётся возможность гипотезы о кубической мозаике быть неверной для размерности семь, хотя при формулировке в терминах клик гипотеза верна.

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

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

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

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

Как только стали известны контрпримеры гипотезе Келлера, появился вопрос о максимальной размерности граней, существование которых гарантируется у кубов в кубической мозаике. Если размерность n не превосходит шести, максимальная размерность равна n − 1 согласно доказательству Перрона гипотезы Келлера для малых размерностей, а при n не меньших восьми максимальная размерность не превосходит n − 2. Лагариас и Шор^[18] дали более строгую оценку сверху, n − √n/3.

Иосевич и Педерсен^[19], а также группа в составе Лагариаса, Рида и Ванга^[20], нашли тесную связь между кубическими мозаиками и спектральной теорией интегрируемих с квадратом функций^[en] на кубе.

Дютур-Сикирич, Ито и Поярков^[21] использовали клики графов Келлера, которые максимальны, но не являются наибольшими, для изучения упаковки кубов в пространство, к которым нельзя добавить дополнительный куб.

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

Примечания

Литература

• K. Corrádi, S. Szabó. A combinatorial approach for Keller's conjecture // Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society. — 1990. — Т. 21, вып. 2. — С. 95–100. — DOI:10.1007/BF01946848.
• Jennifer Debroni, John D. Eblen, Michael A. Langston, Peter Shor, Wendy Myrvold, Dinesh Weerapurage. Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms. — 2011. — С. 129–135.
• Mathieu Dutour Sikirić, Yoshiaki Itoh, Alexei Poyarkov. Cube packings, second moment and holes // European Journal of Combinatorics. — 2007. — Т. 28, вып. 3. — С. 715–725. — DOI:10.1016/j.ejc.2006.01.008.
• Branko Grünbaum, G. C. Shephard. Tilings with congruent tiles // Bulletin of the American Mathematical Society. — 1980. — Т. 3, вып. 3. — С. 951–973. — DOI:10.1090/S0273-0979-1980-14827-2.
• G. Hajós. Sur la factorisation des groupes abéliens // Československá Akademie Věd. Časopis Pro Pěstování Matematiky. — 1949. — Т. 74. — С. 157–162.
• Alex Iosevich, Steen Pedersen. Spectral and tiling properties of the unit cube // International Mathematics Research Notices. — 1998. — Вып. 16. — С. 819–828. — DOI:10.1155/S1073792898000506. — arXiv:math/0104093.
• David S. Johnson, Michael A. Trick. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993. — Boston, MA, USA: American Mathematical Society, 1996. — ISBN 0-8218-6609-5.
• O.-H. Keller. Über die lückenlose Erfüllung des Raumes mit Würfeln (нем.) // Journal für die reine und angewandte Mathematik. — 1930. — Bd. 163. — S. 231–248. — DOI:10.1515/crll.1930.163.231.
• Jeffrey C. Lagarias, James A. Reeds, Yang Wang. Orthonormal bases of exponentials for the n-cube // Duke Mathematical Journal. — 2000. — Т. 103, вып. 1. — С. 25–37. — DOI:10.1215/S0012-7094-00-10312-2.
• Jeffrey C. Lagarias, Peter W. Shor. Keller's cube-tiling conjecture is false in high dimensions // Bulletin of the American Mathematical Society. — 1992. — Т. 27, вып. 2. — С. 279–283. — DOI:10.1090/S0273-0979-1992-00318-X.
• Jeffrey C. Lagarias, Peter W. Shor. Cube-tilings of Rⁿ and nonlinear codes // Discrete and Computational Geometry. — 1994. — Т. 11, вып. 4. — С. 359–391. — DOI:10.1007/BF02574014.
• Magdalena Łysakowska, Krzysztof Przesławski. Keller's conjecture on the existence of columns in cube tilings of Rⁿ. — 2008. — arXiv:0809.1960.
• Magdalena Łysakowska, Krzysztof Przesławski. On the structure of cube tilings and unextendible systems of cubes in low dimensions // European Journal of Combinatorics. — 2011. — Т. 32, вып. 8. — С. 1417–1427. — DOI:10.1016/j.ejc.2011.07.003.
• John Mackey. A cube tiling of dimension eight with no facesharing // Discrete and Computational Geometry. — 2002. — Т. 28, вып. 2. — С. 275–279. — DOI:10.1007/s00454-002-2801-9.
• Oskar Perron. Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel // Mathematische Zeitschrift. — 1940a. — Т. 46. — С. 1–26. — DOI:10.1007/BF01181421.
• Oskar Perron. Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel. II // Mathematische Zeitschrift. — 1940b. — Т. 46. — С. 161–180. — DOI:10.1007/BF01181436.
• Raphael M. Robinson. Multiple tilings of n-dimensional space by unit cubes // Mathematische Zeitschrift. — 1979. — Т. 166, вып. 3. — С. 225–264. — DOI:10.1007/BF01214145.
• Peter Shor. Minkowski's and Keller's cube-tiling conjectures. — 2004.
• Sándor Szabó. Multiple tilings by cubes with no shared faces // Aequationes Mathematicae. — 1982. — Т. 25, вып. 1. — С. 83–89. — DOI:10.1007/BF02189600.
• Sándor Szabó. A reduction of Keller's conjecture // Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society. — 1986. — Т. 17, вып. 4. — С. 265–277. — DOI:10.1007/BF01848388.
• Sándor Szabó. Cube tilings as contributions of algebra to geometry // Beiträge zur Algebra und Geometrie. — 1993. — Т. 34, вып. 1. — С. 63–75.
• Chuanming Zong. What is known about unit cubes // Bulletin of the American Mathematical Society. — 2005. — Т. 42, вып. 2. — С. 181–211. — DOI:10.1090/S0273-0979-05-01050-5.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.