Jump to content

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

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Это свойство эквивалентно утверждению, что (xy)y = x для всех x и y в идемпотентной коммутативной квазигруппе.
  1. ^ «Энциклопедия теории дизайна: t-дизайн» . Designtheory.org. 04.10.2004 . Проверено 17 августа 2012 г.
  2. ^ Киваш, Питер (2014). «Существование конструкций». arXiv : 1401.3665 [ math.CO ].
  3. ^ Эрика Клейррах (9 июня 2015 г.). «Дилемма дизайна решена, без дизайна» . Журнал Кванта . Проверено 27 июня 2015 г.
  4. ^ Калай, Гил. «Дизайн существует!» (PDF) . Семинар Бурбаки.
  5. ^ Колборн и Диниц, 2007 , стр.106.
  6. ^ Остергард и Поттонен, 2008 г.
  7. ^ Бозе, RC (1939). «О построении уравновешенных неполных блочных конструкций» . Анналы евгеники . 9 (4): 353–399. дои : 10.1111/j.1469-1809.1939.tb02219.x .
  8. ^ Т. Сколем. Некоторые замечания о системах троек Штейнера. Математика. Скан. 6 (1958), 273–280.
  9. ^ Колборн и Диниц 2007 , стр.60
  10. ^ Колборн и Диниц 2007 , стр. 497, определение 28.12
  11. ^ Деннистон, RHF (сентябрь 1974 г.). «Газета Деннистона, открытый доступ» . Дискретная математика . 9 (3): 229–233. дои : 10.1016/0012-365X(74)90004-1 .
  12. ^ Ассмус и Ки 1992 , с. 8.
  13. ^ Линднер и Роджер 1997 , стр.3
  14. ^ Бейкер, HF (13 ноября 1943 г.). «Некролог. Доктор Г.Т. Беннетт, ФРС». Природа . 152 (3863): 558–559. дои : 10.1038/152558a0 .
  15. ^ Беннетт, GT (1911). «Двойная шестерка» (PDF) . Труды Лондонского математического общества . 2 (1): 336–351.
  16. ^ Беннетт, GT (1912). «Система линий кубической поверхности» (PDF) . Труды Лондонского математического общества . 2 (1): 479–484.
  17. ^ Кармайкл 1956 , с. 431
  18. ^ Бет, Юнгникель и Ленц 1986 , стр. 196
  19. ^ Кертис 1984
  20. ^ «Учебник ЕАГТС» .
  21. ^ Кармайкл 1931 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 15d3f09e56820f02a1e63e62cf41795d__1721895000
URL1:https://arc.ask3.ru/arc/aa/15/5d/15d3f09e56820f02a1e63e62cf41795d.html
Заголовок, (Title) документа по адресу, URL1:
Steiner system - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)