система Штайнера

В комбинаторной математике система Штейнера (названная в честь Якоба Штейнера ) — это тип блочной конструкции , в частности t-конструкция с λ = 1 и t = 2 или (в последнее время) t ≥ 2.

Система Штейнера с параметрами t , k , n , обозначаемая как S( t , k , n ), представляет собой n -элементный набор S вместе с набором k -элементных подмножеств S (называемых блоками ) со свойством, что каждое t -элементное подмножество S содержится ровно в одном блоке. В альтернативной записи для блочных конструкций S( t , k , n ) будет t- ( n , k ,1) конструкцией.

Это определение относительно новое. Классическое определение систем Штейнера также требовало, чтобы k = t + 1. S(2,3, n ) называлась (и до сих пор называется) системой тройки (или триады ) Штейнера , в то время как S(3,4, n ) называется системой четверки Штейнера , и так далее. С обобщением определения эта система наименований больше не строго соблюдается.

Давними проблемами в теории проектирования были: существуют ли какие-либо нетривиальные системы Штейнера (нетривиальные, то есть t < k < n ) с t ≥ 6; а также существует ли бесконечно много систем с t = 4 или 5. ^[1] Оба существования были доказаны Питером Кивашем в 2014 году. Его доказательство неконструктивно , и по состоянию на 2019 год не известно ни одной реальной системы Штейнера для больших значений t . ^{[2] [3] [4]}

Конечная проективная плоскость порядка q , в которой прямые являются блоками, является S(2, q + 1, q ² + q + 1) , поскольку она имеет q ² + q + 1 точек, каждая прямая проходит через q + 1 точек, и каждая пара различных точек лежит ровно на одной прямой.

Конечная аффинная плоскость порядка q с прямыми в качестве блоков — это S(2,  q ,  q ² ) . Аффинная плоскость порядка 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). ^[5]${\displaystyle \equiv}$

S(4,5, n ) называется пятеричной системой Штейнера . Необходимым условием существования такой системы является то, что n 3 или 5 (mod 6), что следует из соображений, которые применимы ко всем классическим системам Штейнера. Дополнительным необходимым условием является то, что n 4 (mod 5), что следует из того факта, что количество блоков должно быть целым числом. Достаточные условия неизвестны. Существует уникальная пятеричная система Штейнера порядка 11, но ни одна из порядков 15 или 17. ^[6] Известны системы для порядков 23, 35, 47, 71, 83, 107, 131, 167 и 243. Наименьший порядок, существование которого неизвестно (по состоянию на 2011 год), — это 21.${\displaystyle \equiv}$ ${\displaystyle \not \equiv }$

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 ), был доказан Раджем Чандрой Бозе ^[7] и Т. Сколемом. ^[8] Проективная плоскость порядка 2 ( плоскость Фано ) является STS(7), а аффинная плоскость порядка 3 является STS(9). С точностью до изоморфизма STS(7) и STS(9) уникальны, существует два STS(13), 80 STS(15) и 11 084 874 829 STS(19). ^[9]

Мы можем определить умножение на множестве S, используя систему троек Штейнера, установив aa = a для всех a из S , и ab = c, если { a , b , c } — тройка. Это делает S идемпотентной , коммутативной квазигруппой . Она обладает дополнительным свойством, что ab = c влечет bc = a и ca = b . ^{[примечание 1] И наоборот, любая} ( конечная) квазигруппа с этими свойствами возникает из системы троек Штейнера. Коммутативные идемпотентные квазигруппы, удовлетворяющие этому дополнительному свойству, называются квазигруппами Штейнера . ^[10]

Некоторые из систем S(2,3,n) могут иметь свои тройки, разделенные на (n-1)/2 наборов, каждый из которых имеет (n/3) попарно непересекающихся тройок. Это называется разрешимым , и такие системы называются системами троек Киркмана в честь Томаса Киркмана , который изучал такие разрешимые системы до Штейнера. Дейл Меснер, Эрл Крамер и другие исследовали наборы систем троек Штейнера, которые являются взаимно непересекающимися (т. е. никакие две системы Штейнера в таком наборе не имеют общей тройки). Известно (Bays 1917, Kramer & Mesner 1974), что можно сгенерировать семь различных систем S(2,3,9), чтобы вместе покрыть все 84 триплета на 9-наборе; им также было известно, что существует 15360 различных способов нахождения таких 7-множеств решений, которые при переименовании сводятся к двум неизоморфным решениям с кратностями 6720 и 8640 соответственно.

Соответствующий вопрос для нахождения тринадцати различных непересекающихся систем S(2,3,15) был задан Джеймсом Сильвестром в 1860 году как расширение проблемы школьниц Киркмана , а именно, могли ли школьницы Киркмана маршировать в течение всего срока из 13 недель, не повторяя ни одной тройки девочек в течение всего срока. Вопрос был решен Р. Х. Ф. Деннистоном в 1974 году, ^[11], который построил Неделю 1 следующим образом:

День 1 ABJ CEM FKL HIN DGOДень 2 ACH DEI FGM JLN BKOДень 3 ADL BHM GIK CFN EJOДень 4 AEG BIL CJK DMN FHOДень 5 AFI BCD GHJ EKN LMOДень 6 AKM DFJ EHL BGN CIOДень 7 BEF CGL DHK IJM ANO

для девочек, помеченных от A до O, и построил решение каждой последующей недели из его непосредственного предшественника, меняя A на B, B на C, ... L на M и M обратно на A, все время оставляя N и O неизменными. Решение 13-й недели после прохождения этой перемаркировки возвращается к решению 1-й недели. Деннистон сообщил в своей статье, что поиск, который он использовал, занял 7 часов на компьютере Elliott 4130 в Университете Лестера , и он немедленно завершил поиск, найдя решение выше, не пытаясь установить уникальность. Количество неизоморфных решений задачи Сильвестра остается неизвестным по состоянию на 2021 год.

Из определения S ( t , k , n ) ясно , что (Равенства, хотя технически возможны, приводят к тривиальным системам.)${\displaystyle 1<т<к<н}$

Если S( t , k , n ) существует, то взятие всех блоков, содержащих определенный элемент, и отбрасывание этого элемента дает производную систему S( t −1, k −1, n −1) . Следовательно, существование S( t −1, k −1, n −1) является необходимым условием существования S( t , k , n ) .

Число подмножеств t -элементов в S равно , тогда как число подмножеств t -элементов в каждом блоке равно . Поскольку каждое подмножество t -элементов содержится ровно в одном блоке, то имеем , или ${\displaystyle {\tbinom {n}{t}}}$${\displaystyle {\tbinom {k}{t}}}$${\displaystyle {\tbinom {n}{t}}=b{\tbinom {k}{t}}}$

${\displaystyle b={\frac {\tбином {n}{t}}{\tбином {k}{t}}}={\frac {n(n-1)\cdots (n-t+1)}{k(k-1)\cdots (k-t+1)}},}$

где b — число блоков. Аналогичные рассуждения о подмножествах t -элементов, содержащих определенный элемент, дают нам , или ${\displaystyle {\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}}$

${\displaystyle r={\frac {\tbinom {n-1}{t-1}}{\tbinom {k-1}{t-1}}}}$=${\displaystyle {\frac {(n-t+1)\cdots (n-2)(n-1)}{(k-t+1)\cdots (k-2)(k-1)}},}$

где r — число блоков, содержащих любой заданный элемент. Из этих определений следует уравнение . Необходимым условием существования S( t , k , n ) является то, что b и r являются целыми числами. Как и в случае любой блочной конструкции, неравенство Фишера справедливо в системах Штейнера.${\displaystyle bk=rn}$ ${\displaystyle b\geq n}$

Учитывая параметры системы Штейнера S( t, k, n ) и подмножество размера , содержащееся по крайней мере в одном блоке, можно вычислить количество блоков, пересекающих это подмножество в фиксированном количестве элементов, построив треугольник Паскаля . ^[12] В частности, количество блоков, пересекающих фиксированный блок в любом количестве элементов, не зависит от выбранного блока.${\displaystyle t'\leq t}$

Число блоков, содержащих любой i -элементный набор точек, равно:

${\displaystyle \lambda _{i}=\left.{\binom {ni}{ti}}\right/{\binom {ki}{ti}}{\text{ для }}i=0,1,\ldots ,t,}$

Можно показать, что если существует система Штейнера S(2, k , n ) , где k — степень простого числа, большая 1, то n 1 или k (mod k ( k −1)) . В частности, система троек Штейнера S(2, 3, n ) должна иметь n = 6 m + 1 или 6 m + 3. И как мы уже упоминали, это единственное ограничение на системы троек Штейнера, то есть для каждого натурального числа m существуют системы S(2, 3, 6 m + 1) и S(2, 3, 6 m + 3) .${\displaystyle \equiv}$

Системы тройных Штейнера были впервые определены Уэсли С. Б. Вулхаусом в 1844 году в вопросе Prize #1733 журнала Lady's and Gentlemen's Diary. ^[13] Поставленная задача была решена Томасом Киркманом  (1847). В 1850 году Киркман сформулировал вариант задачи, известный как задача школьницы Киркмана , в которой требуется, чтобы системы тройных систем имели дополнительное свойство (разрешимость). Не зная о работе Киркмана, Якоб Штейнер  (1853) вновь ввел системы тройных систем, и поскольку эта работа стала более широко известна, системы были названы в его честь.

В 1910 году Джеффри Томас Беннетт дал графическое представление для тройных систем Штейнера. ^{[14] [15] [16]}

Несколько примеров систем Штейнера тесно связаны с теорией групп . В частности, конечные простые группы , называемые группами Матье, возникают как группы автоморфизмов систем Штейнера:

• Группа Матье M ₁₁ является группой автоморфизмов системы Штейнера S(4,5,11)
• Группа Матье M ₁₂ является группой автоморфизмов системы Штейнера S(5,6,12)
• Группа Матье M ₂₂ является уникальной подгруппой индекса 2 группы автоморфизмов системы Штейнера S(3,6,22)
• Группа Матье M ₂₃ является группой автоморфизмов системы Штейнера S(4,7,23)
• Группа Матье M ₂₄ является группой автоморфизмов системы Штейнера S(5,8,24).

Существует единственная система Штейнера S(5,6,12); ее группа автоморфизмов — группа Матье M ₁₂ , и в этом контексте она обозначается как W ₁₂ .

Эта конструкция принадлежит Кармайклу (1937). ^[17]

Добавьте новый элемент, назовем его ∞ , к 11 элементам конечного поля F ₁₁ (то есть целым числам mod 11). Этот набор, S , из 12 элементов можно формально отождествить с точками проективной прямой над F ₁₁ . Назовем следующее конкретное подмножество размера 6,

${\displaystyle \{\infty,1,3,4,5,9\},}$

"блок" (он содержит ∞ вместе с 5 ненулевыми квадратами в F ₁₁ ). Из этого блока мы получаем другие блоки системы S (5,6,12) путем многократного применения дробно-линейных преобразований :

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

где a,b,c,d находятся в F ₁₁ и ad − bc = 1 . С обычными соглашениями определения f (− d / c ) = ∞ и f (∞) = a / c , эти функции отображают множество S на себя. На геометрическом языке они являются проективностями проективной прямой. Они образуют группу относительно композиции, которая является проективной специальной линейной группой PSL (2,11) порядка 660. Существует ровно пять элементов этой группы, которые оставляют начальный блок фиксированным по существу, ^[18] а именно те, что b = c = 0 и ad = 1, так что f(z) = a ² z . Таким образом, будет 660/5 = 132 изображения этого блока. Как следствие свойства множественной транзитивности этой группы, действующей на это множество, любое подмножество из пяти элементов S появится ровно в одном из этих 132 изображений размера шесть.

Альтернативная конструкция W ₁₂ получается с использованием «котёнка» RT Curtis ^[19] , который был задуман как «ручной калькулятор» для записи блоков по одному за раз. Метод котёнка основан на заполнении шаблонов в сетке чисел 3x3, которые представляют собой аффинную геометрию на векторном пространстве F ₃ xF ₃ , системе S(2,3,9).

Отношения между факторами графа полного графа K ₆ порождают S(5,6,12). ^[20] Граф AK _{6 имеет 6 вершин, 15 ребер, 15} совершенных паросочетаний и 6 различных 1-факторизаций (способов разбиения ребер на непересекающиеся совершенные паросочетания). Набор вершин (обозначенный 123456) и набор факторизаций (обозначенный ABCDEF ) предоставляют по одному блоку каждый. Каждая пара факторизаций имеет ровно одно общее совершенное паросочетание. Предположим, что факторизации A и B имеют общее паросочетание с ребрами 12, 34 и 56. Добавьте три новых блока AB 3456, 12 AB 56 и 1234 AB , заменив каждое ребро в общем паросочетании метками факторизации по очереди. Аналогично добавьте еще три блока 12 CDEF , 34 CDEF и 56 CDEF , заменив метки факторизации соответствующими метками ребер общего соответствия. Сделайте это для всех 15 пар факторизаций, чтобы добавить 90 новых блоков. Наконец, возьмите полный набор комбинаций из 6 объектов из 12 и отбросьте любую комбинацию, которая имеет 5 или более общих объектов с любым из 92 блоков, сгенерированных до сих пор. Остается ровно 40 блоков, что дает 2 + 90 + 40 = 132 блока S(5,6,12). Этот метод работает, потому что есть внешний автоморфизм на симметрической группе S ₆ , который отображает вершины в факторизации, а ребра в разбиения. Перестановка вершин заставляет факторизации переставляться по-разному, в соответствии с внешним автоморфизмом.${\displaystyle {\tbinom {12}{6}}=924}$

Система Штейнера S(5, 8, 24), также известная как схема Витта или геометрия Витта , была впервые описана Кармайклом  (1931) и переоткрыта Виттом  (1938). Эта система связана со многими спорадическими простыми группами и с исключительной 24-мерной решеткой, известной как решетка Лича . Группа автоморфизмов S(5, 8, 24) — это группа Матье M ₂₄ , и в этом контексте схема обозначается W ₂₄ («W» от «Витт»)

Все 8-элементные подмножества 24-элементного набора генерируются в лексикографическом порядке, и любое такое подмножество, которое отличается от некоторого уже найденного подмножества менее чем в четырех позициях, отбрасывается.

Список октад для элементов 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

.

. (следующие 753 октады пропущены)

.

13 14 15 16 17 18 19 20

13 14 15 16 21 22 23 24

17 18 19 20 21 22 23 24

Каждый отдельный элемент встречается 253 раза где-то в какой-то октаде. Каждая пара встречается 77 раз. Каждая тройка встречается 21 раз. Каждая четверка (тетрада) встречается 5 раз. Каждая пятерка (пентада) встречается один раз. Встречаются не все гексада, гептада или октада.

Генерируется 4096 кодовых слов 24-битного двоичного кода Голея , а 759 кодовых слов с весом Хэмминга 8 соответствуют системе S(5,8,24).

Код Голея может быть построен многими методами, такими как генерация всех 24-битных двоичных строк в лексикографическом порядке и отбрасывание тех, которые отличаются от более ранней менее чем на 8 позиций . Результат выглядит следующим образом:

 000000000000000000000000 0000000000000000011111111 000000000000111100001111 . . (следующие 4090 24-битных строк пропущены) . 111111111111000011110000 1111111111111111100000000 111111111111111111111111

Кодовые слова образуют группу под действием операции XOR .

Эта конструкция принадлежит Кармайклу (1931). ^[21]

Добавьте новый элемент, назовем его ∞ , к 23 элементам конечного поля F ₂₃ (то есть целым числам mod 23). Этот набор S из 24 элементов можно формально отождествить с точками проективной прямой над F ₂₃ . Назовем следующее конкретное подмножество размера 8,

${\displaystyle \{\infty,0,1,3,12,15,21,22\},}$

«блок». (Мы можем взять любую октаду расширенного двоичного кода Голея , рассматриваемого как код квадратичного остатка.) Из этого блока мы получаем другие блоки системы S (5,8,24) путем многократного применения дробно-линейных преобразований :

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

где a,b,c,d находятся в F ₂₃ и ad − bc = 1 . С обычными соглашениями определения f (− d / c ) = ∞ и f (∞) = a / c , эти функции отображают множество S на себя. На геометрическом языке они являются проективностями проективной прямой. Они образуют группу относительно композиции, которая является проективной специальной линейной группой PSL (2,23) порядка 6072. Существует ровно 8 элементов этой группы, которые оставляют исходный блок фиксированным. Таким образом, будет 6072/8 = 759 изображений этого блока. Они образуют октады S(5,8,24).

Генератор Miracle Octad (MOG) — это инструмент для генерации октад, например, содержащих указанные подмножества. Он состоит из массива 4x6 с определенными весами, назначенными строкам. В частности, 8-подмножество должно подчиняться трем правилам, чтобы быть октадой S(5,8,24). Во-первых, каждый из 6 столбцов должен иметь одинаковую четность , то есть все они должны иметь нечетное количество ячеек или все они должны иметь четное количество ячеек. Во-вторых, верхняя строка должна иметь ту же четность, что и каждый из столбцов. В-третьих, строки соответственно умножаются на веса 0, 1, 2 и 3 по конечному полю порядка 4 , и суммы столбцов вычисляются для 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 основан на создании биекции (Conwell 1910, "The three-space PG(3,2) and its group") между 35 способами разбиения 8-множества на два различных 4-множества и 35 линиями 3-пространства Фано PG(3,2). Он также геометрически связан (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, стр. A193-194, февраль 1979) с 35 различными способами разбиения массива 4x4 на 4 различные группы по 4 ячейки в каждой, так что если массив 4x4 представляет собой четырехмерное конечное аффинное пространство , то группы образуют набор параллельных подпространств.

• Код постоянного веса
• Проблема школьницы Киркмана
• Конфигурация Сильвестра – Галлая

• Асмус, Э.Ф.; Ки, Дж.Д. (1992), Конструкции и их коды , Кембридж: Cambridge University Press, ISBN 978-0-521-41361-9
• Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1986), Теория дизайна , Кембридж: Cambridge University Press. 2-е изд. (1999) ISBN 978-0-521-44432-3 . 
• Кармайкл, Роберт (1931), «Тактические конфигурации ранга два», American Journal of Mathematics , 53 (1): 217–240, doi :10.2307/2370885, JSTOR  2370885
• Кармайкл, Роберт Д. (1956) [1937], Введение в теорию групп конечного порядка , Довер, ISBN 978-0-486-60300-1
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (1996), Справочник комбинаторных конструкций , Бока-Ратон: Chapman & Hall/CRC, ISBN 978-0-8493-8948-1, ЗБЛ  0836.00010
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник комбинаторных конструкций (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN 978-1-58488-506-1, ЗБЛ  1101.05001
• Кертис, РТ (1984), «Система Штейнера S(5,6,12), группа Матье M ₁₂ и «котенок»", в Аткинсон, Майкл Д. (ред.), Вычислительная теория групп (Дарем, 1982) , Лондон: Academic Press, стр. 353–358, ISBN 978-0-12-066270-8, МР  0760669
• Хьюз, Д. Р.; Пайпер, Ф. К. (1985), Теория дизайна , Cambridge University Press, стр. 173–176, ISBN 978-0-521-35872-9.
• Киркман, Томас П. (1847), «Об одной проблеме сочетаний», Кембриджский и Дублинский математический журнал , II : 191–204.
• Линднер, CC; Роджер, CA (1997), Теория дизайна , Бока-Ратон: CRC Press, ISBN 978-0-8493-3986-8
• Östergard, Patric RJ; Pottonen, Olli (2008), «Системы Штейнера S(4,5,17) не существует», Журнал комбинаторной теории , Серия A, 115 (8): 1570–1573, doi : 10.1016/j.jcta.2008.04.005
• Штайнер, Дж. (1853), «Combinatorische Aufgabe», Journal für die reine und angewandte Mathematik , 1853 (45): 181–182, doi : 10.1515/crll.1853.45.181, S2CID  199547187.
• Витт, Эрнст (1938), "Die 5-Fach transitiven Gruppen von Mathieu", Abh. Математика. Сем. унив. Гамбург , 12 : 256–264, номер номера : 10.1007/BF02948947, S2CID  123658601 .

На Викискладе есть медиафайлы по теме «Системы Штайнера» .

• Роуленд, Тодд и Вайсштейн, Эрик В. «Система Штайнера». Математический мир .
• Румов, Б.Т. (2001) [1994], «Система Штейнера», Энциклопедия математики , Издательство EMS
• Системы Штайнера Андриеса Э. Брауэра
• Реализация S(5,8,24) доктором Альберто Дельгадо, Гейбом Хартом и Майклом Колкебеком
• S(5, 8, 24) Программное обеспечение и листинг Йохана Э. Мебиуса