In der kombinatorischen Mathematik ist ein System von Steiner (genannt nach Jakob Steiner) ein Typ des Block-Designs, spezifisch mit λ = 1 und t  2.

Ein System von Steiner mit Rahmen t, k, n, schriftlicher S (t, k, n), ist ein N-Element, hat S zusammen mit einer Reihe von K-Element-Teilmengen von S (genannt Blöcke) mit dem Eigentum gesetzt, dass jede T-Element-Teilmenge von S in genau einem Block enthalten wird. In einer abwechselnden Notation für Block-Designs würde ein S (t, k, n) ein t-(n, k, 1) Design sein.

Diese Definition ist relativ modern, die klassische Definition von Systemen von Steiner verallgemeinernd, die außerdem dass k = t + 1 verlangt haben. Ein S (2,3, n) war (und ist noch) hat einen Steiner dreifaches System genannt, während ein S (3,4, n) einen Steiner vierfaches System und so weiter genannt wurde. Mit der Generalisation der Definition wird dieses Namengeben-System daran nicht mehr ausschließlich geklebt.

Beispiele

Begrenzte projektive Flugzeuge

Ein begrenztes projektives Flugzeug des Auftrags q, mit den Linien als Blöcke, ist ein S (2, q+1, q+q+1), da es Q+q+1-Punkte hat, führt jede Linie Q+1-Punkte durch, und jedes Paar von verschiedenen Punkten lügt auf genau einer Linie.

Begrenzte affine Flugzeuge

Ein begrenztes affine Flugzeug des Auftrags q, mit den Linien als Blöcke, ist ein S (2, q, q). Ein affine Flugzeug des Auftrags q kann bei einem projektiven Flugzeug derselben Ordnung durch das Entfernen eines Blocks und aller Punkte in diesem Block vom projektiven Flugzeug erhalten werden. Die Auswahl verschiedener Blöcke, um auf diese Weise umzuziehen, kann zu nichtisomorphen affine Flugzeugen führen.

Klassische Systeme von Steiner

Steiner dreifache Systeme

Ein S (2,3, n) wird einen Steiner dreifaches System genannt, und seine Blöcke werden genannt verdreifacht sich. Es ist üblich, die Abkürzung STS (n) für einen Steiner dreifaches System des Auftrags n zu sehen.

Die Zahl dessen verdreifacht sich ist n (n−1)/6. Eine notwendige und genügend Bedingung für die Existenz eines S (2,3, n) besteht dass n 1 oder 3 (mod 6) darin. Das projektive Flugzeug des Auftrags 2 (das Flugzeug von Fano) ist ein STS (7), und das affine Flugzeug des Auftrags 3 ist ein STS (9).

Bis zum Isomorphismus, der STS (7) und STS (9) sind einzigartig, gibt es zwei STS (13) s, 80 STS (15) s und 11,084,874,829 STS (19) s.

Wir können eine Multiplikation auf dem Satz S das Verwenden vom Steiner dreifaches System definieren, indem wir aa = für alle in S und ab = c untergehen, wenn {a, b, c} ein dreifacher ist. Das macht S einen idempotent, Ersatzquasigruppe. Es hat das zusätzliche Eigentum, dass "ab" = "c" "bc" = "a" und "ca" = "b" einbezieht. Umgekehrt entsteht jede (begrenzte) Quasigruppe mit diesen Eigenschaften aus einem Steiner dreifaches System.

Steiner vierfache Systeme

Ein S (3,4, n) wird einen Steiner vierfaches System genannt. Eine notwendige und genügend Bedingung für die Existenz eines S (3,4, n) besteht dass n 2 oder 4 (mod 6) darin. Die Abkürzung SQS (n) wird häufig für diese Systeme verwendet.

Bis zum Isomorphismus SQS (8) und SQS (10) sind einzigartig, gibt es 4 SQS (14) s und 1,054,163 SQS (16) s.

Steiner fünffache Systeme

Ein S (4,5, n) wird einen Steiner fünffaches System genannt. Eine notwendige Bedingung für die Existenz solch eines Systems besteht darin, dass n 3 oder 5 (mod 6), der aus Rücksichten kommt, die für alle klassischen Systeme von Steiner gelten. Eine zusätzliche notwendige Bedingung besteht darin, dass n 4 (mod 5), der aus der Tatsache kommt, dass die Zahl von Blöcken eine ganze Zahl sein muss. Genügend Bedingungen sind nicht bekannt.

Es gibt einen einzigartigen Steiner fünffaches System des Auftrags 11, aber keiner des Auftrags 15 oder Auftrags 17. Systeme sind für Aufträge 23, 35, 47, 71, 83, 107, 131, 167 und 243 bekannt. Die kleinste Ordnung, für die die Existenz nicht bekannt ist (bezüglich 2011) ist 21.

Eigenschaften

Es ist aus der Definition von S (t, k, n) das klar

Wenn S (t, k, n) besteht, dann gibt die Einnahme aller Blöcke, die ein spezifisches Element enthalten und dieses Element verwerfen, ein abgeleitetes System S (t−1,k−1,n−1). Deshalb ist die Existenz von S (t−1,k−1,n−1) eine notwendige Bedingung für die Existenz von S (t, k, n).

Die Zahl von T-Element-Teilmengen in S ist, während die Zahl von T-Element-Teilmengen in jedem Block ist. Da jede T-Element-Teilmenge in genau einem Block enthalten wird, haben wir, oder, wo b die Zahl von Blöcken ist. Das ähnliche Denken über T-Element-Teilmengen, die ein besonderes Element enthalten, gibt uns, oder, wo r die Zahl von Blöcken ist, die jedes gegebene Element enthalten. Aus diesen Definitionen folgt der Gleichung. Es ist eine notwendige Bedingung für die Existenz von S (t, k, n), dass b und r ganze Zahlen sind. Als mit jedem Block-Design ist die Ungleichheit von Fisher in Systemen von Steiner wahr.

Es kann dass gezeigt werden, wenn es ein System von Steiner S (2, k, n) gibt, wo k eine Hauptmacht ist, die größer ist als 1, dann n 1 oder k (mod k (k−1)). Insbesondere ein Steiner muss dreifaches System S (2,3, n) n = 6m+1 oder 6m+3 haben. Es ist bekannt, dass das die einzige Beschränkung von Steiner dreifache Systeme, d. h. für jede natürliche Zahl ist, besteht M, Systeme S (2,3,6m+1) und S (2,3,6m+3).

Geschichte

Steiner dreifache Systeme wurde zum ersten Mal von W.S.B. Woolhouse 1844 in der Preis-Frage #1733 vom Tagebuch der Dame und Herren definiert. Das aufgeworfene Problem wurde darin gelöst. 1850 hat Kirkman eine Schwankung des Problems aufgestellt, das als das Schülerin-Problem von Kirkman bekannt ist, das um dreifache Systeme bittet, die ein zusätzliches Eigentum (Wiederlösbarkeit) haben. Unbewusst der Arbeit von Kirkman hat Jakob Steiner dreifache Systeme in wiedereingeführt, und wie diese Arbeit weiter bekannt war, wurden die Systeme in seiner Ehre genannt.

Gruppen von Mathieu

Mehrere Beispiele von Systemen von Steiner sind nah mit der Gruppentheorie verbunden. Insbesondere die begrenzten einfachen Gruppen genannt Gruppen von Mathieu entstehen als automorphism Gruppen von Systemen von Steiner:

• Die Gruppe von Mathieu M ist die automorphism Gruppe eines S (4,5,11) System von Steiner
• Die Gruppe von Mathieu M ist die automorphism Gruppe eines S (5,6,12) System von Steiner
• Die Gruppe von Mathieu M ist die einzigartige Untergruppe des Index 2 der automorphism Gruppe eines S (3,6,22) System von Steiner
• Die Gruppe von Mathieu M ist die automorphism Gruppe eines S (4,7,23) System von Steiner
• Die Gruppe von Mathieu M ist die automorphism Gruppe eines S (5,8,24) System von Steiner.

Das System von Steiner S (5, 6, 12)

Es gibt einen einzigartigen S (5,6,12) System von Steiner; seine automorphism Gruppe ist die Gruppe von Mathieu M, und in diesem Zusammenhang wird es durch W angezeigt.

Aufbauten

Um es zu bauen, nehmen Sie einen 12-Punkte-Satz und denken Sie daran als die projektive Linie über F - mit anderen Worten, die ganzen Zahlen mod 11 zusammen mit einem Punkt genannt Unendlichkeit. Unter den ganzen Zahlen mod 11, sechs sind vollkommene Quadrate:

:

Nennen Sie diesen Satz einen "Block". Davon können wir andere Blöcke erhalten, indem wir geradlinige Bruchtransformationen anwenden:

:

Diese Blöcke formen sich dann (5,6,12) System von Steiner.

W kann auch gebaut von der affine Geometrie auf dem Vektorraum FxF, ein S (2,3,9) System.

Ein alternativer Aufbau von W ist das 'Kätzchen' von R.T. Curtis.

Das System von Steiner S (5, 8, 24)

Besonders bemerkenswert ist das System von Steiner S (5, 8, 24), auch bekannt als das Design von Witt oder die Geometrie von Witt. Es wurde in einem 1931-Vortrag von R.D. Carmichael beschrieben und von Ernst Witt wieder entdeckt, der eine Zeitung auf dem Thema 1938 veröffentlicht hat:. Dieses System wird mit vielen der sporadischen einfachen Gruppen und mit dem außergewöhnlichen 24-dimensionalen als das Blutegel-Gitter bekannten Gitter verbunden.

Die automorphism Gruppe von S (5, 8, 24) ist die Gruppe von Mathieu M, und in diesem Zusammenhang wird das Design W ("W" für "Witt") angezeigt

Aufbauten

Es gibt viele Weisen, den S (5,8,24) zu bauen. Die Methode gegeben hier ist vielleicht am einfachsten zu beschreiben und ist leicht, sich zu einem Computerprogramm umzuwandeln. Es verwendet Folgen von 24 Bit. Die Idee ist, diese in der lexikografischen Ordnung niederzuschreiben, irgend jemanden auslassend, der sich von einigen früher ein in weniger als 8 Positionen unterscheidet. Das Ergebnis sieht wie das aus:

000000000000000000000000

000000000000000011111111

000000000000111100001111

000000000000111111110000

000000000011001100110011

000000000011001111001100

000000000011110000111100

000000000011110011000011

000000000101010101010101

000000000101010110101010

.

. (folgende 4083 weggelassen)

.

111111111111000011110000

111111111111111100000000

111111111111111111111111

Die Liste enthält 4096 Sachen, die jeder Code Wörter des verlängerten binären Codes von Golay sind. Sie bilden eine Gruppe unter der XOR Operation. Einer von ihnen hat Null 1 Bit, 759 von ihnen haben acht 1 Bit, 2576 von ihnen haben zwölf 1 Bit, 759 von ihnen haben sechzehn 1 Bit, und man hat vierundzwanzig 1 Bit. Die 759 8-Elemente-Blöcke des S (5,8,24) (hat octads genannt), werden durch die Muster 1's in den Codewörtern mit acht 1 Bit gegeben.

Eine noch direktere Annäherung wird durch das Durchbohren aller 8-Elemente-Teilmengen eines 24-Elemente-Satzes und das Auslassen jeder solcher Teilmenge genommen, die sich von einem in weniger als vier Positionen bereits gefundenen octad unterscheidet.

Wenn man

01, 02, 03..., 22, 23, 24 abweicht, erhält man

01 02 03 04 05 06 07 08

01 02 03 04 09 10 11 12

01 02 03 04 13 14 15 16

.

. (folgende 753 octads weggelassen)

.

13 14 15 16 17 18 19 20

13 14 15 16 21 22 23 24

17 18 19 20 21 22 23 24

Jedes einzelne Element kommt 253mal irgendwo in einem octad vor. Jedes Paar kommt 77mal vor. Jeder verdreifacht sich kommt 21mal vor. Jedes Vierfache (Vierbiteinheit) kommt 5mal vor. Jeder fünffache (pentad) kommt einmal vor. Nicht jeder hexad, heptad oder octad kommen vor.

Siehe auch

• Unveränderlicher Gewicht-Code
• Das Schülerin-Problem von Kirkman
• Konfiguration von Sylvester-Gallai

Referenzen

.

• . 2. Hrsg. (1999) internationale Standardbuchnummer 9780521444323.

..

Außenverbindungen

• Systeme von Steiner durch Andries E. Brouwer
• Durchführung von S (5,8,24) durch Dr Alberto Delgado, Gabe Hart und Michael Kolkebeck
• S (5, 8, 24) Software und Auflistung von Johan E. Mebius
• Das Witt Design, das von Ashay Dharwadker geschätzt ist