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

Площина Фано є системою трійок Штейнера 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 точок, а кожна пара різних точок лежить рівно на одній прямій.

Скінченні афінні площини

Скінченна Шаблон:Не перекладено порядку Шаблон: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), довели Шаблон:Не перекладеноШаблон:Sfn і Т. СколемШаблон:Sfn. Проєктивна площина порядку 2 (площина Фано) — це STS(7), а Шаблон:Не перекладено порядку 3 — це STS(9).

З точністю до ізоморфізму STS(7) та STS(9) єдині. Існує дві схеми STS(13), 80 схем STS(15) та Шаблон:Num схем STS(19)Шаблон:Sfn.

Можна визначити множення на множині S, використовуючи систему трійок Штейнера, якщо покласти aa = a для всіх a з S і ab = c, якщо {a,b,c} — трійка Штейнера. Це робить S ідемпотентною комутативною квазігрупою. Квазігрупа має додаткову властивість, що з ab = c випливає bc = a та ca = b. І навпаки, будь-яка (скінченна) квазігрупа з такими властивостями отримується із системи трійок Штейнера. Комутативні ідемпотентні квазігрупи, які задовольняють цій додатковій властивості, називають квазігрупами ШтейнераШаблон:Sfn.

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

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

З точністю до ізоморфізму SQS(8) і SQS(10) єдині, є 4 схеми SQS(14) та Шаблон:Число схем SQS(16) Шаблон:Sfn .

Системи п'ятірок Штейнера

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

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

Властивості

З визначення Шаблон:Math ясно, що $1<t<k<n$. (Рівності, хоча й технічно можливі, призводять до тривіальних систем.)

Якщо система Шаблон:Math існує, вибір блоків, що містять певний елемент та видалення цього елемента, дає похідну систему Шаблон:Math. Отже, існування Шаблон:Math є необхідною умовою існування схеми Шаблон:Math.

ЧислоШаблон:Math Шаблон:Math-елементних підмножин у Шаблон:Math дорівнює $(\genfrac{}{}{0ex}{}{n}{t})$, тоді як число Шаблон:Math-елементних підмножин у кожному з блоків дорівнює $(\genfrac{}{}{0ex}{}{k}{t})$. Оскільки будь-яка Шаблон:Math-елементна підмножина міститься рівно в одному блоці, отримуємо $(\genfrac{}{}{0ex}{}{n}{t})=b(\genfrac{}{}{0ex}{}{k}{t})$, або

$b=\frac{(\genfrac{}{}{0ex}{}{n}{t})}{(\genfrac{}{}{0ex}{}{k}{t})}=\frac{n(n-1)\cdots (n-t+1)}{k(k-1)\cdots (k-t+1)},$

де Шаблон:Math — число блоків. Аналогічні міркування про Шаблон:Math-елементні підмножини, що містять конкретний елемент, дають нам $(\genfrac{}{}{0ex}{}{n-1}{t-1})=r(\genfrac{}{}{0ex}{}{k-1}{t-1})$, або

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

де Шаблон:Math — число блоків, що містять вибраний елемент. Із цих визначень випливає рівність $bk=rn$. Необхідною умовою існування схеми Шаблон:Math є цілочисельність Шаблон:Math і Шаблон:Math. Як і для будь-якої блок-схеми, для систем Штейнера виконується нерівність Фішера $b\ge n$.

Якщо дано параметри системи Штейнера Шаблон:Math і підмножину розміру $t^{\prime }\le t$, що міститься принаймні в одному блоці, можна порахувати число блоків, що перетинають цю підмножину з фіксованим числом елементів, побудувавши трикутник ПаскаляШаблон:Sfn. Зокрема, кількість блоків, що перетинають фіксований блок із будь-яким числом елементів, не залежить від вибору блоку.

Число блоків, що містять будь-яку i-елементну множину точок, дорівнює:

${\lambda }_i=(\genfrac{}{}{0ex}{}{n-i}{t-i})/(\genfrac{}{}{0ex}{}{k-i}{t-i})$ для $i=0,1,\dots ,t,$

Можна показати, що якщо існує система Штейнера Шаблон:Math, де Шаблон:Math — степінь простого числа, більший від 1, тоді Шаблон:Math $\equiv$ 1 або Шаблон:Math. Зокрема, система трійок Штейнера Шаблон:Math повинна мати Шаблон:Math або Шаблон:Math. Як ми вже згадували, це єдине обмеження систем трійок Штейнера, тобто для кожного натурального числа Шаблон:Math системи Шаблон:Math та Шаблон:Math існують.

Історія

Системи трійок Штейнера першим визначив Шаблон:Не перекладено 1844 року в призовому питанні #1733 в журналі Шаблон:Не перекладеноШаблон:Sfn. Поставлену задачу розв'язав Томас КіркманШаблон:Sfn. У 1850 Кіркман поставив варіант задачі, який отримав назву «Задача Кіркмана про школярок», у якій питається про систему трійок з додатковою властивістю (розв'язність). Не знаючи про роботу Кіркмана, Якоб ШтейнерШаблон:Sfn визначив систему трійок, і його робота набула більшої популярності, так що система отримала його ім'я.

Групи Матьє

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

• Шаблон:Не перекладено є групою автоморфізмів системи Штейнера 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). Її група автоморфізмів — група Матьє M₁₂ і в цьому контексті група позначається як W₁₂.

Побудови

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

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

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

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

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

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

$z^{\prime }=f(z)=\frac{az+b}{cz+d},$

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

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

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

Побудова розбиттям графа K₆

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

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

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

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

Див. також

• Шаблон:Не перекладено
• Задача Кіркмана про школярок
• Конфігурація Сильвестра — Галлаї

Література

• Шаблон:Cite web
• Шаблон:СтаттяШаблон:Недоступне посилання
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон:MathWorld
• Шаблон:Springer
• 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