Sistemul Steiner

Sistemul Steiner (numit după Jacob Steiner ) este o variantă a diagramelor bloc , mai precis, o schemă t cu λ = 1 și t ≥ 2.

Un sistem Steiner cu parametrii t , k , n (scris S( t , k , n )) este o mulțime de n - elemente S împreună cu o mulțime de k - submulțimi de elemente ale lui S (numite blocuri ) cu proprietatea că fiecare t - submulțime de elemente din S conținute într-un singur bloc. În notația alternativă cu diagrama bloc, S( t , k , n ) este notat ca t -( n , k ,1) schema.

Această definiție este relativ nouă și generalizează definiția clasică a unui sistem Steiner, care necesită în plus ca k = t + 1. Circuitul S(2,3, n ) a fost (și se numește încă) sistemul triplu Steiner , S(3). ,4, n ) a fost numit sistemul cvadruplu Steiner și așa mai departe. După generalizarea definiției, sistemul de numire nu este atât de strict aplicat.

În teoria circuitelor , a fost necunoscut de multă vreme dacă există un sistem Steiner netrivial ( t < k < n ) cu t ≥ 6 și, de asemenea, dacă există infinit de circuite cu t = 4 sau 5 [1] . Un răspuns afirmativ a fost dat de Peter Kivash în 2014 [2] [3] [4] .

Exemple

Planuri proiective finite

Un plan proiectiv finit de ordinul q cu drepte ca blocuri este S(2, q + 1, q 2 + q + 1) deoarece are q 2 + q + 1 puncte, fiecare linie trece prin q + 1 puncte și fiecare a perechea de puncte distincte se află exact pe aceeași linie.

Planuri afine finite

Un plan afin finit de ordinul q cu linii drept blocuri este schema S(2,  q ,  q 2 ) . Un plan afin de ordinul q poate fi obținut dintr-un plan proiectiv de același ordin prin eliminarea unui bloc și a tuturor punctelor acelui bloc din planul proiectiv. Dacă alegeți alte blocuri de eliminat, puteți obține planuri afine non-izomorfe.

Sisteme clasice Steiner

Sisteme triple Steiner

Circuitul S(2,3, n ) se numește sistemul triplu Steiner , iar blocurile sale sunt numite triple . Notația STS( n ) este adesea folosită pentru sistemele triple Steiner . Numărul de triple care trec prin punct este (n-1)/2 și, prin urmare, numărul total de triple este n ( n −1)/6. Aceasta arată că n trebuie să fie 6k+1 sau 6k + 3 pentru unele k . Faptul că această condiție pentru n este suficientă pentru existența lui S(2,3, n ) a fost dovedit de Ray Chandra Bose [5] și T. Skolem [6] . Planul proiectiv de ordinul 2 ( planul Fano ) este STS(7), iar planul afin de ordinul 3 este STS(9).

Până la izomorfism, STS(7) și STS(9) sunt unice. Există două scheme STS(13), 80 scheme STS(15) și 11.084.874.829 scheme STS(19) [7] .

Putem defini înmulțirea pe o mulțime S folosind sistemul triplu Steiner dacă setăm aa = a pentru tot a din S și ab = c dacă { a , b , c } este un triplu Steiner. Aceasta face din S un cvasigrup comutativ idempotent . Un cvasigrup are proprietatea suplimentară că ab = c implică bc = a și ca = b [comm. 1] . În schimb, orice cvasigrup (finit) cu aceste proprietăți este obținut dintr-un sistem de triple Steiner. Cvasigrupurile idempotente comutative care satisfac această proprietate suplimentară se numesc cvasigrupuri Steiner [8] .

Sistemul lui Steiner cu patru paturi

Schema S(3,4, n ) se numește sistemul cvadruplu Steiner . O condiție necesară și suficientă pentru existența lui S(3,4, n ) este n 2 sau 4 (mod 6). Notația SQS( n ) este adesea folosită pentru aceste sisteme .

Până la izomorfism, SQS(8) și SQS(10) sunt unice, există 4 scheme SQS(14) și 1.054.163 scheme SQS(16) [9] .

Sisteme cvintuple Steiner

Schema S(4,5, n ) se numește sistemul Steiner de pentade . O condiție necesară pentru existența unui astfel de sistem este n 3 sau 5 (mod 6), care rezultă din convenții care se aplică tuturor sistemelor Steiner clasice. O condiție suplimentară pentru sistemele generale, aceea că n 4 (mod 5), vine din faptul că numărul de blocuri trebuie să fie un întreg. Nu se cunosc suficiente condiții.

Există un singur sistem de pentade Steiner de ordinul 11, dar nu există sisteme de ordinul 15 sau 17 [10] . Sunt cunoscute sistemele cu ordinele 23, 35, 47, 71, 83, 107, 131, 167 și 243. Cea mai mică ordine pentru care existența este necunoscută (din 2011) este 21.

Proprietăți

Din definiția lui S( t , k , n ) este clar că . (Egalitățile, deși sunt posibile din punct de vedere tehnic, conduc la sisteme triviale.)

Dacă există un sistem S( t , k , n ) , selectând blocuri care conțin un anumit element și ștergerea acelui element rezultă un sistem derivat S( t −1, k −1, n −1) . Astfel, existența lui S( t −1, k −1, n − 1) este o condiție necesară pentru existența schemei S( t , k , n ) .

Numărul de subseturi de elemente t din S este , în timp ce numărul de subseturi de elemente t din fiecare bloc este . Deoarece orice submulțime de elemente t este conținută într-un singur bloc, obținem , sau

unde b  este numărul de blocuri. Raționament similar despre submulțimile de elemente t care conțin un anumit element ne dă , sau

=

unde r  este numărul de blocuri care conțin elementul selectat. Egalitatea rezultă din aceste definiții . O condiție necesară pentru existența circuitului S( t , k , n ) este ca b și r să fie integrali . Ca în orice diagramă bloc, inegalitatea lui Fisher este adevărată pentru sistemele Steiner.

Având în vedere parametrii sistemului Steiner S( t, k, n ) și o submulțime de dimensiune , conținută în cel puțin un bloc, se poate număra numărul de blocuri care intersectează această submulțime cu un număr fix de elemente construind triunghiul lui Pascal [11] . În special, numărul de blocuri care traversează un bloc fix cu orice număr de elemente nu depinde de alegerea blocului.

Numărul de blocuri care conțin orice set de puncte i -element este:

pentru

Se poate demonstra că dacă există un sistem Steiner S(2, k , n ) , unde k este o putere primă mai mare decât 1, atunci n 1 sau k (mod k ( k −1)) . În special, sistemul triplu Steiner S(2, 3, n ) trebuie să aibă n = 6 m + 1 sau 6 m + 3 . După cum am menționat deja, aceasta este singura restricție a sistemelor triple Steiner, adică pentru fiecare număr natural m există sistemele S(2, 3, 6 m + 1) și S(2, 3, 6 m + 3) .

Istorie

Sistemele triple Steiner au fost primele care au definit V.S.B. Woolhouse în 1844 în numărul premium #1733 în Lady's and Gentlemen's Diary [12] . Problema a fost rezolvată de Thomas Kirkman [13] . În 1850, Kirkman a pus o variantă a problemei numită „ Problema elevelor lui Kirkman ”, care cere un sistem de triple cu o proprietate suplimentară (solubilitate). Fără să cunoască opera lui Kirkman, Jacob Steiner [14] a definit un sistem de triple, iar opera sa a devenit mai faimoasă, așa că sistemul a fost numit după el.

Grupuri Mathieu

Câteva exemple de sisteme Steiner sunt strâns legate de teoria grupurilor . În special, grupurile finite simple , numite grupuri Mathieu , apar ca grupuri de automorfism ale sistemelor Steiner:

Sistemul Steiner S(5, 6, 12)

Există un sistem unic Steiner S(5,6,12). Grupul său de automorfism este grupul Mathieu M 12 , iar în acest context grupul este notat W 12 .

Clădiri

Există diferite moduri de a construi sistemul S(5,6,12).

Metoda liniei proiective

Această construcție se datorează lui Carmichael (1937) [15] .

Adăugăm un nou element, pe care îl notăm ∞ , celor 11 elemente ale câmpului finit F 11 (adică resturi modulo 11). Această mulțime S de 12 elemente poate fi identificat formal cu punctele dreptei proiective peste F 11 . Să numim următorul subset de dimensiune 6,

"bloc". Cu ajutorul acestui bloc, vom obține și alte blocuri ale circuitului S (5,6,12) prin aplicarea repetă a transformării liniar-fracționale :

unde a,b,c,d sunt conținute în F 11 și ad - bc este un pătrat diferit de zero în F 11 . Dacă definim f (− d / c ) = ∞ și f (∞) = a / c , această funcție mapează mulțimea S pe ea însăși. În limbajul geometric, acestea sunt proiecții ale dreptei proiective. Ele formează un grup prin suprapunere, iar acest grup este grupul liniar special proiectiv PSL (2,11) de ordinul 660. Există exact cinci elemente în acest grup care lasă blocul inițial neschimbat [16] , deci avem 132 de imagini ale blocul. Ca o consecință a tranzitivității multiplicative a acestui grup care acționează asupra acestei mulțimi, orice submulțime din cele cinci elemente ale mulțimii S va apărea exact în aceste 132 de imagini de dimensiunea șase.

Metoda Curtis

O construcție alternativă a circuitului W 12 se obține prin aplicarea metodei lui R. T. Curtis [17] , care este destinată „calculului manual” al blocurilor unul câte unul. Metoda Curtis se bazează pe completarea tabelelor 3x3 de numere care reprezintă o geometrie afină pe un spațiu vectorial F 3 xF 3 , sistemul S(2,3,9).

Construcție prin împărțirea graficului K 6

Legătura dintre factorii graficului complet K 6 generează schema S(5,6,12) [18] . Graficul K 6 are 6 1-factorizări diferite (căi de împărțire a muchiilor în potriviri perfecte ), precum și 6 vârfuri. Mulțimea vârfurilor și setul factorizărilor dau un bloc. Pentru fiecare pereche de factorizări, există exact o potrivire perfectă comună. Luați un set de vârfuri și înlocuiți cele două vârfuri corespunzătoare muchiei unei potriviri perfecte generale cu o etichetă corespunzătoare factorizărilor. Să adăugăm rezultatul la un set de blocuri. Să repetăm ​​procesul pentru celelalte două margini ale potrivirii perfecte totale. Pur și simplu luăm un set de factorizări și înlocuim etichetele corespunzătoare a două factorizări cu punctele finale ale unei muchii într-o potrivire perfectă generală. Repetăm ​​acest lucru pentru celelalte două margini potrivite. Există 3+3 = 6 blocuri pentru fiecare pereche de factorizări, și există 6C2 = 15 perechi între cele 6 factorizări, dând 90 de blocuri noi. În cele din urmă, luăm un set total de 12C6 = 924 combinații de 6 obiecte din 12 și aruncăm toate combinațiile care au 5 sau mai multe obiecte în comun cu oricare dintre cele 92 de blocuri. Au rămas exact 40 de blocuri, ceea ce dă 2+90+40 = 132 de blocuri de S(5,6,12).

Sistemul Steiner S(5, 8, 24)

Sistemul Steiner S(5, 8, 24), cunoscut și sub numele de schema lui Witt sau geometria lui Witt , a fost descris de Robert Carmichael [19] și redescoperit de Witt [20] . Acest sistem este asociat cu multe grupuri sporadice și cu o rețea excepțională 24-dimensională cunoscută sub numele de grila Leach .

Grupul de automorfism al unei scheme S(5, 8, 24) este grupul Mathieu M 24 și în contextul schemelor se notează W 24 ("W" din "Witt")

Clădiri

Există multe moduri de a construi S(5,8,24). Două metode sunt descrise aici:

O metodă bazată pe combinarea a 24 de elemente în grupuri de 8

Toate subseturile de 8 elemente ale unui set de 24 de elemente sunt generate în ordine lexicografică și orice astfel de submulțime care diferă de un subset deja găsit în mai puțin de trei poziții este eliminată.

Lista de opt pentru elementele 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 . . (următoarele 753 opt omise) . 13 14 15 16 17 18 19 20 13 14 15 16 21 22 23 24 17 18 19 20 21 22 23 24

Fiecare element individual apare de 253 de ori în orice opt. Fiecare cuplu se întâlnește de 77 de ori. Fiecare triplă apare de 21 de ori. Fiecare cvadruplu apare de 5 ori. Fiecare cinci se întâlnește o dată. Nu se găsesc la fiecare șase, șapte sau opt.

Metodă bazată pe șiruri binare de 24 de biți

Toate șirurile binare de 24 de biți sunt generate în ordine lexicografică și orice astfel de șir care diferă de cel găsit anterior cu mai puțin de 8 poziții este eliminat. Ca rezultat, obținem:

000000000000000000000000 000000000000000011111111 000000000000111100001111 000000000000111111110000 000000000011001100110011 000000000011001111001100 000000000011110000111100 000000000011110011000011 000000000101010101010101 000000000101010110101010 . . (următoarele 4083 linii pe 24 de biți au fost omise) . 111111111111000011110000 111111111111111100000000 111111111111111111111111

Lista conține 4096 de elemente, care sunt cuvintele de cod ale codului binar extins Golay . Ei formează un grup prin operația XOR. Unul dintre cuvinte are 0 biți, 759 cuvinte au opt 1 biți, 2576 cuvinte au 12 1 biți, 759 cuvinte au 16 1 biți și un cuvânt are toți 1 biți. Cele 759 de blocuri de 8 elemente ale modelului S(5,8,24) sunt definite de cuvinte de 1 bit cu opt 1s.

Vezi și

Comentarii

  1. ↑ Această proprietate este echivalentă cu (xy)y = x pentru toate x și y într-un cvasigrup comutativ idempotent.

Note

  1. ↑ Enciclopedie .
  2. ↑ Keevash, 2014 .
  3. ↑ Revista Quanta .
  4. ↑ Kalai .
  5. ↑ Bose, 1939 , p. 353–399.
  6. ↑ Skolem, 1958 , p. 273–280.
  7. ↑ Colbourn, Dinitz, 2007 , p. 60.
  8. ↑ Colbourn, Dinitz, 2007 , p. 497, definiția 28.12.
  9. ↑ Colbourn, Dinitz, 2007 , p. 106.
  10. ↑ Östergard, Pottonen, 2008 .
  11. ↑ Assmus, Key, 1992 , p. opt.
  12. ↑ Lindner și Rodger 1997 , p. 3.
  13. ↑ Kirkman, 1847 .
  14. ↑ Steiner, 1853 .
  15. ↑ Carmichael, 1956 , p. 431.
  16. ↑ Beth, Jungnickel, Lenz, 1986 , p. 196.
  17. ↑ Curtis, 1984 .
  18. ↑ Manual EAGTS . Consultat la 5 iulie 2017. Arhivat din original la 10 decembrie 2017.
  19. ↑ Carmichael, 1931 .
  20. ↑ Witt, 1938 .

Literatură

  • Enciclopedia teoriei designului: t-Designs . Designtheory.org (4 octombrie 2004). Preluat: 17 august 2012.
  • RC Bose. Despre construcția de proiecte de blocuri incomplete echilibrate  // Ann. Eugenie 9. - 1939. - S. 353-399 .  (link indisponibil)
  • Peter Keevash. Existenta desenelor . — 2014.
  • T. Skolem. Câteva observații despre sistemele triple ale lui Steiner  // Math. Scand. 6. - 1958. - S. 273-280 .
  • O dilemă de design rezolvată, minus modele . Revista Quanta (9 iunie 2015). Preluat: 27 iunie 2015.
  • Gil Kalai. Desenele există! . http://www.bourbaki.ens.fr . Seminarul BOURBAKI.
  • E. F. Assmus, J. D. Key. Desenele și codurile lor. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
  • Thomas Beth, Dieter Jungnickel, Hanfried Lenz. teoria designului. - Cambridge: Cambridge University Press , 1986. - ISBN 978-0-521-44432-3 .
  • Robert Carmichael. Configurații tactice ale rangului doi  // American Journal of Mathematics. - 1931. - T. 53 . — S. 217–240 . - doi : 10.2307/2370885 . — .
  • Robert Carmichael. Introducere în teoria grupurilor de ordine finită. - Dover, 1956. - ISBN 0-486-60300-8 .
  • Charles J. Colbourn, Jeffrey H. Dinitz. Manual de desene combinatorii. — al 2-lea. — Boca Raton: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
  • RT Curtis. Sistemul Steiner S(5,6,12), grupul Mathieu M 12 și „pisicuța” // Teoria grupurilor computaționale (Durham, 1982). - Londra: Academic Press, 1984. - S. 353-358. — ISBN 0-12-066270-1 .
  • D. R. Hughes, E. C. Piper. teoria designului . - Cambridge: Cambridge University Press, 1985. - pp  . 173-176 . - ISBN 0-521-25754-9 .
  • Thomas P. Kirkman. Despre o problemă în combinații // The Cambridge and Dublin Mathematical Journal. - Macmillan, Barclay și Macmillan, 1847. - Vol . II . — S. 191–204 .
  • CC Lindner, CA Rodger. Teoria designului . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
  • Patric RJ Östergard, Olli Pottonen. Nu există sistem Steiner S(4,5,17) // Journal of Combinatorial Theory Series A. - 2008. - Vol. 115 , nr. 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. Matematică. Sem. Univ. Hamburg. - 1938. - T. 12 . — S. 256–264 . - doi : 10.1007/BF02948947 .

Link -uri