Welcome to DISCRETA.
DISCRETA is a program for the construction of incidence structures,
t-designs, with prescribed automorphism group.
A t-design, or more precisely a t-(v,k,l) design
for integers t, v, k and l, is a finite incidence structure, i.e.
a finite set of points together with a set of subsets.
More precisely, a t-design is a pair
(*P*,*B*) with *P* a set of v points, and *B*
a set of k-subsets of *P*.
The set *B* has the property that whichever t-subset of *P*
is chosen, there are exactly l sets in *B* containing the
chosen set of t points.
The sets in *B* are also called blocks.
Hence for any t-subset of points we find exactly l blocks
containing them.

The idea to construct such incidence structures is
by means of a prescribed automorphism group.
An automorphism is just a permutation of the set of points such that
when applied to each of the blocks, the set of blocks as a whole is preserved.
Here, when we say, we apply a permutation to a block, we mean that we
apply the permutation to all point in the block.
We then collect all the k points which we get
and form a new block of size k out of these
(we call this the image of the original block under the given permutation).
Of course for a permutation to be an isomorphism,
each image block must be contained in *B* since we required that
the set of blocks as a whole stays invariant under that permutation.
Now, the set of such automorphisms form a group w.r.t. composition.
This means for elements a and b which are automorphisms,
the composition ab is again an automorphism.
Also, the inverses a^{-1} are automorphisms.
The identity mapping which takes each point to itself is trivially an
automorphism. It serves as the identity element in the automorphism group.

Why do we do all this? Well, the construction of t-designs can be a hard task, in particular for certain parameter combinations. t-designs with large t are known to be notoriously hard to construct. At this point, Kramer and Mesner in 1975 introduced their method of constructing designs which are invariant under a group of automorphisms. The clue is that the construction of designs using a prescribed automorphism group becomes much easier the larger the group is. We do not give the details of this construction, but rather go back to DISCRETA and explain how to use this program for this method.

At this point, we see two basic steps in the construction of designs.

- First, we have to fix a set of parameters t, v, k and l of the design we wish to construct. In addition, and rather more at the same time as fixing the parameters, we have to choose a group which shall serve as automorphism group of the design. Of course, the group should be a permutation group on v points, since our design will have v points. The group should have the right size for the problem, i.e. its order should somehow match the difficulty of the problem, since otherwise we may not be able to construct designs at all. Of course, it is a difficult task to choose the right group and often we have to try several possibilities. Let us denote the group we have chosen by G.
- Secondly, we finally got to construct the designs which are invariant under the group G chosen in the first step. This is where the parameters t and k come into play (recall that we have chosen all parameters in the first step). We compute a matrix which is determined by the choice of the group and the choice of t and k (so far, the last parameter l is not yet considered). In honor of Kramer and Mesner's contribution, this matrix is called the Kramer Mesner matrix of the construction. Once the Kramer Mesner matrix is there, the last parameter l comes in and we form a diophantine system of equations with the Kramer Mesner matrix on the left, and a vector whose entries are all l on the right. The system has to be solved for another integer vector, but this time we are restricted to the integers zero and one. The solutions to this system are in one-to-one correspondence to the t-(v,kj,l) designs with prescribed automorphism group G. (i.e. all the designs which are invariant under G).

As described previously, we have to choose parameters t, v, k and l
as well as a permutation group G acting on v points.
First of all, we have t < k < v positive integers.
In order to be successfull, the design parameret set
t-(v,k,l) must satisfy one combinatorial condition.
This condition is on l in terms of the other three parameters.
More precisely, there are two numbers, Dl and l_{max},
depending only on t, v and k,
and l must be a multiple of Dl
but less than l_{max}.
Note that these conditions are only necessary conditions, in other words,
we wouldn't find designs if the condition is violated.
The conditions are not sufficient for the existence of designs.
Note that the condition l not equal l_{max} just excludes the
trivial designs, which consist of all k-subsets of the set of points,
which are always t-designs, but at the same time are not very interesting
(just because we know they exist for all t < k < v).
A design parameter set which satisfies this condition is called admissible.

DISCRETA helps choosing l by computing Dl once t < k < v have been chosen. Let us have a look at the DISCRETA main window:

The discreta_batch calc_lambda_ij 7 33 8 1 calc_lambda_ij t v k lambda calc_delta_lambda(): v=33 t=7 k=8 lambda=1 t'=6 lambda'=27/2 delta_lambda=2 t'=5 lambda'=126/1 delta_lambda=2 t'=4 lambda'=1827/2 delta_lambda=2 t'=3 lambda'=5481/1 delta_lambda=2 t'=2 lambda'=56637/2 delta_lambda=2 t'=1 lambda'=129456/1 delta_lambda=2 t'=0 lambda'=534006/1 delta_lambda=2 warning: this parameter set is not admissible, lambda must be a multiple of 2 !What has happened? Your input amounts to the parameters t-(v,k,1), i.e. with lambda = 1. DISCRETA computes the parameters of the design as an t' design for 0 less or equal t' less than t. The resulting poarameter sets t'-(v,k,lambda') should all be integral, and Delta lambda will be computed as the smallest natural number lambda such that all lambda' are integral. In this case, DISCRETA detects that lambda must be a multiple of Delta lambda, which is 2. Note that if you would have started with an admissible parameter set like 7-(33,8,10), the output would be

calc_lambda_ij t v k lambda calc_delta_lambda(): v=33 t=7 k=8 lambda=1 t'=6 lambda'=27/2 delta_lambda=2 t'=5 lambda'=126/1 delta_lambda=2 t'=4 lambda'=1827/2 delta_lambda=2 t'=3 lambda'=5481/1 delta_lambda=2 t'=2 lambda'=56637/2 delta_lambda=2 t'=1 lambda'=129456/1 delta_lambda=2 t'=0 lambda'=534006/1 delta_lambda=2 5340060 4045500 3034125 2251125 1650825 1195425 853875 600875 1294560 1011375 783000 600300 455400 341550 253000 0 283185 228375 182700 144900 113850 88550 0 0 54810 45675 37800 31050 25300 0 0 0 9135 7875 6750 5750 0 0 0 0 1260 1125 1000 0 0 0 0 0 135 125 0 0 0 0 0 0 10 0 0 0 0 0 0 0This time, DISCRETA does not complain, and you find the parameter sets t'-(v,k,lambda') for 0 less or equal t' less than 7. Also, DISCRETA lists some more parameters which are tabulated in form of a matrix. These are the lambdai,j for i+j less or equal t (and zeroes elsewhere). The value of lambdai,j is the number of blocks in the design which contain a given set of i points and which are disjoint from another given set of j points, provided that the two sets are disjoint and that i + j is at most t.

Let us now describe how to choose a group, by which
we mean a group together with a permutation representation.
First, go into the *Group* menu and choose *Choose prescribed automorphism group*.
The main group selection dialog will appear:

Let us describe now how to construct a group. Most impartant are the
five buttons in the top row, labelled *well known*,
*linear*, *sporadic*, *solvable* and *reg. solid*.
Each of these opens another dialogue, where certain pre-defined permutation groups
can be chosen.
Consider the first one *well known*. After clicking on the button,
the dialogue

Let us go back to the group selection dialogue.
The next button entitled *linear* opens the dialogue

Back in *group selection,* the next button entitled *sporadic* opens the dialogue

The fourth button in *group selection,* entitled *solvable* opens the dialogue

The last button in *group selection,* entitled *reg. solid* opens the dialogue

After choosing a group G by specifying a recipe in the group selection dialogue,
and after pressing the button *choose* and successfully constructing the group,
we will see the name of the group, the permutation degree, and the group order in
the three fields *group*, *v* and *order* in the DISCRETA main window.
From now on, G is fixed.

In case that we have chosen a symmetry group of an Euklidean object,
we may decide to actually see this object itself.
For this, we go into the *Group* menu again and choose *show solid*.
Another window opens up, displaying the object in 3D-space, for instance as

Any time you have defined a group, you may choose to investigate its subgroup lattice.
For this, go into the *Group* menu again and choose
*calc subgroup lattice: w.r.t. inner automorphisms*.
You may wish to invoke this funtion only for groups of moderate size (i.e. at most a few thousand elements),
since otherwise the computation becomes too time and memory intense.
Assume we still have the group of the Dodecahedron, which is isomorphic to A_{5}.
Then coosing the button results in a small computation, which can be traced in the terminal window.
The final output looks like

{1,3,3,1,1} 9 {1,31,21,5,1} 59 computation of subgroup lattice finished.The two rows of numbers correspond to the number of conjugacy classes of subgroups (first row) and the number of subgroups (second row) in each layer of the subgroup lattice. The layers are determined by the number of prime factors (including multiplicities), dividing the order of a subgroup. the layers are listed in brackets, going up from layer 0 (the trivial subgroup) to the highest layer (the group itself). Afterwards, the total number is given.

In order to actually see the subgroup lattice, go into the *Group* menu again and
choose *show subgroup lattice, Burnside matrix*.
A latex document will be prepared and translated autopmatically.
If you browse this document, you may find on the second page
a graphical display of the subgroup lattice.
In case of the group of the Dodecahedron, A_{5}, we obtain:

At the beginning of Step 1, we chose the design parameters t-(v,k,lambda).
Indeed, the parameter v turned out to be the degree of the
permutation group G we have chosen to prescribe.
So far, the other three parameters did not come in, but this will change in a minute.
In order to construct a design which is invariant under G
we apply the method of Kramer and Mesner which allows to describe such designs as 0/1 solutions
of certain integral systems of equations.
The coefficient matrix of this system has already been introduced as the Kramer Mesner matrix.
This matrix depends on G and on the parameters t and k, and hence we denote it as Mt,k^{G}.
The rows are indexed by the orbits of G on t-subsets, whereas the columns are indexed
by the orbits of G on k-subsets (of 1,...d, of course).
The matrix entry corresponding to a t-orbit T^{G}
and a k-orbit K^{G} is the number of elements K' in
the orbit K^{G} which contain T.
In order to compute Mt,k^{G}, we first specify G, which we already did in Step 1.
We now put in the values of t and k into the corresponding text fields in the main window.
After that, we choose *compute Kramer Mesner matrix* from the *Kramer-Mesner* menu
to actually compute the matrix Mt,k^{G}. The actual computation
produces some output in the text window. The orbits of G on sets of size at most k are
computed by an induction on the size of the sets.
In the end, a file is created containing all the data from the computation.
The filename starts with "KM_", then comes the name of the group, and after that the
values of t and k in the format t`value of t'_k`value of k'.
The extension is ".txt".
We call this the KM-file.
Its name appears in the *file* text field in the main window.
We may want top have a look into that file.
For this, we choose *show matrix* in the *Kramer-Mesner* menu.
We may have to scroll within the larg text field in the bottom half of the DISCRETA window,
to find the actual contents of the file.
We are now ready to construct the designs.
We choose lambda and enter the value into the *lambda* text field.
Then we choose *LLL* in the *Solve* menu.
We get information about the existence or nonexistens of solutions in the terminal window.
Note that DISCRETA always trues to compute the *complete set of solutions,*
i.e. the number which is given (if the program terminates successfully)
is the exact number of designs
with that prescribed automorphism group.
Note, however, that this does not give the number of isomorphism types of designs.
That number is to be determined later.
In order to be able to work with these solutions later on, we choose *get solutions from solver*
in the *Solver* menu, which copies the solution vectors into the KM-file.

Example: Assume we want to construct designs invariant under PGGL(2,32). We go into the group selection dialog and from there into the dialog for linear groups. We fill in n = 2 and q = 32 and click on PGGL:

% m, n: 3 13 4 4 8 4 4 4 0 0 0 0 0 0 0 5 5 5 0 0 0 5 1 5 1 1 0 0 1 4 3 2 5 2 2 1 2 1 1 3 1We know choose lambda = 12 (If we don't know what to choose we can ask the

0010100110100 L = 12 0010101001100 L = 12 0010100011100 L = 12 0010101101000 L = 12 0010100111000 L = 12 Prune_cs: 103 Prune_only_zeros: 4 of 106 Prune_hoelder: 0 of 102 Prune_N: 1 Fincke-Pohst: 2 Loops: 265 Total number of solutions: 54 calling ... tail -10 lll.log >lll.log.1 finished !In this case we have 54 solutions, all of which are displayed as 0/1 vectors (we show only the last 5 of them here). We finally choose

File translated from T

On 1 Jul 2003, 21:23.