Kellers dohad - Kellers conjecture - Wikipedia

Kellerovu domněnku o polynomiálních mapách viz Jacobian dohad.
V tomto obložení roviny shodnými čtverci se zelené a fialové čtverce setkávají od okraje k okraji stejně jako modré a oranžové čtverce.

v geometrie, Kellerova domněnka je domněnka, že v každém obklady z Euklidovský prostor identickým hyperkrychle existují dvě kostky, které se setkávají tváří v tvář. Například, jak je znázorněno na obrázku, v jakémkoli obložení roviny stejnými čtverci se některé dva čtverce musí setkat od okraje k okraji.

Tuto domněnku představil Ott-Heinrich Keller  (1930 ), po kom je pojmenován. Po průlomu od Lagarias a Shor  (1992 ) ukázal, že je nepravdivý ve vysokých dimenzích, je nyní známo, že je pravdivý v prostorech dimenze nejvýše sedm a nepravdivý ve všech vyšších dimenzích. Důkazy těchto výsledků využívají přeformulování problému, pokud jde o číslo kliky některých grafů nyní známých jako Kellerovy grafy.

Související Minkowského domněnka o mřížkové krychli uvádí, že kdykoli má dlažba prostoru identickými kostkami další vlastnost, středy krychle tvoří a mříž, některé kostky se musí setkat tváří v tvář. Dokázal to György Hajós v roce 1942.

Szabó (1993), Shor (2004), a Zong (2005) poskytnout průzkumy prací na Kellerově domněnce a souvisejících problémech.

Definice

Rodina uzavřené sady volala dlaždice tvoří a mozaikování nebo obklady euklidovského prostoru, pokud je jejich sjednocením celý prostor a každé dvě odlišné množiny v rodině mají nesouvislé interiéry. Obklad se říká, že je monohedrální pokud jsou všechny dlaždice shodné. Kellerova domněnka se týká monohedrálních obkladů, ve kterých jsou všechny dlaždice hyperkrychle stejné dimenze jako prostor. Tak jako Szabó (1986) formuluje problém, a obklady kostky je obklad kongruentními hyperkrychlemi, ve kterých jsou dlaždice navíc vyžadovány pro všechny překlady navzájem bez jakékoli rotace nebo ekvivalentně tak, aby všechny jejich strany byly rovnoběžné s koordinačními osami prostoru. Ne každá dlažba shodnými kostkami má tuto vlastnost: například trojrozměrný prostor může být obložen dvourozměrnými listy kostek, které jsou navzájem zkroucené v libovolných úhlech. Shor (2004) místo toho definuje obklad krychle jako jakýkoli obklad prostoru shodnými hyperkrychlemi a uvádí bez důkazu, že předpoklad, že kostky jsou osově paralelní, lze přidat bez ztráty obecnosti.

An n-dimenzionální hyperkrychle má 2n tváře dimenze n - 1, které jsou samy o sobě hyperkrychlemi; například čtverec má čtyři hrany a trojrozměrná krychle má šest čtvercových ploch. Dvě dlaždice v obkladu krychle (definované jedním z výše uvedených způsobů) se setkávají z očí do očí pokud existuje (n - 1) -dimenzionální hyperkrychle, která je tváří obou. Kellerova domněnka je tvrzení, že každý obklad kostky má alespoň jeden pár dlaždic, které se tímto způsobem setkávají tváří v tvář.

The Pythagorovy obklady ukazuje, že nerovné čtverce mohou srovnat rovinu, aniž by se setkaly od okraje k okraji.

Původní verze domněnky, kterou uvedl Keller, byla pro silnější tvrzení, že každý obklad kostky má sloupec kostek, které se všechny setkávají tváří v tvář; tato verze problému je pravdivá nebo nepravdivá pro stejné dimenze jako její běžněji studovaná formulace. (Łysakowska & Przesławski2008, 2011 Je nezbytnou součástí domněnky, že všechny kostky v obkladu musí být navzájem shodné, protože pokud jsou povoleny podobné, ale ne shodné kostky, pak Pythagorovy obklady by vytvořil triviální protiklad ve dvou dimenzích.

Skupinová teoretická formulace

Ukázalo se, že Kellerova domněnka je pravdivá v rozměrech maximálně 6 × Perron  (1940a, 1940b ). Vyvrácení Kellerova domněnky pro dostatečně vysoké rozměry pokročilo posloupností redukcí, které ji transformovaly z problému v geometrii obkladů na problém v teorie skupin, a odtud do problému v teorie grafů.

Hajós (1949) první přeformulovaná Kellerova domněnka, pokud jde o faktorizace abelianské skupiny. Ukazuje, že existuje-li protiklad k domněnce, lze jej považovat za a periodické obklady kostek s délkou celé strany a pozicemi celočíselných vrcholů; při studiu domněnky tedy stačí vzít v úvahu náklony této speciální formy. V tomto případě skupina celočíselných překladů, moduluje překlady, které zachovávají obklady, tvoří abelianskou skupinu a určité prvky této skupiny odpovídají pozicím dlaždic. Hajós definuje rodinu podmnožin Ai abelianské skupiny být a faktorizace pokud má každý prvek skupiny jedinečný výraz jako součet A0 + A1 + ..., kde každý Ai patří Ai. S touto definicí Hajósova přeformulovaná domněnka spočívá v tom, že kdykoli má Abelianova skupina faktorizaci, ve které první sada A0 může být libovolný, ale každá následující sada Ai má speciální formulář {0,Gi, 2Gi, 3Gi, ..., (qi − 1)Gi}, pak alespoň jeden z prvků qiGi musí patřit A0 −A0 (dále jen sada rozdílů z A0 sám se sebou).

Szabó (1986) ukázal, že jakýkoli obklad, který tvoří protiklad k domněnce, lze předpokládat, že má ještě zvláštnější formu: kostky mají délku strany sílu dvou a celočíselných vrcholných souřadnic a obklad je periodický s periodou dvojnásobnou délkou strany kostek v každém směru souřadnic. Na základě tohoto geometrického zjednodušení také zjednodušil Hajósovu skupinově-teoretickou formulaci, což ukazuje, že stačí vzít v úvahu abelianské skupiny, které jsou přímými součty cyklické skupiny řádu čtyři a s každým qi = 2.

Kellerovy grafy

Kellerův graf dimenze dva, izomorfní s Clebschův graf.

Corrádi & Szabó (1990) přeformuloval Szabóův výsledek jako podmínku existence velkého klika v určité rodině grafů, která se následně stala známou jako Kellerovy grafy. Přesněji, vrcholy Kellerova grafu dimenze n jsou 4n elementy (m1,...,mn) kde každý m je 0, 1, 2 nebo 3. Dva vrcholy jsou spojeny hranou, pokud se liší alespoň ve dvou souřadnicích a liší se přesně dvěma v alespoň jedné souřadnici. Corrádi a Szabó ukázali, že maximální klika v tomto grafu má velikost maximálně 2n, a že pokud existuje klika této velikosti, pak je Kellerova domněnka nepravdivá. S takovou klikou lze vytvořit pokrytí prostoru kostkami druhé strany, jejíž středy mají souřadnice, které, když se vezmou modulo čtyři, jsou vrcholy kliky. Podmínka, že kterékoli dva vrcholy kliky mají souřadnici, která se liší o dvě, znamená, že kostky odpovídající těmto vrcholům se nepřekrývají. Podmínka, že klika má velikost 2n znamená, že kostky v libovolném období obkladu mají stejný celkový objem jako samotné období. Spolu se skutečností, že se nepřekrývají, to znamená, že kostky umístěné tímto způsobem vedle sebe. Podmínka, že se dva vrcholy kliky liší alespoň na dvou souřadnicích, však znamená, že žádné dvě kostky nemají společnou plochu.

Lagarias a Shor (1992 ) vyvrátil Kellerovu domněnku hledání kliky velikosti 210 v Kellerově grafu dimenze 10. Tato klika vede k obkladu tváří v tvář v dimenzi 10 a její kopie lze skládat (odsazené o polovinu jednotky v každém směru souřadnic), aby se vytvořily tváří v tvář - obklady povrchu v jakékoli vyšší dimenzi. Podobně, Mackey (2002) zmenšil rozměr, ve kterém je znám protipříklad k domněnce, nalezením kliky o velikosti 28 v Kellerově grafu dimenze osm.

Následně Debroni a kol. (2011) ukázal, že Kellerův graf dimenze sedm má maximální kliku velikosti 124 <27. Protože to je méně než 27, graficko-teoretická verze Kellerova domněnky je pravdivá v sedmi rozměrech. Překlad z obkladů krychle na teorii grafů však může změnit rozměr problému, takže tento výsledek neusadí geometrickou verzi domněnky v sedmi rozměrech.

Nakonec 200 gigabajt počítačem podporovaný důkaz v roce 2019 použil Kellerovy grafy k prokázání, že domněnka platí v sedmi rozměrech (Brakensiek et al. 2020 ). Proto může být otázka, kterou položil Keller, považována za vyřešenou: domněnka je pravdivá v sedmi dimenzích nebo méně, ale je nepravdivá, když existuje více než sedm dimenzí (Hartnett 2020 ).

Velikosti maximálních klik v Kellerových grafech rozměrů 2, 3, 4, 5 a 6 jsou 2, 5, 12, 28 a 60. Kellerovy grafy rozměrů 4, 5 a 6 byly součástí sady „grafů výzev DIMACS“ často používaných jako a měřítko pro algoritmy hledání klik (Johnson & Trick 1996 ).

Související problémy

Tak jako Szabó (1993) popisuje, Hermann Minkowski byl veden ke speciálnímu případu domněnky krychle o obkladu z problému v diofantická aproximace. Jedním z důsledků Minkowského věta je to vůbec mříž (normalizováno mít určující jeden) musí obsahovat nenulový bod, jehož Čebyševova vzdálenost k původu je nanejvýš jeden. Mřížky, které neobsahují nenulový bod s Čebyševovou vzdáleností striktně menší než jedna, se nazývají kritické a body kritické mřížky tvoří středy kostek v obkladu krychle. Minkowski se domníval v roce 1900, že kdykoli má obklad krychle své kostky vycentrované v mřížových bodech tímto způsobem, musí obsahovat dvě kostky, které se setkávají tváří v tvář. Pokud je to pravda, pak (kvůli symetrii mřížky) musí být každá krychle v obkladu součástí sloupu kostek a průřezy těchto sloupů tvoří obklad kostky jedné menší dimenze. Tímto způsobem Minkowski ukázal, že (za předpokladu pravdivosti jeho domněnky) má každá kritická mřížka základ, který lze vyjádřit jako trojúhelníková matice, s těmi na hlavní úhlopříčce a čísly méně než jedna od úhlopříčky. György Hajós prokázal Minkowského domněnku v roce 1942 Hajósova věta o faktorizacích abelianských skupin, podobná metoda skupiny-teoretická jako ta, kterou později použil na Kellerovu obecnější domněnku.

Kellerova domněnka je variantou Minkowského domněnky, ve které je uvolněná podmínka, že středy krychle tvoří mřížku. Druhá domněnka, kterou vytvořil Furtwängler v roce 1936, místo toho uvolňuje podmínku, že kostky tvoří obklad. Furtwängler se zeptal, zda soustava kostek se soustředila na mřížové body a tvořila a k-násobné pokrytí prostoru (to znamená, že všechny podmnožiny bodů v prostoru s nulovou mírou musí být přesně v interiéru k kostky) musí mít nutně dvě kostky, které se setkávají tváří v tvář. Furtwänglerova domněnka platí pro dvourozměrný prostor, ale Hajós našel v roce 1938 čtyřrozměrný protiklad. Robinson (1979) charakterizoval kombinace k a dimenze n které umožňují protiklad. Robinson to navíc kombinoval jak s Furtwänglerovými, tak s Kellerovými domněnkami k- skládané čtvercové krytiny euklidovské roviny musí zahrnovat dva čtverce, které se setkávají od okraje k okraji. Nicméně pro každého k > 1 a každý n > 2 existuje k- skládací obklady n-dimenzionální prostor kostkami bez sdílených tváří (Szabó 1982 ).

Jakmile se staly známé protiklady Kellerova domněnky, stalo se zajímavé požádat o maximální rozměr sdílené tváře, který lze zaručeně existovat v obkladu krychle. Když dimenze n je maximálně šest, tato maximální dimenze je spravedlivá n - 1, podle Perronova důkazu Kellerova domněnky o malých rozměrech a kdy n je nejméně osm, pak je tento maximální rozměr maximálně n − 2. Lagarias & Shor (1994) silněji ukázal, že to je nanejvýš n − √n/3.

Iosevich & Pedersen (1998) a Lagarias, Reeds & Wang (2000) našel úzké spojení mezi obklady kostek a spektrální teorie z čtvercově integrovatelné funkce na krychli.

Dutour Sikirić, Itoh a Poyarkov (2007) použijte kliky v grafech Keller, které jsou maximální ale ne maximálně pro studium balení kostek do vesmíru, které nelze rozšířit přidáním dalších kostek.

V roce 1975 Ludwig Danzer a samostatně Branko Grünbaum a G. C. Shephard našel obklad trojrozměrného prostoru podle rovnoběžnostěny s úhly obličeje 60 ° a 120 °, ve kterých žádné dva rovnoběžnostěny nesdílejí obličej; vidět Grünbaum & Shephard (1980).

Reference