Гіпотеза Келлера
Гіпотеза Келлера — гіпотеза, яку висунув Отт-Генріх Келлер[en][1], про те, що в будь-якій мозаїці в евклідовому просторі, яка складається з однакових гіперкубів, знайдуться два куби, що дотикаються грань-до-грані. Наприклад, як показано на малюнку, в будь-якій мозаїці на площині з однакових квадратів якісь два квадрати повинні дотикатися сторона-до-сторони.
Остаточно розв'язана у 2020 році[2]. Перон довів, що гіпотеза виконується в розмірності до 6[3][4]; Бракензік зі співавторами довели істинність гіпотези для розмірності 7[2]. Проте для більших розмірностей це неправильно, як показали Лагаріас і Шор для розмірностей 10 і вищих[5], Макей для розмірностей 8 і вищих[6], для чого переформулювали задачу в термінах клікового числа деяких графів, відомих тепер як графи Келлера.
Пов'язана гіпотеза Мінковського про ґратку кубічної мозаїки стверджує, що при заповненні простору однаковими кубами з додатковою властивістю, що центри кубів утворюють ґратку, деякі куби мають дотикатися грань-до-грані. Гіпотезу довів Хайош[de] 1942 року.
Визначення[ред. | ред. код]
Сімейство замкнутих множин, званих плитками, утворює паркет або мозаїку в евклідовому просторі, якщо їх об'єднання повністю заповнює простір і будь-які дві різні множини в сімействі мають внутрішні частини, що не перетинаються. Кажуть, що мозаїка моноедрична, якщо всі її плитки конгруентні. Гіпотеза Келлера стосується моноедричних мозаїк, у яких всі плитки є гіперкубами. Як сформулював Сабо[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.
Йосевіч і Педерсен[21], а також група у складі Лагаріаса, Ріда і Ванга[22] знайшли тісний зв'язок між кубічними мозаїками і спектральною теорією інтегровних із квадратом функцій[en] на кубі.
Дютур-Сикирич, Іто і Поярков[23] використали кліки графів Келлера, які максимальні, але не є найбільшими, для вивчення пакування кубів у простір, до яких не можна додати додаткового куба.
1975 року Людвіг Данцер і, незалежно, Бранко Ґрюнбаум і Шепард знайшли мозаїку тривимірного простору паралелепіпедами з нахилом граней 60° і 120°, в якій жодні два паралелепіпеди не мають спільної грані[24].
Примітки[ред. | ред. код]
- ↑ Keller, 1930.
- ↑ а б 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, S2CID 203951899
- ↑ Perron, 1940a.
- ↑ Perron, 1940b.
- ↑ а б Lagarias, Shor, 1992.
- ↑ а б Mackey, 2002.
- ↑ а б Szabó, 1986.
- ↑ Shor, 2004.
- ↑ Łysakowska, Przesławski, 2008.
- ↑ Łysakowska, Przesławski, 2011.
- ↑ Hajós, 1949.
- ↑ Corrádi, Szabó, 1990.
- ↑ Debroni, Eblen, и др., 2011.
- ↑ Brakensiek et al, 2020.
- ↑ Kevin Hartnett (19 серпня 2020). Computer Search Settles 90-Year-Old Math Problem. Quanta (англ.). Архів оригіналу за 30 серпня 2020. Процитовано 30 серпня 2020.
- ↑ Johnson, Trick, 1996.
- ↑ Szabó, 1993.
- ↑ Robinson, 1979.
- ↑ Szabó, 1982.
- ↑ Lagarias, Shor, 1994.
- ↑ Iosevich, Pedersen, 1998.
- ↑ Lagarias, Reeds, Wang, 2000.
- ↑ Dutour-Sikirić, Itoh, Poyarkov, 2007.
- ↑ Grünbaum, Shephard, 1980.
Література[ред. | ред. код]
- 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:.
- Jennifer Debroni, John D. Eblen, Michael A. Langston, Peter Shor, Wendy Myrvold, Dinesh Weerapurage. [1] — 2011. — С. 129–135. Архівовано з джерела 18 жовтня 2012
- Mathieu Dutour Sikirić, Yoshiaki Itoh, Alexei Poyarkov. Cube packings, second moment and holes // European Journal of Combinatorics. — 2007. — Т. 28, вип. 3. — С. 715–725. — DOI:.
- Branko Grünbaum, G. C. Shephard. Tilings with congruent tiles // Bulletin of the American Mathematical Society. — 1980. — Т. 3, вип. 3. — С. 951–973. — DOI:.
- 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:.
- 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:.
- 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:.
- 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. — (New Series). — DOI:.
- Jeffrey C. Lagarias, Peter W. Shor. Cube-tilings of Rn and nonlinear codes // Discrete and Computational Geometry. — 1994. — Т. 11, вип. 4. — С. 359–391. — DOI:.
- Magdalena Łysakowska, Krzysztof Przesławski. Keller's conjecture on the existence of columns in cube tilings of Rn. — 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:.
- John Mackey. A cube tiling of dimension eight with no facesharing // Discrete and Computational Geometry. — 2002. — Т. 28, вип. 2. — С. 275–279. — DOI:.
- Oskar Perron. Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel // Mathematische Zeitschrift. — 1940a. — Т. 46. — С. 1–26. — DOI:.
- Oskar Perron. Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel. II // Mathematische Zeitschrift. — 1940b. — Т. 46. — С. 161–180. — DOI:.
- Raphael M. Robinson. Multiple tilings of n-dimensional space by unit cubes // Mathematische Zeitschrift. — 1979. — Т. 166, вип. 3. — С. 225–264. — DOI:.
- Peter Shor. Minkowski's and Keller's cube-tiling conjectures. — 2004. — (Lecture notes for IAP Mathematics Lecture Series) Архівовано з джерела 7 травня 2021
- Sándor Szabó. Multiple tilings by cubes with no shared faces // Aequationes Mathematicae. — 1982. — Т. 25, вип. 1. — С. 83–89. — DOI:.
- 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:.
- Sándor Szabó. Cube tilings as contributions of algebra to geometry // Beiträge zur Algebra und Geometrie. — 1993. — Т. 34, вип. 1. — С. 63–75. Архівовано з джерела 3 березня 2016. Процитовано 11 червня 2022.
- Chuanming Zong. What is known about unit cubes // Bulletin of the American Mathematical Society. — 2005. — Т. 42, вип. 2. — С. 181–211. — (New Series). — DOI:.