Proposal for a search for Steiner 5-designs

The search is reduced by the appropriate theory, see below, to the problem
of solving a Diophantine system of linear equations.
The matrix of coefficients has entries 0 or 1 and on the right hand side
the inhomogenous part is the all-1-vector. Any solution vector so also
has only entries 0 or 1. 

Since most entries are 0, a data structure is chosen that only uses the
non-zero entries. So, for each row there is a stack of all column numbers 
where this row has an entry 1.
The solutions of the search problem are selected column numbers such that 
in each row exactly one of the selected numbers occurs.

A second representation is available where for each column all row numbers are
listed where the column has an entry 1.

The present system can be tested online via


http://btm2xl.mat.uni-bayreuth.de/discreta/disc_online.html

where solutions are produced by a backtrack search sequentially.
The algorithms can be made available by email request:
laue@uni-bayreuth.de
Alfred.Wassermann@uni-bayreuth.de


The proposal shall  allow to attack larger problems successfully.
It consists of the following general strategy:
- A given preselection of columns shall be augmented by a random
  selection of further columns in a given search space
  such that no row contains more than
  one selected column number.
  This can be done in parallel for various random choices and a
  bounded number of steps. Each of these will produce partial
  solutions.
- For a set of several partial solutions the union of all selected columns
  forms a new universe of columns for a search space 
  in which better partial solutions are searched. 
- The two steps are to be combined by some strategy until solutions
  are found or a prescribed number of steps has been exhausted
  to stop without success.



A similar approach has been used already in the DISCRETA project
in a search for Large Sets and has been very successful.

Theoretical background:

A Steiner t-design on a set of points V consists of a selection of
k-element subsets of V, called the blocks of the design, such
that any t-element subset of V is contained in exactly one block.
Thinking of the blocks as being code words, knowing only t correct 
members allows to determine the unique block containing them.
That allows to correct errors.
Steiner systems have played an important role in the history
of finite simple groups.

No Steiner t-design has been found for t>5.

There are only finitely many Steiner 5-designs known up to now. With
only one exception, all of them admit some group of automorphisms
PSL(2,q), where q is a prime power. Then there are q+1 points given by the
projective line over GF(q). It is therefore promising to 
direct the search for Steiner 5-designs especially to this situation.
The problem is hard, since it belongs to the binary packing problem
family.

As a first step a software has been written that computes orbit 
representatives from the orbits of PSL(2,p), p a prime, on 
6-element subsets where the stabilizer of an orbit representative
is prescribed. This approach is very fast and allows to tackle
problems of a size far beyond previous approaches.
Using an invariant for the orbits of  PSL(2,p) on sequences of
length 4 the orbits on 5-element subsets can be identified.
Thus, for each representative K from 6-element subset orbits
all orbits on 5-element subsets T where T \subset K can be 
determined. This is also done by the existing software.
This part of the software could be tested for example for p = 443.


So, the existing software provides a matrix where the columns
correspond to orbits on 6-element subsets with prescribed stabilizers
and the rows correspond to the orbits on 5-element subsets. 
The information is given in two ways: 

- For each 5-element orbit the numbers of columns are listed where 
  any 5-set from this orbit is contained in exactly one 6-element 
  subset from each of the 6-set orbits of these columns.

- For each 6-element orbit the numbers of rows are listed where
  each of the 5-sets in the orbit of one of these rows is contained
  in exactly one 6-set from the orbit of this column.

A Steiner system is obtained by selecting column numbers such that
in each row of the matrix exactly one of the selected numbers 
appears.

For p = 443 and stabilizer C_2 there are 3234  rows and 8028  columns.
The present solver version was successful up to p = 131.

The goal is twofold. On one hand, interesting cases as p=227
and stabilizer only C_2 should be treated. On the other hand,
theoretical investigation should be assisted that try to find
promising preselections from solutions in smaller cases via
group embeddings. An infinite series of Steiner 5-systems
would be an ultimate goal but presently seems to be out of range.
Maybe the detailed analysis of this approach could give some insight.