XIV. Bolyai Konferencia 2009. Március 14.
Bodnár József IV. matematikus, ELTE TTK Eötvös Collegium
Színes papíroktól a narancspakolásig – a blokkrendszerek szimmetrikus világa
1873-ban Émile Mathieu kivételes permutációcsoportokat fedez fel 5-tranzitív Mathieu-csoportok
1938-ban Ernst Witt különleges általánosításait fedezi fel véges geometriáknak Witt-blokkrendszerek
1979-ben a Voyager űrszonda képeket küld a Szaturnuszról Golay-kód
Hibajavító kódok 011001100
011001100 Zajos csatorna
011001100 0
1
010010100
0
0
Kódolás
000 111 000
1
0 Dekódolás
Zajos csatorna
001 011 010 ???
Hibajavító kód mint részhalmaz: Kódszavak: 000, 111 Nem kódszavak: 001, 010, 100, 110, 101, 011
Az összes 3 hosszúságú szó listájában
Ha nem kódszót kapunk: javítsuk azt a legközelebbi kódszóra!
A Hamming-távolság (00011010110111) = u (00110110010011) = v
Az eltérések száma d(u, v) = 5
Lineáris kód: a kódszavak alteret alkotnak egy véges test fölötti vektortérben. Rácsszerű szerkezet: Kódszó Javítható szó Nem javítható szó
Minél sűrűbb térkitöltés gömbökkel – meglepően nehéz probléma
Véges test fölött megvalósítható a hézagmentesség: Perfekt kód – minden szó közel esik (Hamming-távolság) valamelyik kódszóhoz
A Golay-kód
12 lap, 12x12-es mátrix •Az identitásmátrix és a dodekaéder lapszomszédsági mátrixának komplementere •A sorok generálják: 12 dimenziós altér a 24 dimenziós térben •Az utolsó koordinátát elhagyva: bármely 23 hosszúságú 0-1 sorozat legfeljebb 3 helyen tér el egy kódszótól – perfekt kód •Ha nem hagyunk el koordinátát: a csupa 0 szó kódszó, minden más kódszó legalább 8 darab 1-est tartalmaz
Blokkrendszerek •Véges (v darab „pontból”) halmaz k elemű részhalmazainak rendszere - blokkok •Bármely t darab ponthoz pontosan λ darab olyan blokk létezik, ami tartalmazza őket •Nagyfokú szimmetria •Jelölés: t – (v, k, λ) Példa: Fano-sík – t = 2, v = 7, k = 3, λ = 1: 2-(7, 3, 1) blokkrendszer •Algebrai összefüggések a paraméterek között •Nem minden paraméterre létezik, és nem is mindig egyértelmű •Egyre nagyobb t-re egyre ritkábbak •Speciális eset: λ = 1 – Steiner-rendszer
Konstrukciók: Deriválás: •Egy kiválasztott pontot tartalmazó blokkokat hagyok meg •Törlöm a kiválasztott pontot
•t – (v, k, λ) → (t - 1) – (v - 1, k - 1, λ) •Minden blokkrendszerre elvégezhető •Példa: 3 – (8, 4, 1) → 2 – (7, 3, 1)
Blokkrendszer bővítése: •Olyan blokkrendszer keresése, melyből deriválással kapható •t – (v, k, λ) → (t + 1) – (v + 1, k + 1, λ) •Nem mindig végezhető el! •A bővíthetőség „nyomai” olyan k + 1 elemű részhalmazok, hogy bármely, nem egy blokkba eső v + 1 pontra pontosan λ darab illeszkedik
A Witt-blokkrendszerek •PG(2, 4) – a négyelemű test fölötti projektív geometria egy 2 – (21, 5, 1) rendszer •Háromszor is bővíthető egymás után! •2 – (21, 5, 1) → 3 – (22, 6, 1) → 4 – (23, 7, 1) → 5 – (24, 8, 1) •Az utolsó blokkrendszer: 24 elemű halmaz 8 elemű részhalmazai, bármely 5 elemhez egyértelműen létezik őt tartalmazó nyolcas •A Golay-kód nyolc súlyú szavainak 1-esei! •0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1
0 1 0 0
0 0 1 0
0 1 1 1
0 0 0 1
0 0 0 1
1 0 0 0
„Miracle Octad Generator” Richard T. Curtis, 1976
Nyolcelemű halmaz két részre bontásai – 35 féle A kételemű test fölötti négydimenziós vektortér affin két dimenziós altereinek párhuzamossági osztályai – 35 darab •Mind a 759 darab nyolc elemű blokk (oktád) előáll valamelyik párból: választunk •párt, •részhalmazt, •affin alteret, •permutációt. Plusz még három „tégla” oktád
Kódok és blokkrendszerek szimmetriái •Kód szimmetriája: a jelsorozat jeleinek olyan cseréje, mellyel kódszóból kódszót kapunk, és nem kaphatunk kódszót nem kódszóból •Permutációcsoport Például: 7 hosszúságú sorozatban a 3. és a 6. pozíción álló jel cseréje: 0110100 → 0100110 Ez a csere megengedett, ha: kódszó → kódszó és nem kódszó → nem kódszó minden egyes szóra •Blokkrendszer szimmetriája: a pontok olyan cseréje, ami blokkot blokkba visz •Szintén permutációcsoport
A Mathieu-csoport •A Golay-kód és az 5 – (24, 8, 1) Steiner-rendszer automorfizmuscsoportja (azaz ezeknek a szimmetriái alkotják) •24 fokú permutációcsoport •5-tranzitív! •Rendje 244 823 040
A hiperbolikus sík hétszínű háromszögekkel való parkettázásából konstruálható egy poliéder…
A „kis kubikuboktaéder” •20 lap •24 csúcs
•Már két permutáció generálja a Mathieucsoportot a csúcsokon
Források: • J. D. Dixon, B. Mortimer: Permutation Groups • J. H. Conway, N. J. A. Sloane: Sphere Packings, Lattices and Groups • B. Polster: A Geometrical Picture Book
Internetes források: • David A. Richter honlapja: http://homepages.wmich.edu/~drichter/ • Steven H. Cullinane honlapja: http://finitegeometry.org/sc/24/MOG.html • http://en.wikipedia.org/wiki/File:Small_cubicuboctahedron.png http://www.software3d.com/Stella.html
