Steinerův systém

Steinerův systém (pojmenovaný po Jacobu Steinerovi ) je variantou blokových diagramů , přesněji t-schéma s λ = 1 a t ≥ 2.

Steinerův systém s parametry t , k , n (psáno S( t , k , n )) je n - prvková množina S spolu s množinou k - prvkových podmnožin S (tzv. bloky ) s vlastností, že každé t- podmnožina prvků S obsažená právě v jednom bloku. V alternativním zápisu blokového diagramu je S( t , k , n ) označeno jako t- ( n , k,1) schéma.

Tato definice je relativně nová a zobecňuje klasickou definici Steinerova systému, která navíc vyžaduje, aby k = t + 1. Obvod S(2,3, n ) byl (a stále se nazývá) Steinerův trojný systém , S(3 ,4, n ) se nazýval Steinerův čtyřnásobný systém a tak dále. Po zobecnění definice není systém pojmenování tak striktně prosazován.

V teorii obvodů se dlouho nevědělo, zda existuje netriviální ( t < k < n ) Steinerův systém s t ≥ 6 a také zda existuje nekonečně mnoho obvodů s t = 4 nebo 5 [1] . Kladnou odpověď dal Peter Kivash v roce 2014 [2] [3] [4] .

Příklady

Konečné projektivní roviny

Konečná projektivní rovina řádu q s čarami jako bloky je S(2, q + 1, q 2 + q + 1) , protože má q 2 + q + 1 bodů, každá přímka prochází q + 1 body a každá a dvojice odlišných bodů leží přesně na stejné čáře.

Konečné afinní roviny

Konečná afinní rovina řádu q s čarami jako bloky je schéma S(2,  q ,  q 2 ) . Afinní rovinu řádu q lze získat z projektivní roviny stejného řádu odstraněním jednoho bloku a všech bodů tohoto bloku z projektivní roviny. Pokud zvolíte jiné bloky k odstranění, můžete získat neizomorfní afinní roviny.

Klasické Steinerovy systémy

Steinerovy trojité systémy

Obvod S(2,3, n ) se nazývá Steinerův trojitý systém a jeho bloky se nazývají trojice . Pro Steinerovy trojité systémy se často používá označení STS( n ) . Počet trojic procházejících bodem je (n-1)/2 , a proto je celkový počet trojic n ( n −1)/6. To ukazuje, že n musí být 6k+1 nebo 6k + 3 pro nějaké k . To, že tato podmínka pro n postačuje pro existenci S(2,3, n ), dokázali Ray Chandra Bose [5] a T. Skolem [6] . Projektivní rovina řádu 2 ( Fano rovina ) je STS(7) a afinní rovina řádu 3 je STS(9).

Až do izomorfismu jsou STS(7) a STS(9) jedinečné. Existují dvě schémata STS(13), 80 schémat STS(15) a 11 084 874 829 schémat STS (19) [7] .

Násobení na množině S můžeme definovat pomocí Steinerovy trojné soustavy, pokud pro všechna a z S a ab = c nastavíme aa = a , jestliže { a , b , c } je Steinerova trojice. Toto dělá S idempotentní komutativní kvazigrupu . Kvazigrupa má další vlastnost, že ab = c implikuje bc = a a ca = b [comm. 1] . Naopak jakákoli (konečná) kvazigrupa s těmito vlastnostmi se získá ze systému Steinerových trojic. Komutativní idempotentní kvazigrupy, které splňují tuto další vlastnost, se nazývají Steinerovy kvazigrupy [8] .

Steinerův systém čtyř

Schéma S(3,4, n ) se nazývá Steinerův čtyřnásobný systém . Nezbytnou a postačující podmínkou pro existenci S(3,4, n ) je n 2 nebo 4 (mod 6). Pro tyto systémy se často používá označení SQS( n ) .

Až do izomorfismu jsou SQS(8) a SQS(10) jedinečné, existují 4 schémata SQS(14) a 1.054.163 schémata SQS(16) [9] .

Steiner pětinásobné systémy

Schéma S(4,5, n ) se nazývá Steinerův systém pentád . Nezbytnou podmínkou pro existenci takového systému je n 3 nebo 5 (mod 6), což vyplývá z konvencí, které platí pro všechny klasické Steinerovy systémy. Další podmínka pro obecné systémy, že n 4 (mod 5), pochází ze skutečnosti, že počet bloků musí být celé číslo. Dostatečné podmínky nejsou známy.

Existuje jediný systém Steinerových pentád řádu 11, ale neexistují žádné systémy řádu 15 nebo 17 [10] . Známé jsou systémy s řády 23, 35, 47, 71, 83, 107, 131, 167 a 243. Nejmenší řád, u kterého není známa existence (k roku 2011), je 21.

Vlastnosti

Z definice S( t , k , n ) je zřejmé, že . (Rovnosti, i když jsou technicky možné, vedou k triviálním systémům.)

Pokud existuje systém S( t , k , n ) , výběrem bloků obsahujících určitý prvek a vymazáním tohoto prvku vznikne odvozený systém S( t −1, k −1, n −1) . Existence S( t −1, k −1, n − 1) je tedy nezbytnou podmínkou existence schématu S( t , k , n ) .

Počet podmnožin t -prvků v S je , zatímco počet podmnožin t -prvků v každém bloku je . Protože jakákoliv podmnožina t -prvků je obsažena právě v jednom bloku, dostaneme , nebo

kde b  je počet bloků. Podobná úvaha o t -prvkových podmnožinách obsahujících konkrétní prvek nám dává , popř

=

kde r  je počet bloků obsahujících vybraný prvek. Z těchto definic vyplývá rovnost . Nezbytnou podmínkou pro existenci obvodu S( t , k , n ) je, že b a r jsou integrální . Stejně jako u každého blokového diagramu platí Fisherova nerovnost pro Steinerovy systémy.

Vzhledem k parametrům Steinerova systému S( t, k, n ) a podmnožině velikosti obsažené alespoň v jednom bloku lze spočítat počet bloků protínajících tuto podmnožinu s pevným počtem prvků sestrojením Pascalova trojúhelníku [11] . Zejména počet bloků protínajících pevný blok s libovolným počtem prvků nezávisí na volbě bloku.

Počet bloků obsahujících jakoukoli sadu bodů i -prvků je:

pro

Lze ukázat, že pokud existuje Steinerův systém S(2, k , n ) , kde k je prvočíslo větší než 1, pak n 1 nebo k (mod k ( k −1)) . Zejména Steinerova trojná soustava S(2, 3, n ) musí mít n = 6 m + 1 nebo 6 m + 3 . Jak jsme již uvedli, toto je jediné omezení Steinerových trojných soustav, tedy pro každé přirozené číslo m existují soustavy S(2, 3, 6 m + 1) a S(2, 3, 6 m + 3) . .

Historie

Steinerovy trojité systémy byly první, kdo definoval V.S.B. Woolhouse v roce 1844 v prémiovém vydání #1733 v Deníku dámy a pánů [12] . Problém vyřešil Thomas Kirkman [13] . V roce 1850 Kirkman předložil variantu problému nazvanou „ Kirkmanův problém školačky “, který požaduje systém trojic s další vlastností (řešitelnost). Aniž by znal Kirkmanovo dílo, Jacob Steiner [14] definoval systém trojic a jeho práce se stala slavnější, proto byl systém pojmenován po něm.

Mathieu skupiny

Některé příklady Steinerových systémů úzce souvisejí s teorií skupin . Konkrétně konečné jednoduché grupy , nazývané Mathieuovy grupy , vznikají jako automorfní grupy Steinerových systémů:

Steinerův systém S(5, 6, 12)

Existuje unikátní Steinerův systém S(5,6,12). Jeho grupou automorfismu je Mathieuova grupa M 12 a v tomto kontextu je grupa označena W 12 .

Budovy

Existují různé způsoby konstrukce systému S(5,6,12).

Metoda projektivní čáry

Tuto konstrukci má na svědomí Carmichael (1937) [15] .

K 11 prvkům konečného pole F 11 (tedy zbytky modulo 11) přidáme nový prvek, který označíme ∞ . Tuto množinu S 12 prvků lze formálně identifikovat s body projektivní čáry nad F11 . Nazvěme následující podmnožinu velikosti 6,

"blok". Pomocí tohoto bloku získáme další bloky obvodu S (5,6,12) opakovaným aplikováním lineárně-zlomkové transformace :

kde a,b,c,d jsou obsaženy v F 11 a ad - bc je nenulová čtverec v F 11 . Pokud definujeme f (− d / c ) = ∞ a f (∞) = a / c , tato funkce mapuje množinu S na sebe. V geometrické řeči jde o průměty projektivní přímky. Superpozicí tvoří skupinu a tato skupina je projektivní speciální lineární grupa PSL (2,11) řádu 660. V této skupině je přesně pět prvků, které ponechávají počáteční blok beze změny [16] , takže máme 132 obrázků blok. V důsledku multiplikativní tranzitivity této skupiny působící na tuto množinu se jakákoli podmnožina z pěti prvků množiny S objeví přesně v těchto 132 obrázcích velikosti šest.

Curtisova metoda

Alternativní konstrukce obvodu W 12 je získána aplikací metody R. T. Curtise [17] , která je určena pro „ruční výpočet“ bloků po jednom. Curtisova metoda je založena na vyplňování 3x3 tabulek čísel, které reprezentují afinní geometrii na vektorovém prostoru F 3 xF 3 , systém S(2,3,9).

Konstrukce rozdělením grafu K 6

Spojení mezi faktory úplného grafu K 6 generuje schéma S(5,6,12) [18] . Graf K 6 má 6 různých 1-faktorizací (cesty dělení hran na dokonalé shody ) a také 6 vrcholů. Množina vrcholů a množina faktorizací dávají blok. Pro každou dvojici rozkladů existuje přesně jedna společná dokonalá shoda. Vezměte sadu vrcholů a nahraďte dva vrcholy odpovídající okraji obecné dokonalé shody štítkem odpovídajícím faktorizacím. Výsledek přidáme do sady bloků. Zopakujeme postup pro zbývající dva okraje celkového dokonalého lícování. Jednoduše vezmeme sadu rozkladů a nahradíme štítky odpovídající dvěma rozkladům koncovými body hrany v obecné dokonalé shodě. Toto opakujeme pro další dvě odpovídající hrany. Pro každý pár rozkladů je 3+3 = 6 bloků a mezi 6 rozklady je 6C2 = 15 párů, což dává 90 nových bloků. Nakonec vezmeme celkovou sadu 12C6 = 924 kombinací 6 objektů z 12 a zahodíme všechny kombinace, které mají 5 nebo více objektů společných s kterýmkoli z 92 bloků. Zbývá přesně 40 bloků, což dává 2+90+40 = 132 bloků S(5,6,12).

Steinerův systém S(5, 8, 24)

Steinerův systém S(5, 8, 24), známý také jako Wittovo schéma nebo Wittova geometrie , byl popsán Robertem Carmichaelem [19] a znovu objeven Wittem [20] . Tento systém je spojen s mnoha sporadickými skupinami a s výjimečnou 24rozměrnou mřížkou známou jako mřížka Leach .

Skupina automorfismu schématu S(5, 8, 24) je Mathieuova grupa M 24 a v kontextu schémat je označena W 24 ("W" z "Witt")

Budovy

Existuje mnoho způsobů, jak sestrojit S(5,8,24). Jsou zde popsány dva způsoby:

Metoda založená na kombinování 24 prvků ve skupinách po 8

Všechny 8prvkové podmnožiny 24prvkové sady jsou generovány v lexikografickém pořadí a každá taková podmnožina, která se liší od některé již nalezené podmnožiny na méně než třech pozicích, je vyřazena.

Seznam osmiček pro prvky 01, 02, 03, ..., 22, 23, 24:

01 02 03 04 05 06 07 08 01 02 03 04 09 10 11 12 01 02 03 04 13 14 15 16 . . (dalších 753 osmiček vynecháno) . 13 14 15 16 17 18 19 20 13 14 15 16 21 22 23 24 17 18 19 20 21 22 23 24

Každý jednotlivý prvek se vyskytuje 253krát v libovolných osmičkách. Každý pár se sejde 77krát. Každá trojice se vyskytuje 21krát. Každá čtveřice se vyskytuje 5krát. Každých pět se sejde jednou. Ne každých šest, sedm nebo osm se najde.

Metoda založená na 24bitových binárních řetězcích

Všechny 24bitové binární řetězce jsou generovány v lexikografickém pořadí a jakýkoli takový řetězec, který se liší od dříve nalezeného o méně než 8 pozic, je vyřazen. V důsledku toho získáme:

000000000000000000000000 0000000000000001111111 00000000000011110001111 00000000000011111110000 000000000011001100110011 000000000011001111001100 000000000011110000111100 000000000011110011000011 000000000101010101010101 000000000101010110101010 . . (dalších 4083 24bitových řádků vynecháno) . 111111111111000011110000 11111111111111100000000 11111111111111111111111

Seznam obsahuje 4096 prvků, což jsou kódová slova rozšířeného binárního Golayova kódu . Tvoří skupinu operací XOR. Jedno ze slov má 0 bitů, 759 slov má osm 1 bitů, 2576 slov má 12 1 bitů, 759 slov má 16 1 bitů a jedno slovo je celé 1 bity. 759 8-prvkových bloků vzoru S(5,8,24) je definováno 1-bitovými slovy s osmi jedničkami.

Viz také

Komentáře

  1. ↑ Tato vlastnost je ekvivalentní (xy)y = x pro všechna x a y v idempotentní komutativní kvazigrupě.

Poznámky

  1. ↑ Encyklopedie .
  2. ↑ Keevash, 2014 .
  3. ↑ Magazín Quanta .
  4. ↑ Kalai .
  5. ↑ Bose, 1939 , str. 353–399.
  6. ↑ Skolem, 1958 , s. 273–280.
  7. ↑ Colbourn, Dinitz, 2007 , str. 60.
  8. ↑ Colbourn, Dinitz, 2007 , str. 497, definice 28.12.
  9. ↑ Colbourn, Dinitz, 2007 , str. 106.
  10. ↑ Östergard, Pottonen, 2008 .
  11. ↑ Assmus, Key, 1992 , str. osm.
  12. ↑ Lindner a Rodger 1997 , s. 3.
  13. ↑ Kirkman, 1847 .
  14. ↑ Steiner, 1853 .
  15. ↑ Carmichael, 1956 , s. 431.
  16. ↑ Beth, Jungnickel, Lenz, 1986 , str. 196.
  17. ↑ Curtis, 1984 .
  18. ↑ Učebnice EAGTS . Získáno 5. července 2017. Archivováno z originálu 10. prosince 2017.
  19. ↑ Carmichael, 1931 .
  20. ↑ Witt, 1938 .

Literatura

  • Encyklopedie teorie designu: t-Designs . Designtheory.org (4. října 2004). Staženo: 17. srpna 2012.
  • RC Bose. O konstrukci vyvážených neúplných blokových návrhů  // Ann. Eugenika 9. - 1939. - S. 353-399 .  (nedostupný odkaz)
  • Peter Keevash. Existence designů . — 2014.
  • T. Skolem. Několik poznámek o trojných systémech Steiner  // Math. Scand. 6. - 1958. - S. 273-280 .
  • Designové dilema vyřešeno, mínus designy . Magazín Quanta (9. června 2015). Staženo: 27. června 2015.
  • Gil Kalai. Návrhy existují! . http://www.bourbaki.ens.fr . Seminář BOURBAKI.
  • E. F. Assmus, J. D. Key. Designy a jejich kódy. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
  • Thomas Beth, Dieter Jungnickel, Hanfried Lenz. teorie designu. - Cambridge: Cambridge University Press , 1986. - ISBN 978-0-521-44432-3 .
  • Robert Carmichael. Taktické konfigurace druhé pozice  // American Journal of Mathematics. - 1931. - T. 53 . — S. 217–240 . - doi : 10.2307/2370885 . — .
  • Robert Carmichael. Úvod do teorie grup konečného řádu. - Dover, 1956. - ISBN 0-486-60300-8 .
  • Charles J. Colbourn, Jeffrey H. Dinitz. Příručka kombinačních návrhů. — 2. — Boca Raton: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
  • RT Curtis. Steinerův systém S(5,6,12), Mathieuova grupa M 12 a "kotě" // Computational group theory (Durham, 1982). - London: Academic Press, 1984. - S. 353-358. — ISBN 0-12-066270-1 .
  • D. R. Hughes, E. C. Piper. teorie designu . - Cambridge: Cambridge University Press, 1985. - s  . 173-176 . - ISBN 0-521-25754-9 .
  • Thomas P. Kirkman. O problému v kombinacích // The Cambridge and Dublin Mathematical Journal. - Macmillan, Barclay a Macmillan, 1847. - Svazek II . — S. 191–204 .
  • CC Lindner, CA Rodger. Teorie designu . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
  • Patric RJ Östergard, Olli Pottonen. Neexistuje žádný Steinerův systém S(4,5,17) // Journal of Combinatorial Theory Series A. - 2008. - Vol. 115 , no. 8 . - S. 1570-1573 . - doi : 10.1016/j.jcta.2008.04.005 .
  • J. Steiner. Combinatorische Aufgabe // Journal für die Reine und Angewandte Mathematik . - 1853. - T. 45 . — S. 181–182 .
  • Ernst Witt. Die 5-Fach transitiven Gruppen von Mathieu // Abh. Matematika. Sem. Univ. Hamburg. - 1938. - T. 12 . — S. 256–264 . - doi : 10.1007/BF02948947 .

Odkazy