Кіріспе
Комбинаторлық математикада блоктық жобалау
Комбинаторлық математикада Штайнер жүйесі (Якоб Штайнердің есімімен аталған) – блоктық жобалаудың бір түрі, нақтырақ айтқанда λ = 1 және t = 2 немесе (жақында) t ≥ 2 болатын t-жобалау. S(t, k, n) параметрлері бар Штайнер жүйесі, S элементтері жиынтығымен бірге, S-тің k элементтен тұратын ішкі жиынтықтары жиынтығын (блоктар деп аталады) қамтиды, мұнда S-тің кез келген t элементтен тұратын ішкі жиынтығы дәл бір блокқа кіреді. Блоктық жобалаулар үшін баламалы белгіде S(t, k, n) – t(n, k, 1) жобалау болып табылады. Бұл анықтама салыстырмалы түрде жаңа. Штайнер жүйелерінің классикалық анықтамасы сондай-ақ k = t + 1 шартын қосымша талап еткен. S(2, 3, n) – Штайнердің үштігі (немесе триадасы) жүйесі деп, ал S(3, 4, n) – Штайнердің төрттігі жүйесі деп аталды, және т.б. Анықтаманың жалпылануымен бұл номенклатура қатаң сақталмайды. Дизайн теориясындағы ұзақ жылдар бойы шешілмей келген мәселелердің бірі – t ≥ 6 болғанда тривиалды емес (яғни t < k < n) Штайнер жүйелерінің болуы; сондай-ақ t = 4 немесе 5 болғанда шексіз көп жүйелердің болуы. Екі жағдайды да Питер Киваш 2014 жылы дәлелдеді. Оның дәлелі конструктивті емес, және 2019 жылға дейін t-ның үлкен мәндері үшін нақты Штайнер жүйелері белгісіз.
Штайнер жүйелерінің түрлері
Q ретті шекті проекциялық жазықтық, сызықтар блок ретінде, S(2, q + 1, q^(2) + q + 1) болады, өйткені оның q^(2) + q + 1 нүктесі бар, әр сызық q + 1 нүкте арқылы өтеді, әр ерекше нүктелер жұбы дәл бір түзуде жатыр. Q реттік шекті аффиндік жазықтық, сызықтар блок ретінде, S(2, q, q^(2)) болады. Q реттік аффиндік жазықтықты, бір блок пен сол блоктағы барлық нүктелерді проекциялық жазықтықтан алып тастау арқылы сол реттік проекциялық жазықтықтан алуға болады. Осылайша алып тастау үшін әртүрлі блоктарды таңдау изоморфты емес аффиндік жазықтықтарға әкелуі мүмкін. S(3,4,n) Штайнердің төрттік жүйесі деп аталады. S(3,4,n) жүйесінің болуы үшін қажетті және жеткілікті шарт – n 2 немесе 4 (mod 6) болуы. Бұл жүйелер үшін SQS(n) аббревиатурасы жиі қолданылады. Изоморфизмге дейін SQS(8) және SQS(10) бірегей, 4 SQS(14) және 1,054,163 SQS(16) бар.
S(4,5,n) Штайнердің бестік жүйесі деп аталады. Мұндай жүйенің болуы үшін қажетті шарт – n 3 немесе 5 (mod 6) болуы, бұл барлық классикалық Штайнер жүйелеріне қатысты қарастырулардан туындайды. Қосымша қажетті шарт – n 4 (mod 5) болуы, бұл блоктардың саны бүтін сан болуын білдіреді. Жеткілікті шарттар белгісіз. 11-ші реттік бестік Штайнер жүйесінің бірегейі бар, бірақ 15-ші немесе 17-ші реттік жүйелер жоқ. Жүйелер 23, 35, 47, 71, 83, 107, 131, 167 және 243 реттері бойынша белгілі. 2011 жылғы мәлімет бойынша, бар болуы белгісіз ең кіші рет – 21.
Штайнердің үштік жүйелері
S(2,3,n) Штайнердің үштік жүйесі деп аталады, ал оның блоктары үштіктер деп аталады. Штайнердің n-реттік үштік жүйесі үшін STS(n) деген қысқарту жиі қолданылады. Жұптардың жалпы саны n(n-1)/2-ге тең, олардың үшеуі бір үштікке кіреді, сондықтан үштіктердің жалпы саны n(n-1)/6-ға тең. Бұл n-нің 6k+1 немесе 6k+3 түрінде болуын көрсетеді, мұнда k – қандай да бір сан. Радж Чандра Бозе және Т. Сколем бұл шарттың n үшін S(2,3,n) жүйесінің болуы үшін жеткілікті екенін дәлелдеді. 2-реттік проективтік жазықтық (Фано жазықтығы) – STS(7), ал 3-реттік аффиндік жазықтық – STS(9). Изоморфизмге дейін STS(7) және STS(9) бірегей, екі STS(13) бар, 80 STS(15) және 11 084 874 829 STS(19) бар.
Штайнердің үштік жүйесін пайдаланып, S жиынында көбейтуді былай анықтауға болады: әрбір a ∈ S үшін aa = a, және егер {a,b,c} үштік болса, онда ab = c. Бұл S-ті идемпотентті, коммутативті квазитопқа айналдырады. Оның қосымша қасиеті бар: егер ab = c болса, онда bc = a және ca = b. Керісінше, осы қасиеттерге ие кез келген (шекті) квазитоп Штайнердің үштік жүйесінен туындайды. Осы қосымша қасиетті қанағаттандыратын коммутативті идемпотентті квазитоптар Штайнер квазитоптары деп аталады.
Тарих
Штайнердің үштік жүйелері алғаш рет 1844 жылы Уэсли С. Б. Вулхаус Lady's and Gentlemen's Diary журналының 1733 нөміріндегі сыйлық сұрағында анықталды. 1850 жылы Киркман бұл мәселенің Киркманның оқушы қыздарының мәселесі деп белгілі бір түрін ұсынды, ол қосымша қасиеті (шешімділігі) бар үштік жүйелерді талап етеді. Киркманның жұмысынан хабарсыз, үштік жүйелерді қайтадан енгізді, және оның еңбегі кеңірек танылғандықтан, жүйелер оның құрметіне аталды.
Штайнер жүйесі S ((5, 6, 12)
Бірегей S(5,6,12) Штайнер жүйесі бар; оның автоморфизм тобы Матье тобы M12 болып табылады, және осы ретте ол W12 деп аталады.
Жобалық желі құрылысы
Бұл конструкция Кармайклдың (1937) еңбегіне сәйкес келеді. F11 шекті өрісінің 11 элементіне (яғни 11-ге бөлінген қалдықтарға) ∞ деп аталатын жаңа элементті қосыңыз. 12 элементтен тұратын бұл S жиыны F11 үстіндегі проективтік түзудің нүктелерімен формальды түрде сәйкес келеді. Келесі 6 элементтен тұратын ерекше ішкі жиынды "блок" деп атаңыз (оған F11-дегі 5 нөлдік емес квадраттармен бірге ∞ кіреді). Осы блоктан S(5,6,12) жүйесінің қалған блоктарын сызықтық бөлшектей трансформацияларды қайталап қолдану арқылы аламыз:
a "block" (it contains ∞ together with the 5 nonzero squares in F11). From this block, we obtain the other blocks of the S(5,6,12) system by repeatedly applying the linear fractional transformations:
where a,b,c,d are in F11 and 1= ad − bc = 1. With the usual conventions of defining 1= f (−d/c) = ∞ and 1= f (∞) = a/c, these functions map the set S onto itself. In geometric language, they are projectivities of the projective line. They form a group under composition which is the projective special linear group PSL(2,11) of order 660. There are exactly five elements of this group that leave the starting block fixed setwise, namely those such that 1= b=c=0 and 1= ad=1 so that 1= f(z) = a^(2) z. So there will be 660/5 = 132 images of that block. As a consequence of the multiply transitive property of this group acting on this set, any subset of five elements of S will appear in exactly one of these 132 images of size six.
мұнда a, b, c, d F11 өрісінен алынған және 1 = ad − bc = 1 шарты орындалады. Әдеттегі келісім бойынша 1= f (−d/c) = ∞ және 1= f (∞) = a/c деп есептесек, бұл функциялар S жиынын өзіне бейнелейді. Геометриялық тұрғыдан алғанда, бұл проективтік түзудің проективті трансформациялары. Олар құрамы бойынша топты құрайды, ол 660 ретті проективтік арнайы сызықтық топ PSL(2,11) болып табылады. Бұл топтың дәл бес элементі бастапқы блокты өзгеріссіз қалдырады, атап айтқанда, 1= b=c=0 және 1= ad=1 шарты орындалса, 1= f(z) = a²z болады. Сондықтан, осы блоктың 660/5 = 132 бейнесі болады. Бұл топтың осы жиынға қатысты көптік транзитивті қасиетінің салдарынан S жиынының кез келген бес элементтен тұратын ішкі жиыны осы 132 бейненің дәл біреуінде 6 элементтік түрінде кездеседі.
a "block" (it contains ∞ together with the 5 nonzero squares in F11). From this block, we obtain the other blocks of the S(5,6,12) system by repeatedly applying the linear fractional transformations:
where a,b,c,d are in F11 and 1= ad − bc = 1. With the usual conventions of defining 1= f (−d/c) = ∞ and 1= f (∞) = a/c, these functions map the set S onto itself. In geometric language, they are projectivities of the projective line. They form a group under composition which is the projective special linear group PSL(2,11) of order 660. There are exactly five elements of this group that leave the starting block fixed setwise, namely those such that 1= b=c=0 and 1= ad=1 so that 1= f(z) = a^(2) z. So there will be 660/5 = 132 images of that block. As a consequence of the multiply transitive property of this group acting on this set, any subset of five elements of S will appear in exactly one of these 132 images of size six.
Кішкентай үй күшіктерінің құрылысы
W12-нің баламалы құрылымы Р.Т. Кертистің "кішкентай ғалым" құрылғысын пайдалану арқылы алынады, ол блоктарды бірінен кейін бірін жазу үшін "қолмен есептегіш" ретінде ойластырылған. "Кішкентай ғалым" әдісі F3xF3 векторлық кеңістігіндегі аффиндік геометрияны көрсететін, сандардың 3x3 торлы кестесіндегі үлгілерді толықтыруға негізделген, S(2,3,9) жүйесі.
K6 графигін факторлаудан құрастыру
Толық K6 графигінің график факторлары арасындағы қатынастар S(5,6,12) құрайды. K6 графигі 6 төбе, 15 қабырға, 15 толық сәйкестік және 6 түрлі 1-факторлық жіктелуге (қабырғаларды толық сәйкестіктерге бөлу тәсілдеріне) ие. Төбелер жиыны (123456 деп белгіленеді) және жіктелулер жиыны (ABCDEF деп белгіленеді) әрқайсысы бір блоктан тұрады. Кез келген жіктелу жұбының дәл бір толық сәйкестігі ортақ. А және В жіктелулерінің 12, 34 және 56 қабырғаларымен ортақ сәйкестігі бар деп есептейік. Ортақ сәйкестіктегі әр қабырғаны жіктелу белгілерімен кезекпен алмастыра отырып, AB3456, 12AB56 және 1234AB үш жаңа блокты қосыңыз. Сонымен қатар, 12CDEF, 34CDEF және 56CDEF тағы үш блогын қосып, жіктелу белгілерін ортақ сәйкестіктің сәйкес қабырға белгілерімен алмастырыңыз. Бұл әдісті 15 жіктелу жұбы үшін қолданып, 90 жаңа блок қосыңыз. Соңында, 12 нысанның 6-сының барлық комбинацияларын алыңыз және осы уақытқа дейін жасалған 92 блоктың кез келгенімен 5 немесе одан көп нысаны ортақ болатын кез келген комбинацияны жойыңыз. Дәл 40 блок қалды, нәтижесінде 1=2 + 90 + 40 = 132 блок S(5,6,12) құрайды. Бұл әдіс S6 симметриялық тобындағы сыртқы автоморфизмнің болуына байланысты жұмыс істейді, ол төбелерді жіктелулерге, ал қабырғаларды бөлімдерге бейнелейді. Төбелерді өзгерту сыртқы автоморфизмға сәйкес жіктелулердің әртүрлі ауысуына әкеледі.
Штайнер жүйесі S ((5, 8, 24)
Штайнер жүйесі S(5, 8, 24), сондай-ақ Витт дизайны немесе Витт геометриясы деп аталады, алғаш рет осы жүйе сипатталған, кейін қайта ашылған. Бұл жүйе көптеген спорадикалық қарапайым топтармен және Лич торы деп аталатын ерекше 24 өлшемді тормен байланысты. S(5, 8, 24) жүйесінің автоморфизм тобы – M24 Матье тобы, және осы контексте дизайн W24 ("W" – "Witt") деп белгіленеді.
Жобалық желі құрылысы
Бұл конструкция Кармайклға (1931) тиесілі. F23 шекті өрісінің 23 элементіне (яғни 23-ке бөлінген қалдықтарға) ∞ деп аталатын жаңа элементті қосыңыз. Бұл 24 элементтен тұратын S жиынтығын F23 үстіндегі проективті түзудің нүктелерімен формальды түрде сәйкестендіруге болады. Келесі 8 элементтен тұратын нақты ішкі жиынды "блок" деп атаңыз. (Біз кеңейтілген екілік Голай кодінің кез келген октадасын, квадраттық қалдық коді ретінде қарастырамыз.) Осы блоктан S(5,8,24) жүйесінің басқа блоктарын сызықтық бөлшектік түрлендірулерді қайталап қолдану арқылы аламыз:
a "block". (We can take any octad of the extended binary Golay code, seen as a quadratic residue code.) From this block, we obtain the other blocks of the S(5,8,24) system by repeatedly applying the linear fractional transformations:
where a,b,c,d are in F23 and 1= ad − bc = 1. With the usual conventions of defining 1= f (−d/c) = ∞ and 1= f (∞) = a/c, these functions map the set S onto itself. In geometric language, they are projectivities of the projective line. They form a group under composition which is the projective special linear group PSL(2,23) of order 6072. There are exactly 8 elements of this group that leave the initial block fixed setwise. So there will be 6072/8 = 759 images of that block. These form the octads of S(5,8,24).
мұнда a, b, c, d F23-ке жатады және 1 = ad − bc = 1. Әдеттегі шарттар бойынша 1= f (−d/c) = ∞ және 1= f (∞) = a/c деп есептесек, бұл функциялар S жиынын өзіне бейнелейді. Геометриялық тұрғыдан алғанда, бұл проективті түзудің проективті түрлендірулері. Олар құрамы бойынша топты құрайды, ол 6072 реті бар PSL(2,23) проективті арнайы сызықтық тобы болып табылады. Осы топта бастапқы блокты өзгеріссіз қалдыратын дәл 8 элемент бар. Сондықтан, осы блоктан 6072/8 = 759 бейне шығады. Бұл S(5,8,24) октадаларын құрайды.
a "block". (We can take any octad of the extended binary Golay code, seen as a quadratic residue code.) From this block, we obtain the other blocks of the S(5,8,24) system by repeatedly applying the linear fractional transformations:
where a,b,c,d are in F23 and 1= ad − bc = 1. With the usual conventions of defining 1= f (−d/c) = ∞ and 1= f (∞) = a/c, these functions map the set S onto itself. In geometric language, they are projectivities of the projective line. They form a group under composition which is the projective special linear group PSL(2,23) of order 6072. There are exactly 8 elements of this group that leave the initial block fixed setwise. So there will be 6072/8 = 759 images of that block. These form the octads of S(5,8,24).
Керемет октада генераторының құрылысы
Миракл Октад Генераторы (MOG) – нақтыланған кіші топтарды қамтитын октадтарды құру құралы. Ол 4x6 массивтен тұрады, онда қатарларға белгілі бір салмақтар тағайындалады. Атап айтқанда, 8 кіші жиынтығы S(5,8,24) октады болу үшін үш ережеге бағынуы керек. Біріншіден, 6 бағанның әрқайсысы бірдей жұптылыққа ие болуы керек, яғни олардың барлығы жұп санды ұяшықтарға немесе барлығы тақ санды ұяшықтарға ие болуы керек. Екіншіден, жоғарғы қатардың жұптылығы бағандардың жұптылығымен сәйкес келуі керек. Үшіншіден, қатарлар 4-реттік шекті өрісте 0, 1, 2 және 3 салмақтарымен көбейтіледі, ал 6 баған үшін бағандардың сомасы шекті өрістің арифметикалық анықтамалары бойынша көбейту және қосу арқылы есептеледі. Нәтижесінде алынған бағандардың сомалары (a, b, c, a + b + c, 3a + 2b + c, 2a + 3b + c) түріндегі жарамды гексакод сөзін құрауы керек, мұнда a, b, c де 4-реттік шекті өрістен алынған. Егер бағандар сомасының жұптылығы қатар сомасының жұптылығымен сәйкес келмесе немесе бір-бірімен сәйкес келмесе, немесе бағандар сомасы жарамды гексакод сөзін құрайтын a, b, c табылмаса, онда 8-нің бұл кіші жиынтығы S(5,8,24) октады емес. MOG 8 жиынын екі түрлі 4 жиынға бөлудің 35 жолы мен Fano 3 кеңістігі PG(3,2) сызықтарының 35 арасындағы биекцияны (Conwell 1910, "Үш кеңістік PG(3,2) және оның тобы") құруға негізделген. Ол сондай-ақ геометриялық тұрғыдан байланысты (Cullinane, "Алмас сақинасындағы симметриялық инварианттық", AMS хабарламалары, A193–194 беттер, 1979 жылғы ақпан) 4x4 массивын әрқайсысы 4 ұяшықтан тұратын 4 топқа бөлудің 35 әртүрлі тәсілімен, егер 4x4 массивы төрт өлшемді шекті аффиндік кеңістікті білдірсе, онда топтар параллель кіші кеңістіктер жиынтығын құрайды.