 Площина Фано є системою трійок Штейнера 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 Задача Кіркмана про школярок», у якій питається про систему трійок з додатковою властивістю (розв'язність). Не знаючи про роботу Кіркмана, Якоб Штейнер визначив систему трійок, і його робота набула більшої популярності, так що система отримала його ім'я.

Групи Матьє
Деякі приклади систем Штейнера тісно пов'язані з теорією груп. Зокрема, , які називають групами Матьє, виникають як групи автоморфізмів систем Штейнер:

*  є групою автоморфізмів системи Штейнера 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). Її група автоморфізмів — група Матьє M12 і в цьому контексті група позначається як W12.

Побудови
Є різні шляхи побудови системи S(5,6,12).

Метод проєктивної прямої
Ця побудова належить Кармайклу (1937).

Додамо новий елемент, який позначимо як , до 11 елементів скінченного поля 11 (тобто лишків за модулем 11). Цю множину  із 12 елементів можна формально ототожнити з точками проєктивної прямої над 11. Назвемо таку підмножину розміру 6,

: 

«блоком». За допомогою цього блоку ми отримаємо інші блоки схеми (5,6,12) шляхом багаторазового застосування дробово-лінійного перетворення:

: 

де  містяться в 11, а  є ненульовим квадратом у 11. Якщо визначити  та , ця функція відображає множину  на себе. Геометричною мовою це проєкції проєктивної прямої. Вони утворюють групу за суперпозицією, і ця група є проєктивною спеціальною лінійною групою  (2,11) порядку 660. Існує рівно п'ять елементів у цій групі, які залишають початковий блок без змін, тому ми маємо 132 образи блоку. Як наслідок мультиплікативної транзитивності цієї групи, що діє на цю множину, будь-яка підмножина з п'яти елементів множини  з'явиться в цих 132 образах розміру 6.

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

Побудова розбиттям графа K6
Зв'язок між факторами повного графа K6 генерує схему S(5,6,12). Граф K6 має 6 різних 1-факторизацій (способів розбиття ребер на досконалі парування), а також 6 вершин. Множина вершин та множина факторизацій дають по блоку. Для кожної пари факторизацій існує рівно одне загальне досконале парування. Візьмемо множину вершин і замінимо дві вершини, що відповідають ребру загального досконалого парування міткою, що відповідає факторизаціям. Додамо результат у множину блоків. Повторимо процес для двох ребер загального досконалого парування. Просто візьмемо множину факторизацій і замінимо мітки, що відповідають двом факторизаціям, кінцевими точками ребра в загальному досконалому паруванні. Повторюємо це для інших двох ребер парування. Існує 3+3 = 6 блоків для кожної пари факторизацій, і є  пар серед 6 факторизацій, що дає 90 нових блоків. Нарешті, беремо множину  комбінацій 6 об'єктів з 12 і відкидаємо будь-які комбінації, які мають 5 або більше спільних об'єктів з будь-якими з 92 блоків. Залишається рівно 40 блоків, що дає 2+90+40 = 132 блоків схеми S(5,6,12).

Система Штейнера S(5, 8, 24)
Систему Штейнера S(5, 8, 24), відому також як схема Вітта або геометрія Вітта, описав Роберт Кармайкл і перевідкрив Вітт. Ця система пов'язана з багатьма спорадичними групами і з  24-вимірною ґраткою, відомою як ґратка Ліча.

Група автоморфізмів схеми S(5, 8, 24) є  і в контексті схем позначається 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) задаються одиничними бітами слів із вісьмома одиницями.

Див. також
* 
* Задача Кіркмана про школярок
* Конфігурація Сильвестра — Галлаї

Коментарі


Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 


Посилання
* 
* 
*  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



