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

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

Конечная аффинная плоскость^[англ.] порядка q с прямыми в качестве блоков является схемой S(2, q, q²). Аффинная плоскость порядка q может быть получена из проективной плоскости того же порядка получается путём удаления одного блока и всех точек этого блока из проективной плоскости. Если выбрать другие блоки для удаления, можно получить неизоморфные аффинные плоскости.

Схема S(2,3,n) называется системой троек Штейнера, а его блоки называются тройками. Часто для систем троек Штейнера используется обозначение STS(n).Число троек, проходящих через точку, равно (n-1)/2, а потому общее число троек равно n(n−1)/6. Это показывает, что n должно иметь вид 6k+1 или 6k + 3 для некоторого k. Факт, что это условие для n достаточно для существования S(2,3,n), доказали Рей Чандра Бозе^{[англ.][5]} и Т. Сколем^[6]. Проективная плоскость порядка 2 (плоскость Фано) — это STS(7), а аффинная плоскость^[англ.] порядка 3 — это STS(9).

С точностью до изоморфизма STS(7) и STS(9) единственны. Существует две схемы STS(13), 80 схем STS(15) и 11 084 874 829 схем STS(19)^[7].

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

Схема S(3,4,n) называется системой четвёрок Штейнера. Необходимое и достаточное условие существования S(3,4,n) — n ${\displaystyle \equiv }$ 2 или 4 (mod 6). Для этих систем часто используется обозначение SQS(n).

С точностью до изоморфизма SQS(8) и SQS(10) единственны, имеется 4 схемы SQS(14) и 1.054.163 схем SQS(16)^[9].

Схема S(4,5,n) называется системой пятёрок Штейнера. Необходимое условие существования такой системы — n ${\displaystyle \equiv }$ 3 или 5 (mod 6), что получается из соглашений, которые применимы ко всем классическим системам Штейнера. Дополнительное условие для общих систем, что n ${\displaystyle \not \equiv }$ 4 (mod 5), получается из факта, что число блоков должно быть целым. Достаточные условия неизвестны.

Существует единственная система пятёрок Штейнера порядка 11, но нет систем порядка 15 или 17^[10]. Известны системы с порядками 23, 35, 47, 71, 83, 107, 131, 167 и 243. Наименьший порядок, для которого существование неизвестно (на 2011 год) — 21.

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

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

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

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

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

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

${\displaystyle \lambda _{i}=\left.{\binom {n-i}{t-i}}\right/{\binom {k-i}{t-i}}}$ для ${\displaystyle i=0,1,\ldots ,t,}$

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

Системы троек Штейнера первым определил В.С.Б. Вулхауз^[англ.] в 1844 в премиальном вопросе #1733 в журнале Lady's and Gentlemen's Diary^{[англ.][12]}. Поставленную задачу решил Томас Киркман^[13]. В 1850 Киркман поставил вариант задачи, получивший название «задача Киркмана о школьницах», в которой спрашивается о системе троек с дополнительным свойством (разрешимость). Не зная работы Киркмана, Якоб Штейнер^[14] определил систему троек, и его работа получила бо́льшую известность, так что система получила его имя.

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

• Группа Матьё 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₁₂.

Имеются различные пути построения системы S(5,6,12).

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

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

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

«блоком». С помощью этого блока мы получим другие блоки схемы S(5,6,12) путём многократного применения дробно-линейного преобразования:

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

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

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

Связь между факторами полного графа K₆ генерирует схему S(5,6,12)^[18]. Граф K₆ имеет 6 различных 1-факторизаций (путей разбиения рёбер на совершенные паросочетания), а также 6 вершин. Множество вершин и множество факторизаций дают по блоку. Для каждой пары факторизаций существует ровно одно общее совершенное паросочетание. Возьмём множество вершин и заменим две вершины, соответствующие ребру общего совершенного паросочетания меткой, соответствующей факторизациям. Добавим результат в множество блоков. Повторим процесс для оставшихся двух рёбер общего совершенного паросочетания. Просто возьмём множество факторизаций и заменим метки, соответствующие двум факторизациям, конечными точками ребра в общем совершенном паросочетании. Повторяем это для других двух рёбер паросочетания. Существуют 3+3 = 6 блоков для каждой пары факторизаций, и имеется 6C2 = 15 пар среди 6 факторизаций, что даёт 90 новых блоков. Наконец, берём полное множество 12C6 = 924 комбинаций 6 объектов из 12 и отбрасываем любые комбинации, которые имеют 5 или более общих объектов с любыми из 92 блоков. Остаётся ровно 40 блоков, что даёт 2+90+40 = 132 блоков схемы S(5,6,12).

Система Штейнера S(5, 8, 24), известная также как схема Витта или геометрия Витта, была описана Робертом Кармайклом^[19] и переоткрыта Виттом^[20]. Эта система связана с многими спорадическими группами и с исключительной^[англ.] 24-мерной решёткой, известной как решётка Лича.

Группа автоморфизмов схемы S(5, 8, 24) является группой Матьё M₂₄^[англ.] и в контексте схем обозначается W₂₄ («W» от «Witt»)

Существует много путей построения S(5,8,24). Здесь описано два метода:

Все 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 раз. Каждая пятёрка встречается один раз. Не любая шестёрка семёрка или восьмёрка встречается.

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

    000000000000000000000000    000000000000000011111111    000000000000111100001111    000000000000111111110000    000000000011001100110011    000000000011001111001100    000000000011110000111100    000000000011110011000011    000000000101010101010101    000000000101010110101010    .    . (следующие 4083 24-битных строк опущены)    .    111111111111000011110000    111111111111111100000000    111111111111111111111111

Список содержит 4096 элементов, которые являются кодовыми словами расширенного двоичного кода Голея. Они образуют группу по операции XOR. Одно из слов состоит из нулевых бит, 759 слов имеют по восемь единичных бит, 2576 слов имеют по двенадцать единичных бит, 759 слов имеют шестнадцать единичных бит и одно слово полностью состоит из единичных бит. 759 8-элементных блоков схемы S(5,8,24) задаются единичными битами слов с восемью единицами.

• Код с постоянным весом^[англ.]
• Задача Киркмана о школьницах
• Конфигурация Сильвестра — Галлаи

• Rowland, Todd and Weisstein, Eric W. Steiner System (англ.) на сайте Wolfram MathWorld.
• Rumov, B.T. (2001), "Steiner system", in Hazewinkel, Michiel (ed.), Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Steiner systems by Andries E. Brouwer
• Implementation of S(5,8,24) by Dr. Alberto Delgado, Gabe Hart, and Michael Kolkebeck
• S(5, 8, 24) Software and Listing by Johan E. Mebius
• The Witt Design computed by Ashay Dharwadker