Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Гіпотеза Келлера гіпотеза яку висунув en про те що в будь якій мозаїці в евклідовому просторі яка складається з однакови

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

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

Гіпотеза Келлера — гіпотеза, яку висунув [en], про те, що в будь-якій мозаїці в евклідовому просторі, яка складається з однакових гіперкубів, знайдуться два куби, що дотикаються грань-до-грані. Наприклад, як показано на малюнку, в будь-якій мозаїці на площині з однакових квадратів якісь два квадрати повинні дотикатися сторона-до-сторони.

image
У цій мозаїці з квадратів на площині зелені та фіолетові квадрати прилягають сторона-до-сторони, так само, як сині та помаранчеві

Остаточно розв'язана у 2020 році. Перон довів, що гіпотеза виконується в розмірності до 6; Бракензік зі співавторами довели істинність гіпотези для розмірності 7. Проте для більших розмірностей це неправильно, як показали Лагаріас і Шор для розмірностей 10 і вищих, Макей для розмірностей 8 і вищих, для чого переформулювали задачу в термінах клікового числа деяких графів, відомих тепер як графи Келлера.

Пов'язана гіпотеза Мінковського про ґратку кубічної мозаїки стверджує, що при заповненні простору однаковими кубами з додатковою властивістю, що центри кубів утворюють ґратку, деякі куби мають дотикатися грань-до-грані. Гіпотезу довів [de] 1942 року.

Визначення

Сімейство замкнутих множин, званих плитками, утворює паркет або мозаїку в евклідовому просторі, якщо їх об'єднання повністю заповнює простір і будь-які дві різні множини в сімействі мають внутрішні частини, що не перетинаються. Кажуть, що мозаїка моноедрична, якщо всі її плитки конгруентні. Гіпотеза Келлера стосується моноедричних мозаїк, у яких всі плитки є гіперкубами. Як сформулював Сабо, кубічна мозаїка — це мозаїка з конгруентних гіперкубів, у якій потрібно, щоб усі плитки були паралельним перенесенням одна одної без поворотів, або, еквівалентно, всі ребра плиток мають бути паралельними осям координат. Не будь-яка мозаїка з конгруентних кубів має таку властивість. Наприклад, тривимірний простір можна замостити шарами кубів, повернутими один відносно одного під довільним кутом. Шор, навпаки, визначає кубічну мозаїку як довільне замощення простору гіперкубами і стверджує без доведення, що паралельність сторін осям можна вимагати без втрати загальності.

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

Оригінальна версія гіпотези, яку висловив Келлер, містила сильніше твердження, що будь-яка кубічна мозаїка має стовпець кубів, які дотикаються грань-до-грані. Воно істинне в тих самих розмірностях, що й слабке твердження, яке зазвичай розглядають дослідники.

Істотною вимогою гіпотези є вимога конгруентності плиток одна одній. Для подібних, але не конгруентних кубів можлива піфагорова мозаїка, яка є тривіальним контрприкладом у двовимірному просторі.

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

Спростування гіпотези Келлера для досить високих розмірностей йшло через послідовність зведень, які перетворюють задачу з геометрії мозаїк на задачу теорії груп, а з неї на задачу теорії графів.

Хайош першим сформулював гіпотезу Келлера в термінах факторизації абелевих груп. Він показав, що якщо й існує контрприклад гіпотезі, можна вважати його кубів з цілою довжиною ребра і з цілими координатами вершин. Отже, щодо гіпотези досить розглядати мозаїки спеціального вигляду. У цьому випадку група цілочисельних паралельних перенесень, що зберігають мозаїку, утворює абелеву групу, а елементи групи відповідають позиціям плиток мозаїки. Хайош визначив сімейство підмножин Ai абелевої групи як факторизацію, якщо кожен елемент групи має єдиний вираз у вигляді суми a0 + a1 + …, де кожне ai належить Ai. Відповідно до цього визначення Хайош переформулював гіпотезу: якщо абелева група має факторизацію, в якій перша множина A0 може бути довільною, а кожна наступна множина Ai має особливий вигляд {0, gi, 2gi, 3gi, …, (qi − 1)gi}, то принаймні один із елементів qigi має належати A0 − A0 (різниця Мінковського A0 із самою собою).

Сабо показав, що будь-яка мозаїка, що утворює контрприклад гіпотезі, повинна мати навіть специфічніший вигляд — довжина сторони куба дорівнює степеню двійки, вершини мають цілочисельні координати, мозаїка періодична з періодом, рівним подвоєній довжині сторони куба за кожною координатою. Ґрунтуючись на цьому геометричному спрощенні, він спростив теоретико-групове формулювання Хайоша, показавши, що досить розглядати абелеві групи, які є прямими сумами циклічних груп порядку чотири з qi = 2.

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

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

Корраді та Сабо переформулювали результат Сабо у вигляді умови про існування великої кліки в деякому сімействі графів, які згодом стали називатися графами Келлера. Точніше, вершини графа Келлера розмірності n — це 4n елементів (m1,…,mn), де кожне число m дорівнює 0, 1, 2 або 3. Дві вершини пов'язані ребром, якщо вони відрізняються принаймні двома координатами і відрізняються на два принаймні в одній координаті. Корраді і Сабо показали, що найбільша кліка в цьому графі має розмір, що не перевищує 2n і, якщо існує кліка такого розміру, то гіпотеза Келлера хибна. Якщо таку кліку задано, можна сформувати простір кубів зі стороною два центри яких мають координати, які, якщо брати за модулем чотири, є вершинами кліки. З умови, що будь-які дві вершини кліки мають координати, що відрізняються на два, випливає, що куби, які відповідають цим вершинам, не накладаються. З умови, що кліка має розмір 2n, випливає, що куби всередині будь-якого періоду мозаїки мають такий самий об'єм, як і сам період. Разом із фактом, що плитки не накладаються, це дає наслідок, що куби замощують простір. Однак із умови, що вершини будь-яких двох клік відрізняються принаймні двома координатами, випливає, що жодні два куби не мають спільних граней.

Лагаріас і Шор у роботі 1992 року спростували гіпотезу Келлера, знайшовши кліку розміру 210 у графі Келлера розмірності 10. Ці кліки призводять до мозаїки в розмірності 10 без спільних граней (дотиків грань-до-грані), і копії плиток можна помістити в просторі (зі зміщенням на половину одиниці в кожному координатному напрямку), створюючи мозаїку без дотиків грань-до-грані у будь-якій вищій розмірності. Подібним способом Макей зменшив розмірності, в яких знайдено контрприклади, виявивши кліку розміру 28 у графі Келлера розмірності вісім.

Деброні, Еблен, Лангстон і Шор показали, що граф Келлера розмірності сім має найбільшу кліку розміру 124 < 27. Таким чином, у цій розмірності не вдалося знайти контрприклад до гіпотези Келлера тим самим способом, що й у розмірності 10 і 8 раніше. Пізніше показано, що якщо кліки розміру 27 немає у певному графі, спорідненому з графом Келлера, то гіпотеза істинна в розмірності 7. Відсутність такої кліки в цьому графі показано в роботі Бракензіка та ін., опублікованій на arXiv.org 2019 року та в працях конференції 2020 року. Умову відсутності кліки записано у вигляді пропозиціональної формули, спрощено за допомогою спеціальної програми, її нездійсненність доведено за допомогою автоматичного SAT-розв'язувача, після чого доведення додатково програмно формально верифіковано.

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

Пов'язані проблеми

Як пише Сабо, Герман Мінковський прийшов до окремого випадку гіпотези про кубічну мозаїку із задачі про діофантове наближення. Один із наслідків теореми Мінковського — будь-яка ґратка (нормалізована, щоб мати визначник, рівний одиниці) має містити ненульову точку, відстань Чебишова, від якої до початку координат не перевищує одиниці. Ґратки, які не містять ненульових точок з відстанню Чебишова, строго меншою від одиниці, називають критичними і точки критичної ґратки утворюють центри кубів кубічної мозаїки. Мінковський 1900 року припустив, що якщо кубічна ґратка має таке розташування центрів, вона має містити два куби, що дотикаються грань-до-грані. Якщо це так, то (завдяки симетрії ґратки) кожен куб у цій мозаїці має бути частиною стовпця кубів і перетини цих кубів мають утворити кубічну мозаїку меншої розмірності. Розмірковуючи таким чином, Мінковський показав, що (у припущенні істинності гіпотези) будь-яка критична ґратка має базис, який можна виразити трикутною матрицею з одиницями на головній діагоналі та числами меншими від одиниці поза діагоналлю. [en] довів гіпотезу Мінковського 1942 року, скориставшись теоремою Хайоша про факторизацію абелевих груп, теоретико-груповий підхід, який він пізніше застосував для загальнішої гіпотези Келлера.

Гіпотеза Келлера є варіантом гіпотези Мінковського, в якій ослаблено умову, що центри кубів утворюють ґратку. Інша пов'язана гіпотеза, яку висунув Фюртванглер 1936 року, натомість послаблює умову, що куби утворюють ґратку. Фюртванглер запитував, чи повинна система кубів з центрами в ґратці, що утворює k-кратне покриття простору (тобто будь-яка точка простору, за винятком точок підмножини міри нуль, повинна належати внутрішності точно k кубів), містити два куби, що дотикаються грань-до-грані. Гіпотеза Фюртванглера істинна для розмірностей два і три, а ось для чотиривимірного простору Шайош 1938 року знайшов контрприклад. Робінсон описав комбінації числа кубів k і розмірності n, для яких можливі контрприклади. Крім того, комбінуючи гіпотези Фюртванглера і Келлера, Робінсон показав, що k-кратне квадратне покриття евклідової площини має містити два квадрати, що дотикаються сторона-до-сторони. Однак для будь-якого k > 1 та n > 2 існує k-кратне замощення n-вимірного простору кубами, які не мають спільних граней.

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

Йосевіч і Педерсен, а також група у складі Лагаріаса, Ріда і Ванга знайшли тісний зв'язок між кубічними мозаїками і спектральною теорією [en] на кубі.

Дютур-Сикирич, Іто і Поярков використали кліки графів Келлера, які максимальні, але не є найбільшими, для вивчення пакування кубів у простір, до яких не можна додати додаткового куба.

1975 року Людвіг Данцер і, незалежно, Бранко Ґрюнбаум і Шепард знайшли мозаїку тривимірного простору паралелепіпедами з нахилом граней 60° і 120°, в якій жодні два паралелепіпеди не мають спільної грані.

Примітки

  1. Keller, 1930.
  2. 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
  3. Perron, 1940a.
  4. Perron, 1940b.
  5. Lagarias, Shor, 1992.
  6. Mackey, 2002.
  7. Szabó, 1986.
  8. Shor, 2004.
  9. Łysakowska, Przesławski, 2008.
  10. Łysakowska, Przesławski, 2011.
  11. Hajós, 1949.
  12. Corrádi, Szabó, 1990.
  13. Debroni, Eblen, и др., 2011.
  14. Brakensiek et al, 2020.
  15. Kevin Hartnett (19 серпня 2020). Computer Search Settles 90-Year-Old Math Problem. Quanta (англ.). оригіналу за 30 серпня 2020. Процитовано 30 серпня 2020.
  16. Johnson, Trick, 1996.
  17. Szabó, 1993.
  18. Robinson, 1979.
  19. Szabó, 1982.
  20. Lagarias, Shor, 1994.
  21. Iosevich, Pedersen, 1998.
  22. Lagarias, Reeds, Wang, 2000.
  23. Dutour-Sikirić, Itoh, Poyarkov, 2007.
  24. 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:10.1007/BF01946848.
  • Jennifer Debroni, John D. Eblen, Michael A. Langston, , Wendy Myrvold, Dinesh Weerapurage. [1] — 2011. — С. 129–135. з джерела 18 жовтня 2012
  • Mathieu Dutour Sikirić, Yoshiaki Itoh, Alexei Poyarkov. Cube packings, second moment and holes // . — 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.
  • . 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. — .
  • O.-H. Keller. Über die lückenlose Erfüllung des Raumes mit Würfeln // . — 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 // . — 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. — (New Series). — DOI:10.1090/S0273-0979-1992-00318-X.
  • Jeffrey C. Lagarias, Peter W. Shor. Cube-tilings of Rn and nonlinear codes // . — 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 Rn. — 2008. — arXiv:0809.1960.
  • Magdalena Łysakowska, Krzysztof Przesławski. On the structure of cube tilings and unextendible systems of cubes in low dimensions // . — 2011. — Т. 32, вип. 8. — С. 1417–1427. — DOI:10.1016/j.ejc.2011.07.003.
  • John Mackey. A cube tiling of dimension eight with no facesharing // . — 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 // . — 1940a. — Т. 46. — С. 1–26. — DOI:10.1007/BF01181421.
  • Oskar Perron. Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel. II // . — 1940b. — Т. 46. — С. 161–180. — DOI:10.1007/BF01181436.
  • Raphael M. Robinson. Multiple tilings of n-dimensional space by unit cubes // . — 1979. — Т. 166, вип. 3. — С. 225–264. — DOI:10.1007/BF01214145.
  • 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: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. з джерела 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:10.1090/S0273-0979-05-01050-5.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Gipoteza Kellera gipoteza yaku visunuv en pro te sho v bud yakij mozayici v evklidovomu prostori yaka skladayetsya z odnakovih giperkubiv znajdutsya dva kubi sho dotikayutsya gran do grani Napriklad yak pokazano na malyunku v bud yakij mozayici na ploshini z odnakovih kvadrativ yakis dva kvadrati povinni dotikatisya storona do storoni U cij mozayici z kvadrativ na ploshini zeleni ta fioletovi kvadrati prilyagayut storona do storoni tak samo yak sini ta pomaranchevi Ostatochno rozv yazana u 2020 roci Peron doviv sho gipoteza vikonuyetsya v rozmirnosti do 6 Brakenzik zi spivavtorami doveli istinnist gipotezi dlya rozmirnosti 7 Prote dlya bilshih rozmirnostej ce nepravilno yak pokazali Lagarias i Shor dlya rozmirnostej 10 i vishih Makej dlya rozmirnostej 8 i vishih dlya chogo pereformulyuvali zadachu v terminah klikovogo chisla deyakih grafiv vidomih teper yak grafi Kellera Pov yazana gipoteza Minkovskogo pro gratku kubichnoyi mozayiki stverdzhuye sho pri zapovnenni prostoru odnakovimi kubami z dodatkovoyu vlastivistyu sho centri kubiv utvoryuyut gratku deyaki kubi mayut dotikatisya gran do grani Gipotezu doviv de 1942 roku ViznachennyaSimejstvo zamknutih mnozhin zvanih plitkami utvoryuye parket abo mozayiku v evklidovomu prostori yaksho yih ob yednannya povnistyu zapovnyuye prostir i bud yaki dvi rizni mnozhini v simejstvi mayut vnutrishni chastini sho ne peretinayutsya Kazhut sho mozayika monoedrichna yaksho vsi yiyi plitki kongruentni Gipoteza Kellera stosuyetsya monoedrichnih mozayik u yakih vsi plitki ye giperkubami Yak sformulyuvav Sabo kubichna mozayika ce mozayika z kongruentnih giperkubiv u yakij potribno shob usi plitki buli paralelnim perenesennyam odna odnoyi bez povorotiv abo ekvivalentno vsi rebra plitok mayut buti paralelnimi osyam koordinat Ne bud yaka mozayika z kongruentnih kubiv maye taku vlastivist Napriklad trivimirnij prostir mozhna zamostiti sharami kubiv povernutimi odin vidnosno odnogo pid dovilnim kutom Shor navpaki viznachaye kubichnu mozayiku yak dovilne zamoshennya prostoru giperkubami i stverdzhuye bez dovedennya sho paralelnist storin osyam mozhna vimagati bez vtrati zagalnosti Giperkub u n vimirnomu prostori maye 2n granej rozmirnosti n 1 yaki ye giperkubami Napriklad kvadrat maye chotiri storoni a trivimirnij kub maye shist kvadratnih granej Dvi plitki v kubichnij mozayici viznachenij bud yakim iz vishe zaznachenih sposobiv stikayutsya gran do grani yaksho isnuye n 1 vimirnij giperkub sho ye grannyu oboh plitok Gipoteza Kellera stverdzhuye sho bud yaka kubichna mozayika mistit shonajmenshe odnu paru plitok yaki dotikayutsya gran do grani v takij sposib Originalna versiya gipotezi yaku visloviv Keller mistila silnishe tverdzhennya sho bud yaka kubichna mozayika maye stovpec kubiv yaki dotikayutsya gran do grani Vono istinne v tih samih rozmirnostyah sho j slabke tverdzhennya yake zazvichaj rozglyadayut doslidniki Istotnoyu vimogoyu gipotezi ye vimoga kongruentnosti plitok odna odnij Dlya podibnih ale ne kongruentnih kubiv mozhliva pifagorova mozayika yaka ye trivialnim kontrprikladom u dvovimirnomu prostori Teoretiko grupove formulyuvannyaSprostuvannya gipotezi Kellera dlya dosit visokih rozmirnostej jshlo cherez poslidovnist zveden yaki peretvoryuyut zadachu z geometriyi mozayik na zadachu teoriyi grup a z neyi na zadachu teoriyi grafiv Hajosh pershim sformulyuvav gipotezu Kellera v terminah faktorizaciyi abelevih grup Vin pokazav sho yaksho j isnuye kontrpriklad gipotezi mozhna vvazhati jogo kubiv z ciloyu dovzhinoyu rebra i z cilimi koordinatami vershin Otzhe shodo gipotezi dosit rozglyadati mozayiki specialnogo viglyadu U comu vipadku grupa cilochiselnih paralelnih perenesen sho zberigayut mozayiku utvoryuye abelevu grupu a elementi grupi vidpovidayut poziciyam plitok mozayiki Hajosh viznachiv simejstvo pidmnozhin Ai abelevoyi grupi yak faktorizaciyu yaksho kozhen element grupi maye yedinij viraz u viglyadi sumi a0 a1 de kozhne ai nalezhit Ai Vidpovidno do cogo viznachennya Hajosh pereformulyuvav gipotezu yaksho abeleva grupa maye faktorizaciyu v yakij persha mnozhina A0 mozhe buti dovilnoyu a kozhna nastupna mnozhina Ai maye osoblivij viglyad 0 gi 2gi 3gi qi 1 gi to prinajmni odin iz elementiv qigi maye nalezhati A0 A0 riznicya Minkovskogo A0 iz samoyu soboyu Sabo pokazav sho bud yaka mozayika sho utvoryuye kontrpriklad gipotezi povinna mati navit specifichnishij viglyad dovzhina storoni kuba dorivnyuye stepenyu dvijki vershini mayut cilochiselni koordinati mozayika periodichna z periodom rivnim podvoyenij dovzhini storoni kuba za kozhnoyu koordinatoyu Gruntuyuchis na comu geometrichnomu sproshenni vin sprostiv teoretiko grupove formulyuvannya Hajosha pokazavshi sho dosit rozglyadati abelevi grupi yaki ye pryamimi sumami ciklichnih grup poryadku chotiri z qi 2 Grafi KelleraGraf Kellera rozmirnosti dva izomorfnij grafu Klebsha Korradi ta Sabo pereformulyuvali rezultat Sabo u viglyadi umovi pro isnuvannya velikoyi kliki v deyakomu simejstvi grafiv yaki zgodom stali nazivatisya grafami Kellera Tochnishe vershini grafa Kellera rozmirnosti n ce 4n elementiv m1 mn de kozhne chislo m dorivnyuye 0 1 2 abo 3 Dvi vershini pov yazani rebrom yaksho voni vidriznyayutsya prinajmni dvoma koordinatami i vidriznyayutsya na dva prinajmni v odnij koordinati Korradi i Sabo pokazali sho najbilsha klika v comu grafi maye rozmir sho ne perevishuye 2n i yaksho isnuye klika takogo rozmiru to gipoteza Kellera hibna Yaksho taku kliku zadano mozhna sformuvati prostir kubiv zi storonoyu dva centri yakih mayut koordinati yaki yaksho brati za modulem chotiri ye vershinami kliki Z umovi sho bud yaki dvi vershini kliki mayut koordinati sho vidriznyayutsya na dva viplivaye sho kubi yaki vidpovidayut cim vershinam ne nakladayutsya Z umovi sho klika maye rozmir 2n viplivaye sho kubi vseredini bud yakogo periodu mozayiki mayut takij samij ob yem yak i sam period Razom iz faktom sho plitki ne nakladayutsya ce daye naslidok sho kubi zamoshuyut prostir Odnak iz umovi sho vershini bud yakih dvoh klik vidriznyayutsya prinajmni dvoma koordinatami viplivaye sho zhodni dva kubi ne mayut spilnih granej Lagarias i Shor u roboti 1992 roku sprostuvali gipotezu Kellera znajshovshi kliku rozmiru 210 u grafi Kellera rozmirnosti 10 Ci kliki prizvodyat do mozayiki v rozmirnosti 10 bez spilnih granej dotikiv gran do grani i kopiyi plitok mozhna pomistiti v prostori zi zmishennyam na polovinu odinici v kozhnomu koordinatnomu napryamku stvoryuyuchi mozayiku bez dotikiv gran do grani u bud yakij vishij rozmirnosti Podibnim sposobom Makej zmenshiv rozmirnosti v yakih znajdeno kontrprikladi viyavivshi kliku rozmiru 28 u grafi Kellera rozmirnosti visim Debroni Eblen Langston i Shor pokazali sho graf Kellera rozmirnosti sim maye najbilshu kliku rozmiru 124 lt 27 Takim chinom u cij rozmirnosti ne vdalosya znajti kontrpriklad do gipotezi Kellera tim samim sposobom sho j u rozmirnosti 10 i 8 ranishe Piznishe pokazano sho yaksho kliki rozmiru 27 nemaye u pevnomu grafi sporidnenomu z grafom Kellera to gipoteza istinna v rozmirnosti 7 Vidsutnist takoyi kliki v comu grafi pokazano v roboti Brakenzika ta in opublikovanij na arXiv org 2019 roku ta v pracyah konferenciyi 2020 roku Umovu vidsutnosti kliki zapisano u viglyadi propozicionalnoyi formuli sprosheno za dopomogoyu specialnoyi programi yiyi nezdijsnennist dovedeno za dopomogoyu avtomatichnogo SAT rozv yazuvacha pislya chogo dovedennya dodatkovo programno formalno verifikovano Rozmiri najbilshih klik grafiv Kellera v malih rozmirnostyah 2 3 4 5 i 6 rivni vidpovidno 2 5 12 28 i 60 Grafi Kellera rozmirnostej 4 5 i 6 vklyucheno v nabir testovih grafiv DIMACS yaki chasto vikoristovuyut yak testi produktivnosti dlya algoritmiv poshuku klik Pov yazani problemiYak pishe Sabo German Minkovskij prijshov do okremogo vipadku gipotezi pro kubichnu mozayiku iz zadachi pro diofantove nablizhennya Odin iz naslidkiv teoremi Minkovskogo bud yaka gratka normalizovana shob mati viznachnik rivnij odinici maye mistiti nenulovu tochku vidstan Chebishova vid yakoyi do pochatku koordinat ne perevishuye odinici Gratki yaki ne mistyat nenulovih tochok z vidstannyu Chebishova strogo menshoyu vid odinici nazivayut kritichnimi i tochki kritichnoyi gratki utvoryuyut centri kubiv kubichnoyi mozayiki Minkovskij 1900 roku pripustiv sho yaksho kubichna gratka maye take roztashuvannya centriv vona maye mistiti dva kubi sho dotikayutsya gran do grani Yaksho ce tak to zavdyaki simetriyi gratki kozhen kub u cij mozayici maye buti chastinoyu stovpcya kubiv i peretini cih kubiv mayut utvoriti kubichnu mozayiku menshoyi rozmirnosti Rozmirkovuyuchi takim chinom Minkovskij pokazav sho u pripushenni istinnosti gipotezi bud yaka kritichna gratka maye bazis yakij mozhna viraziti trikutnoyu matriceyu z odinicyami na golovnij diagonali ta chislami menshimi vid odinici poza diagonallyu en doviv gipotezu Minkovskogo 1942 roku skoristavshis teoremoyu Hajosha pro faktorizaciyu abelevih grup teoretiko grupovij pidhid yakij vin piznishe zastosuvav dlya zagalnishoyi gipotezi Kellera Gipoteza Kellera ye variantom gipotezi Minkovskogo v yakij oslableno umovu sho centri kubiv utvoryuyut gratku Insha pov yazana gipoteza yaku visunuv Fyurtvangler 1936 roku natomist poslablyuye umovu sho kubi utvoryuyut gratku Fyurtvangler zapituvav chi povinna sistema kubiv z centrami v gratci sho utvoryuye k kratne pokrittya prostoru tobto bud yaka tochka prostoru za vinyatkom tochok pidmnozhini miri nul povinna nalezhati vnutrishnosti tochno k kubiv mistiti dva kubi sho dotikayutsya gran do grani Gipoteza Fyurtvanglera istinna dlya rozmirnostej dva i tri a os dlya chotirivimirnogo prostoru Shajosh 1938 roku znajshov kontrpriklad Robinson opisav kombinaciyi chisla kubiv k i rozmirnosti n dlya yakih mozhlivi kontrprikladi Krim togo kombinuyuchi gipotezi Fyurtvanglera i Kellera Robinson pokazav sho k kratne kvadratne pokrittya evklidovoyi ploshini maye mistiti dva kvadrati sho dotikayutsya storona do storoni Odnak dlya bud yakogo k gt 1 ta n gt 2 isnuye k kratne zamoshennya n vimirnogo prostoru kubami yaki ne mayut spilnih granej Yak tilki stali vidomimi kontrprikladi gipotezi Kellera postalo pitannya pro najbilshu rozmirnist granej isnuvannya yakih garantuyetsya v kubiv u kubichnij mozayici Yaksho rozmirnist n ne perevishuye shesti maksimalna rozmirnist dorivnyuye n 1 zgidno z dovedennyam Perrona gipotezi Kellera dlya malih rozmirnostej a pri n ne menshih vosmi najbilsha rozmirnist ne perevishuye n 2 Lagarias i Shor dali strogishu ocinku zverhu n n 3 Josevich i Pedersen a takozh grupa u skladi Lagariasa Rida i Vanga znajshli tisnij zv yazok mizh kubichnimi mozayikami i spektralnoyu teoriyeyu en na kubi Dyutur Sikirich Ito i Poyarkov vikoristali kliki grafiv Kellera yaki maksimalni ale ne ye najbilshimi dlya vivchennya pakuvannya kubiv u prostir do yakih ne mozhna dodati dodatkovogo kuba 1975 roku Lyudvig Dancer i nezalezhno Branko Gryunbaum i Shepard znajshli mozayiku trivimirnogo prostoru paralelepipedami z nahilom granej 60 i 120 v yakij zhodni dva paralelepipedi ne mayut spilnoyi grani PrimitkiKeller 1930 Brakensiek Joshua Heule Marijn Mackey John Narvaez David 2020 The resolution of Keller s conjecture u Peltier Nicolas Sofronie Stokkermans Viorica red Automated Reasoning 10th International Joint Conference IJCAR 2020 Paris France July 1 4 2020 Proceedings Part I Lecture Notes in Computer Science t 12166 Springer s 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 Szabo 1986 Shor 2004 Lysakowska Przeslawski 2008 Lysakowska Przeslawski 2011 Hajos 1949 Corradi Szabo 1990 Debroni Eblen i dr 2011 Brakensiek et al 2020 Kevin Hartnett 19 serpnya 2020 Computer Search Settles 90 Year Old Math Problem Quanta angl originalu za 30 serpnya 2020 Procitovano 30 serpnya 2020 Johnson Trick 1996 Szabo 1993 Robinson 1979 Szabo 1982 Lagarias Shor 1994 Iosevich Pedersen 1998 Lagarias Reeds Wang 2000 Dutour Sikiric Itoh Poyarkov 2007 Grunbaum Shephard 1980 LiteraturaJoshua Brakensiek Marijn Heule John Mackey David Narvaez The Resolution of Keller s Conjecture International Joint Conference on Automated Reasoning 2020 Automated Reasoning Springer 2020 P 48 65 K Corradi S Szabo A combinatorial approach for Keller s conjecture Periodica Mathematica Hungarica Journal of the Janos Bolyai Mathematical Society 1990 T 21 vip 2 S 95 100 DOI 10 1007 BF01946848 Jennifer Debroni John D Eblen Michael A Langston Wendy Myrvold Dinesh Weerapurage 1 2011 S 129 135 z dzherela 18 zhovtnya 2012 Mathieu Dutour Sikiric Yoshiaki Itoh Alexei Poyarkov Cube packings second moment and holes 2007 T 28 vip 3 S 715 725 DOI 10 1016 j ejc 2006 01 008 Branko Grunbaum G C Shephard Tilings with congruent tiles Bulletin of the American Mathematical Society 1980 T 3 vip 3 S 951 973 DOI 10 1090 S0273 0979 1980 14827 2 Sur la factorisation des groupes abeliens Ceskoslovenska Akademie Ved Casopis Pro Pestovani Matematiky 1949 T 74 S 157 162 Alex Iosevich Steen Pedersen Spectral and tiling properties of the unit cube International Mathematics Research Notices 1998 Vip 16 S 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 O H Keller Uber die luckenlose Erfullung des Raumes mit Wurfeln 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 2000 T 103 vip 1 S 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 T 27 vip 2 S 279 283 New Series DOI 10 1090 S0273 0979 1992 00318 X Jeffrey C Lagarias Peter W Shor Cube tilings of Rn and nonlinear codes 1994 T 11 vip 4 S 359 391 DOI 10 1007 BF02574014 Magdalena Lysakowska Krzysztof Przeslawski Keller s conjecture on the existence of columns in cube tilings of Rn 2008 arXiv 0809 1960 Magdalena Lysakowska Krzysztof Przeslawski On the structure of cube tilings and unextendible systems of cubes in low dimensions 2011 T 32 vip 8 S 1417 1427 DOI 10 1016 j ejc 2011 07 003 John Mackey A cube tiling of dimension eight with no facesharing 2002 T 28 vip 2 S 275 279 DOI 10 1007 s00454 002 2801 9 Oskar Perron Uber luckenlose Ausfullung des n dimensionalen Raumes durch kongruente Wurfel 1940a T 46 S 1 26 DOI 10 1007 BF01181421 Oskar Perron Uber luckenlose Ausfullung des n dimensionalen Raumes durch kongruente Wurfel II 1940b T 46 S 161 180 DOI 10 1007 BF01181436 Raphael M Robinson Multiple tilings of n dimensional space by unit cubes 1979 T 166 vip 3 S 225 264 DOI 10 1007 BF01214145 Peter Shor Minkowski s and Keller s cube tiling conjectures 2004 Lecture notes for IAP Mathematics Lecture Series z dzherela 7 travnya 2021 Sandor Szabo Multiple tilings by cubes with no shared faces Aequationes Mathematicae 1982 T 25 vip 1 S 83 89 DOI 10 1007 BF02189600 Sandor Szabo A reduction of Keller s conjecture Periodica Mathematica Hungarica Journal of the Janos Bolyai Mathematical Society 1986 T 17 vip 4 S 265 277 DOI 10 1007 BF01848388 Sandor Szabo Cube tilings as contributions of algebra to geometry Beitrage zur Algebra und Geometrie 1993 T 34 vip 1 S 63 75 z dzherela 3 bereznya 2016 Procitovano 11 chervnya 2022 Chuanming Zong What is known about unit cubes Bulletin of the American Mathematical Society 2005 T 42 vip 2 S 181 211 New Series DOI 10 1090 S0273 0979 05 01050 5

Дата публікації:
Топ