Kellerova domněnka je hypotéza předložená Ottem-Heinrichem Kellerem [1] , že v jakékoli teselaci v euklidovském prostoru sestávajícím z identických hyperkrychlí existují dvě tváří v tvář dotýkající se krychle. Například, jak je znázorněno na obrázku, v jakékoli dlaždici na rovině identických čtverců se musí některá dvě políčka dotýkat okrajem k okraji. Perron dokázal, že to platí v rozměrech do 6 [2] [3] ; Brackenzik a spoluautoři prokázali správnost domněnky pro dimenzi 7 [4] . To však neplatí pro vyšší dimenze, jak ukázali Lagarias a Shor pro dimenze 10 a vyšší [5] , Mackay pro dimenze 8 a vyšší [6] , pro které použili přeformulování problému z hlediska počtu kliků. některé grafy, nyní známé jako Kellerovy grafy .
Související Minkowského domněnka o kubické dlaždicové mřížce uvádí, že když je prostor vyplněn identickými krychlemi s další vlastností, že středy krychlí tvoří mřížku , některé krychle se musí dotýkat tváří v tvář. Hypotézu potvrdil Hayosh v roce 1942.
Rodina uzavřených sad , nazývaných dlaždice , tvoří parkety nebo obklady v euklidovském prostoru, pokud jejich spojení zcela vyplní prostor a jakékoli dvě odlišné sady v rodině mají nesourodé interiéry. Dlaždice se říká, že je monoedrická , pokud jsou všechny její dlaždice shodné. Kellerův dohad se týká monohedrálních obkladů, ve kterých jsou všechny dlaždice hyperkrychle . Jak uvedl Szabo [7] , kubický obklad je obklad shodných hyperkrychlí, který vyžaduje, aby všechny dlaždice byly vzájemně rovnoběžné bez rotace, nebo ekvivalentně, všechny okraje dlaždic musí být rovnoběžné se souřadnicovými osami. Ne každý obklad shodných kostek má tuto vlastnost. Trojrozměrný prostor lze například vydláždit vrstvami krychlí, které jsou vůči sobě natočeny v libovolném úhlu. Naproti tomu Shor [8] definuje kubický obklad jako libovolné obkládání prostoru hyperkrychlemi a bez důkazu tvrdí, že strany rovnoběžné s osami lze vyžadovat bez ztráty obecnosti.
Hyperkrychle v n - rozměrném prostoru má 2n ploch dimenze n − 1, které jsou samy hyperkrychlí. Například čtverec má čtyři hrany a trojrozměrná krychle má šest čtvercových ploch. Dva dlaždice v krychlovém obkladu (definovaném kteroukoli z výše uvedených metod) se dotýkají tváří v tvář , pokud existuje ( n − 1)-rozměrná hyperkrychle, která je tváří obou dlaždic. Kellerův dohad uvádí, že jakýkoli krychlový obklad obsahuje alespoň jeden pár dlaždic, které se tímto způsobem dotýkají tváří v tvář.
Původní Kellerova verze domněnky obsahovala silnější tvrzení, že jakýkoli krychlový obklad má sloupec tečných krychlí tváří v tvář. Platí ve stejných dimenzích jako slabší tvrzení, o kterém vědci obvykle uvažují [9] [10] .
Základním požadavkem hypotézy je požadavek, aby dlaždice byly navzájem shodné. Pro podobné, ale ne shodné kostky je možné pythagorejské pokládání , sloužící jako triviální protipříklad ve dvourozměrném prostoru.
Vyvrácení Kellerovy domněnky o dostatečně vysokých dimenzích prošlo sekvencí redukcí, které transformují problém z mozaikové geometrie na problém teorie grup az něj na problém teorie grafů .
Hayosh [11] byl první, kdo formuloval Kellerovu domněnku v podmínkách faktorizace abelovských skupin . Ukázal, že pokud existuje protipříklad k domněnce, pak jej lze považovat za periodické skládání krychlí s celočíselnými délkami stran a celočíselnými souřadnicemi vrcholů. Při studiu hypotézy tedy stačí uvažovat o obkladech speciální formy. V tomto případě skupina celočíselných paralelních překladů, které zachovávají mozaiku, tvoří abelovskou skupinu a prvky skupiny odpovídají pozicím mozaikových dlaždic. Hayosh definoval rodinu podmnožin A i Abelovské grupy jako faktorizaci , jestliže každý prvek grupy má jedinečný výraz jako součet a 0 + a 1 + ..., kde každé a i náleží A i . Podle této definice Hayosh přeformuloval domněnku - má-li abelovská grupa rozklad, ve kterém první množina A 0 může být libovolná, a každá následující množina A i má speciální tvar {0, g i , 2 g i , 3 g i , ..., ( q i − 1) g i }, pak alespoň jeden z prvků q i g i musí patřit A 0 − A 0 ( Minkowského rozdíl A 0 se sebou samým).
Szabo [7] ukázal, že každý obklad, který tvoří protipříklad k domněnce, musí mít ještě konkrétnější tvar: délka strany krychle je mocninou dvou, vrcholy mají celočíselné souřadnice a obklady jsou periodické s perioda se rovná dvojnásobku délky strany krychle v každé souřadnici. Na základě tohoto geometrického zjednodušení zjednodušil Hajosovu grupově teoretickou formulaci tím, že ukázal, že stačí uvažovat abelovské grupy, které jsou přímými součty cyklických grup řádu čtyři s q i = 2.
Corradi a Szabo [12] Szabův výsledek přeformulovali do podoby podmínky existence velké kliky v určité rodině grafů, které se později začalo říkat Kellerovy grafy . Přesněji řečeno, vrcholy Kellerova grafu dimenze n jsou 4 n prvky ( m 1 ,..., m n ), kde každé číslo m je 0, 1, 2 nebo 3. Dva vrcholy jsou spojeny hranou, jestliže liší se alespoň ve dvou souřadnicích a liší se o dvě alespoň v jedné souřadnici. Corradi a Szabo ukázali, že největší klika v tomto grafu má velikost nejvýše 2 n , a pokud existuje klika této velikosti, pak Kellerova domněnka není pravdivá. S takovou klikou lze vytvořit prostor z krychlí druhé strany, jejichž středy mají souřadnice, modulo čtyři, jsou vrcholy kliky. Z podmínky, že libovolné dva vrcholy kliky mají souřadnice, které se liší o dvě, vyplývá, že krychle odpovídající těmto vrcholům se nepřekrývají. Z podmínky, že klika má velikost 2 n , vyplývá, že kostky v libovolné periodě mozaiky mají stejný objem jako samotná perioda. Spolu s tím, že se dlaždice nepřekrývají, to znamená, že kostky obkládají prostor. Avšak z podmínky, že se vrcholy libovolných dvou klik liší alespoň ve dvou souřadnicích, vyplývá, že žádné dvě krychle nemají společné plochy.
Lagarias a Shor v roce 1992 [5] vyvrátili Kellerovu domněnku tím , že našli kliku o velikosti 2 10 v Kellerově grafu dimenze 10. Tyto kliky vedou k obkladu dimenze 10 bez společných tváří (kontakt tváří v tvář), a kopie dlaždic lze umístit do prostoru (odsazené o půl jednotky v každém směru souřadnic), čímž vznikne mozaika bez přímého kontaktu v jakémkoli vyšším rozměru. Podobně Makei [6] zmenšil rozměry, ve kterých byly nalezeny protipříklady, nalezením kliky o velikosti 2 8 v Kellerově grafu dimenze osm.
Debrony, Eblen, Langston a Shore [13] ukázali, že sedmirozměrný Kellerův graf má největší kliku o velikosti 124 < 2 7 . V této dimenzi tedy nebylo možné najít protipříklad ke Kellerově domněnce, stejně jako v dimenzích 10 a 8 dříve. Později se ukázalo, že pokud v určitém grafu souvisejícím s Kellerovým grafem není klika o velikosti 2 7 , pak je domněnka pravdivá v dimenzi 7. Absenci takové kliky v tomto grafu ukázal Brackenzik et al. na arXiv.org v roce 2019 a ve sborníku z konference v roce 2020. Podmínka nepřítomnosti kliky byla zapsána jako výroková formule , zjednodušená pomocí speciálního programu, její nemožnost byla prokázána pomocí automatického řešiče SAT , načež byl důkaz dodatečně formálně ověřen programem [4] [14] .
Velikosti největších kliků Kellerových grafů v nízkých dimenzích 2, 3, 4, 5 a 6 jsou 2, 5, 12, 28 a 60. Používají se jako testy výkonu pro algoritmy vyhledávání kliknutí [15] .
Jak píše Szabo [16] , Herman Minkowski dospěl ke zvláštnímu případu domněnky o kubických dlaždicích z problému diofantinské aproximace . Jedním z důsledků Minkowského teorému je, že každá mřížka (normalizovaná tak, aby měla determinant rovný jedné) musí obsahovat nenulový bod, Chebyshevovu vzdálenost , od které k počátku nepřesahuje jednu. Mříže, které neobsahují nenulové body s Čebyševovou vzdáleností přísně menší než jedna, se nazývají kritické a body kritické mřížky tvoří středy krychlí kubického obkladu. Minkowski v roce 1900 navrhl, že pokud má kubická mřížka takové uspořádání středů, musí obsahovat dvě krychle, které se dotýkají tváří v tvář. Pokud je to pravda, pak (kvůli symetrii mřížky) musí být každá krychle v tomto obkladu součástí sloupce krychlí a průsečíky těchto krychlí musí tvořit krychlový obklad menšího rozměru. Minkowski tímto způsobem ukázal, že (za předpokladu, že hypotéza je pravdivá) každá kritická mřížka má základ, který lze vyjádřit jako trojúhelníkovou matici s jedničkami na hlavní diagonále a čísly menšími než jedna mimo úhlopříčku. György Hajos dokázal Minkowského domněnku v roce 1942 pomocí Hajosova faktorizačního teorému pro Abelovské grupy, což je skupinově teoretický přístup, který později aplikoval na obecnější Kellerovu domněnku.
Kellerova hypotéza je variantou Minkowského hypotézy, ve které je oslabena podmínka, že středy krychlí tvoří mřížku. Další související domněnka, kterou předložil Furtwangler v roce 1936, místo toho uvolňuje podmínku, že kostky tvoří mřížku. Furtwangler se ptal, zda by systém krychlí se středem mřížky tvořících k - násobné zakrytí prostoru (to znamená, že jakýkoli bod v prostoru, kromě bodů podmnožiny nulové míry, musí patřit k vnitřkům přesně k krychlí), měl obsahovat dvě kostky dotýkající se lícem k hranám. Furtwanglerova domněnka platí pro dimenze dva a tři, ale pro čtyřrozměrný prostor našel Shayosh v roce 1938 protipříklad. Robinson [17] popsal kombinace počtu krychlí k a dimenze n , pro které jsou možné protipříklady. Navíc, kombinací Furtwanglerovy a Kellerovy hypotézy, Robinson ukázal, že k -násobný čtvercový kryt euklidovské roviny musí obsahovat dva čtverce od okraje k okraji. Pro libovolné k > 1 an > 2 však existuje k - násobné skládání n - rozměrného prostoru krychlemi, které nemají společné plochy [18] .
Jakmile vešly ve známost protipříklady ke Kellerově domněnce, vyvstala otázka maximálního rozměru tváří, jejichž existence je pro kostky v krychlovém obkladu zaručena. Pokud rozměr n nepřesahuje šest, pak maximální rozměr je roven n − 1 podle Perronova důkazu Kellerovy domněnky pro malé rozměry a pro n ne menší než osm nepřesahuje maximální rozměr n − 2. Lagarias a Shor [19] uvedli přísnější horní hranici, n − √n / 3.
Iosevich a Pedersen [20] , stejně jako skupina skládající se z Lagariase, Reeda a Wanga [21] , nalezli úzké spojení mezi kubickými obklady a spektrální teorií kvadrátově integrovatelných funkcí na krychli.
Dutour-Sikirich, Ito a Poyarkov [22] použili kliky Kellerových grafů, které jsou maximální , ale ne maximální, ke studiu uspořádání krychlí v prostoru, do kterého nelze přidat další krychli.
V roce 1975 našli Ludwig Danzer a nezávisle na sobě Branko Grünbaum a Shepard trojrozměrnou rovnoběžnostěnnou teselaci se sklony 60° a 120°, ve které žádné dva rovnoběžnostěny nesdílejí tvář [23] .
| geometrické mozaiky | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Pravidelné |
| ||||||||
| aperiodický |
| ||||||||
| jiný |
| ||||||||
| Podle konfigurace vrcholu |
| ||||||||