Система Штейнера
В комбинаторной математике система Штейнера (названная в честь Якоба Штайнера ) — это тип блочной схемы , а именно 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 проективная плоскость порядка q с прямыми в виде блоков представляет собой S(2, q + 1 , 2 + q + 1) , так как он имеет q 2 + q + 1 точек, каждая прямая проходит через q + 1 точку и каждая пара различных точек лежит ровно на одной прямой.
Конечная S аффинная плоскость порядка q с прямыми в виде блоков представляет собой (2, q , q 2 ) . Аффинная плоскость порядка q может быть получена из проективной плоскости того же порядка, удалив один блок и все точки в этом блоке из проективной плоскости. Выбор разных блоков для удаления таким образом может привести к неизоморфным аффинным плоскостям.
S(3,4, n ) называется системой четверок Штейнера . Необходимым и достаточным условием существования S(3,4, n ) является то, что n 2 или 4 (мод 6). аббревиатура SQS( n Для этих систем часто используется ). С точностью до изоморфизма SQS(8) и SQS(10) уникальны, имеется 4 SQS(14) и 1 054 163 SQS(16). [5]
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.
Тройные системы Штейнера
[ редактировать ]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 ), был доказан Раджем Чандрой Бозе. [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 недель без тройки девочек повторяется в течение всего семестра. Вопрос был решен RHF Denniston в 1974 году. [11] который построил первую неделю следующим образом:
Day 1 ABJ CEM FKL HIN DGODay 2 ACH DEI FGM JLN BKODay 3 ADL BHM GIK CFN EJODay 4 AEG BIL CJK DMN FHODay 5 AFI BCD GHJ EKN LMODay 6 AKM DFJ EHL BGN CIODay 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 ) что . (Равенства, хотя и технически возможны, приводят к тривиальным системам.)
Если 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 -элементов содержится ровно в одном блоке, мы имеем , или
где b — количество блоков. Аналогичные рассуждения о подмножествах t -элементов, содержащих конкретный элемент, дают нам , или
- =
где r — количество блоков, содержащих любой заданный элемент. Из этих определений следует уравнение . Необходимым условием существования S( t , k , n ) является то, что b и r являются целыми числами. Как и в любой блочной конструкции, неравенство Фишера верно в системах Штейнера.
Учитывая параметры системы Штейнера S( t, k, n ) и подмножества размера , содержащийся хотя бы в одном блоке, можно вычислить количество блоков, пересекающих это подмножество в фиксированном количестве элементов, построив треугольник Паскаля . [12] В частности, количество блоков, пересекающих фиксированный блок по любому количеству элементов, не зависит от выбранного блока.
Количество блоков, содержащих любой i -элементный набор точек, равно:
Можно показать, что если существует система Штейнера 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) существовать.
История
[ редактировать ]Тройные системы Штейнера были впервые определены Уэсли С.Б. Вулхаусом в 1844 году в призовом вопросе № 1733 журнала «Дневник леди и джентльменов». [13] Поставленную задачу решил Томас Киркман ( 1847 ). В 1850 году Киркман сформулировал вариант проблемы, известной как проблема школьницы Киркмана , которая требует наличия тройных систем, обладающих дополнительным свойством (разрешимостью). Не зная о работе Киркмана, Якоб Штайнер ( 1853 ) вновь ввел тройные системы, и, поскольку эта работа получила более широкую известность, системы были названы в его честь.
В 1910 году Джеффри Томас Беннетт дал графическое представление тройных систем Штейнера. [14] [15] [16]
Группы Матье
[ редактировать ]Некоторые примеры систем Штейнера тесно связаны с теорией групп . В частности, конечные простые группы , называемые группами Матье, возникают как группы автоморфизмов систем Штейнера:
- Группа Матье M 11 — это группа автоморфизмов S(4,5,11) системы Штейнера.
- Группа Матье M 12 — это группа автоморфизмов S(5,6,12) системы Штейнера.
- Группа Матье M 22 — это единственная подгруппа индекса 2 группы автоморфизмов S(3,6,22) системы Штейнера.
- Группа Матье M 23 — это группа автоморфизмов S(4,7,23)-системы Штейнера.
- Группа Матье M 24 является группой автоморфизмов S(5,8,24)-системы Штейнера.
Система Штейнера S(5, 6, 12)
[ редактировать ]Существует уникальная система Штейнера S(5,6,12); ее группой автоморфизмов является группа Матье M 12 , и в этом контексте она обозначается W 12 .
Построение проективной линии
[ редактировать ]Эта конструкция принадлежит Кармайклу (1937). [17]
Добавьте новый элемент, назовем его ∞ , к 11 элементам конечного поля F 11 (т. е. целым числам по модулю 11). Этот набор S из 12 элементов формально можно отождествить с точками проективной прямой над F 11 . Вызовите следующее конкретное подмножество размера 6,
«блок» (он содержит ∞ вместе с 5 ненулевыми квадратами в F 11 ). получаем остальные блоки системы S Из этого блока путем многократного применения дробно-линейных преобразований (5,6,12) :
где a,b,c,d находятся в F 11 и ad − bc = 1 .С обычными соглашениями об определении f (− d / c ) = ∞ и f (∞) = a / c эти функции отображают множество S на себя. На геометрическом языке это проективности проективной прямой. Они образуют группу под композицией, которая представляет собой проективную специальную линейную группу PSL (2,11) порядка 660. В этой группе ровно пять элементов, которые оставляют стартовый блок фиксированным по заданному принципу: [18] а именно такие, что b=c=0 и ad =1, так что f(z) = a 2 з . Таким образом, изображений этого блока будет 660/5 = 132. В результате свойства кратной транзитивности этой группы, действующего на это множество, любое подмножество из пяти элементов S появится ровно в одном из этих 132 изображений размера шесть.
Строительство котенка
[ редактировать ]Альтернативная конструкция W 12 получена с использованием «котенка» Р. Т. Кертиса, [19] который был задуман как «ручной калькулятор» для записи блоков по одному. Метод котенка основан на заполнении шаблонов в сетке чисел 3x3, которые представляют собой аффинную геометрию в векторном пространстве F 3 xF 3 , системе S(2,3,9).
Построение из K 6 факторизации графа
[ редактировать ]Отношения между факторами графа полного графа K 6 порождают 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). существует поскольку в симметричной группе S6 Этот метод работает , внешний автоморфизм , который отображает вершины в факторизации, а ребра в разбиения. Перестановка вершин приводит к тому, что факторизации переставляются по-разному в соответствии с внешним автоморфизмом.
Система Штейнера S(5, 8, 24)
[ редактировать ]Система Штейнера S(5, 8, 24), также известная как план Витта или геометрия Витта , была впервые описана Кармайклом ( 1931 ) и заново открыта Виттом ( 1938 ). Эта система связана со многими спорадическими простыми группами и с исключительной 24-мерной решеткой, известной как решетка Лича . Группа автоморфизмов S(5, 8, 24) — это группа Матье M 24 , и в этом контексте конструкция обозначается W 24 («W» означает «Витт»).
Прямая лексикографическая генерация
[ редактировать ]Все подмножества из 24 элементов из 8 элементов генерируются в лексикографическом порядке, и любое такое подмножество, которое отличается от некоторого подмножества, уже найденного менее чем в четырех позициях, отбрасывается.
Тогда список октад для элементов 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 000000000000000011111111 000000000000111100001111 . . (next 4090 24-bit strings omitted) . 111111111111000011110000 111111111111111100000000 111111111111111111111111
Кодовые слова образуют группу в рамках операции XOR .
Построение проективной линии
[ редактировать ]Эта конструкция принадлежит Кармайклу (1931). [21]
Добавьте новый элемент, назовем его ∞ , к 23 элементам конечного поля F 23 (т. е. целым числам по модулю 23). Это множество S из 24 элементов формально можно отождествить с точками проективной прямой над F 23 . Вызовите следующее конкретное подмножество размера 8,
«блок». (Мы можем взять любую октаду расширенного двоичного кода Голея , рассматриваемого как код квадратичного вычета.) Из этого блока мы получаем другие блоки системы S (5,8,24), многократно применяя дробно-линейные преобразования :
где a,b,c,d находятся в F 23 и ad − bc = 1 .С обычными соглашениями об определении f (− d / c ) = ∞ и f (∞) = a / c эти функции отображают множество S на себя. На геометрическом языке это проективности проективной прямой. Они образуют группу по композиции, которая представляет собой проективную специальную линейную группу PSL (2,23) порядка 6072. В этой группе ровно 8 элементов, которые оставляют исходный блок фиксированным по заданному принципу. Таким образом, изображений этого блока будет 6072/8 = 759. Они образуют октады S(5,8,24).
Конструкция из чудо-генератора октадов
[ редактировать ]Miracle Octad Generator (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 основан на создании биекции (Конвелл 1910, «Трёхпространственный PG(3,2) и его группа») между 35 способами разделения набора из 8 на два разных набора из 4 и 35 строками PG трехмерное пространство Фано (3,2). Это также геометрически связано (Куллинан, «Инвариантность симметрии в кольце с бриллиантом», Уведомления AMS, стр. A193-194, февраль 1979 г.) с 35 различными способами разделения массива 4x4 на 4 разные группы по 4 ячейки в каждой, например что если массив 4x4 представляет собой четырехмерное конечное аффинное пространство , то группы образуют набор параллельных подпространств.
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Это свойство эквивалентно утверждению, что (xy)y = x для всех x и y в идемпотентной коммутативной квазигруппе.
Ссылки
[ редактировать ]- ^ «Энциклопедия теории дизайна: t-дизайн» . Designtheory.org. 04.10.2004 . Проверено 17 августа 2012 г.
- ^ Киваш, Питер (2014). «Существование конструкций». arXiv : 1401.3665 [ math.CO ].
- ^ Эрика Клейррах (9 июня 2015 г.). «Дилемма дизайна решена, без дизайна» . Журнал Кванта . Проверено 27 июня 2015 г.
- ^ Калай, Гил. «Дизайн существует!» (PDF) . Семинар Бурбаки.
- ^ Колборн и Диниц, 2007 , стр.106.
- ^ Остергард и Поттонен, 2008 г.
- ^ Бозе, RC (1939). «О построении уравновешенных неполных блочных конструкций» . Анналы евгеники . 9 (4): 353–399. дои : 10.1111/j.1469-1809.1939.tb02219.x .
- ^ Т. Сколем. Некоторые замечания о системах троек Штейнера. Математика. Скан. 6 (1958), 273–280.
- ^ Колборн и Диниц 2007 , стр.60
- ^ Колборн и Диниц 2007 , стр. 497, определение 28.12
- ^ Деннистон, RHF (сентябрь 1974 г.). «Газета Деннистона, открытый доступ» . Дискретная математика . 9 (3): 229–233. дои : 10.1016/0012-365X(74)90004-1 .
- ^ Ассмус и Ки 1992 , с. 8.
- ^ Линднер и Роджер 1997 , стр.3
- ^ Бейкер, HF (13 ноября 1943 г.). «Некролог. Доктор Г.Т. Беннетт, ФРС». Природа . 152 (3863): 558–559. дои : 10.1038/152558a0 .
- ^ Беннетт, GT (1911). «Двойная шестерка» (PDF) . Труды Лондонского математического общества . 2 (1): 336–351.
- ^ Беннетт, GT (1912). «Система линий кубической поверхности» (PDF) . Труды Лондонского математического общества . 2 (1): 479–484.
- ^ Кармайкл 1956 , с. 431
- ^ Бет, Юнгникель и Ленц 1986 , стр. 196
- ^ Кертис 1984
- ^ «Учебник ЕАГТС» .
- ^ Кармайкл 1931 г.
Ссылки
[ редактировать ]- Ассмус, EF; Ки, JD (1992), Проекты и их коды , Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-41361-9
- Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1986), Теория дизайна , Кембридж: Издательство Кембриджского университета . 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
- Кертис, RT (1984), «Система Штейнера S (5,6,12), группа Матье M 12 и «котенок» », в книге Аткинсона, Майкла Д. (ред.), Вычислительная теория групп (Дарем, 1982). ) , Лондон: Academic Press, стр. 353–358, ISBN. 978-0-12-066270-8 , МР 0760669
- Хьюз, доктор медицинских наук; Пайпер, ФК (1985), Теория дизайна , Издательство Кембриджского университета, стр. 173–176, ISBN 978-0-521-35872-9 .
- Киркман, Томас П. (1847), «О проблеме комбинаций», Кембриджский и Дублинский математический журнал , II : 191–204.
- Линднер, CC; Роджер, Калифорния (1997), Теория дизайна , Бока-Ратон: CRC Press, ISBN 978-0-8493-3986-8
- Остергард, Патрик Р.Дж.; Поттонен, Олли (2008), «Не существует системы Штейнера S (4,5,17)», Журнал комбинаторной теории , серия A, 115 (8): 1570–1573, doi : 10.1016/j.jcta.2008.04. 005
- Штайнер, Дж. (1853), «Комбинаторная задача» , Журнал чистой и прикладной математики , 1853 (45): 181–182, doi : 10.1515/crll.1853.45.181 , S2CID 199547187 .
- Витт, Эрнст (1938), «5-кратные транзитивные группы Матье», кафедра математики Univ. Гамбург , 12 : 256–264, doi : 10.1007/BF02948947 , S2CID 123658601
Внешние ссылки
[ редактировать ]- Роуленд, Тодд и Вайсштейн, Эрик В. «Система Штайнера» . Математический мир .
- Румов, Б.Т. (2001) [1994], «Система Штейнера» , Энциклопедия математики , EMS Press
- Системы Штейнера Андриса Э. Брауэра
- Реализация S(5,8,24) доктором Альберто Дельгадо, Гейбом Хартом и Майклом Колкебеком
- S(5, 8, 24) Программное обеспечение и листинг Йохана Э. Мебиуса