Система Штейнера
Система Штейнера (названа ім'ям Якоба Штейнера) — варіант блок-схем, точніше, 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]. Ствердну відповідь дав Пітер Ківаш[ru] 2014 року[2][3][4].
Приклади[ред. | ред. код]
Скінченні проєктивні площини[ред. | ред. код]
Скінченна проєктивна площина порядку q з прямими як блоками є схемою S(2, q + 1, q2 + q + 1), оскільки вона має q2 + q + 1 точок, кожна пряма проходить через q + 1 точок, а кожна пара різних точок лежить рівно на одній прямій.
Скінченні афінні площини[ред. | ред. код]
Скінченна афінна площина[en] порядку q з прямими як блоками є схемою S(2, q, q2). Афінну площину порядку 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][5] і Т. Сколем[6]. Проєктивна площина порядку 2 (площина Фано) — це STS(7), а афінна площина[en] порядку 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 2 чи 4 (mod 6). Для цих систем часто використовують позначення SQS(n).
З точністю до ізоморфізму SQS(8) і SQS(10) єдині, є 4 схеми SQS(14) та 1 054 163 схем SQS(16) [9] .
Системи п'ятірок Штейнера[ред. | ред. код]
Схему S(4,5,n) називають системою п'ятірок Штейнера. Необхідна умова існування такої системи — n 3 або 5 (mod 6), що виходить з домовленостей, які застосовують до всіх класичних систем Штейнера. Додаткова умова для загальних систем, що n 4 (mod 5), випливає з факту, що число блоків має бути цілим. Достатні умови невідомі.
Існує єдина система п'ятірок Штейнера порядку 11 але немає систем порядку 15 або 17[10]. Відомі системи з порядками 23, 35, 47, 71, 83, 107, 131, 167 та 243. Найменший порядок, для якого існування невідоме (на 2011 рік) — 21.
Властивості[ред. | ред. код]
З визначення S(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 дорівнює , тоді як число t-елементних підмножин у кожному з блоків дорівнює . Оскільки будь-яка t-елементна підмножина міститься рівно в одному блоці, отримуємо , або
де b — число блоків. Аналогічні міркування про t-елементні підмножини, що містять конкретний елемент, дають нам , або
- =
де r — число блоків, що містять вибраний елемент. Із цих визначень випливає рівність . Необхідною умовою існування схеми S(t, k, n) є цілочисельність b і r. Як і для будь-якої блок-схеми, для систем Штейнера виконується нерівність Фішера .
Якщо дано параметри системи Штейнера S(t, k, n) і підмножину розміру , що міститься принаймні в одному блоці, можна порахувати число блоків, що перетинають цю підмножину з фіксованим числом елементів, побудувавши трикутник Паскаля[11]. Зокрема, кількість блоків, що перетинають фіксований блок із будь-яким числом елементів, не залежить від вибору блоку.
Число блоків, що містять будь-яку i-елементну множину точок, дорівнює:
- для
Можна показати, що якщо існує система Штейнера S(2, k, n), де k — степінь простого числа, більший від 1, тоді n 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 в журналі The Lady's and Gentleman's Diary[en][12]. Поставлену задачу розв'язав Томас Кіркман[13]. У 1850 Кіркман поставив варіант задачі, який отримав назву «Задача Кіркмана про школярок», у якій питається про систему трійок з додатковою властивістю (розв'язність). Не знаючи про роботу Кіркмана, Якоб Штейнер[14] визначив систему трійок, і його робота набула більшої популярності, так що система отримала його ім'я.
Групи Матьє[ред. | ред. код]
Деякі приклади систем Штейнера тісно пов'язані з теорією груп. Зокрема, скінченні прості групи[en], які називають групами Матьє, виникають як групи автоморфізмів систем Штейнер:
- Група Матьє M11[en] є групою автоморфізмів системи Штейнера S(4,5,11)
- Група Матьє M12[en] є групою автоморфізмів системи Штейнера S(5,6,12)
- Група Матьє M22[en] є єдиною підгрупою з індексом 2 групи автоморфізмів системи Штейнера S(3,6,22)
- Група Матьє M23[en] є групою автоморфізмів системи Штейнера S(4,7,23)
- Група Матьє M24[en] є групою автоморфізмів системи Штейнера S(5,8,24).
Система Штейнера S(5,6,12)[ред. | ред. код]
Існує єдина система Штейнера S (5,6,12). Її група автоморфізмів — група Матьє M12 і в цьому контексті група позначається як W12.
Побудови[ред. | ред. код]
Є різні шляхи побудови системи S(5,6,12).
Метод проєктивної прямої[ред. | ред. код]
Ця побудова належить Кармайклу (1937)[15].
Додамо новий елемент, який позначимо як ∞, до 11 елементів скінченного поля F11 (тобто лишків за модулем 11). Цю множину S із 12 елементів можна формально ототожнити з точками проєктивної прямої над F11. Назвемо таку підмножину розміру 6,
«блоком». За допомогою цього блоку ми отримаємо інші блоки схеми S(5,6,12) шляхом багаторазового застосування дробово-лінійного перетворення:
де a,b,c,d містяться в F11, а ad - bc є ненульовим квадратом у F11. Якщо визначити f (−d/c) = ∞ та f (∞) = a/c, ця функція відображає множину S на себе. Геометричною мовою це проєкції проєктивної прямої. Вони утворюють групу за суперпозицією, і ця група є проєктивною спеціальною лінійною групою PSL (2,11) порядку 660. Існує рівно п'ять елементів у цій групі, які залишають початковий блок без змін[16], тому ми маємо 132 образи блоку. Як наслідок мультиплікативної транзитивності цієї групи, що діє на цю множину, будь-яка підмножина з п'яти елементів множини S з'явиться в цих 132 образах розміру 6.
Метод Куртіса[ред. | ред. код]
Альтернативна побудова схеми W12 виконується із застосуванням методу Р. Т. Куртіса[17], призначеного для «ручного обчислення» блоків одного за одним. Метод Куртіса ґрунтується на заповненні таблиць чисел 3x3, які представляють афінну геометрію на векторному просторі F3xF3, систему S(2,3,9).
Побудова розбиттям графа K6[ред. | ред. код]
Зв'язок між факторами повного графа K6 генерує схему S(5,6,12)[18]. Граф 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), відому також як схема Вітта або геометрія Вітта, описав Роберт Кармайкл[19] і перевідкрив Вітт[20]. Ця система пов'язана з багатьма спорадичними групами і з виключною[en] 24-вимірною ґраткою, відомою як ґратка Ліча.
Група автоморфізмів схеми S(5, 8, 24) є групою Матьє M24[en] і в контексті схем позначається 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) задаються одиничними бітами слів із вісьмома одиницями.
Див. також[ред. | ред. код]
Коментарі[ред. | ред. код]
- ↑ Ця властивість еквівалентна (xy)y = x для всіх x і y в ідемпотентній комутативній квазігрупі.
Примітки[ред. | ред. код]
- ↑ Encyclopaedia.
- ↑ Keevash, 2014.
- ↑ Quanta Magazine.
- ↑ Kalai.
- ↑ Bose, 1939, с. 353–399.
- ↑ Skolem, 1958, с. 273–280.
- ↑ Colbourn, Dinitz, 2007, с. 60.
- ↑ Colbourn, Dinitz, 2007, с. 497, визначення 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. Архів оригіналу за 10 грудня 2017. Процитовано 5 липня 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.[недоступне посилання з грудня 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. — 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: .
- 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 M12 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: .
- 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: .
Посилання[ред. | ред. код]
- Rowland, Todd and Weisstein, Eric W. Система Штейнера(англ.) на сайті Wolfram MathWorld.
- Hazewinkel, Michiel, ред. (2001), Steiner system, Математична енциклопедія, 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
|