´

Next: Bibliography Up: Partitioned Steiner 5-Designs Previous: Subgroups of order up

# Invariants

Each of the stabilizers of order 6 acts transitively on any invariant 6-set . So, there is only one 5-set orbit on . Correspondingly, the column for in the Kramer-Mesner matrix has only one entry 1 and all other entries are 0. So, in these cases, we easily determine the entries of the Kramer-Mesner matrix in these columns. The remaining cases are more complicated. Here we use Alltop's Lemma. That requires for each 5-set contained in a representative of a 6-set orbit with stabilizer to find out the 5-set orbit of . We do this by computing an invariant which separates the 5-set 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 k-set.

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 cross-ratio of geometry. The group acts 3-transitive on the projective line and regular on 3-sequences of pairwise different 1-dimensional 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 4-sequence the image of the fourth point after normalizing the first 3-element 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 3-sequences and then uses the image of the fourth point one again has an invariant. We use this for . This group is 2-transitive 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 non-squares.

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 5-set as the representative of .

Of course this could be done as well for any -sets. But for larger we get too many 4-sets contained in a -set. So, for and our special goal of finding Steiner systems we here make use of the following observation. If a 6-set is contained in an orbit that already occured then the 5-orbits it covers are already covered by the earlier found representative. In terms of the Kramer-Mesner 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 6-sets from different orbits produce identical columns of the Kramer-Mesner 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 1-dimensional 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 1-dimensional 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 4-sequence 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 1-dimensional subspaces must fix all 1-dimensional 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 3-sequences 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 cross-ratio 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 1-dimensional 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 non-square 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 3-element sets of 1-dimensional subspaces are in one orbit. This means that is 3-homogeneous.

For our goal of normalizing a given sequence of 1-dimensional 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 cross-ratio 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 cross-ratio 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 non-quadratic residue modulo . So, if then the invariant is the product of the cross-ratio and the Legendre symbol.

Using this invariant, the orbit of a 4-sequence 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 4-element subsets instead of sequences. They can be obtained from the sequences by the fusion version of the homomorphism principle. A given 4-set 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 4-element subset the canonical representative of its orbit and a matrix which does this transformation.

A slight variation should be made when many 4-sets 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 non-square. 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 4-sets we can in a further step get the orbits on 5-sets. If a 5-set is given, then one can form 5 partitions into a sequence of a 4-set 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 5-set 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 5-sets 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 5-set. The smallest of them defines the canonical representative for our 5-set.

The discussion yields the following result.

Definition For a sequence of 4 pairwise different 1-dimensional subspaces of let the cross-ratio of and the square indicator of be defined by the following table.

 1 if is a quadratic residue -1 else
 1 if is a quadratic residue -1 else
 1 if is a quadratic residue -1 else
 1 if is a quadratic residue -1 else
 1 if is a quadratic residue -1 else

Theorem Let be a sequence of 4 pairwise different 1-dimensional 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 4-element sequence of pairwise different 1-dimensional 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 6-sets is 32300. Out of these only 2070 have length . The number of 5-orbits is 840. In the Kramer-Mesner Matrix, reduced to these 6-orbits, 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 5-orbits by 8028 6-orbits. 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 5-Designs Previous: Subgroups of order up
N.N. 2002-02-25

University of Bayreuth -