Русская Википедия:Система Штейнера

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Система Штейнера (названа именем Якоба Штейнера) — вариант блок-схем, точнее, t-схемы с λ = 1 и 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Шаблон:Sfn. Утвердительный ответ дал Питер Киваш в 2014Шаблон:SfnШаблон:SfnШаблон:Sfn.

Примеры

Конечные проективные плоскости

Конечная проективная плоскость порядка Шаблон:Math с прямыми в качестве блоков является схемой Шаблон:Math, поскольку она имеет Шаблон:Math точек, каждая прямая проходит через Шаблон:Math точек, а каждая пара различных точек находится ровно на одной прямой.

Конечные аффинные плоскости

Конечная Шаблон:Не переведено 5 порядка Шаблон:Math с прямыми в качестве блоков является схемой Шаблон:Math. Аффинная плоскость порядка Шаблон:Math может быть получена из проективной плоскости того же порядка получается путём удаления одного блока и всех точек этого блока из проективной плоскости. Если выбрать другие блоки для удаления, можно получить неизоморфные аффинные плоскости.

Классические системы Штейнера

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

Схема S(2,3,n) называется системой троек Штейнера, а его блоки называются тройками. Часто для систем троек Штейнера используется обозначение STS(n). Число троек, проходящих через точку, равно (n-1)/2, а потому общее число троек равно n(n−1)/6. Это показывает, что n должно иметь вид 6k+1 или 6k + 3 для некоторого k. Факт, что это условие для n достаточно для существования S(2,3,n), доказали Шаблон:Не переведено 5Шаблон:Sfn и Т. СколемШаблон:Sfn. Проективная плоскость порядка 2 (плоскость Фано) — это STS(7), а Шаблон:Не переведено 5 порядка 3 — это STS(9).

С точностью до изоморфизма STS(7) и STS(9) единственны. Существует две схемы STS(13), 80 схем STS(15) и Шаблон:Число схем STS(19)Шаблон:Sfn.

Мы можем определить умножение на множестве S используя систему троек Штейнера, если положим aa = a для всех a из S и ab = c, если {a,b,c} — тройка Штейнера. Это делает S идемпотентной коммутативной квазигруппой. Квазигруппа имеет дополнительное свойство, что из ab = c следует bc = a и ca = b[комм. 1]. В обратную сторону, любая (конечная) квазигруппа с такими свойствами получается из системы троек Штейнера. Коммутативные идемпотентные квазигруппы, которые удовлетворяют этому дополнительному свойству, называются квазигруппами ШтейнераШаблон:Sfn.

Система четвёрок Штейнера

Схема S(3,4,n) называется системой четвёрок Штейнера. Необходимое и достаточное условие существования S(3,4,n) — n <math>\equiv</math> 2 или 4 (mod 6). Для этих систем часто используется обозначение SQS(n).

С точностью до изоморфизма SQS(8) и SQS(10) единственны, имеется 4 схемы SQS(14) и 1.054.163 схем SQS(16)Шаблон:Sfn.

Системы пятёрок Штейнера

Схема S(4,5,n) называется системой пятёрок Штейнера. Необходимое условие существования такой системы — n <math>\equiv</math> 3 или 5 (mod 6), что получается из соглашений, которые применимы ко всем классическим системам Штейнера. Дополнительное условие для общих систем, что n <math>\not\equiv</math> 4 (mod 5), получается из факта, что число блоков должно быть целым. Достаточные условия неизвестны.

Существует единственная система пятёрок Штейнера порядка 11, но нет систем порядка 15 или 17Шаблон:Sfn. Известны системы с порядками 23, 35, 47, 71, 83, 107, 131, 167 и 243. Наименьший порядок, для которого существование неизвестно (на 2011 год) — 21.

Свойства

Из определения Шаблон:Math ясно, что <math>1 < t < k < n</math>. (Равенства, хотя технически возможны, приводят к тривиальным системам.)

Если система Шаблон:Math существует, выбор блоков, содержащих определённый элемент и удаление этого элемента, даёт производную систему Шаблон:Math. Таким образом, существование Шаблон:Math является необходимым условием существования схемы Шаблон:Math.

Число Шаблон:Math-элементных подмножеств в Шаблон:Math равно <math>\tbinom n t</math>, в то время как число Шаблон:Math-элементных подмножеств в каждом блоке равно <math>\tbinom k t</math>. Поскольку любое Шаблон:Math-элементное подмножество содержится ровно в одном блоке, мы получаем <math>\tbinom n t = b\tbinom k t</math>, или

<math>b = \frac{\tbinom nt}{\tbinom kt} = \frac{n(n-1)\cdots(n-t+1)}{k(k-1)\cdots(k-t+1)},</math>

где Шаблон:Math — число блоков. Аналогичные рассуждения о Шаблон:Math-элементных подмножествах, содержащих конкретный элемент, даёт нам <math>\tbinom{n-1}{t-1}=r\tbinom{k-1}{t-1}</math>, или

<math>r=\frac{\tbinom{n-1}{t-1}}{\tbinom{k-1}{t-1}}</math> =<math>\frac{(n-t+1)\cdots(n-2)(n-1)}{(k-t+1)\cdots(k-2)(k-1)},</math>

где Шаблон:Math — число блоков, содержащих выбранный элемент. Из этих определений следует равенство <math>bk=rn</math>. Необходимым условием для существования схемы Шаблон:Math является целочисленность Шаблон:Math и Шаблон:Math. Как и для любой блок-схемы, неравенство Фишера <math>b\ge n</math> верно для систем Штейнера.

Если заданы параметры системы Штейнера Шаблон:Math и подмножество размера <math>t' \leq t</math>, содержащееся по меньшей мере в одном блоке, можно посчитать число блоков, пересекающих это подмножество с фиксированным числом элементов путём построения треугольника ПаскаляШаблон:Sfn. В частности, число блоков, пересекающих фиксированный блок с любым числом элементов, не зависит от выбора блока.

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

<math> \lambda_i = \left.\binom{n-i}{t-i} \right/ \binom{k-i}{t-i}</math> для <math>i = 0,1,\ldots,t, </math>

Можно показать, что если существует система Штейнера Шаблон:Math, где Шаблон:Math степень простого числа, большая 1, тогда Шаблон:Math <math>\equiv</math> 1 или Шаблон:Math. В частности, система троек Штейнера Шаблон:Math должна иметь Шаблон:Math или Шаблон:Math. Как мы уже упоминали, это является единственным ограничением систем троек Штейнера, то есть для каждого натурального числа Шаблон:Math системы Шаблон:Math и Шаблон:Math существуют.

История

Системы троек Штейнера первым определил Шаблон:Не переведено 5 в 1844 в премиальном вопросе #1733 в журнале Шаблон:Не переведено 5Шаблон:Sfn. Поставленную задачу решил Томас КиркманШаблон:Sfn. В 1850 Киркман поставил вариант задачи, получивший название «задача Киркмана о школьницах», в которой спрашивается о системе троек с дополнительным свойством (разрешимость). Не зная работы Киркмана, Якоб ШтейнерШаблон:Sfn определил систему троек, и его работа получила бо́льшую известность, так что система получила его имя.

Группы Матьё

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

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

Существует единственная система Штейнера S(5,6,12). Её группа автоморфизмов — группа Матьё M12, и в этом контексте группа обозначается как W12.

Построения

Имеются различные пути построения системы S(5,6,12).

Метод проективной прямой

Это построение принадлежит Кармайклу (1937)Шаблон:Sfn.

Добавим новый элемент, который обозначим как Шаблон:Mvar, к 11 элементам конечного поля Шаблон:Mvar11 (то есть вычетам по модулю 11). Это множество Шаблон:Mvar из 12 элементов можно формально отождествить с точками проективной прямой над Шаблон:Mvar11. Назовём следующее подмножество размера 6,

<math>\{\infty,1,3,4,5,9\}, </math>

«блоком». С помощью этого блока мы получим другие блоки схемы Шаблон:Mvar(5,6,12) путём многократного применения дробно-линейного преобразования:

<math>z' = f(z) = \frac{az + b}{cz + d},</math>

где Шаблон:Mvar содержатся в Шаблон:Mvar11, а Шаблон:Math является ненулевым квадратом в Шаблон:Mvar11. Если определить Шаблон:Math и Шаблон:Math, эта функция отображает множество Шаблон:Mvar на себя. На геометрическом языке это проекции проективной прямой. Они образуют группу по суперпозиции, и эта группа является проективной специальной линейной группой Шаблон:Mvar(2,11) порядка 660. Существует ровно пять элементов в этой группе, оставляющих начальный блок без измененийШаблон:Sfn, так что мы имеем 132 образа блока. Как следствие мультипликативной транзитивности этой группы, действующей на это множество, любое подмножество из пяти элементов множества Шаблон:Mvar появится ровно в этих 132 образах размера шесть.

Метод Куртиса

Альтернативное построение схемы W12 получается применением метода Р. Т. КуртисаШаблон:Sfn, который предназначен для «ручного вычисления» блоков одного за другим. Метод Куртиса основывается на заполнении 3x3 таблиц чисел, которые представляют аффинную геометрию на векторном пространстве F3xF3, систему S(2,3,9).

Построение путём разбиения графа K6

Связь между факторами полного графа K6 генерирует схему S(5,6,12)[1]. Граф K6 имеет 6 различных 1-факторизаций (путей разбиения рёбер на совершенные паросочетания), а также 6 вершин. Множество вершин и множество факторизаций дают по блоку. Для каждой пары факторизаций существует ровно одно общее совершенное паросочетание. Возьмём множество вершин и заменим две вершины, соответствующие ребру общего совершенного паросочетания меткой, соответствующей факторизациям. Добавим результат в множество блоков. Повторим процесс для оставшихся двух рёбер общего совершенного паросочетания. Просто возьмём множество факторизаций и заменим метки, соответствующие двум факторизациям, конечными точками ребра в общем совершенном паросочетании. Повторяем это для других двух рёбер паросочетания. Существуют 3+3 = 6 блоков для каждой пары факторизаций, и имеется 6C2 = 15 пар среди 6 факторизаций, что даёт 90 новых блоков. Наконец, берём полное множество 12C6 = 924 комбинаций 6 объектов из 12 и отбрасываем любые комбинации, которые имеют 5 или более общих объектов с любыми из 92 блоков. Остаётся ровно 40 блоков, что даёт 2+90+40 = 132 блоков схемы S(5,6,12).

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

Система Штейнера S(5, 8, 24), известная также как схема Витта или геометрия Витта, была описана Робертом КармайкломШаблон:Sfn и переоткрыта ВиттомШаблон:Sfn. Эта система связана с многими спорадическими группами и с Шаблон:Не переведено 5 24-мерной решёткой, известной как решётка Лича.

Группа автоморфизмов схемы S(5, 8, 24) является Шаблон:Не переведено 5 и в контексте схем обозначается W24 («W» от «Witt»)

Построения

Существует много путей построения S(5,8,24). Здесь описано два метода:

Метод, основанный на комбинировании 24 элементов в группы по 8

Все 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 раз. Каждая пятёрка встречается один раз. Не любая шестёрка семёрка или восьмёрка встречается.

Метод, основанный на 24-битных бинарных строках

Все 24-битные бинарные строки генерируются в лексикографическом порядке, и любая такая строка, отличающаяся от ранее найденной меньше чем в 8 позициях, отбрасывается. В результате получаем: 

    000000000000000000000000
    000000000000000011111111
    000000000000111100001111
    000000000000111111110000
    000000000011001100110011
    000000000011001111001100
    000000000011110000111100
    000000000011110011000011
    000000000101010101010101
    000000000101010110101010
    .
    . (следующие 4083 24-битных строк опущены)
    .
    111111111111000011110000
    111111111111111100000000
    111111111111111111111111

Список содержит 4096 элементов, которые являются кодовыми словами расширенного двоичного кода Голея. Они образуют группу по операции XOR. Одно из слов состоит из нулевых бит, 759 слов имеют по восемь единичных бит, 2576 слов имеют по двенадцать единичных бит, 759 слов имеют шестнадцать единичных бит и одно слово полностью состоит из единичных бит. 759 8-элементных блоков схемы S(5,8,24) задаются единичными битами слов с восемью единицами.

См. также

Комментарии

Шаблон:Примечания

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное


Ошибка цитирования Для существующих тегов <ref> группы «комм.» не найдено соответствующего тега <references group="комм."/>

  1. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Система_Штейнера&oldid=10802457