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

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

В комбинаторной математике система Штейнера (названная в честь Якоба Штайнера ) — это тип блочной схемы , а именно 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. Оба существования были доказаны Питером Кивашем в 2014 году. Его доказательство неконструктивно , и по состоянию на 2019 год не известно ни одной реальной системы Штейнера для больших значений t .

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

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

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

S(3,4, n ) называется системой четверок Штейнера . Необходимым и достаточным условием существования S(3,4, n ) является то, что n $\equiv$ 2 или 4 (мод 6). аббревиатура SQS( n Для этих систем часто используется ). С точностью до изоморфизма SQS(8) и SQS(10) уникальны, имеется 4 SQS(14) и 1 054 163 SQS(16).

S(4,5, n ) называется пятерной системой Штейнера . Необходимым условием существования такой системы является то, что n $\equiv$ 3 или 5 (mod 6), что исходит из соображений, применимых ко всем классическим системам Штейнера. Дополнительное необходимое условие состоит в том, что n $\not \equiv$ 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 . И наоборот, любая (конечная) квазигруппа с этими свойствами возникает из системы троек Штейнера. Коммутативные идемпотентные квазигруппы, удовлетворяющие этому дополнительному свойству, называются квазигруппами Штейнера .

системы

Тройки некоторых систем 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 году. который построил первую неделю следующим образом:

Day 1 ABJ CEM FKL HIN DGO
Day 2 ACH DEI FGM JLN BKO
Day 3 ADL BHM GIK CFN EJO
Day 4 AEG BIL CJK DMN FHO
Day 5 AFI BCD GHJ EKN LMO
Day 6 AKM DFJ EHL BGN CIO
Day 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 ) что $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 равно ${\tbinom {n}{t}}$, а количество подмножеств t -элементов в каждом блоке равно ${\tbinom {k}{t}}$. Поскольку каждое подмножество t -элементов содержится ровно в одном блоке, мы имеем ${\tbinom {n}{t}}=b{\tbinom {k}{t}}$, или

$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 -элементов, содержащих конкретный элемент, дают нам ${\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}$, или

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

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

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

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

$\lambda _{i}=\left.{\binom {n-i}{t-i}}\right/{\binom {k-i}{t-i}}{\text{ for }}i=0,1,\ldots ,t,$

Можно показать, что если существует система Штейнера S(2, k , n ) , где k — степень простого числа, большая 1, то n $\equiv$ 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 журнала «Дневник леди и джентльменов». Поставленную задачу решил Томас Киркман ( 1847 ). В 1850 году Киркман сформулировал вариант проблемы, известной как проблема школьницы Киркмана , которая требует наличия тройных систем, обладающих дополнительным свойством (разрешимостью). Не зная о работе Киркмана, Якоб Штайнер ( 1853 ) вновь ввел тройные системы, и, поскольку эта работа получила более широкую известность, системы были названы в его честь.

Группы Матье

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

• Группа Матье 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)

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

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

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

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

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

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

$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. В этой группе ровно пять элементов, которые оставляют стартовый блок фиксированным по заданному принципу: а именно такие, что b=c=0 и ad =1, так что f(z) = a ² з . Таким образом, изображений этого блока будет 660/5 = 132. В результате свойства кратной транзитивности этой группы, действующего на это множество, любое подмножество из пяти элементов S появится ровно в одном из этих 132 изображений размера шесть.

Строительство котенка

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

из ₆ графа

Отношения между факторами графа полного графа K ₆ порождают S(5,6,12). AK ₆ Граф имеет 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 новых блоков. Наконец, возьмите полный набор ${\tbinom {12}{6}}=924$ комбинации из 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 ₂₄ , и в этом контексте конструкция обозначается W ₂₄ («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).

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

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

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

$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 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 представляет собой четырехмерное конечное аффинное пространство , то группы образуют набор параллельных подпространств.

См. также

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

Ссылки

• Ассмус, 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 ₁₂ и «котенок» », в книге Аткинсона, Майкла Д. (ред.), Вычислительная теория групп (Дарем, 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) Программное обеспечение и листинг Йохана Э. Мебиуса