Incombinatorialmathematics, aSteiner system (named afterJakob Steiner) is a type ofblock design, specifically at-design with λ = 1 andt = 2 or (recently)t ≥ 2.
A Steiner system with parameterst,k,n, written S(t,k,n), is ann-elementsetS together with a set ofk-elementsubsets ofS (calledblocks) with the property that eacht-element subset ofS is contained in exactly one block. In an alternative notation for block designs, an S(t,k,n) would be at-(n,k,1) design.
This definition is relatively new. The classical definition of Steiner systems also required thatk =t + 1. An S(2,3,n) was (and still is) called aSteiner triple (ortriad)system, while an S(3,4,n) is called aSteiner quadruple system, and so on. With the generalization of the definition, this naming system is no longer strictly adhered to.
Long-standing problems indesign theory were whether there exist any nontrivial Steiner systems (nontrivial meaningt <k <n) witht ≥ 6; also whether infinitely many havet = 4 or 5.[1] Both existences were proved byPeter Keevash in 2014. His proof isnon-constructive and, as of 2019, no actual Steiner systems are known for large values oft.[2][3][4]
Afiniteprojective plane of orderq, with the lines as blocks, is anS(2,q + 1,q2 +q + 1), since it hasq2 +q + 1 points, each line passes throughq + 1 points, and each pair of distinct points lies on exactly one line.
Afiniteaffine plane of orderq, with the lines as blocks, is anS(2, q, q2). An affine plane of orderq can be obtained from a projective plane of the same order by removing one block and all of the points in that block from the projective plane. Choosing different blocks to remove in this way can lead to non-isomorphic affine planes.
An S(3,4,n) is called aSteiner quadruple system. A necessary and sufficient condition for the existence of an S(3,4,n) is thatn 2 or 4 (mod 6). The abbreviation SQS(n) is often used for these systems. Up to isomorphism, SQS(8) and SQS(10) are unique, there are 4 SQS(14)s and 1,054,163 SQS(16)s.[5]
An S(4,5,n) is called aSteiner quintuple system. A necessary condition for the existence of such a system is thatn 3 or 5 (mod 6) which comes from considerations that apply to all the classical Steiner systems. An additional necessary condition is thatn 4 (mod 5), which comes from the fact that the number of blocks must be an integer. Sufficient conditions are not known. There is a unique Steiner quintuple system of order 11, but none of order 15 or order 17.[6] Systems are known for orders 23, 35, 47, 71, 83, 107, 131, 167 and 243. The smallest order for which the existence is not known (as of 2011) is 21.
An S(2,3,n) is called aSteiner triple system, and its blocks are calledtriples. It is common to see the abbreviation STS(n) for a Steiner triple system of ordern. The total number of pairs isn(n-1)/2, of which three appear in a triple, and so the total number of triples isn(n−1)/6. This shows thatn must be of the form6k+1 or6k + 3 for somek. The fact that this condition onn is sufficient for the existence of an S(2,3,n) was proved byRaj Chandra Bose[7] and T. Skolem.[8] The projective plane of order 2 (theFano plane) is an STS(7) and theaffine plane of order 3 is an STS(9). Up to isomorphism, the STS(7) and STS(9) are unique, there are two STS(13)s, 80 STS(15)s, and 11,084,874,829 STS(19)s.[9]
We can define a multiplication on the setS using the Steiner triple system by settingaa =a for alla inS, andab =c if {a,b,c} is a triple. This makesS anidempotent,commutativequasigroup. It has the additional property thatab =c impliesbc =a andca =b.[note 1] Conversely, any (finite) quasigroup with these properties arises from a Steiner triple system. Commutative idempotent quasigroups satisfying this additional property are calledSteiner quasigroups.[10]
Some of the S(2,3,n) systems can have their triples partitioned into (n-1)/2 sets each having (n/3) pairwise disjoint triples. This is calledresolvable and such systems are calledKirkman triple systems afterThomas Kirkman, who studied such resolvable systems before Steiner. Dale Mesner, Earl Kramer, and others investigated collections of Steiner triple systems that are mutually disjoint (i.e., no two Steiner systems in such a collection share a common triplet). It is known (Bays 1917, Kramer & Mesner 1974) that seven different S(2,3,9) systems can be generated to together cover all 84 triplets on a 9-set; it was also known by them that there are 15360 different ways to find such 7-sets of solutions, which reduce to two non-isomorphic solutions under relabeling, with multiplicities 6720 and 8640 respectively.
The corresponding question for finding thirteen different disjoint S(2,3,15) systems was asked byJames Sylvester in 1860 as an extension of theKirkman's schoolgirl problem, namely whether Kirkman's schoolgirls could march for an entire term of 13 weeks with no triplet of girls being repeated over the whole term. The question was solved byRHF Denniston in 1974,[11] who constructed Week 1 as follows:
Day 1 ABJ CEM FKL HIN DGODay 2 ACH DEI FGM JLN BKODay 3 ADL BHM GIK CFN EJODay 4 AEG BIL CJK DMN FHODay 5 AFI BCD GHJ EKN LMODay 6 AKM DFJ EHL BGN CIODay 7 BEF CGL DHK IJM ANO
for girls labeled A to O, and constructed each subsequent week's solution from its immediate predecessor by changing A to B, B to C, ... L to M and M back to A, all while leaving N and O unchanged. The Week 13 solution, upon undergoing that relabeling, returns to the Week 1 solution. Denniston reported in his paper that the search he employed took 7 hours on anElliott 4130 computer at theUniversity of Leicester, and he immediately ended the search on finding the solution above, not looking to establish uniqueness. The number of non-isomorphic solutions to Sylvester's problem remains unknown as of 2021.
It is clearfrom the definition ofS(t,k,n) that. (Equalities, while technically possible, lead to trivial systems.)
IfS(t,k,n) exists, then taking all blocks containing a specific element and discarding that element gives aderived systemS(t−1,k−1,n−1). Therefore, the existence ofS(t−1,k−1,n−1) is a necessary condition for the existence ofS(t,k,n).
The number oft-element subsets inS is, while the number oft-element subsets in each block is. Since everyt-element subset is contained in exactly one block, we have, or
whereb is the number of blocks. Similar reasoning aboutt-element subsets containing a particular element gives us, or
wherer is the number of blocks containing any given element. From these definitions follows the equation. It is a necessary condition for the existence ofS(t,k,n) thatb andr are integers. As with any block design,Fisher's inequality is true in Steiner systems.
Given the parameters of a Steiner systemS(t, k, n) and a subset of size, contained in at least one block, one can compute the number of blocks intersecting that subset in a fixed number of elements by constructing aPascal triangle.[12] In particular, the number of blocks intersecting a fixed block in any number of elements is independent of the chosen block.
The number of blocks that contain anyi-element set of points is:
It can be shown that if there is a Steiner systemS(2,k,n), wherek is aprime power greater than 1, thenn 1 ork (modk(k−1)). In particular, a Steiner triple systemS(2, 3,n) must haven = 6m + 1 or 6m + 3. And as we have already mentioned, this is the only restriction on Steiner triple systems, that is, for eachnatural numberm, systemsS(2, 3, 6m + 1) andS(2, 3, 6m + 3) exist.
Steiner triple systems were defined for the first time byWesley S. B. Woolhouse in 1844 in the Prize question #1733 of Lady's and Gentlemen's Diary.[13] The posed problem was solved byThomas Kirkman (1847). In 1850 Kirkman posed a variation of the problem known asKirkman's schoolgirl problem, which asks for triple systems having an additional property (resolvability). Unaware of Kirkman's work,Jakob Steiner (1853) reintroduced triple systems, and as this work was more widely known, the systems were named in his honor.
In 1910Geoffrey Thomas Bennett gave a graphical representation for Steiner triple systems.[14][15][16]
Several examples of Steiner systems are closely related togroup theory. In particular, thefinite simple groups calledMathieu groups arise asautomorphism groups of Steiner systems:
There is a unique S(5,6,12) Steiner system; its automorphism group is theMathieu group M12, and in that context it is denoted by W12.
This construction is due to Carmichael (1937).[17]
Add a new element, call it∞, to the 11 elements of thefinite fieldF11 (that is, the integers mod 11). This set,S, of 12 elements can be formally identified with the points of theprojective line overF11. Call the following specific subset of size 6,
a "block" (it contains∞ together with the 5 nonzero squares inF11). From this block, we obtain the other blocks of theS(5,6,12) system by repeatedly applying thelinear fractional transformations:
wherea,b,c,d are inF11 andad − bc = 1.With the usual conventions of definingf (−d/c) = ∞ andf (∞) =a/c, these functions map the setS onto itself. In geometric language, they areprojectivities of the projective line. They form agroup under composition which is theprojective special linear groupPSL(2,11) of order 660. There are exactly five elements of this group that leave the starting block fixed setwise,[18] namely those such thatb=c=0 andad=1 so thatf(z) = a2z. So there will be 660/5 = 132 images of that block. As a consequence of the multiply transitive property of this groupacting on this set, any subset of five elements ofS will appear in exactly one of these 132 images of size six.
An alternative construction of W12 is obtained by use of the 'kitten' of R.T. Curtis,[19] which was intended as a "hand calculator" to write down blocks one at a time. The kitten method is based on completing patterns in a 3x3 grid of numbers, which represent anaffine geometry on thevector space F3xF3, an S(2,3,9) system.
The relations between thegraph factors of thecomplete graph K6 generate an S(5,6,12).[20] A K6 graph has 6 vertices, 15 edges, 15perfect matchings, and 6 different 1-factorizations (ways to partition the edges into disjoint perfect matchings). The set of vertices (labeled 123456) and the set of factorizations (labeledABCDEF) provide one block each. Every pair of factorizations has exactly one perfect matching in common. Suppose factorizationsA andB have the common matching with edges 12, 34 and 56. Add three new blocksAB3456, 12AB56, and 1234AB, replacing each edge in the common matching with the factorization labels in turn. Similarly add three more blocks 12CDEF, 34CDEF, and 56CDEF, replacing the factorization labels by the corresponding edge labels of the common matching. Do this for all 15 pairs of factorizations to add 90 new blocks. Finally, take the full set of combinations of 6 objects out of 12, and discard any combination that has 5 or more objects in common with any of the 92 blocks generated so far. Exactly 40 blocks remain, resulting in2 + 90 + 40 = 132 blocks of the S(5,6,12). This method works because there is anouter automorphism on the symmetric groupS6, which maps the vertices to factorizations and the edges to partitions. Permuting the vertices causes the factorizations to permute differently, in accordance with the outer automorphism.
The Steiner system S(5, 8, 24), also known as theWitt design orWitt geometry, was first described byCarmichael (1931) and rediscovered byWitt (1938). This system is connected with many of thesporadic simple groups and with theexceptional 24-dimensionallattice known as theLeech lattice. The automorphism group of S(5, 8, 24) is theMathieu group M24, and in that context the design is denoted W24 ("W" for "Witt")
All 8-element subsets of a 24-element set are generated inlexicographic order, and any such subset which differs from some subset already found in fewer than four positions is discarded.
The list of octads for the elements 01, 02, 03, ..., 22, 23, 24 is then:
Each single element occurs 253 times somewhere in some octad. Each pair occurs 77 times. Each triple occurs 21 times. Each quadruple (tetrad) occurs 5 times. Each quintuple (pentad) occurs once. Not every hexad, heptad or octad occurs.
The 4096 codewords of the 24-bitbinary Golay code are generated, and the 759 codewords with aHamming weight of 8 correspond to the S(5,8,24) system.
The Golay code can be constructed by many methods, such as generating all 24-bit binary strings in lexicographic order and discarding those thatdiffer from some earlier one in fewer than 8 positions. The result looks like this:
000000000000000000000000 000000000000000011111111 000000000000111100001111 . . (next 4090 24-bit strings omitted) . 111111111111000011110000 111111111111111100000000 111111111111111111111111
The codewords form agroup under theXOR operation.
This construction is due to Carmichael (1931).[21]
Add a new element, call it∞, to the 23 elements of thefinite fieldF23 (that is, the integers mod 23). This set,S, of 24 elements can be formally identified with the points of theprojective line overF23. Call the following specific subset of size 8,
a "block". (We can take any octad of the extendedbinary Golay code, seen as a quadratic residue code.) From this block, we obtain the other blocks of theS(5,8,24) system by repeatedly applying thelinear fractional transformations:
wherea,b,c,d are inF23 andad − bc = 1.With the usual conventions of definingf (−d/c) = ∞ andf (∞) =a/c, these functions map the setS onto itself. In geometric language, they areprojectivities of the projective line. They form agroup under composition which is theprojective special linear groupPSL(2,23) of order 6072. There are exactly 8 elements of this group that leave the initial block fixed setwise. So there will be 6072/8 = 759 images of that block. These form the octads of S(5,8,24).
TheMiracle Octad Generator (MOG) is a tool to generate octads, such as those containing specified subsets. It consists of a 4x6 array with certain weights assigned to the rows. In particular, an 8-subset should obey three rules in order to be an octad of S(5,8,24). First, each of the 6 columns should have the sameparity, that is, they should all have an odd number of cells or they should all have an even number of cells. Second, the top row should have the same parity as each of the columns. Third, the rows are respectively multiplied by the weights 0, 1, 2, and 3 over thefinite field of order 4, and column sums are calculated for the 6 columns, with multiplication and addition using thefinite field arithmetic definitions. The resulting column sums should form a validhexacodeword of the form(a,b,c,a +b +c,3a +2b +c,2a +3b +c) wherea, b, c are also from the finite field of order 4. If the column sums' parities don't match the row sum parity, or each other, or if there do not exista, b, c such that the column sums form a valid hexacodeword, then that subset of 8 is not an octad of S(5,8,24).
The MOG is based on creating abijection (Conwell 1910, "The three-space PG(3,2) and its group") between the 35 ways to partition an 8-set into two different 4-sets, and the 35 lines of theFano 3-space PG(3,2). It is also geometrically related (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, pp A193-194, Feb 1979) to the 35 different ways to partition a 4x4 array into 4 different groups of 4 cells each, such that if the 4x4 array represents a four-dimensional finiteaffine space, then the groups form a set of parallel subspaces.
{{citation}}:ISBN / Date incompatibility (help)