Steiner systems

Following Peter Keevash’s asymptotic existence proof for Steiner systems, does anything remain to be done? I would say yes, it certainly does; here are a few thoughts about the open problems in this area.

Existence

We are looking for a Steiner system S(t,k,n): that is, n points, blocks of size k, any t points in a unique block, with t < k < n. There are some divisibility conditions which are necessary for existence, and Keevash’s theorem asserts that they are also sufficient for large enough n, for fixed t and k. But that leaves a big hole.

The existence theorem was proved for t = 2 in the early 1970s by Richard Wilson, whose lower bounds for existence are not absurdly large, but still probably not best possible.

(Keevash does not give explicit lower bounds for n in terms of t and k. It would be interesting to know what order of magnitude can be obtained from his method.)

The general problem is:

Find necessary and sufficient conditions on the parameters for the existence of a Steiner system.

It is too much to expect a general solution to this problem, so we restrict to some special cases which have been interesting to geometers and combinatorialists.

For which q does there exist a projective plane of order q, that is, a Steiner system with t = 2, k = q+1, n = q2+q+1?

This is one of the most celebrated problems in finite mathematics. We know that projective planes exist when q is a prime power. The Bruck–Ryser theorem shows that they do not exist if q is congruent to 1 or 2 (mod 4) and q is not the sum of two squares. A huge computation by Clement Lam and colleagues shows that there is no projective plane of order 10. And that is the sum total of our knowledge. The last result, though very special, destroys the extreme optimists’ conjecture, that the Bruck–Ryser condition is necessary and sufficient.

The extreme pessimists’ conjecture, on the other hand, that projective planes exist only for prime power orders, is still open. A related conjecture, also still open, is that there is a unique projective plane of prime order, the classical one over the field of integers mod p. The rationale behind these conjectures is that, despite two centuries of effort, all the projective planes we know are coordinatised by algebraic systems of some sort (fields, or things obtained by twisting the multiplication in a field, or vector spaces over fields), and perhaps that is all there is. Moreover, the field of prime order cannot be twisted.

The existence of a projective plane is equivalent to that of an affine plane, a Steiner system with t = 2, k = q, n = q2. However, other interesting geometric objects are still undecided, such as inversive planes, with t = 3, k = q+1, n = q2+1.

Another interesting family satisfying the divisibility conditions has k = t+1, n = 2t+2, where t+2 is prime. These exist for t = 3 and t = 5 (both very famous designs with large automorphism groups), but not for t = 9.

Enumeration

An even harder question than existence is enumeration: how many Steiner systems with given parameters are there? Of course this is more general since a system exists if and only if the number is non-zero.

Indeed, there is only one general case in which results exist. Richard Wilson showed that the number of Steiner triple systems (t = 2, k = 3) of admissible order n is about ncn2. More precisely, the logarithm of this number is asymptotically (n2 log n)/6. This number is so much larger than n! that it makes little difference whether we account for isomorphisms between different systems or not.

Apart from this, all that is known are enumerations for particular values of the parameters, most notably the result of Østergård and Kaski that the number of Steiner triple systems on a set of 19 points (up to isomorphism) is 11084874829.

Any general non-trivial upper or lower bounds would be welcome …

Automorphisms

A consequence of Wilson’s enumeration result, proved by László Babai, is that almost all Steiner triple systems have no automorphisms apart from the identity. Even this is unknown for any other parameter values, though it may well be true for any fixed t and k as n → ∞.

On the other hand, “highly symmetric” Steiner systems will not exist in general. We know, from the classification of finite simple groups, that there are no 6-transitive groups apart from the symmetric and alternating groups. This means that the known highly symmetric examples, let us say the S(t,k,n) systems admitting t-transitive automorphism groups, are very special and precious and should be cherished.

Random choice

Here the situation is even worse.

Jacobson and Matthews gave a Markov chain for Latin squares which converged to the uniform distribution. There is an obvious modification of this which applies to Steiner triple systems, but (despite heroic efforts by Andrew Drizen in his PhD thesis) we do not even know whether it is connected in general!

Large sets and resolutions

If the necessary conditions for the existence of a Steiner triple system are satisfied, and if in addition the number of blocks of such a system divides the number of all k-subsets of the point set, then we can ask:

Can the set of all k-subsets of the point set be partitioned into Steiner systems?

A set of Steiner systems using each k-set exactly once is called a large set. Luc Teirlinck showed that large sets of Steiner triple systems exist for all orders except n = 7, where the non-existence goes back to Cayley (who showed that one cannot find more than two distinct systems in this case).

A resolution of a Steiner system is a partition of the block set into “resolution classes”, each of which partitions the point set. Do resolvable systems exist whenever the necessary conditions are satisfied and k divides n? This was proved for Steiner triple systems by Ray-Chaudhuri and Wilson, thereby answering a question posed by Kirkman in the 1840s.

A question which generalises both of the above is the following. Suppose that both of the parameter sets (t,k,n) and (s,k,n) are admissible, where s < t. Does there exist a S(t,k,n) whose block set can be partitioned into subsets each forming an S(s,k,n)?

Universal algebra

It is well known that Steiner triple systems give rise to two types of quasigroups or loops: we take the “product” of two points to be the third point on the block containing it, and use one of two possible strategies for the product of a point with itself. Algebraic properties such as associativity or the Moufang law for these structures translate into geometric or combinatorial properties for the Steiner triple systems.

Ganter, Quackenbush, and others extended this to other kinds of Steiner systems, but apparently came up against a natural boundary to the techniques quite soon. It may be that there are no surprises lurking here.

Steiner systems in vector spaces

I think that this is the most important area to attack next.

We can alter the definition of Steiner system by replacing “set” and “subset” by “vector space” and “subspace” (over a given finite field GF(q)). In other words, we have a collection of k-dimensional subspaces over an n-dimensional vector space over GF(q) with the property that any t-dimensional subspace lies in a unique subspace in our collection.

This is in a sense part of a programme instigated by Jacques Tits, which regards the combinatorics of sets and subsets (and other things) as “projective geometry over the field with one element“. Many areas of combinatorics can be “extended” to larger fields. Sometimes the theorems are known (e.g. the analogue of Ramsey’s theorem, due to Graham and Rothschild, uses the Hales–Jewett theorem); others, such as Steiner systems, still await progress.

The problem is a virtually complete lack of examples!

Perfect matroid designs

A common generalisation of Steiner systems over sets and vector spaces is the area of “perfect matroid designs”. These are matroids where the cardinality of a flat depends only on its rank.

Michel Deza popularised the problem (which also arose in some early work of mine) of finding a perfect matroid design of rank 4 on 183 points, where the lines have three points and the planes have 21 points. Each plane is a Steiner triple system of order 21; and the quotient by a point is a projective plane of order 9. These designs are still unknown. Indeed, very few examples of perfect matroid designs are known, even though they are beautiful structures with many interesting properties.

t-designs

Peter Keevash also proved the asymptotic existence of t-designs, where each set of t points lies in exactly λ blocks (rather than exactly one block). Everything said so far can be generalised to t-designs. Most of the problems are wide open!

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in mathematics, open problems and tagged , , , , , . Bookmark the permalink.

2 Responses to Steiner systems

  1. Dima says:

    regarding examples for “Steiner systems in vector spaces”, there are certainly examples for t=1, as it’s nothing but spreads of k-subspaces of the underlying projective space.

    • Yes, and this gives some small evidence that this case is harder than the set case. Nobody would have any difficulty deciding when S(1,k,n) systems exist (and when they exist they are unique), but in the vector space case it is not so trivial and (for n=2k) their existence is equivalent to that of translation planes, of which there are many different ones. This is partly why I think this is the best problem to tackle!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s