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

Система Штейнера (названа ім'ям Якоба Штейнера) — варіант блок-схем, точніше, (t-схеми) з λ = 1 і t ≥ 2.

Площина Фано є системою трійок Штейнера S (2,3,7). Блоками є 7 прямих, кожна з яких містить 3 точки. Будь-яка пара точок належить єдиній прямій.

Система Штейнера з параметрами 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. Ствердну відповідь дав ^[ru] 2014 року.

Приклади

Скінченні проєктивні площини

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

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

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

З точністю до ізоморфізму STS(7) та STS(9) єдині. Існує дві схеми STS(13), 80 схем STS(15) та 11 084 874 829 схем STS(19).

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

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

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

З точністю до ізоморфізму SQS(8) і SQS(10) єдині, є 4 схеми SQS(14) та 1 054 163 схем SQS(16) .

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

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

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

Властивості

З визначення S(t, k, n) ясно, що ${\displaystyle 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 t-елементних підмножин у S дорівнює ${\displaystyle {\tbinom {n}{t}}}$, тоді як число t-елементних підмножин у кожному з блоків дорівнює ${\displaystyle {\tbinom {k}{t}}}$. Оскільки будь-яка t-елементна підмножина міститься рівно в одному блоці, отримуємо ${\displaystyle {\tbinom {n}{t}}=b{\tbinom {k}{t}}}$, або

${\displaystyle 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-елементні підмножини, що містять конкретний елемент, дають нам ${\displaystyle {\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}}$, або

${\displaystyle r={\frac {\tbinom {n-1}{t-1}}{\tbinom {k-1}{t-1}}}}$ = ${\displaystyle {\frac {(n-t+1)\cdots (n-2)(n-1)}{(k-t+1)\cdots (k-2)(k-1)}},}$

де r — число блоків, що містять вибраний елемент. Із цих визначень випливає рівність ${\displaystyle bk=rn}$. Необхідною умовою існування схеми S(t, k, n) є цілочисельність b і r. Як і для будь-якої блок-схеми, для систем Штейнера виконується нерівність Фішера ${\displaystyle b\geq n}$.

Якщо дано параметри системи Штейнера S(t, k, n) і підмножину розміру ${\displaystyle t'\leq t}$, що міститься принаймні в одному блоці, можна порахувати число блоків, що перетинають цю підмножину з фіксованим числом елементів, побудувавши трикутник Паскаля. Зокрема, кількість блоків, що перетинають фіксований блок із будь-яким числом елементів, не залежить від вибору блоку.

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

${\displaystyle \lambda _{i}=\left.{\binom {n-i}{t-i}}\right/{\binom {k-i}{t-i}}}$ для ${\displaystyle i=0,1,\ldots ,t,}$

Можна показати, що якщо існує система Штейнера S(2, k, n), де k — степінь простого числа, більший від 1, тоді n ${\displaystyle \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) існують.

Історія

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

Групи Матьє

Докладніше: Група Матьє

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

• ^[en] є групою автоморфізмів системи Штейнера S(4,5,11)
• ^[en] є групою автоморфізмів системи Штейнера S(5,6,12)
• ^[en] є єдиною підгрупою з індексом 2 групи автоморфізмів системи Штейнера S(3,6,22)
• ^[en] є групою автоморфізмів системи Штейнера S(4,7,23)
• ^[en] є групою автоморфізмів системи Штейнера S(5,8,24).

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

Існує єдина система Штейнера S (5,6,12). Її група автоморфізмів — група Матьє M₁₂ і в цьому контексті група позначається як W₁₂.

Побудови

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

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

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

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

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

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

${\displaystyle 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. Існує рівно п'ять елементів у цій групі, які залишають початковий блок без змін, тому ми маємо 132 образи блоку. Як наслідок мультиплікативної транзитивності цієї групи, що діє на цю множину, будь-яка підмножина з п'яти елементів множини S з'явиться в цих 132 образах розміру 6.

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

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

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

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

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

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

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

Див. також

• ^[en]
• Задача Кіркмана про школярок
• Конфігурація Сильвестра — Галлаї

Коментарі

1. Ця властивість еквівалентна (xy)y = x для всіх x і y в ідемпотентній комутативній квазігрупі.

Примітки

1. Encyclopaedia.
2. Keevash, 2014.
3. Quanta Magazine.
4. Kalai.
5. Bose, 1939, с. 353–399.
6. Skolem, 1958, с. 273–280.
7. Colbourn, Dinitz, 2007, с. 60.
8. Colbourn, Dinitz, 2007, с. 497, визначення 28.12.
9. Colbourn, Dinitz, 2007, с. 106.
10. Östergard, Pottonen, 2008.
11. Assmus, Key, 1992, с. 8.
12. Lindner, Rodger, 1997, с. 3.
13. Kirkman, 1847.
14. Steiner, 1853.
15. Carmichael, 1956, с. 431.
16. Beth, Jungnickel, Lenz, 1986, с. 196.
17. Curtis, 1984.
18. EAGTS textbook. оригіналу за 10 грудня 2017. Процитовано 5 липня 2017.
19. Carmichael, 1931.
20. 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.^{[недоступне посилання з грудня 2019]}
• 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! (PDF). http://www.bourbaki.ens.fr. S´eminaire BOURBAKI.
• E.F. Assmus, J.D. Key. Designs and Their Codes. — Cambridge : Cambridge University Press, 1992. — .
• Thomas Beth, Dieter Jungnickel, Hanfried Lenz. Design Theory. — Cambridge : Cambridge University Press, 1986. — .
• Robert Carmichael. Tactical Configurations of Rank Two // American Journal of Mathematics. — 1931. — Т. 53. — С. 217–240. — DOI:10.2307/2370885.
• Robert Carmichael. Introduction to the theory of Groups of Finite Order. — Dover, 1956. — .
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — .
• 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. — .
• D.R. Hughes, E.C. Piper. Design theory. — Cambridge : Cambridge University Press, 1985. — С. 173–176. — .
• 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. — .
• 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 // . — 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. Система Штейнера(англ.) на сайті Wolfram MathWorld.
• Hazewinkel, Michiel, ред. (2001), system Steiner system, Математична енциклопедія, , ISBN 
• 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