У цій мозаїці з квадратів на площині зелені та фіолетові квадрати прилягають сторона-до-сторони, так само, як сині та помаранчеві
Гіпотеза Келлера — гіпотеза, яку висунув Отт-Генріх Келлер[en][1], про те, що в будь-якій мозаїці в евклідовому просторі, яка складається з однакових гіперкубів, знайдуться два куби, що дотикаються грань-до-грані. Наприклад, як показано на малюнку, в будь-якій мозаїці на площині з однакових квадратів якісь два квадрати повинні дотикатися сторона-до-сторони.
Остаточно розв'язана у 2020 році[2]. Перон довів, що гіпотеза виконується в розмірності до 6[3][4]; Бракензік зі співавторами довели істинність гіпотези для розмірності 7[2]. Проте для більших розмірностей це неправильно, як показали Лагаріас і Шор для розмірностей 10 і вищих[5], Макей для розмірностей 8 і вищих[6], для чого переформулювали задачу в термінах клікового числа деяких графів, відомих тепер як графи Келлера.
Сімейство замкнутих множин, званих плитками, утворює паркет або мозаїку в евклідовому просторі, якщо їх об'єднання повністю заповнює простір і будь-які дві різні множини в сімействі мають внутрішні частини, що не перетинаються. Кажуть, що мозаїка моноедрична, якщо всі її плитки конгруентні. Гіпотеза Келлера стосується моноедричних мозаїк, у яких всі плитки є гіперкубами. Як сформулював Сабо[7], кубічна мозаїка — це мозаїка з конгруентних гіперкубів, у якій потрібно, щоб усі плитки були паралельним перенесенням одна одної без поворотів, або, еквівалентно, всі ребра плиток мають бути паралельними осям координат. Не будь-яка мозаїка з конгруентних кубів має таку властивість. Наприклад, тривимірний простір можна замостити шарами кубів, повернутими один відносно одного під довільним кутом. Шор[8], навпаки, визначає кубічну мозаїку як довільне замощення простору гіперкубами і стверджує без доведення, що паралельність сторін осям можна вимагати без втрати загальності.
Гіперкуб у n-вимірному просторі має 2n граней розмірності n − 1, які є гіперкубами. Наприклад, квадрат має чотири сторони, а тривимірний куб має шість квадратних граней. Дві плитки в кубічній мозаїці (визначеній будь-яким із вище зазначених способів) стикаються грань-до-грані, якщо існує (n − 1)-вимірний гіперкуб, що є гранню обох плиток. Гіпотеза Келлера стверджує, що будь-яка кубічна мозаїка містить щонайменше одну пару плиток, які дотикаються грань-до-грані в такий спосіб.
Оригінальна версія гіпотези, яку висловив Келлер, містила сильніше твердження, що будь-яка кубічна мозаїка має стовпець кубів, які дотикаються грань-до-грані. Воно істинне в тих самих розмірностях, що й слабке твердження, яке зазвичай розглядають дослідники[9][10].
Істотною вимогою гіпотези є вимога конгруентності плиток одна одній. Для подібних, але не конгруентних кубів можлива піфагорова мозаїка, яка є тривіальним контрприкладом у двовимірному просторі.
Теоретико-групове формулювання
Спростування гіпотези Келлера для досить високих розмірностей йшло через послідовність зведень, які перетворюють задачу з геометрії мозаїк на задачу теорії груп, а з неї на задачу теорії графів.
Хайош[11] першим сформулював гіпотезу Келлера в термінах факторизації абелевих груп. Він показав, що якщо й існує контрприклад гіпотезі, можна вважати його періодичною мозаїкою кубів з цілою довжиною ребра і з цілими координатами вершин. Отже, щодо гіпотези досить розглядати мозаїки спеціального вигляду. У цьому випадку група цілочисельних паралельних перенесень, що зберігають мозаїку, утворює абелеву групу, а елементи групи відповідають позиціям плиток мозаїки. Хайош визначив сімейство підмножин Ai абелевої групи як факторизацію, якщо кожен елемент групи має єдиний вираз у вигляді суми a0 + a1 + …, де кожне ai належить Ai. Відповідно до цього визначення Хайош переформулював гіпотезу: якщо абелева група має факторизацію, в якій перша множина A0 може бути довільною, а кожна наступна множина Ai має особливий вигляд {0, gi, 2gi, 3gi, …, (qi − 1)gi}, то принаймні один із елементів qigi має належати A0 − A0 (різниця МінковськогоA0 із самою собою).
Сабо[7] показав, що будь-яка мозаїка, що утворює контрприклад гіпотезі, повинна мати навіть специфічніший вигляд — довжина сторони куба дорівнює степеню двійки, вершини мають цілочисельні координати, мозаїка періодична з періодом, рівним подвоєній довжині сторони куба за кожною координатою. Ґрунтуючись на цьому геометричному спрощенні, він спростив теоретико-групове формулювання Хайоша, показавши, що досить розглядати абелеві групи, які є прямими сумами циклічних груп порядку чотири з qi = 2.
Графи Келлера
Граф Келлера розмірності два, ізоморфний графу Клебша
Корраді та Сабо[12] переформулювали результат Сабо у вигляді умови про існування великої кліки в деякому сімействі графів, які згодом стали називатися графами Келлера. Точніше, вершини графа Келлера розмірності n — це 4n елементів (m1,…,mn), де кожне число m дорівнює 0, 1, 2 або 3. Дві вершини пов'язані ребром, якщо вони відрізняються принаймні двома координатами і відрізняються на два принаймні в одній координаті. Корраді і Сабо показали, що найбільша кліка в цьому графі має розмір, що не перевищує 2n і, якщо існує кліка такого розміру, то гіпотеза Келлера хибна. Якщо таку кліку задано, можна сформувати простір кубів зі стороною два центри яких мають координати, які, якщо брати за модулем чотири, є вершинами кліки. З умови, що будь-які дві вершини кліки мають координати, що відрізняються на два, випливає, що куби, які відповідають цим вершинам, не накладаються. З умови, що кліка має розмір 2n, випливає, що куби всередині будь-якого періоду мозаїки мають такий самий об'єм, як і сам період. Разом із фактом, що плитки не накладаються, це дає наслідок, що куби замощують простір. Однак із умови, що вершини будь-яких двох клік відрізняються принаймні двома координатами, випливає, що жодні два куби не мають спільних граней.
Лагаріас і Шор у роботі 1992 року[5] спростували гіпотезу Келлера, знайшовши кліку розміру 210 у графі Келлера розмірності 10. Ці кліки призводять до мозаїки в розмірності 10 без спільних граней (дотиків грань-до-грані), і копії плиток можна помістити в просторі (зі зміщенням на половину одиниці в кожному координатному напрямку), створюючи мозаїку без дотиків грань-до-грані у будь-якій вищій розмірності. Подібним способом Макей[6] зменшив розмірності, в яких знайдено контрприклади, виявивши кліку розміру 28 у графі Келлера розмірності вісім.
Деброні, Еблен, Лангстон і Шор[13] показали, що граф Келлера розмірності сім має найбільшу кліку розміру 124 < 27. Таким чином, у цій розмірності не вдалося знайти контрприклад до гіпотези Келлера тим самим способом, що й у розмірності 10 і 8 раніше. Пізніше показано, що якщо кліки розміру 27 немає у певному графі, спорідненому з графом Келлера, то гіпотеза істинна в розмірності 7. Відсутність такої кліки в цьому графі показано в роботі Бракензіка та ін., опублікованій на arXiv.org 2019 року та в працях конференції 2020 року. Умову відсутності кліки записано у вигляді пропозиціональної формули, спрощено за допомогою спеціальної програми, її нездійсненність доведено за допомогою автоматичного SAT-розв'язувача, після чого доведення додатково програмно формально верифіковано[14][15].
Розміри найбільших клік графів Келлера в малих розмірностях 2, 3, 4, 5 і 6 рівні відповідно 2, 5, 12, 28 і 60. Графи Келлера розмірностей 4, 5 і 6 включено в набір «тестових графів DIMACS», які часто використовують як тести продуктивності для алгоритмів пошуку клік[16].
Пов'язані проблеми
Як пише Сабо[17], Герман Мінковський прийшов до окремого випадку гіпотези про кубічну мозаїку із задачі про діофантове наближення. Один із наслідків теореми Мінковського — будь-яка ґратка (нормалізована, щоб мати визначник, рівний одиниці) має містити ненульову точку, відстань Чебишова, від якої до початку координат не перевищує одиниці. Ґратки, які не містять ненульових точок з відстанню Чебишова, строго меншою від одиниці, називають критичними і точки критичної ґратки утворюють центри кубів кубічної мозаїки. Мінковський 1900 року припустив, що якщо кубічна ґратка має таке розташування центрів, вона має містити два куби, що дотикаються грань-до-грані. Якщо це так, то (завдяки симетрії ґратки) кожен куб у цій мозаїці має бути частиною стовпця кубів і перетини цих кубів мають утворити кубічну мозаїку меншої розмірності. Розмірковуючи таким чином, Мінковський показав, що (у припущенні істинності гіпотези) будь-яка критична ґратка має базис, який можна виразити трикутною матрицею з одиницями на головній діагоналі та числами меншими від одиниці поза діагоналлю. Дьордь Хайош[en] довів гіпотезу Мінковського 1942 року, скориставшись теоремою Хайоша про факторизацію абелевих груп, теоретико-груповий підхід, який він пізніше застосував для загальнішої гіпотези Келлера.
Гіпотеза Келлера є варіантом гіпотези Мінковського, в якій ослаблено умову, що центри кубів утворюють ґратку. Інша пов'язана гіпотеза, яку висунув Фюртванглер 1936 року, натомість послаблює умову, що куби утворюють ґратку. Фюртванглер запитував, чи повинна система кубів з центрами в ґратці, що утворює k-кратне покриття простору (тобто будь-яка точка простору, за винятком точок підмножини міри нуль, повинна належати внутрішності точно k кубів), містити два куби, що дотикаються грань-до-грані. Гіпотеза Фюртванглера істинна для розмірностей два і три, а ось для чотиривимірного простору Шайош 1938 року знайшов контрприклад. Робінсон[18] описав комбінації числа кубів k і розмірності n, для яких можливі контрприклади. Крім того, комбінуючи гіпотези Фюртванглера і Келлера, Робінсон показав, що k-кратне квадратне покриття евклідової площини має містити два квадрати, що дотикаються сторона-до-сторони. Однак для будь-якого k > 1 та n > 2 існує k-кратне замощення n-вимірного простору кубами, які не мають спільних граней[19].
Як тільки стали відомими контрприклади гіпотезі Келлера, постало питання про найбільшу розмірність граней, існування яких гарантується в кубів у кубічній мозаїці. Якщо розмірність n не перевищує шести, максимальна розмірність дорівнює n − 1 згідно з доведенням Перрона гіпотези Келлера для малих розмірностей, а при n не менших восьми найбільша розмірність не перевищує n − 2. Лагаріас і Шор[20] дали строгішу оцінку зверху, n − √n/3.
Дютур-Сикирич, Іто і Поярков[23] використали кліки графів Келлера, які максимальні, але не є найбільшими, для вивчення пакування кубів у простір, до яких не можна додати додаткового куба.
1975 року Людвіг Данцер і, незалежно, Бранко Ґрюнбаум і Шепард знайшли мозаїку тривимірного простору паралелепіпедами з нахилом граней 60° і 120°, в якій жодні два паралелепіпеди не мають спільної грані[24].
↑ абBrakensiek, Joshua; Heule, Marijn; Mackey, John; Narváez, David (2020), The resolution of Keller's conjecture, у Peltier, Nicolas; Sofronie-Stokkermans, Viorica (ред.), Automated Reasoning: 10th International Joint Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Proceedings, Part I, Lecture Notes in Computer Science, т. 12166, Springer, с. 48—65, arXiv:1910.03740, doi:10.1007/978-3-030-51074-9_4, S2CID203951899
Joshua Brakensiek, Marijn Heule, John Mackey, David Narváez. The Resolution of Keller’s Conjecture // International Joint Conference on Automated Reasoning 2020: Automated Reasoning. — Springer, 2020. — P. 48—65.
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. [1] — 2011. — С. 129–135. Архівовано з джерела 18 жовтня 2012
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. — arXiv:math/0104093. — DOI:10.1155/S1073792898000506.
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.
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.
