Введение
Блочные конструкции в комбинаторной математике
В комбинаторной математике система Штайнера (названная в честь Якоба Штайнера) является типом блочной конструкции, а именно t-конструкцией с λ = 1 и t = 2 или (в последнее время) t ≥ 2. Система Штайнера с параметрами t, k, n, обозначаемая S(t, k, n), представляет собой множество S из n элементов вместе с набором 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. Существование обоих случаев было доказано Питером Кивашем в 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) называется системой Штейнера из троек, а ее блоки называются тройками. Обычно используется аббревиатура STS(n) для системы Штейнера из троек порядка 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, используя систему Штейнера из троек, положив aa = a для всех a из S, и ab = c, если {a,b,c} является тройкой. Это делает S идемпотентной, коммутативной квазигруппой. Она обладает дополнительным свойством, что ab = c влечет bc = a и ca = b. Обратно, любая (конечная) квазигруппа с этими свойствами возникает из системы Штейнера из троек. Коммутативные идемпотентные квазигруппы, удовлетворяющие этому дополнительному свойству, называются квазигруппами Штейнера.
История
Тройные системы Штайнера были впервые определены Уэсли С. Б. Вулхаусом в 1844 году в вопросе № 1733 "Дневника леди и джентльмена". В 1850 году Киркман предложил вариацию этой задачи, известную как задача о школьницах Киркмана, которая требует, чтобы тройные системы обладали дополнительным свойством (разрешимостью). Не зная о работе Киркмана, он заново ввёл тройные системы, и поскольку его работа получила более широкое распространение, системы были названы в его честь.
Система Штайнера S ((5, 6, 12)
Существует единственная система Штайнера S(5,6,12); её группа автоморфизмов — группа Матье M12, и в этом контексте она обозначается W12.
Строительство проективной линии
Эта конструкция восходит к Кармайклу (1937). Добавьте новый элемент, обозначим его ∞, к 11 элементам конечного поля F11 (то есть, целым числам по модулю 11). Этот набор, S, из 12 элементов может быть формально отождествлен с точками проективной прямой над F11. Назовем следующее специфическое подмножество размера 6 "блоком" (оно содержит ∞ вместе с 5 ненулевыми квадратами в F11). Из этого блока мы получаем остальные блоки системы 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 и выполняется условие ad − bc = 1. При общепринятых соглашениях об определении f(−d/c) = ∞ и f(∞) = a/c, эти функции отображают множество S на себя. В геометрических терминах, это проективные преобразования проективной прямой. Они образуют группу относительно композиции, которая является проективной специальной линейной группой PSL(2,11) порядка 660. В этой группе ровно пять элементов, которые оставляют исходный блок инвариантным как множество, а именно те, для которых b = c = 0 и ad = 1, так что f(z) = a²z. Следовательно, существует 660/5 = 132 образа этого блока. В силу мультитранзитивного свойства этой группы, действующей на этом множестве, любое подмножество из пяти элементов S встречается ровно в одном из этих 132 образов размера шесть.
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 получена с использованием "котенка" Р. Т. Кертиса, изначально задуманного как "ручной вычислитель" для последовательной записи блоков. Метод "котенка" основан на дополнении шаблонов в сетке 3x3, представляющей аффинную геометрию на векторном пространстве F3xF3, являющейся системой S(2,3,9).
Конструкция из факторизации графа K6
Отношения между графовыми факторами полного графа K6 генерируют S(5,6,12). Граф K6 имеет 6 вершин, 15 ребер, 15 совершенных соответствий и 6 различных 1-факторизаций (способов разбиения ребер на непересекающиеся совершенные соответствия). Множество вершин (обозначенных 123456) и множество факторизаций (обозначенных ABCDEF) предоставляют по одному блоку каждый. Каждая пара факторизаций имеет ровно одно совершенное соответствие в общем. Предположим, факторизации A и B имеют общее соответствие с ребрами 12, 34 и 56. Добавьте три новых блока AB3456, 12AB56 и 1234AB, заменяя каждое ребро в общем соответствии метками факторизаций поочередно. Аналогично добавьте еще три блока 12CDEF, 34CDEF и 56CDEF, заменяя метки факторизаций соответствующими метками ребер общего соответствия. Повторите это для всех 15 пар факторизаций, чтобы добавить 90 новых блоков. Наконец, возьмите полный набор комбинаций из 6 объектов из 12 и отбросьте любую комбинацию, которая имеет 5 или более объектов в общем с любым из 92 блоков, сгенерированных до сих пор. Остается ровно 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). Добавьте новый элемент, обозначим его ∞, к 23 элементам конечного поля F23 (то есть, целым числам по модулю 23). Этот набор, S, из 24 элементов может быть формально отождествлен с точками проективной прямой над 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 и выполняется условие ad − bc = 1. При общепринятых соглашениях об определении f(−d/c) = ∞ и f(∞) = a/c, эти функции отображают множество S на себя. В геометрических терминах, это проективные преобразования проективной прямой. Они образуют группу относительно композиции, которая является проективной специальной линейной группой PSL(2,23) порядка 6072. В этой группе ровно 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 столбцов должен иметь одинаковый паритет, то есть все они должны содержать нечетное число ячеек или все — четное. Во-вторых, верхняя строка должна иметь тот же паритет, что и каждый из столбцов. В-третьих, строки последовательно умножаются на веса 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 прямыми в пространстве Фано PG(3,2). Он также геометрически связан (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, pp A193–194, Feb. 1979) с 35 различными способами разбиения массива 4x4 на 4 различные группы по 4 ячейки в каждой, так что, если массив 4x4 представляет собой четырехмерное конечное аффинное пространство, то группы образуют набор параллельных подпространств.