Система Штейнера - Steiner system

В Самолет Фано является системой троек Штейнера S (2,3,7). Блоки представляют собой 7 строк, каждая по 3 точки. Каждая пара точек принадлежит единственной прямой.

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

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

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

Давние проблемы в теория дизайна существуют ли какие-либо нетривиальные системы Штейнера (нетривиальный смысл т < k < п) с т ≥ 6; а также бесконечно много т = 4 или 5.^[1] Оба существования были доказаны Питер Кееваш в 2014 году. Его доказательство неконструктивный и, по состоянию на 2019 год, нет реальных систем Штайнера для больших значений т.^[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,п) называется Счетверенная система Штейнера. Необходимое и достаточное условие существования S (3,4,п) в том, что п ${displaystyle Equiv}$ 2 или 4 (мод. 6). Аббревиатура SQS (п) часто используется для этих систем. С точностью до изоморфизма SQS (8) и SQS (10) уникальны, всего 4 SQS (14) и 1 054 163 SQS (16).^[5]

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

Тройные системы Штейнера

Ан S (2,3,п) называется Тройная система Штейнера, а его блоки называются тройки. Обычно встречается сокращение STS (п) для системы троек Штейнера порядка п. Общее количество пар п (п-1) / 2, из которых три входят в тройку, и поэтому общее количество троек равно п(п−1) / 6. Это показывает, что п должен иметь форму 6к + 1 или же 6к + 3 для некоторых k. Дело в том, что это условие на п достаточно для существования S (2,3,п) было доказано Радж Чандра Бос^[7] и Т. Сколем.^[8] Проективная плоскость порядка 2 ( Самолет Фано ) является СТС (7), а аффинная плоскость порядка 3 - это СТС (9). С точностью до изоморфизма STS (7) и STS (9) уникальны, существует два STS (13), 80 STS (15) и 11 084 874 829 STS (19).^[9]

Блоки некоторых систем 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 г. и ответил РХФ Деннистон в 1974. Существует по крайней мере одно такое 13-множество S (2,3,15), но его изоморфизм неизвестен.

Мы можем определить умножение на множестве S используя тройную систему Штейнера, установив аа = а для всех а в S, и ab = c если {а,б,c} - тройка. Это делает S ан идемпотент, коммутативный квазигруппа. Он имеет дополнительное свойство: ab = c подразумевает до н.э = а и ок = б.^[10] Наоборот, любая (конечная) квазигруппа с этими свойствами возникает из системы троек Штейнера. Коммутативные идемпотентные квазигруппы, удовлетворяющие этому дополнительному свойству, называются Квазигруппы Штейнера.^[11]

Характеристики

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

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

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

${displaystyle b = {frac {binom {n} {t}} {binom {k} {t}}} = {frac {n (n-1) cdots (n-t + 1)} {k (k-1) ) cdots (k-t + 1)}},}$

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

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

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

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

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

${displaystyle lambda _ {i} = left. {inom {n-i} {t-i}} ight / {inom {k-i} {t-i}} {ext {for}} i = 0,1, ldots, t,}$

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

История

Системы троек Штейнера были впервые определены Уэсли С. Б. Вулхаус в 1844 г. в вопросе о премии № 1733 «Дневника леди и джентльменов».^[13] Поставленная проблема была решена Томас Киркман  (1847 ). В 1850 году Киркман предложил вариант задачи, известный как Проблема школьницы Киркмана, который запрашивает тройные системы, обладающие дополнительным свойством (разрешимостью). Не зная о работе Киркмана, Якоб Штайнер  (1853 ) повторно представил тройные системы, и, поскольку эта работа была более широко известна, системы были названы в его честь.

Матье группы

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

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

Система Штейнера S (5, 6, 12)

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

Построение проекционной линии

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

Добавьте новый элемент, назовите его ∞, к 11 элементам конечное поле F₁₁ (то есть целые числа по модулю 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}},}$

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

Строительство котят

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

Строительство из К₆ факторизация графа

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

Система Штейнера S (5, 8, 24)

Система Штейнера S (5, 8, 24), также известная как Дизайн Витта или же Геометрия Витта, был впервые описан Кармайкл  (1931 ) и заново открыл Витт  (1938 ). Эта система связана со многими спорадические простые группы и с исключительный 24-мерный решетка известный как Решетка пиявки. Группа автоморфизмов S (5, 8, 24) - это Матьё группа М₂₄, и в этом контексте дизайн обозначается 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 000000000000000011111111 000000000000111100001111. . (следующие 4090 24-битных строк опущены). 111111111111000011110000 111111111111111100000000 111111111111111111111111

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

Строительство из Чудо-октадный генератор

В Чудо-октадный генератор (MOG) - это инструмент для генерации октад, например, содержащих указанные подмножества. Он состоит из массива 4x6 с определенными весами, присвоенными строкам. В частности, 8-подмножество должно подчиняться трем правилам, чтобы быть октадой S (5,8,24). Во-первых, в каждом из 6 столбцов должны быть одинаковые паритет, то есть все они должны иметь нечетное количество ячеек или все они должны иметь четное количество ячеек. Во-вторых, верхняя строка должна иметь ту же четность, что и каждый из столбцов. В-третьих, строки соответственно умножаются на веса 0, 1, 2 и 3 над конечное поле порядка 4, а суммы столбцов вычисляются для 6 столбцов с умножением и сложением с использованием арифметических определений конечных полей. Итоговые суммы столбцов должны формировать действительные шестнадцатеричное кодовое слово формы (а, б, c, а + б + c, 3а + 2b + c, 2а + 3b + c) куда а, б, в также из конечного поля порядка 4. Если четности сумм столбцов не соответствуют четности сумм строк, или друг другу, или если их не существует а, б, в таким образом, что суммы столбцов образуют допустимое шестнадцатеричное кодовое слово, тогда это подмножество 8 не является октадой S (5,8,24).

MOG основан на создании биекция (Conwell 1910, «Трехмерный PG (3,2) и его группа») между 35 способами разбить 8-набор на два разных 4-набора и 35 строками Фано 3-пространство PG (3,2). Он также геометрически связан (Куллинан, «Симметрия инвариантности в алмазном кольце», Уведомления AMS, стр. A193-194, февраль 1979 г.) с 35 различными способами разбиения массива 4x4 на 4 разные группы по 4 ячейки в каждой, например что если массив 4x4 представляет собой четырехмерный конечный аффинное пространство, то группы образуют набор параллельных подпространств.

Смотрите также

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

Примечания

Рекомендации

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

внешняя ссылка

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