Conjectura lui Keller este ipoteza prezentată de Ott-Heinrich Keller [1] că în orice teselație din spațiul euclidian constând din hipercuburi identice , există două cuburi care se ating față în față. De exemplu, așa cum se arată în figură, în orice placare pe un plan de pătrate identice, aproximativ două pătrate trebuie să atingă margine la margine. Perron a demonstrat că acest lucru este adevărat în dimensiuni de până la 6 [2] [3] ; Brackenzik și coautorii au dovedit corectitudinea conjecturii pentru dimensiunea 7 [4] . Totuși, acest lucru nu este valabil pentru dimensiunile mai mari, așa cum arată Lagarias și Shor pentru dimensiunile 10 și mai mari [5], Makei pentru dimensiunile 8 și mai mari [6] , pentru care am folosit o reformulare a problemei în termeni de număr de clică al unor grafice, cunoscute acum sub numele de grafice Keller .
O conjectura Minkowski înrudită cu privire la rețeaua de placare cubică afirmă că atunci când spațiul este umplut cu cuburi identice cu proprietatea suplimentară că centrele cuburilor formează o rețea , unele cuburi trebuie să atingă față în față. Ipoteza a fost dovedită de Hayosh în 1942.
O familie de seturi închise , numite gresie , formează un parchet sau gresie în spațiul euclidian dacă uniunea lor umple complet spațiul și oricare două seturi distincte din familie au interioare disjunse. Se spune că o placă este monoedrică dacă toate plăcile sale sunt congruente. Conjectura lui Keller se referă la plăci monoedrice în care toate plăcile sunt hipercuburi . Așa cum a spus Szabo [7] , o placare cubică este o placă de hipercuburi congruente care necesită ca toate plăcile să fie translații paralele una de cealaltă fără rotație sau, echivalent, toate marginile plăcilor trebuie să fie paralele cu axele de coordonate. Nu orice placă de cuburi congruente are această proprietate. De exemplu, spațiul tridimensional poate fi placat cu straturi de cuburi care sunt rotite unul față de celălalt la un unghi arbitrar. Shor [8] , pe de altă parte, definește o placare cubică ca o placare arbitrară a spațiului de către hipercuburi și afirmă fără dovezi că laturile paralele cu axele pot fi necesare fără pierderea generalității.
Un hipercub în spațiu n -dimensional are 2n fețe de dimensiunea n - 1, care sunt ele însele hipercuburi. De exemplu, un pătrat are patru margini, iar un cub tridimensional are șase fețe pătrate. Două plăci dintr-o placă cubică (definită prin oricare dintre metodele de mai sus) ating față în față dacă există un hipercub ( n - 1)-dimensional care este o față a ambelor plăci. Conjectura lui Keller afirmă că orice placă cubică conține cel puțin o pereche de plăci care se ating față în față în acest mod.
Versiunea originală a conjecturii lui Keller conținea afirmația mai puternică că orice placare cubică are o coloană de cuburi tangente față în față. Este adevărat în aceleași dimensiuni ca afirmația mai slabă, care este de obicei considerată de cercetători [9] [10] .
O cerință esențială a ipotezei este cerința ca plăcile să fie congruente între ele. Pentru cuburi similare, dar nu congruente , este posibilă o placare pitagoreică , servind ca un contraexemplu trivial în spațiul bidimensional.
Infirmarea conjecturii lui Keller pentru dimensiuni suficient de mari a trecut printr-o succesiune de reduceri care transformă problema din geometria mozaicului într-o problemă de teorie de grup și din aceasta într-o problemă de teoria grafurilor .
Hayosh [11] a fost primul care a formulat conjectura lui Keller în ceea ce privește factorizarea grupurilor abeliene . El a arătat că, dacă există un contraexemplu pentru conjectura, atunci acesta poate fi considerat o împărțire periodică a cuburilor cu lungimi întregi ale laturii și coordonate întregi ale vârfurilor. Astfel, atunci când se studiază o ipoteză, este suficient să se ia în considerare piese de o formă specială. În acest caz, grupul de translații paralele întregi care păstrează mozaicul formează un grup abelian, iar elementele grupului corespund pozițiilor plăcilor de mozaic. Hayosh a definit o familie de submulțimi A i ale unui grup abelian ca factorizare dacă fiecare element al grupului are o expresie unică ca sumă a 0 + a 1 + ..., unde fiecare a i aparține lui A i . Conform acestei definiții, Hayosh a reformulat conjectura - dacă un grup abelian are o factorizare în care prima mulțime A 0 poate fi arbitrară, iar fiecare mulțime ulterioară A i are o formă specială {0, g i , 2 g i , 3 g i , ..., ( q i − 1) g i }, atunci cel puțin unul dintre elementele q i g i trebuie să aparțină lui A 0 − A 0 ( diferența Minkowski a lui A 0 cu sine).
Szabo [7] a arătat că orice tiling care formează un contraexemplu pentru conjectura trebuie să aibă o formă și mai specifică: lungimea unei laturi a unui cub este o putere de doi, vârfurile au coordonate întregi, iar tilingul este periodic cu o perioadă egală cu de două ori lungimea laturii cubului în fiecare coordonată. Pe baza acestei simplificări geometrice, el a simplificat formularea teoretică a grupurilor lui Hajos, arătând că este suficient să luăm în considerare grupurile abeliene care sunt sume directe ale grupurilor ciclice de ordinul patru cu q i = 2.
Corradi și Szabo [12] au reformulat rezultatul lui Szabo sub forma unei condiții privind existența unei clicuri mari într-o anumită familie de grafuri, care mai târziu au devenit cunoscute sub numele de grafuri Keller . Mai precis, vârfurile unui grafic Keller de dimensiunea n sunt 4 n elemente ( m 1 ,..., m n ), unde fiecare număr m este 0, 1, 2 sau 3. Două vârfuri sunt conectate printr-o muchie dacă ele diferă în cel puțin două coordonate și diferă cu două în cel puțin o coordonată. Corradi și Szabo au arătat că cea mai mare clică din acest grafic are o dimensiune de cel mult 2 n , iar dacă există o clică de această dimensiune, atunci conjectura lui Keller nu este adevărată. Având în vedere o astfel de clică, se poate forma un spațiu de cuburi de latura doi ale căror centre au coordonate care, modulo patru, sunt vârfurile clicei. Din condiția ca oricare două vârfuri ale unei clicuri să aibă coordonate care diferă cu două, rezultă că cuburile corespunzătoare acestor vârfuri nu se suprapun. Din condiția ca clica să aibă o dimensiune de 2 n , rezultă că cuburile din orice perioadă a mozaicului au același volum ca și perioada în sine. Împreună cu faptul că plăcile nu se suprapun, acest lucru implică faptul că cuburile placă spațiul. Totuși, din condiția că vârfurile oricăror două clicuri diferă în cel puțin două coordonate, rezultă că nu există două cuburi să aibă fețe comune.
Lagarias și Shor în 1992 [5] au infirmat conjectura Keller prin găsirea unei clicuri de dimensiunea 2 10 în graficul Keller de dimensiunea 10. Aceste clicuri duc la o tiling de dimensiunea 10 fără fețe comune (contact față în față) și copiile plăcilor pot fi plasate în spațiu (compensate cu jumătate de unitate în fiecare direcție de coordonate), creând un mozaic fără contact față în față în orice dimensiune superioară. În mod similar, Makei [6] a redus dimensiunile în care au fost găsite contraexemple, găsind o clică de dimensiunea 2 8 într-un grafic Keller de dimensiunea opt.
Debrony, Eblen, Langston și Shore [13] au arătat că graficul Keller cu șapte dimensiuni are cea mai mare clică cu dimensiunea 124 < 2 7 . Astfel, în această dimensiune, nu a fost posibil să găsim un contraexemplu la conjectura Keller în același mod ca în dimensiunile 10 și 8 mai devreme. Ulterior s-a arătat că, dacă nu există nicio clică de dimensiunea 2 7 într-un anumit grafic legat de graficul Keller, atunci conjectura este adevărată în dimensiunea 7. Absența unei astfel de clici în acest grafic a fost arătată de Brackenzik și colab. pe arXiv.org în 2019 și în lucrările conferinței în 2020. Condiția pentru absența unei clici a fost scrisă ca formulă propozițională , simplificată cu ajutorul unui program special, imposibilitatea acesteia a fost dovedită cu ajutorul unui rezolvator automat SAT , după care demonstrația a fost verificată suplimentar formal de program [4] [14] .
Dimensiunile celor mai mari clicuri de grafice Keller în dimensiuni mici 2, 3, 4, 5 și 6 sunt 2, 5, 12, 28 și, respectiv, 60. utilizate ca teste de performanță pentru algoritmii de căutare a clicurilor [15] .
Așa cum scrie Szabo [16] , Herman Minkowski a ajuns la un caz special al conjecturei de țiglare cubică din problema de aproximare diofantină . Una dintre consecințele teoremei Minkowski este că orice rețea (normalizată pentru a avea un determinant egal cu unu) trebuie să conțină un punct diferit de zero, distanța Chebyshev , de la care până la origine nu depășește unu. Rețelele care nu conțin puncte diferite de zero cu o distanță Chebyshev strict mai mică de unu sunt numite critice, iar punctele rețelei critice formează centrele cuburilor plăcilor cubice. Minkowski a sugerat în 1900 că, dacă o rețea cubică avea un astfel de aranjament de centre, trebuie să conțină două cuburi care se ating față în față. Dacă acest lucru este adevărat, atunci (din cauza simetriei rețelei) fiecare cub din această placare trebuie să facă parte dintr-o coloană de cuburi, iar intersecțiile acestor cuburi trebuie să formeze o placă cubică de dimensiune mai mică. Raționând în acest fel, Minkowski a arătat că (presupunând că ipoteza este adevărată) orice rețea critică are o bază care poate fi exprimată ca o matrice triunghiulară cu cele pe diagonala principală și numere mai mici de unu în afara diagonalei. György Hajos a dovedit conjectura lui Minkowski în 1942 folosind teorema de factorizare a lui Hajos pentru grupurile abeliene, o abordare teoretică a grupurilor pe care a aplicat-o mai târziu la conjectura Keller mai generală.
Ipoteza Keller este o variantă a ipotezei Minkowski, în care condiția ca centrii cuburilor să formeze o rețea este slăbită. O altă presupunere înrudită, avansată de Furtwangler în 1936, relaxează în schimb condiția ca cuburile să formeze o rețea. Furtwangler a întrebat dacă un sistem de cuburi centrate pe zăbrele care formează o acoperire în k - fold a spațiului (adică orice punct din spațiu, cu excepția punctelor dintr-un submult de măsură zero, trebuie să aparțină interioarelor exacte a k cuburi) ar trebui să conțină două cuburi care se ating față în margini. Conjectura lui Furtwangler este adevărată pentru dimensiunile două și trei, dar pentru un spațiu cu patru dimensiuni, Shayosh a găsit un contraexemplu în 1938. Robinson [17] a descris combinații ale numărului de cuburi k și dimensiunii n pentru care sunt posibile contraexemple. În plus, combinând ipotezele lui Furtwangler și Keller, Robinson a arătat că o acoperire pătrată în k -fold a planului euclidian trebuie să conțină două pătrate de la margine la margine. Totuși, pentru orice k > 1 și n > 2, există un k -fold a spațiului n - dimensional prin cuburi care nu au fețe comune [18] .
De îndată ce au devenit cunoscute contraexemple la conjectura lui Keller, s-a pus problema dimensiunii maxime a fețelor a căror existență este garantată pentru cuburile dintr-o placare cubică. Dacă dimensiunea lui n nu depășește șase, atunci dimensiunea maximă este egală cu n - 1 conform demonstrației lui Perron a conjecturii Keller pentru dimensiuni mici, iar pentru n nu mai puțin de opt, dimensiunea maximă nu depășește n - 2. Lagarias și Shor [19] au dat o limită superioară mai strictă, n − √n / 3.
Iosevich și Pedersen [20] , precum și grupul format din Lagarias, Reed și Wang [21] , au găsit o legătură strânsă între plăcile cubice și teoria spectrală a funcțiilor pătrat-integrabile pe cub.
Dutour-Sikirich, Ito și Poyarkov [22] au folosit clicuri de grafice Keller care sunt maxime , dar nu maxime pentru a studia împachetarea cuburilor în spațiu la care nu se poate adăuga niciun cub suplimentar.
În 1975, Ludwig Danzer și, în mod independent, Branko Grünbaum și Shepard au găsit o teselație paralelipipedamică tridimensională cu pante ale feței de 60° și 120°, în care nu există două paralelipipede în comun [23] .
| mozaicuri geometrice | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Periodic |
| ||||||||
| Aperiodic |
| ||||||||
| Alte |
| ||||||||
| Prin configurarea vârfurilor |
| ||||||||