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

Система Штейнера (названа именем Якоба Штейнера) — вариант блок-схем, точнее, 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^[1]. Утвердительный ответ дал Питер Киваш в 2014^[2]^[3]^[4].

Примеры

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

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

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

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

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

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

Схема 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] и Т. Сколем^[6]. Проективная плоскость порядка 2 (плоскость Фано) — это STS(7), а аффинная плоскость^[англ.] порядка 3 — это STS(9).

С точностью до изоморфизма STS(7) и STS(9) единственны. Существует две схемы STS(13), 80 схем STS(15) и 11 084 874 829 схем STS(19)^[7].

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

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

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

С точностью до изоморфизма SQS(8) и SQS(10) единственны, имеется 4 схемы SQS(14) и 1.054.163 схем SQS(16)^[9].

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

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

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

Свойства

Из определения 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$ , содержащееся по меньшей мере в одном блоке, можно посчитать число блоков, пересекающих это подмножество с фиксированным числом элементов путём построения треугольника Паскаля^[11]. В частности, число блоков, пересекающих фиксированный блок с любым числом элементов, не зависит от выбора блока.

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

\lambda _{i}=\left.{\binom {n-i}{t-i}}\right/{\binom {k-i}{t-i}}

для

i=0,1,\ldots ,t,

Можно показать, что если существует система Штейнера S(2, k, n), где k степень простого числа, большая 1, тогда n $\equiv$ 1 или k (mod k(k−1)). В частности, система троек Штейнера S(2, 3, n) должна иметь n = 6m + 1 или 6m + 3. Как мы уже упоминали, это является единственным ограничением систем троек Штейнера, то есть для каждого натурального числа m системы S(2, 3, 6m + 1) и S(2, 3, 6m + 3) существуют.

История

Системы троек Штейнера первым определил В.С.Б. Вулхауз^[англ.] в 1844 в премиальном вопросе #1733 в журнале Lady's and Gentlemen's Diary^[англ.]^[12]. Поставленную задачу решил Томас Киркман^[13]. В 1850 Киркман поставил вариант задачи, получивший название «задача Киркмана о школьницах», в которой спрашивается о системе троек с дополнительным свойством (разрешимость). Не зная работы Киркмана, Якоб Штейнер^[14] определил систему троек, и его работа получила бо́льшую известность, так что система получила его имя.

Группы Матьё

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

Группа Матьё 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₁₂.

Построения

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

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

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

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

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

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

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

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

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

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

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

Связь между факторами полного графа K₆ генерирует схему S(5,6,12)^[18]. Граф K₆ имеет 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), известная также как схема Витта или геометрия Витта, была описана Робертом Кармайклом^[19] и переоткрыта Виттом^[20]. Эта система связана с многими спорадическими группами и с исключительной^[англ.] 24-мерной решёткой, известной как решётка Лича.

Группа автоморфизмов схемы S(5, 8, 24) является группой Матьё M₂₄^[англ.] и в контексте схем обозначается W₂₄ («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) задаются единичными битами слов с восемью единицами.

См. также

Примечания

↑ Encyclopaedia.
↑ Keevash, 2014.
↑ Quanta Magazine.
↑ Kalai.
↑ Bose, 1939, с. 353–399.
↑ Skolem, 1958, с. 273–280.
↑ Colbourn, Dinitz, 2007, с. 60.
↑ Colbourn, Dinitz, 2007, с. 497, definition 28.12.
↑ Colbourn, Dinitz, 2007, с. 106.
↑ Östergard, Pottonen, 2008.
↑ Assmus, Key, 1992, с. 8.
↑ Lindner, Rodger, 1997, с. 3.
↑ Kirkman, 1847.
↑ Steiner, 1853.
↑ Carmichael, 1956, с. 431.
↑ Beth, Jungnickel, Lenz, 1986, с. 196.
↑ Curtis, 1984.
↑ EAGTS textbook (неопр.). Дата обращения: 5 июля 2017. Архивировано 10 декабря 2017 года.
↑ Carmichael, 1931.
↑ Witt, 1938.

Литература

Encyclopaedia of Design Theory: t-Designs (неопр.). Designtheory.org (4 октября 2004). Дата обращения: 17 августа 2012.
R. C. Bose. On the construction of balanced incomplete block designs // Ann. Eugenics 9. — 1939. — С. 353–399. (недоступная ссылка)
Peter Keevash. The existence of designs. — 2014.
T. Skolem. Some remarks on the triple systems of Steiner // Math. Scand. 6. — 1958. — С. 273–280.
A Design Dilemma Solved, Minus Designs (неопр.). Quanta Magazine (9 июня 2015). Дата обращения: 27 июня 2015.
Gil Kalai. Designs exist! (неопр.) http://www.bourbaki.ens.fr. S´eminaire BOURBAKI.
E.F. Assmus, J.D. Key. Designs and Their Codes. — Cambridge: Cambridge University Press, 1992. — ISBN 0-521-41361-3.
Thomas Beth, Dieter Jungnickel, Hanfried Lenz. Design Theory. — Cambridge: Cambridge University Press, 1986. — ISBN 978-0-521-44432-3.
Robert Carmichael. Tactical Configurations of Rank Two // American Journal of Mathematics. — 1931. — Т. 53. — С. 217–240. — doi:10.2307/2370885. — JSTOR 10.2307/2370885.
Robert Carmichael. Introduction to the theory of Groups of Finite Order. — Dover, 1956. — ISBN 0-486-60300-8.
Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton: Chapman & Hall/ CRC, 2007. — ISBN 1-58488-506-8.
R.T. Curtis. The Steiner system S(5,6,12), the Mathieu group M₁₂ and the "kitten" // Computational group theory (Durham, 1982). — London: Academic Press, 1984. — С. 353–358. — ISBN 0-12-066270-1.
D.R. Hughes, E.C. Piper. Design theory. — Cambridge: Cambridge University Press, 1985. — С. 173–176. — ISBN 0-521-25754-9.
Thomas P. Kirkman. On a Problem in Combinations // The Cambridge and Dublin Mathematical Journal. — Macmillan, Barclay, and Macmillan, 1847. — Т. II. — С. 191–204.
C.C. Lindner, C.A. Rodger. Design Theory. — Boca Raton: CRC Press, 1997. — ISBN 0-8493-3986-3.
Patric R.J. Östergard, Olli Pottonen. There exists no Steiner system S(4,5,17) // Journal of Combinatorial Theory Series A. — 2008. — Т. 115, вып. 8. — С. 1570–1573. — doi:10.1016/j.jcta.2008.04.005.
J. Steiner. Combinatorische Aufgabe // Journal für die Reine und Angewandte Mathematik. — 1853. — Т. 45. — С. 181–182.
Ernst Witt. Die 5-Fach transitiven Gruppen von Mathieu // Abh. Math. Sem. Univ. Hamburg. — 1938. — Т. 12. — С. 256–264. — doi:10.1007/BF02948947.

Ссылки

Rowland, Todd and Weisstein, Eric W. Steiner System (англ.) на сайте Wolfram MathWorld.
Rumov, B.T. (2001), "Steiner system", in Hazewinkel, Michiel (ed.), Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Steiner systems by Andries E. Brouwer
Implementation of S(5,8,24) by Dr. Alberto Delgado, Gabe Hart, and Michael Kolkebeck
S(5, 8, 24) Software and Listing by Johan E. Mebius
The Witt Design computed by Ashay Dharwadker

[8] Это свойство эквивалентно (xy)y = x для всех x и y в идемпотентной коммутативной квазигруппе.

[_a7ba0fba5286d41a-1] Encyclopaedia.

[_b843c29ce34781e3-2] Keevash, 2014.

[_77f0bd34b821e147-3] Quanta Magazine.

[_4852aa921015c24d-4] Kalai.

[_d3f424824a6f0835-5] Bose, 1939, с. 353–399.

[_7d72c76d035b1414-6] Skolem, 1958, с. 273–280.

[_796d3792115915a2-7] Colbourn, Dinitz, 2007, с. 60.

[_b19539b17f6a8672-9] Colbourn, Dinitz, 2007, с. 497, definition 28.12.

[_ad9a11337a51524f-10] Colbourn, Dinitz, 2007, с. 106.

[_44212b0545d00c9f-11] Östergard, Pottonen, 2008.

[_18aa465f1ea953a9-12] Assmus, Key, 1992, с. 8.

[_1f562ad9025dc495-13] Lindner, Rodger, 1997, с. 3.

[_b082edb2f3e1dd76-14] Kirkman, 1847.

[_39a9bbb0553d3446-15] Steiner, 1853.

[_da45fee1f35530e7-16] Carmichael, 1956, с. 431.

[_0e8a956122d24a25-17] Beth, Jungnickel, Lenz, 1986, с. 196.

[_0e3711b0c01734d5-18] Curtis, 1984.

[19] EAGTS textbook (неопр.). Дата обращения: 5 июля 2017. Архивировано 10 декабря 2017 года.

[_dde4a55fd74c6310-20] Carmichael, 1931.

[_f643086ca52089a2-21] Witt, 1938.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[комм. 1]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

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

Содержание

Примеры

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

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

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

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

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

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

Свойства

История

Группы Матьё

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

Построения

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

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

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

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

Построения

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

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

См. также

Комментарии

Примечания

Литература

Ссылки

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

Примеры

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

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

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

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

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

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

Свойства

История

Группы Матьё

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

Построения

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

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

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

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

Построения

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

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

См. также

Комментарии

Примечания

Литература

Ссылки

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