Next: Bibliography
Up: Partitioned Steiner 5Designs
Previous: Subgroups of order up
Invariants
Each of the stabilizers of order 6 acts transitively on any invariant 6set . So, there is only one 5set orbit on . Correspondingly, the column for in the KramerMesner matrix has only one entry 1 and all other entries are 0. So, in these cases, we easily determine the entries of the KramerMesner matrix in these columns. The remaining cases are more complicated. Here we use Alltop's Lemma. That requires for each 5set contained in a representative of a 6set orbit with stabilizer to find out the 5set orbit of . We do this by computing an invariant which separates the 5set orbits.
If a group acts transitive then any element sequence of pairwise different
elements can be mapped onto any other such sequence by some group element.
If the stabilizer of a sequence acts trivially then already the sequence of the
image points of determines the image points of all other points.
To see this assume there would be different image points for some element . That would mean that there are two group elements such that but . Then fixes each element of and thus should be trivial by assumption. But then also fixes .
Any sequence of pairwise different entries of length bigger than
can be truncated after the first three entries. This is a projection
that is compatible with the group action. So, two longer sequences
with identical starting sequence of length are in the same orbit
only if some element in the stabilizer of the first elements maps
one onto the other. If the stabilizer is trivial all these sequences
lie in pairwise different orbits. This strategy of using mappings that are compatible with the group action
to simplify the problem is called homomorphism principle [14], [16].
We have already used this approach in Lemma 4 where the homomorphism of group actions
is the assignment of the stabilizer to its kset.
If a group is regular on the orbit of then the orbit of each sequence
with starting subsequence can be uniquely described by first applying the
unique group element that maps the starting sequence onto to
and then using the sequence of the images of remaining points under as an
invarant.
A prominent example of this kind is the crossratio of geometry.
The group acts 3transitive on the projective line
and regular on 3sequences of pairwise different 1dimensional subspaces.
By means of linear algebra a matrix can be found mapping one such sequence
onto a given second one. In particular, taking as the first sequence
a standard representative produces invariants.
For any 4sequence the image of the fourth point after normalizing the first 3element
sequence uniquely determines the orbit.
In any subgroup the stabilizer of three points acts
trivially. So, if one first determines each orbit of the subgroup on the 3sequences
and then uses the image of the fourth point one again has an invariant. We use this for
.
This group is 2transitive and the stabilizer of two points is transitive on
those points that lie in the same image of the determinant, that is those that are either
all squares or all nonsquares.
In this way we can map each sequence of 4 pairwise different points onto a unique
representative of its orbit. We define some ordering on the set of these representatives
and declare the smallest of all representatives from all sequences of
4 pairwise different points of a 5set as the representative
of .
Of course this could be done as well for any sets. But for larger we get
too many 4sets contained in a set. So, for and our special goal
of finding Steiner systems we here make use of the following observation.
If a 6set is contained in an orbit that already occured then the 5orbits
it covers are already covered by the earlier found representative.
In terms of the KramerMesner matrix that would mean that the column computed
for the new set is identical to an already existing one. So, we omit multiple
columns.
There are cases where 6sets from different orbits produce identical columns
of the KramerMesner matrix. But if we look for Steiner systems we can use at
most one of two such columns. So, we could store for each column the multiplicity
of its occurrence and then multiply each solution with the factors of all columns
belonging to that solution. This would allow to count the complete number of solutions.
Then the number of isomorphism types is just half of the number of solutions
by [16]. This has not yet been implemented.
We work out the computation.
Take and as the representatives of the sequences of two 1dimensional
subspaces. Then given any two subspaces and or we can determine a
matrix mapping the given sequence onto the sequence of representatives.
The matrix
maps onto ,
The matrix
maps onto ,
The matrix
maps onto ,
So, in each case we know the matrix transforming a given sequence of two
1dimensional subspaces onto the standard basis. We have chosen the matrices so that
the determinant is a square modulo .
The matrix can be applied to all entries of a 4sequence such that the first two
members are mapped onto and .
So, in a first step, the sequences are normalized in their first two components.
This can be done in constant time.
We now consider the second step, where the third component is normalized.
The first two components now have to remain unchanged.
The subgroup of all matrices fixing the two subspaces and
consists of the matrices
of the form where . There are such matrices.
Since any matrix that fixes 3 1dimensional subspaces must fix all 1dimensional subspaces,
this subgroup acts regularly on the set of subspaces of the form for
.
We chose as a representative . The matrix
normalizes the third component.
So, there is only one orbit on 3sequences under
.
A sequence
is transformed into normal form by first transforming by
and then by
So, the product of these transformations
sends to .
The quotient
thus is an invariant of the orbit of the given sequence under . This quotient is known as the crossratio in finite geometry.
In case of the special linear group the diagonal matrix has to lie in the coset of a matrix with determinant 1
modulo the kernel of the action of on the set of all 1dimensional subspaces.
This kernel consists of all matrices of the form
such that their determinant is a square. The squares form a subgroup of index two in the multiplicative group of residues modulo , which therefore has elements. So, the subspaces lie in two orbits of length each. A representative of the first orbit is and the orbit consists of all where is a square. If 4 divides then 4 does not divide . So, the multiplicative group of residues modulo has no element of order 4 such that there is no with . We have found the nonsquare which gives rise to a representative of the other orbit.
We now have seen that there are two orbits of PSL(2,p) on the set of
sequences of length 3 with representatives
and
If we apply the matrix
of determinant 1 to the first sequence we obtain a permuted version of the second representatives. This shows that the corresponding 3element sets of 1dimensional subspaces are in one orbit. This means that is 3homogeneous.
For our goal of normalizing a given sequence of 1dimensional subspaces
we, after having transformed the sequence such that the first two
components are normalized, have to multiply with some
where is a square such that we either get
or
as the third component.
The first case is just the crossratio derived above.
The second one is obtained similarly. It turns out that then
is sent to
.
So, in this case we have to multiply the crossratio by 1.
That allows to use the well known mathematical term of a Legendre symbol.
For a prime and one has
if is a quadratic residue modulo and
if is a nonquadratic residue modulo . So, if then the invariant is the product of the crossratio and the Legendre symbol.
Using this invariant, the orbit of a 4sequence can be
determined in constant time.
Now we have achieved a sequence of the form
or
where or . By the homomorphism principle, applied to the projection to the first 3 components, two such sequences could be in the same orbit only if they are mapped one onto the other by some element in the stabilizer of the firest three components. This stabilizer is trivial such that all choices of in the two sequences belong to pairwise different orbits. The pair or thus is an invariant for the orbits on sequences of length 4.
Of course, this can be continued to sequences of length 5 and longer.
We now consider 4element subsets instead of sequences.
They can be obtained from the sequences by the fusion version
of the homomorphism principle.
A given 4set can be arranged as a sequence 24 times.
So, we will get 24 values
of our invariant for .
Each transformation also transforms to some .
The sequences we can form from are in the same orbits
as the sequences we have formed from .
So, we don't have to iterate this process.
We can define the set coming from the lexicographically smallest
sequence among the 24 sequences as the canonical representative.
We also can use the transformation which transformed the
selected sequence
into canonical form for transforming into canonical form.
In fact, if we take the 24 sequences of pairwise different points
from then by normalizing them we will get back those that we obtained from .
This shows that there is a bijection between the set of all 24 values of the
invariant and the selected smallest one.
Alltogether we have presented a constant time algorithm which computes
for any given 4element subset the canonical representative of its orbit
and a matrix which does this transformation.
A slight variation should be made when many 4sets have to be transformed
into canonical form. Then searching each time for a square
such that
where or would take too much time. So, a table can be computed first which contains for each value of the corresponding square . This can be done in linear time, since either is the inverse of and then is a square or is the inverse of and then is a nonsquare. So, besides a table of inverses another table of squares is needed.
The stabilizer of is obtained by taking the transforming elements that
map one sequence onto another one that also lies in .
The order of the stabilizer is obtained by just the number of transformed sequences
that lie in .
From the orbits on 4sets we can in a further step get the orbits on 5sets.
If a 5set is given, then one can form 5 partitions
into a sequence of a 4set and the remaining element. Transform by
the same element of that maps onto its canonical representative .
Then the stabilizer of may map the transformed point onto a smaller one.
Choose the smallest one to get a representative on the set of all partitions
of a 5set into two components of sizes 4 and 1.
The stabilizer will be trivial in the case where we know in advance that already the
stabilizers of all 5sets are trivial. So, then we need not compute them in this case.
We will get 5 different orbits of partitions that fuse to the same 5set. The smallest
of them defines the canonical representative for our 5set.
The discussion yields the following result.
Definition
For a sequence of 4 pairwise different 1dimensional subspaces of
let the crossratio of and the square indicator of
be defined by the following table.









Theorem
Let be a sequence of 4 pairwise different 1dimensional subspaces
of .
Then the orbit of under is uniquely determined by .
The sequence is transformed into normal form
by the matrix
If 4 divides then the orbit of under is uniquely determined by
and .
The sequence is transformed into normal form
by the matrix
Using these formulae the time complexity of determining the orbit of a 4element sequence of pairwise different 1dimensional subspaces is dominated by forming a constant number of arithmetic operations and deciding whether some number is a quadratic residue modulo . The last problem can be solved in time using the Gauß reciprocity formula, [19], by a strategy similar to Euclid's gcd algorithm.
For a small prime and many tasks of computing canonical forms it is a better strategy to first set up tables of squares and of inverses in linear time and then for each canonical form computation using only constant time.
.
Remarks
The next open case is .
For prime powers there are further results.
There exist at least isomorphism types of  designs
with automorphism group
[5].
Besides that there exists one  design with automorphism group
.
Most remarkable are the partitionable Steiner systems consisting of orbits
of the same size.
We have obtained exactly 1 isomorphism type for a prescribed stabilizer
and and exactly 7 isomorphism types
for .
The next case would be
v = 228:
We would need 280 orbits with stabilizer or 140 orbits with trivial stabilizer
for a  design.
So, we need only half as many orbits if we prescribe a trivial stabilizer
as we need with stabilizer .
But there are by far too many orbits with trivial stabilizer to choose the 140 orbits from.
So, it might be easier to prescribe .
The total number of orbits on 6sets is 32300.
Out of these only 2070 have length
.
The number of 5orbits is 840. In the KramerMesner Matrix, reduced to these
6orbits, in each column there are exactly 3 entries 1 and all others are 0.
The effect of the space reduction by using only a sparse matrix can be seen with where prescribing stabilizer results in a matrix of
3234 5orbits by 8028 6orbits. The full matrix requires 52 MB
while the sparse matrix only needs 0.53 MB.
This problem size is far out of our present reach.
Next: Bibliography Up: Partitioned Steiner 5Designs Previous: Subgroups of order up N.N. 20020225