Steiner system

From Wikipedia, the free encyclopedia

In combinatorial mathematics, a Steiner system is a type of block design.

A Steiner system with parameters l, m, n, written S(l,m,n), is an n-element set S together with a set of m-element subsets of S (called blocks) with the property that each l-element subset of S is contained in exactly one block. A Steiner system with parameters l, m, n is often called simply "an S(l,m,n)".

An S(2,3,n) is called a Steiner triple system, and its blocks are called triples. The number of triples is n(n-1)/6. We can define a multiplication on a Steiner triple system by setting aa = a for all a in S, and ab = c if {a,b,c} is a triple. This makes S into an idempotent commutative quasigroup.

An S(2,4,n) is sometimes called a Steiner quadruple system. Systems with higher values of m are not usually called by special names.

It can be shown that if there is a Steiner system S(2,m,n), where m is a prime power greater than 1, then n = 1 or m (mod m(m−1)). In particular, a Steiner triple system S(2,3,n) must have n = 6k+1 or 6k+3. It is known that this is the only restriction on Steiner triple systems, that is, for each natural number k, systems S(2,3,6k+1) and S(2,3,6k+3) exist.

A finite projective plane of order q, with the lines as blocks, is an S(2, q+1, q²+q+1), since it has q²+q+1 points, each line passes through q+1 points, and each pair of distinct points lies on exactly one line.

Several examples of Steiner systems are closely related to group theory.

[edit] S(5,8,24)

Particularly remarkable is the Steiner system S(5,8,24). This is connected with many of the sporadic simple groups and with the exceptional 24-dimensional lattice known as the Leech lattice. There are many ways to construct the S(5,8,24). The method given here is perhaps the simplest to describe, and is easy to convert into a computer program. It uses sequences of 24 bits. The idea is to write these down in lexicographic order, missing out any one which differs from some earlier one in less than 8 positions. The result looks like this:

   000000000000000000000000
   000000000000000011111111
   000000000000111100001111
   000000000000111111110000
   000000000011001100110011
   000000000011001111001100
   000000000011110000111100
   000000000011110011000011
   000000000101010101010101
   000000000101010110101010
   .
   . (next 4083 omitted)
   .
   111111111111000011110000
   111111111111111100000000
   111111111111111111111111

The list contains 4096 items, which are each code words of the extended binary Golay code. They form a group under the XOR operation. One of them has zero 1-bits, 759 of them have eight 1-bits, 2576 of them have twelve 1-bits, 759 of them have sixteen 1-bits, and one has twenty-four 1-bits. The 759 8-element blocks of the S(5,8,24) (called octads) are given by the patterns of 1's in the code words with eight 1-bits.

For a different construction of the S(5,8,24), due to R. T. Curtis, see Geometry of the 4x4 Square.