Prescribing a group of automorphisms
The intention is to reduce the incidence matrix to a much smaller matrix so that we can solve the corresponding diophantine system of equations by running a modern implementation of the LLL-algorithm on a workstation or a personal computer. To achieve this goal we use the concept of finite group actions and the prescription of a group of automorphisms (similar to the methods we use in the above mentioned research project on the construction of classical -designs). Of course, this prescription is risky since there may be no designs with that particular group of automorphisms, but if there are such designs then it will pay since the number of rows of the incidence matrix, which is the number of -subspaces in , will reduce to the number of orbits of that group, and the same holds for the number of columns. This will bring the construction problem within reach of computers!
An automorphism of a -design is an element of the general linear group which leaves the design invariant, i. e. it maps blocks onto blocks, it permutes the design:
A group consisting only of automorphisms of is an automorphism group of , the maximal group with this property is called the (full) automorphism group of The crucial facts are now as simple as this:
2.1 Remarks If is an automorphism group of the -design then
- consists of full orbits of We may therefore restrict our attention to the orbits of
- The inclusion of -spaces in -spaces is invariant under the action of
- Therefore, for and the number of in the orbit of which lie above is constant on the orbit of
- This number is a sum of values of the -function on the lattice of subspaces of and we shall denote it as follows:
This embeds this problem into the theory of group actions on posets (cf. ) and it motivates the introduction of the matrix , a -analog of the Kramer-Mesner matrix () for standard combinatorial designs on sets. Its rows (resp. columns) are indicated by the elements (resp. ) of a transversal of the set of orbits of on (resp. of a transversal of the set of orbits of on ), and the entries are the above mentioned values
The following theorem is now immediate from the above remarks:
2.2 Theorem The set of -designs having as an automorphism group can be obtained from the 0-1-vectors solving the linear system of equations
in the following way:
This method of generalizing the Kramer-Mesner approach to -analogs of designs was already used in , but the derivation of 2-designs which admit which is given there, uses ad hoc methods which cannot be used in the general case. We are therefore going to describe now a general approach that can be used, in principle, in any case. The first step in this direction is the evaluation of transversals of the sets of orbits
2.3 The Fundamental Lemma If
denotes a finite group action, and a subgroup of then, for each the set of orbits of on can be mapped bijectively onto the set of -double cosets:
where means the stabilizer of in
In order to apply it we use the fact that the general linear group is transitive both on and on and so the following is true:
2.4 Corollary We can obtain the desired transversals of the orbit sets of from transversals of sets of double cosets by reverting the following bijections
where and are (arbitrary but fixed) elements of respectively, while and denote their stabilizers in the full linear group.
For and , respectively, we can take the subspaces generatedby the , respectively first unit vectors, and The corresponding stabilizers and consist of the nonsingular matrices with a box of zeros of size and in the lower left hand corner.
All what remains is the determination of transversals of the sets of double cosets and . For this purpose we use a generalization of the ladder game introduced by B. Schmalz in ,, in order to construct designs on sets.