04 septembra 2008

Hadamardova hypotéza

Sériu príspevkov týkajúcich sa konfigurácií kameňov by som chcel ukončiť jednou naozaj ťažkou úlohou. Tak ťažkou, že odoláva pokusom o vyriešenie už minimálne od tridsiatych rokov 20. storočia, no s veľkou pravdepodobnosťou nad ňou rozmýšľali už v 19. storočí James Sylvester a Jacques Hadamard. Ale kto vie? Možno je medzi Vami niekto, koho napadne nejaký veľmi originálny trik a stane sa slávnym...

Jedno z viacerých možných zadaní tejto úlohy je prekvapivo jednoduché:

Hadamardova domnienka: Nech n je akýkoľvek násobok štyroch a nech mriežka n×n má najnižší riadok ako aj najľavší stĺpec pokrytý čiernymi kameňmi. Je možné túto mriežku doplniť bielymi a čiernymi kameňmi tak, že každá dvojica riadkov ako aj každá dvojica stĺpcov má presne na n/2 pozíciách kamene rovnakej farby a na zvyšných n/2 pozíciách kamene rôznej farby?

Na ilustračnom obrázku je názorná ukážka, že to skutočne je možné pre n=4 a n=8:


Uveďme si ešte dve ekvivalentné formulácie Hadamardovej domnienky; prvá je klasická a druhú som pre Vás poprivymyslel ja.

Ekvivalentná formulácia 1: Existuje pre každé n, ktoré je násobkom štyroch Hadamardova matica Hn? Hadamardova matica Hn je taká matica typu n×n, ktorej prvky sú buď -1, alebo 1 a pre ktorú platí HnHnT=nIn, kde T označuje transpozíciu matice a In je jednotková matica rozmeru n×n.

Ekvivalentná formulácia 2: Nech n je akýkoľvek násobok štyroch. Dá sa vybrať n vrcholov (n-1)-rozmernej kocky tak, aby všetky vzájomné vzdialenosti týchto vrcholov boli rovnaké?

Všimnite si, že pre n=4 je podmienka z formulácie 2 splnená: Skutočne, ľahko nájdeme také štyri vrcholy klasickej trojrozmernej kocky, ktoré majú všetky vzájomné vzdialenosti rovnaké, t.j. tvoria vrcholy pravidelného štvorstenu:


Dôležitosť Hadamardovej domnienky umocňuje fakt, že Hadamardove matice nie sú len intelektuálnou zábavkou pre čistých matematikov, ale majú veľmi konkrétne aplikácie, napríklad v teórii kódovania, alebo pri navrhovaní štatistických experimentov.

Ak sa Vám nepodarí vyriešiť našu úlohu vo všeobecnosti, t.j. pre všetky násobky štyroch, môžete sa pokúsiť aspoň nájsť príslušnú konfiguráciu kameňov (Hadamardovu maticu, resp. n-ticu vrcholov kocky) pre konkrétny násobok štyroch. Najmenšia veľkosť, pre ktorú takáto konfigurácia ešte nie je skonštruovaná, je n=668.

Formuláciu 2 odporúčam pre tých, ktorí majú obzvlášť dobrú geometrickú predstavivosť. Stačí si totiž predstaviť 667 rozmernú hyperkocku a z jej približne 6×10200 vrcholov vybrať 668, ktoré tvoria vrcholy pravidelného 667 rozmerného simplexu.

Držím palce! :-)

Poznámka: Budúci týždeň som na konferencii, takže chvíľu nebudem písať na blog. Stay tuned!

6 komentárov:

Anonymný povedal(a)...

tak peknu konferenciu. :-) zaujimavy problem. hlavne odstavec o praktickosti formulacie 2 sa mi velmi pacil :-) - nieco podobne mi chodilo po rozume uz pri jej citani. :-)) inak, ja som doteraz vsetky 'kamenaky' [=ulohy o kamenoch :-)] riesila s ceruzkou a papierom, ale nakreslit si stvorec 668 x 668 ... to bude fuska. :-)

Anonymný povedal(a)...

Napadaju vas nejake algoritmy? Ja som nad tym trosku rozmyslal ale nic som nevymyslel...

Anonymný povedal(a)...

Na margo geometrickej predstavivosti: Isty znamy profesor na FMFI nam raz povedal, ze mysliet v dimenzii vyssej ako 3 nie je zdraviu prospesne :D

Peter Richtárik povedal(a)...

Super, nepoznal som!

Mimochodom, na akej konferencii si to (bol)?

Peter Richtárik povedal(a)...

Aleph0:

Co sa tyka predstavivosti/spravnosti intuicie vo vyssich dimenziach: poznam jeden cool priklad kde je jasne ako nas intuicia (inak evolucne vyvinuta v 3och dimenziach; pripadne v troch dominantnych {ak teda prihliadnem na teoriu superstrun s 11timi rozmermy}) zavadza. Tu je:

V 2D si predstav stvorec 2x2 rozdeleny na styri 1x1 stvorce. Kazdemu z nich vpiseme kruh (s priemerom 1). Tieto kruhy sa po dvoch dotykaju, ale do priestoru "medzi ne" sa da vpisat este jeden kruh, so stredom v strede velkeho stvorca, dotykajuci sa ostatnych styroch.

Je celkom lahke spocitat (po nakresleni obrazku), ze tento kruh ma polomer

"odmocina(2)/2-1/2".

V troch rozmeroch mame kocku 2x2x2 rozelenu na 8 kociek 1x1x1, v nich 8 guli s priemerom 1 a napokon jednu gulu v strede velkej kocky dotykajucu sa vsetkych 8 guli... Tato bude mat polomer

"odmocnina(3)/2-1/2".

Je intuitivne "jasne" ze tato posledna gula bude vtesnana niekde medzi 8 gulami, ktore su vsetky >>vnutri<< velkej kocky. Clovek by si povedal ze to tak bude v kazdej dimenzii. Ale, cuj sa svete, nie.

Pre n>=10 bude polomer vnutornej gule aspon
"odmocnina(10)/2 - 1/2", co je vacsie ako 3/2 - 1/2 = 1!!! Strenda gula bude teda vycnievat z (hyper)kocy von!!!

Intuicia nas sklamala.

Aleph0: Ak poznas iny podobny jednoduchy priklad, napis! Budem rad!!!

Radoslav Harman povedal(a)...

Tak už som späť z konferencie; ďakujem za komentáre.

Peter: Tá konferencia sa volá ROBUST a každé dva roky ju organizuje katedra pravdepodobnosti a štatistiky na pražskom matfyze; šéfom organizačného výboru býva pravidelne profesor J. Antoch. Tentokrát bola (myslím) prvýkrát Slovensku - v Račkovej doline a mne dali dokonca hodinovú pozvanú prednášku, takže som bol poctený. Bolo úplne super; možno o tom napíšem príspevok.

Inak veľmi zaujímavý príklad, ten s tými sférami v kocke.