Kellerin olettamus on Ott-Heinrich Kellerin [1] esittämä hypoteesi, jonka mukaan missä tahansa euklidisen avaruuden tessellaatiossa , joka koostuu identtisistä hyperkuutioista , on kaksi kasvotusten koskettavaa kuutiota. Esimerkiksi, kuten kuvasta näkyy, missä tahansa laatoituksessa identtisten neliöiden tasossa noin kahden ruudun on koskettava reunasta reunaan. Perron osoitti, että tämä pitää paikkansa aina 6:een asti [2] [3] ; Brackenzik ja muut kirjoittajat osoittivat arvelun oikeellisuuden ulottuvuudelle 7 [4] . Tämä ei kuitenkaan pidä paikkaansa korkeampien ulottuvuuksien kohdalla, kuten Lagarias ja Shor ovat osoittaneet, kun mitat ovat 10 ja sitä suuremmat [5], Makei dimensiolle 8 ja sitä suuremmille [6] , joissa käytimme ongelman uudelleenmuotoilua joidenkin graafien klikkausmäärän suhteen , joka tunnetaan nykyään Keller-graafina .
Tähän liittyvä Minkowski-oletus kuutiomaisesta laatoitushilasta väittää, että kun tila täytetään identtisillä kuutioilla, joiden lisäominaisuus on, että kuutioiden keskipisteet muodostavat hilan , joidenkin kuutioiden on koskettava kasvotusten. Hayosh todisti hypoteesin vuonna 1942.
Suljettujen sarjojen perhe , jota kutsutaan laatoiksi , muodostaa parketin tai laatoituksen euklidisessa tilassa, jos niiden liitto täyttää tilan kokonaan ja missä tahansa perheen kahdessa erillisessä sarjassa on hajanaiset sisätilat. Laatoituksen sanotaan olevan yksitasainen , jos kaikki sen laatat ovat yhteneväisiä. Kellerin olettamus viittaa monohedraalisiin laatoituksiin, joissa kaikki laatat ovat hyperkuutioita . Kuten Szabo [7] sanoi , kuutiolaatoitus on yhtenevien hyperkuutioiden laatoitus, joka edellyttää, että kaikki laatat ovat rinnakkaisia toistensa käännöksiä ilman kiertoa, tai vastaavasti, laattojen kaikkien reunojen on oltava yhdensuuntaisia koordinaattiakselien kanssa. Kaikilla yhteneväisten kuutioiden laatoilla ei ole tätä ominaisuutta. Esimerkiksi kolmiulotteinen tila voidaan laatoittaa kuutiokerroksilla, joita kierretään toistensa suhteen mielivaltaisessa kulmassa. Shor [8] puolestaan määrittelee kuutiolaatoituksen mielivaltaiseksi tilan laatoituksena hyperkuutioilla ja väittää ilman todisteita, että akselien suuntaisia sivuja voidaan vaatia ilman yleisyyden menetystä.
Hyperkuutiolla n - ulotteisessa avaruudessa on 2n pintaa, joiden mitat ovat n − 1, jotka ovat itse hyperkuutioita. Esimerkiksi neliöllä on neljä reunaa ja kolmiulotteisessa kuutiossa kuusi neliöpintaa. Kuutiolaatoituksen kaksi ruutua (määritetty millä tahansa yllä olevista menetelmistä) koskettavat toisiaan vastakkain, jos on olemassa ( n − 1)-ulotteinen hyperkuutio, joka on molempien laattojen pinta. Kellerin olettamus väittää, että mikä tahansa kuutiolaatoitus sisältää vähintään yhden parin laattoja, jotka koskettavat kasvotusten tällä tavalla.
Kellerin alkuperäinen versio oletuksesta sisälsi vahvemman väitteen, että missä tahansa kuutiolaatoituksessa on sarake, jossa on kasvotusten tangenttikuutioita. Se on totta samoissa ulottuvuuksissa kuin heikompi väite, jota tutkijat yleensä pitävät [9] [10] .
Hypoteesin olennainen vaatimus on vaatimus, että laatat ovat keskenään yhteneväisiä. Samankaltaisille mutta ei yhteneväisille kuutioille Pythagoraan laatoitus on mahdollinen , mikä toimii triviaalina vastaesimerkkinä kaksiulotteisessa avaruudessa.
Kellerin oletuksen kumoaminen riittävän suurista ulottuvuuksista kävi läpi reduktioiden sarjan, jotka muuttivat ongelman mosaiikkigeometriasta ryhmäteoriaongelmaksi ja siitä graafiteoriaongelmaksi .
Hayosh [11] oli ensimmäinen, joka muotoili Kellerin arvelun Abelin ryhmien tekijöiden jakautumisesta . Hän osoitti, että jos olettamukselle on vastaesimerkki, sitä voidaan pitää kuutioiden jaksoittaisena laatoituksena kokonaislukuisten sivujen pituuksilla ja kokonaislukujen kärkikoordinaateilla. Siten hypoteesia tutkittaessa riittää, että huomioidaan erikoismuotoiset laatoitukset. Tässä tapauksessa mosaiikkia säilyttävien kokonaislukujen rinnakkaiskäännösten ryhmä muodostaa Abelin ryhmän ja ryhmän elementit vastaavat mosaiikkilaattojen paikkoja. Hayosh määritteli Abelin ryhmän osajoukkojen A i -perheen tekijöinä, jos jokaisella ryhmän elementillä on yksilöllinen lauseke summana a 0 + a 1 + ..., jossa jokainen a i kuuluu A i :ään . Tämän määritelmän mukaan Hayosh muotoili uudelleen oletuksen - jos Abelin ryhmällä on tekijöiden jako, jossa ensimmäinen joukko A 0 voi olla mielivaltainen ja jokaisella seuraavalla joukolla A i on erityinen muoto {0, g i , 2 g i , 3 g i , ..., ( q i − 1) g i }, silloin ainakin yhden alkioista q i g i täytyy kuulua A 0 − A 0 :aan ( A 0 : n Minkowskin ero itseensä).
Szabo [7] osoitti, että jokaisella laatoituksella, joka muodostaa vastaesimerkin olettamukselle, täytyy olla vielä tarkempi muoto: kuution sivun pituus on potenssi kaksi, kärjeillä on kokonaislukukoordinaatit ja laatoitus on jaksollista. jakso, joka on kaksi kertaa kuution sivun pituus kussakin koordinaatissa. Tämän geometrisen yksinkertaistamisen perusteella hän yksinkertaisti Hajosin ryhmäteoreettista muotoilua osoittamalla, että riittää, kun tarkastellaan Abelin ryhmiä, jotka ovat suoria summia neljänkertaisten syklisten ryhmien kanssa, joiden q i = 2.
Corradi ja Szabo [12] muotoilivat Szabon tuloksen uudelleen ehdon muodossa suuren klikin olemassaolosta tietyssä graafiperheessä, joka myöhemmin tunnettiin Keller-graafina . Tarkemmin sanottuna Keller-graafin, jonka ulottuvuus on n , kärjet ovat 4 n alkiota ( m 1 ,..., m n ), joissa jokainen luku m on 0, 1, 2 tai 3. Kaksi kärkeä on yhdistetty reunalla, jos ne eroavat vähintään kahdella koordinaatilla ja eroavat kahdella ainakin yhdessä koordinaatissa. Corradi ja Szabo osoittivat, että tämän kaavion suurimman klikkin koko on enintään 2 n , ja jos on tämän kokoinen klikki, Kellerin olettamus ei pidä paikkaansa. Kun tällainen klikki on annettu, voidaan muodostaa kakkospuolen kuutioiden avaruus, jonka keskipisteillä on koordinaatit, jotka modulo neljä ovat klikkin kärjet. Edellytyksestä, että klikin kahdella kärjellä on koordinaatit, jotka eroavat kahdella, seuraa, että näitä pisteitä vastaavat kuutiot eivät mene päällekkäin. Ehdosta, että klikin koko on 2 n , seuraa, että kuutiot missä tahansa mosaiikin jaksossa ovat samat kuin itse jakso. Yhdessä sen tosiasian kanssa, että laatat eivät mene päällekkäin, tämä tarkoittaa, että kuutiot laatoittavat tilan. Kuitenkin siitä ehdosta, että minkä tahansa kahden klikin kärjet eroavat toisistaan vähintään kahdella koordinaatilla, seuraa, että kahdella kuutiolla ei ole yhteistä pintaa.
Lagarias ja Shor vuonna 1992 [5] kumosivat Keller- oletuksen löytämällä koon 2 10 klikkin ulottuvuuden 10 Keller-kaaviosta. Nämä klikkit johtavat ulottuvuuden 10 laatoittamiseen ilman yhteisiä kasvoja (kasvokkainen kosketus) ja laattojen kopioita voidaan sijoittaa avaruuteen (poikkeama puoli yksikköä kumpaankin koordinaattisuuntaan), jolloin muodostuu mosaiikki ilman kasvokkain kosketusta missään korkeammassa ulottuvuudessa. Samoin Makei [6] pienensi mittoja, joissa vastaesimerkkejä löydettiin, löytämällä koon 2 8 klikkin Kellerin kaaviosta, jonka ulottuvuus on kahdeksan.
Debrony, Eblen, Langston ja Shore [13] osoittivat, että seitsemänulotteisella Keller-graafilla on suurin klikki, jonka koko on 124 < 2 7 . Tästä dimensiosta ei siis voitu löytää vastaesimerkkiä Kellerin olettamukselle samalla tavalla kuin dimensioissa 10 ja 8 aiemmin. Myöhemmin osoitettiin, että jos tietyssä Keller-graafiin liittyvässä graafissa ei ole koon 27 klikkia, niin olettamus on totta ulottuvuudessa 7. Sellaisen klikkin puuttumisen tässä kaaviossa osoittivat Brackenzik et al., julkaissut. arXiv.orgissa vuonna 2019 ja konferenssijulkaisuissa vuonna 2020. Klikin puuttumisen ehto kirjoitettiin lausekaavana , yksinkertaistettiin erikoisohjelmalla, sen mahdottomuus todistettiin automaattisella SAT - ratkaisijalla, minkä jälkeen todistus vahvistettiin lisäksi muodollisesti ohjelmalla [4] [14] .
Keller-kaavioiden suurimpien klikkien koot pienissä ulottuvuuksissa 2, 3, 4, 5 ja 6 ovat vastaavasti 2, 5, 12, 28 ja 60. Käytetään napsautushakualgoritmien suorituskykytesteinä [ 15 ] .
Kuten Szabo kirjoittaa [16] , Herman Minkowski päätyi erityistapaukseen kuutiomaisesta laatoitusoletuksesta Diofantin approksimaatioongelmasta . Yksi Minkowski-lauseen seurauksista on, että minkä tahansa hilan (normalisoitu siten, että sen determinantti on yhtä suuri) täytyy sisältää nollasta poikkeava piste, Chebyshev-etäisyys , josta origoon ei ylitä yhtä. Hiloja, jotka eivät sisällä nollasta poikkeavia pisteitä, joiden Tšebyshev-etäisyys on ehdottomasti pienempi kuin yksi, kutsutaan kriittisiksi, ja kriittisen hilan pisteet muodostavat kuutiolaatoituksen kuutioiden keskipisteet. Minkowski ehdotti vuonna 1900, että jos kuutiohilassa olisi tällainen keskusten järjestely, sen täytyy sisältää kaksi kasvotusten koskettavaa kuutiota. Jos tämä pitää paikkansa, niin (hilan symmetrian vuoksi) jokaisen tässä laatoituksessa olevan kuution tulee olla osa kuutiosaraketta ja näiden kuutioiden leikkauskohtien tulee muodostaa pienempikokoinen kuutiolaatoitus. Tällä tavalla päätellen Minkowski osoitti, että (olettaen, että hypoteesi pitää paikkansa) kaikilla kriittisillä hilailla on perusta, joka voidaan ilmaista kolmiomatriisina, jonka päälävistäjällä on ykkösiä ja diagonaalista pienempiä lukuja. György Hajos osoitti Minkowskin olettamuksen vuonna 1942 käyttämällä Hajosin Abelin ryhmien faktorointilausetta, ryhmäteoreettista lähestymistapaa, jota hän myöhemmin sovelsi yleisempään Keller-arvaukseen.
Kellerin hypoteesi on muunnos Minkowskin hypoteesista, jossa ehto, että kuutioiden keskipisteet muodostavat hilan, heikkenee. Toinen asiaan liittyvä arvelu, jonka Furtwangler esitti vuonna 1936, sen sijaan lieventää ehtoa, että kuutiot muodostavat hilan. Furtwangler kysyi, pitäisikö hilakeskittyneiden kuutioiden järjestelmän, joka muodostaa avaruuden k - kertaisen peitteen (eli minkä tahansa avaruuden pisteen, lukuun ottamatta mitan nollan osajoukon pisteitä, kuulua täsmälleen k kuution sisäosaan) kuutiot, jotka koskettavat reunoja. Furtwanglerin olettamus pitää paikkansa kahden ja kolmen ulottuvuuden osalta, mutta neliulotteiselle avaruudelle Shayosh löysi vastaesimerkin vuonna 1938. Robinson [17] kuvasi kuutioiden lukumäärän k ja mittasuhteen n yhdistelmiä , joille vastaesimerkit ovat mahdollisia. Lisäksi yhdistämällä Furtwanglerin ja Kellerin hypoteeseja Robinson osoitti, että euklidisen tason k -kertaisen neliön kannen täytyy sisältää kaksi reunasta reunaan olevaa neliötä. Kuitenkin millä tahansa k > 1 ja n > 2:lla on k -kertainen n - ulotteinen avaruus kuutioilla, joilla ei ole yhteisiä pintoja [18] .
Heti kun vastaesimerkkejä Kellerin olettamukselle tuli tunnetuksi, heräsi kysymys pintojen enimmäismitoista, joiden olemassaolo on taattu kuutiolaatoituksessa oleville kuutioille. Jos n : n mitta ei ole suurempi kuin kuusi, niin maksimimitta on yhtä suuri kuin n − 1 Perronin Keller-oletuksen pienille mitoille osoittaman todisteen mukaan, ja n :lle vähintään kahdeksan maksimimitta ei ylitä n − 2. Lagarias ja Shor [19] antoivat tiukemman ylärajan, n − √n / 3.
Iosevich ja Pedersen [20] sekä Lagariasin, Reedin ja Wangin [21] muodostama ryhmä löysivät läheisen yhteyden kuutiolaatoitusten ja neliöintegroitavien funktioiden spektriteorian välillä kuutiosta.
Dutour-Sikirich, Ito ja Poyarkov [22] käyttivät Keller-graafien klikkejä, jotka ovat maksimaalisia mutta eivät maksimaalisia tutkiakseen kuutioiden pakkaamista avaruudessa, johon ei voida lisätä kuutiota.
Vuonna 1975 Ludwig Danzer ja itsenäisesti Branko Grünbaum ja Shepard löysivät kolmiulotteisen suuntaissärmiön tessellaation, jonka kasvojen kaltevuus oli 60° ja 120°, jossa kahdella suuntaissärmiöllä ei ole yhteistä pintaa [23] .
| geometriset mosaiikit | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Jaksottainen |
| ||||||||
| jaksoton |
| ||||||||
| Muut |
| ||||||||
| Vertex- konfiguraation mukaan |
| ||||||||