Przypuszczenie Kellera

W tym ułożeniu płaszczyzny przystającymi kwadratami kwadraty zielony i fioletowy stykają się krawędziami, podobnie jak kwadraty niebieski i pomarańczowy.

W geometrii przypuszczenie Kellera jest przypuszczeniem, że w każdym kafelku $n$ -wymiarowej przestrzeni euklidesowej za pomocą identycznych hipersześcianów istnieją dwa hipersześciany, które dzielą ze sobą całą $(n - 1) -wymiarową ścianę.$ Na przykład, w dowolnym układzie płaszczyzny identycznymi kwadratami, jakieś dwa kwadraty muszą dzielić całą krawędź, tak jak to ma miejsce na ilustracji.

Przypuszczenie to zostało wprowadzone przez Otta-Heinricha Kellera ( 1930 ), od którego pochodzi jego nazwa. Przełom dokonany przez Lagariasa i Shora ( 1992 ) wykazał, że jest on fałszywy w dziesięciu lub więcej wymiarach, a po kolejnych udoskonaleniach obecnie wiadomo, że jest prawdziwy w przestrzeniach o wymiarze najwyżej siedmiu i fałszywy we wszystkich wyższych wymiarach. Dowody tych wyników wykorzystują przeformułowanie problemu w kategoriach liczby klik pewnych grafów, znanych obecnie jako grafy Kellera .

Powiązana hipoteza układania kostek kratowych Minkowskiego stwierdza, że za każdym razem, gdy układanie przestrzeni identycznymi kostkami ma dodatkową właściwość polegającą na tym, że środki kostek tworzą siatkę , niektóre kostki muszą stykać się twarzą w twarz. Udowodnił to György Hajós w 1942 roku.

Szabó (1993) , Shor (2004) i Zong (2005) przedstawiają przegląd prac nad hipotezą Kellera i powiązanymi problemami.

Oświadczenie

Teselacja lub kafelkowanie przestrzeni euklidesowej to intuicyjnie rodzina podzbiorów, które pokrywają całą przestrzeń bez nakładania się . Bardziej formalnie, rodzina zbiorów domkniętych , zwanych kaflami , tworzy kafelki, jeśli ich sumą jest cała przestrzeń, a każde dwa odrębne zbiory w rodzinie mają rozłączne wnętrza. Mówimy, że płytka jest jednościenna , jeśli wszystkie płytki mają ten sam kształt (są do siebie przystające). Hipoteza Kellera dotyczy jednościennych nachyleń, w których wszystkie płytki są hipersześcianami o tym samym wymiarze co przestrzeń. Jak Szabo (1986) formułuje problem, układanie sześcianu to układanie płytek za pomocą przystających hipersześcianów, w których dodatkowo wymaga się, aby wszystkie płytki były wzajemnymi translacjami bez żadnego obrotu lub równoważnie, aby wszystkie ich boki były równoległe do osi współrzędnych przestrzeni. Nie każde ułożenie płytek przystającymi kostkami ma tę właściwość; na przykład przestrzeń trójwymiarowa może być wyłożona dwuwymiarowymi arkuszami kostek, które są skręcone pod dowolnymi kątami względem siebie. Formułując ten sam problem, Shor (2004) zamiast tego rozważa wszystkie nachylenia przestrzeni za pomocą przystających hipersześcianów i stwierdza, bez dowodu, że założenie, że sześciany są równoległe do osi, można dodać bez utraty ogólności.

$N -wymiarowy$ hipersześcian ma $2 n$ ścian o wymiarze $n - 1$ , które same są hipersześcianami; na przykład kwadrat ma cztery krawędzie, a trójwymiarowy sześcian ma sześć kwadratowych ścian. Dwie płytki w kafelku sześcianu (zdefiniowanym na jeden z powyższych sposobów) spotykają się twarzą w twarz , jeśli istnieje hipersześcian wymiarowy ( $n - 1$ ), który jest ścianą ich obu. Hipoteza Kellera polega na stwierdzeniu, że każda płytka kostki ma co najmniej jedną parę płytek, które stykają się twarzą w twarz w ten sposób.

Płytki pitagorejskie pokazują, że nierówne kwadraty mogą układać płaszczyznę bez stykania się krawędzi z krawędziami.

Oryginalna wersja hipotezy sformułowanej przez Kellera była mocniejszym stwierdzeniem: każda płytka kostki ma kolumnę kostek, z których wszystkie spotykają się twarzą w twarz. Ta wersja problemu jest prawdziwa lub fałszywa dla tych samych wymiarów, co jej częściej badane sformułowanie. Niezbędną częścią przypuszczenia jest to, aby wszystkie sześciany w kafelkach były do siebie przystające, ponieważ gdyby dozwolone były sześciany o nierównych rozmiarach, wówczas pitagorejskie kafelki stanowiłyby kontrprzykład w dwóch wymiarach.

Przypuszczenie, jak stwierdzono, nie wymaga, aby wszystkie kostki w kafelku stykały się twarzą w twarz z innymi kostkami. Chociaż kafelkowanie przystających kwadratów na płaszczyźnie ma silniejszą właściwość polegającą na tym, że każdy kwadrat styka się krawędzią z innym kwadratem, niektóre kafelki w kafelkach hipersześcianu o wyższych wymiarach mogą nie stykać się twarzą w twarz z żadnym innym kafelkiem. Na przykład w trzech wymiarach tetrastix utworzona przez trzy prostopadłe zestawy kwadratowych pryzmatów może być wykorzystana do skonstruowania kostki sześciennej, kombinatorycznie równoważnej strukturze Weaire-Phelana , w którym jedna czwarta sześcianów (tych, które nie są częścią żadnego graniastosłupa) jest otoczona dwunastoma innymi sześcianami, nie stykając się z żadnym z nich twarzą w twarz.

Przeformułowanie teorii grup

Perron ( 1940a , 1940b ) wykazał, że hipoteza Kellera jest prawdziwa w wymiarach co najwyżej sześciu . Obalenie hipotezy Kellera, dla wystarczająco wysokich wymiarów, przeszło przez sekwencję redukcji, które przekształcają ją z problemu w geometrii nachylenia w problem w teorii grup, a stamtąd w problem w teorii grafów .

Hajós (1949) jako pierwszy przeformułował hipotezę Kellera w kategoriach faktoryzacji grup abelowych . Pokazuje, że jeśli istnieje kontrprzykład na przypuszczenie, to można założyć, że jest to okresowe układanie sześcianów o całkowitej długości boku i całkowitych pozycjach wierzchołków; tak więc, studiując przypuszczenie, wystarczy wziąć pod uwagę nachylenia tej szczególnej formy. W tym przypadku grupa translacji liczb całkowitych, modulo translacji, które zachowują kafelkowanie, tworzy grupę abelową, a niektóre elementy tej grupy odpowiadają pozycjom płytek. Hajós definiuje rodzinę podzbiorów $A i$ grupy abelowej jest rozkładem na czynniki , jeśli każdy element grupy ma unikalne wyrażenie jako sumę $0 a + a 1 + ...$ , gdzie każdy $a i$ należy do $A i$ . Z tą definicją przeformułowana hipoteza Hajósa jest taka, że ilekroć grupa abelowa ma rozkład na czynniki, w którym pierwszy zbiór $A 0$ może być dowolny, ale każdy kolejny zbiór $A i$ przyjmuje specjalną postać ${0, g i, 2 g i, 3 sol ja, ..., (| ZA ja | - 1) sol ja$ } dla pewnego elementu $g ja$ z $A i$ , to co najmniej jeden element $| ja |_g i$ musi należeć do $0 A - A 0$ ( zbiór różnic $A 0$ z samym sobą).

Szabó (1986) wykazał, że można przyjąć, że każde układanie płytek, które stanowi kontrprzykład dla hipotezy, ma jeszcze bardziej specjalną postać: sześciany mają długość boku potęgę dwójki i całkowite współrzędne wierzchołków, a układanie płytek jest okresowe z okresem dwukrotnie dłuższym od boku długości sześcianów w każdym kierunku współrzędnych. Opierając się na tym uproszczeniu geometrycznym, uprościł również sformułowanie teorii grup Hajósa, pokazując, że wystarczy wziąć pod uwagę grupy abelowe, które są bezpośrednimi sumami grup cyklicznych rzędu czwartego, gdzie każda $q i = 2$ .

wykresy Kellera

Wykres Kellera wymiaru drugiego, izomorficzny z wykresem Clebscha .

Corrádi i Szabó (1990) przeformułowali wynik Szabó jako warunek istnienia dużej kliki w pewnej rodzinie grafów, która później stała się znana jako grafy Kellera . Dokładniej, wierzchołki wykresu Kellera o wymiarze $n$ to $4 n$ elementów $(m 1,..., m n)$ , gdzie każde $m$ wynosi 0, 1, 2 lub 3. Dwa wierzchołki są połączone krawędzią, jeśli różnią się co najmniej dwoma współrzędnymi i różnią się dokładnie o dwa co najmniej jedną współrzędną. Corrádi i Szabó wykazali, że maksymalna klika na tym wykresie ma rozmiar co najwyżej $2 n$ , a jeśli istnieje klika o takim rozmiarze, to hipoteza Kellera jest fałszywa. Biorąc pod uwagę taką klikę, można utworzyć pokrycie przestrzeni sześcianami o boku drugim, których środki mają współrzędne, które wzięte modulo cztery są wierzchołkami kliki. Warunek, że dowolne dwa wierzchołki kliki mają współrzędne różniące się o dwa, oznacza, że sześciany odpowiadające tym wierzchołkom nie zachodzą na siebie. Warunek, że wierzchołki różnią się dwoma współrzędnymi, oznacza, że te sześciany nie mogą się stykać twarzą w twarz. Warunek, że klika ma rozmiar $2 n$ oznacza, że sześciany w dowolnym okresie układania mają taką samą całkowitą objętość jak sam okres. Wraz z faktem, że nie zachodzą na siebie, oznacza to, że kostki ułożone w ten sposób układają się w przestrzeń bez stykania się twarzą w twarz.

Lagarias i Shor ( 1992 ) obalili hipotezę Kellera, znajdując klikę o rozmiarze 2 ¹⁰ na wykresie Kellera o wymiarze 10. Ta klika prowadzi do układania płytek nietwarzą w twarz w wymiarze 10, a jej kopie można układać w stosy ( przesunięte o pół jednostki w każdym kierunku współrzędnych) w celu uzyskania niestykających się ze sobą powierzchni w dowolnym wyższym wymiarze. Podobnie Mackey (2002) znalazł klikę o rozmiarze 2 ⁸ na grafie Kellera o wymiarze ósmym, prowadzącą w ten sam sposób do układania kafelków nietwarzą w twarz w wymiarze 8 i (przez układanie w stosy) w wymiarze 9.

Następnie Debroni i in. (2011) wykazali, że wykres Kellera w wymiarze siódmym ma maksymalną klikę o rozmiarze 124. Ponieważ jest to mniej niż 2 · ⁷ = 128, wersja hipotezy Kellera opartej na teorii grafów jest prawdziwa w siedmiu wymiarach. Jednak tłumaczenie z układania sześcianów na teorię grafów może zmienić wymiar problemu, więc ten wynik nie rozstrzyga geometrycznej wersji hipotezy w siedmiu wymiarach. Wreszcie 200-gigabajtowy dowód wspomagany komputerowo w 2019 roku wykorzystał wykresy Kellera, aby ustalić, czy przypuszczenie jest prawdziwe w siedmiu wymiarach. Dlatego pytanie postawione przez Kellera można uznać za rozwiązane: przypuszczenie jest prawdziwe w siedmiu wymiarach lub mniej, ale jest fałszywe, gdy jest więcej niż siedem wymiarów.

Rozmiary maksymalnych klik na wykresach Kellera o wymiarach 2, 3, 4, 5 i 6 wynoszą odpowiednio 2, 5, 12, 28 i 60. Wykresy Kellera o wymiarach 4, 5 i 6 zostały zawarte w zestawie „wykresów wyzwań DIMACS” często używanych jako punkt odniesienia dla algorytmów wyszukiwania klik .

Powiązane problemy

Jak opisuje Szabó (1993) , Hermann Minkowski został doprowadzony do szczególnego przypadku hipotezy układania sześcianów na podstawie problemu aproksymacji diofantycznej . Jedną z konsekwencji twierdzenia Minkowskiego jest to, że każda krata (znormalizowana tak, aby miała wyznacznik ) musi zawierać niezerowy punkt, którego odległość Czebyszewa od początku wynosi co najwyżej jeden. Kraty, które nie zawierają niezerowego punktu z odległością Czebyszewa ściśle mniejszą niż jeden, nazywane są krytycznymi , a punkty sieci krytycznej tworzą środki sześcianów w ułożeniu sześcianu. Minkowski wywnioskował w 1900 r., Że ilekroć kostki układające się w kostkę mają swoje kostki wyśrodkowane w punktach siatki w ten sposób, muszą zawierać dwa kostki, które stykają się twarzą w twarz. Jeśli to prawda, to (z powodu symetrii siatki) każdy sześcian w ułożeniu musi być częścią kolumny sześcianów, a przekroje tych kolumn tworzą ułożenie sześcianu o jeden mniejszy wymiar. Rozumując w ten sposób Minkowski wykazał, że (zakładając prawdziwość swojego przypuszczenia) każda krata krytyczna ma bazę, którą można wyrazić jako macierz trójkątną , z jedynkami na głównej przekątnej i liczbami mniejszymi niż jeden od przekątnej. György Hajós udowodnił hipotezę Minkowskiego w 1942 r., Używając twierdzenia Hajósa o faktoryzacji grup abelowych, metody teorii grup podobnej do tej, którą później zastosował do bardziej ogólnej hipotezy Kellera.

Hipoteza Kellera jest wariantem hipotezy Minkowskiego, w której warunek, że środki sześcianów tworzą siatkę, jest złagodzony. Druga pokrewna hipoteza, wysunięta przez Furtwänglera w 1936 r., Zamiast tego rozluźnia warunek, że kostki tworzą płytki. Furtwängler zapytał, czy system sześcianów wyśrodkowany na punktach sieci tworzących $k$ -krotne pokrycie przestrzeni (to znaczy wszystkie podzbiór punktów w przestrzeni z wyjątkiem miary zero musi być wewnętrzny do dokładnie $k$ sześciany) muszą koniecznie mieć dwa sześciany stykające się twarzą w twarz. Przypuszczenie Furtwänglera jest prawdziwe dla przestrzeni dwu- i trójwymiarowej, ale Hajós znalazł czterowymiarowy kontrprzykład w 1938 r. Robinson (1979) scharakteryzował kombinacje $k$ i wymiaru $n$ , które pozwalają na kontrprzykład. Dodatkowo, łącząc hipotezy Furtwänglera i Kellera, Robinson wykazał, że $k$ -krotne kwadratowe pokrycia płaszczyzny euklidesowej muszą zawierać dwa kwadraty, które stykają się krawędziami. Jednak dla każdego $k > 1$ i każdego $n > 2$ , istnieje $k$ -krotne ułożenie $n$ -wymiarowej przestrzeni przez sześciany bez wspólnych ścian.

Gdy znane były kontrprzykłady do hipotezy Kellera, interesujące stało się zapytanie o maksymalny wymiar wspólnej powierzchni, który można zagwarantować w kafelku sześcianu. Kiedy wymiar $n$ wynosi co najwyżej siedem, ten maksymalny wymiar wynosi po prostu $n - 1$ , na podstawie dowodów hipotezy Kellera dla tych małych wymiarów, a gdy $n$ wynosi co najmniej osiem, to ten maksymalny wymiar wynosi co najwyżej $n - 2$ . Lagarias i Shor (1994) wykazali, że jest to co najwyżej $n - \sqrt n /3$ , silniejszy dla dziesięciu lub więcej wymiarów.

Iosevich i Pedersen (1998) oraz Lagarias, Reeds i Wang (2000) odkryli bliskie powiązania między nachylaniem sześcianu a teorią widmową funkcji całkowalnych z kwadratem na sześcianie.

Dutour Sikirić, Itoh i Poyarkov (2007) wykorzystują kliki w grafach Kellera, które są maksymalne , ale nie maksymalne, do badania upakowania kostek w przestrzeni, której nie można rozszerzyć przez dodanie dodatkowych kostek.

W 1975 roku Ludwig Danzer i niezależnie Branko Grünbaum i GC Shephard odkryli ułożenie trójwymiarowej przestrzeni za pomocą równoległościanów o kątach twarzy 60 ° i 120 °, w których żadne dwa równoległościany nie mają wspólnej ściany.

Notatki

Brakensiek, Jozue; Heule, Marijn ; Mackey, John; Narváez, David (2020), „Rezolucja hipotezy Kellera”, w: Peltier, Nicolas; Sofronie-Stokkermans, Viorica (red.), Automated Reasoning: 10th International Joint Conference, IJCAR 2020, Paryż, Francja, 1–4 lipca 2020 r., Proceedings, Part I , Lecture Notes in Computer Science, tom. 12166, Springer, s. 48–65, arXiv : 1910.03740 , doi : 10.1007/978-3-030-51074-9_4 , S2CID 203951899
Conway, John H .; Burgiel, Heidi; Goodman-Strauss, Chaim (2008), „Zrozumienie baniek irlandzkich” , The Symmetry of Things , Wellesley, Massachusetts: AK Peters, s. 351, ISBN 978-1-56881-220-5 , MR 2410150
Corrádi, K.; Szabó, S. (1990), „Kombinatoryczne podejście do hipotezy Kellera”, Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society , 21 (2): 95–100, doi : 10.1007/BF01946848 , MR 1070948 , S2CID 121453908 .
Debroni, Jennifer; Eblen, John D.; Langston, Michael A .; Szor, Piotr ; Myrvold, Wendy ; Weerapurage, Dinesh (2011), „Pełne rozwiązanie problemu maksymalnej kliki Kellera” (PDF) , Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms , s. 129–135, doi : 10.1137 / 1.9781611973082.11 , hdl : 1721.1/81184 , S2CID 15797721 .
Dutour Sikirić, Mathieu; Ito, Yoshiaki; Poyarkov, Alexei (2007), „Uszczelnienia kostki, drugi moment i dziury”, European Journal of Combinatorics , 28 (3): 715–725, arXiv : math/0509100 , doi : 10.1016/j.ejc.2006.01.008 , MR 2300752 , S2CID 15876010 .
Grünbaum, Branko ; Shephard, GC (1980), „Nachylenia z przystającymi płytkami”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 3 (3): 951–973, doi : 10.1090 / S0273-0979-1980-14827-2 , MR 0585178 .
Hajós, G. (1949), „Sur la faktoryzacja des groupes abéliens”, Československá Akademie Věd. Časopis Pro Pěstování Matematiky , 74 : 157–162, MR 0045727 .
Hartnett, Kevin (19 sierpnia 2020), „Wyszukiwarka komputerowa rozwiązuje 90-letni problem matematyczny” , Quanta Magazine .
Iosevich, Alex; Pedersen, Steen (1998), „Widmowe i kafelkowe właściwości sześcianu jednostkowego”, International Mathematics Research Notices , 1998 (16): 819–828, arXiv : math / 0104093 , doi : 10,1155 / S1073792898000506 , MR 1643694 , S2CID 1423 2561 .
Johnson, David S .; Trick, Michael A. (1996), Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, warsztaty, 11–13 października 1993 r. , Boston, MA, USA: American Mathematical Society, ISBN 0-8218-6609-5 . Zobacz w szczególności strony 43, 114, 147, 156 i 161–163, opisujące różne wyniki obliczeń na wykresach Kellera zawartych w tym zestawie wyzwań.
Keller, O.-H. ( 1930 ) . _ _ _ _ _ _ _ , S2CID 199547028 .
Lagarias, Jeffrey C .; Reeds, James A.; Wang, Yang (2000), „Ortonormalne podstawy wykładników dla $”$ , Duke Mathematical Journal , 103 (1): 25–37, CiteSeerX 10.1.1.207.4194 , doi : 10.1215 / S0012- 7094-00-10312-2 , MR 1758237 .
Lagarias, Jeffrey C .; Shor, Peter W. (1992), „Przypuszczenie układania kostek Kellera jest fałszywe w dużych wymiarach”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , New Series, 27 (2): 279–283, arXiv : math / 9210222 , Bibcode : 1992math .....10222L , doi : 10.1090/S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600 .
Lagarias, JC ; Shor, PW (1994) , „ $Układanie$ kostek i kodów nieliniowych”, Discrete and Computational Geometry , : 359–391, doi : 10,1007 / BF02574014 , MR 1273224 .
Łysakowska, Magdalena; Przesławski, Krzysztof (2011), „O strukturze płytek sześciennych i nierozciągliwych układów kostek w małych wymiarach”, European Journal of Combinatorics , 32 (8): 1417–1427, doi : 10.1016/j.ejc.2011.07.003 .
Łysakowska, Magdalena; Przesławski, $(2$ (2012), „Przypuszczenie Kellera dotyczące istnienia kolumn w nachyleniu sześcianu , Advances in Geometry , 12 ): 329–352, arXiv : 0809.1960 , doi : 10.1515/advgeom.2011.055 , MR 2911153 , S2CID 14016886
Mackey, John (2002), „Dachówka kostki wymiaru ósmego bez współdzielenia twarzy”, Discrete and Computational Geometry , 28 (2): 275–279, doi : 10.1007 / s00454-002-2801-9 , MR 1920144 .
Perron, Oskar (1940a), "Über lückenlose Ausfüllung des ${\ displaystyle n}$ -dimensionalen Raumes durch kongruente Würfel", Mathematische Zeitschrift , 46 : 1–26, doi : 10.1007 / BF01181421 , MR 0003041 , S2CID 1862 36462 .
Perron Oskar ( 1940b ) $.$ _ _ _ _ _ _ _ _ _ _ _ _
Robinson, Raphael M. (1979), „Wiele nachyleń $)$ przestrzeni za pomocą kostek jednostkowych” , Mathematische Zeitschrift , 166 (3 : 225–264, doi : 10.1007 / BF01214145 , MR 0526466 , S2CID 123242152 .
Shor, Peter (2004), hipotezy układania kostek Minkowskiego i Kellera , Notatki z serii wykładów z matematyki IAP .
Szabó, Sándor (1982), „Wiele płytek na kostkach bez wspólnych ścian” (PDF) , Aequationes Mathematicae , 25 (1): 83–89, doi : 10.1007/BF02189600 , MR 0716380 , S2CID 122364522 .
Szabó, Sándor (1986), „Redukcja hipotezy Kellera”, Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society , 17 (4): 265–277, doi : 10.1007/BF01848388 , MR 0866636 , S2CID 120163301 .
Szabó, Sándor (1993), „Układanie kostek jako wkład algebry w geometrię” , Beiträge zur Algebra und Geometrie , 34 (1): 63–75, MR 1239279 .
Zong, Chuanming (2005), „Co wiadomo o kostkach jednostkowych”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , New Series, 42 (2): 181–211, doi : 10.1090 / S0273-0979-05-01050-5 , MR 2133310 .