Anton Betten

    The DISCRETA - GAP Interface

    Abstract:
    We describe the commands which are available in the DISCRETA-GAP interface. The interface is available for both versions of GAP (GAP3 and GAP4). The two versions differ slightly.

    The Basic Concept

    The DISCRETA GAP interface shall combine the general purpose system for computational group theory GAP with the special purpose system DISCRETA for constructing t-designs with prescribed automorphism group. Using this interface, it is possible to combine the huge functionality of the command line driven system GAP with the efficiency of the plain C++ program DISCRETA. Most of the code for constructing t-designs is written in DISCRETA (in C++). Using its Motif interface, the DISCRETA program is easy to use. However, the idea behind the GAP interface was to make everything available also from the GAP command prompt. Most of the functionality and all of the data should be available for the GAP user. In GAP, one types in plain commands instead of pressing buttons. This does not seem attractive at first sight but the variety of group theoretic functions make GAP a very powerful system. Second, one can use the GAP language to perform small programming tasks on top of DISCRETA. By this we mean that for example a loop over all possible values of lambda for solving the equations is no problem in GAP (it can be a problem in the graphical user interface if the number of different values of lambda becomes large).

    The concept of the GAP interface is the following. We still have DISCRETA running in compiled C++ code, but now driven by the GAP command prompt. This means that one has to learn a lot of commands but on the other hand one is free to combine those function calls to new powerful programs. The system works as follows: we have the DISCRETA code compiled into a batch program (called discreta_batch) which takes all its input from the command line and writes its result into files readable for GAP. Sometimes, input files in plain ASCII are provides for the batch program. The syntax of the arguments for the batch program is complicated and is of no interest for the end-user. The discreta batch program collaborates with the gap part of the interface, which is simply a collection of GAP routines forming the other end of the discreta_batch GAP cooperation. This set of functions is contained in the file "discreta.g".

    The Commands

    • Read("discreta.g");
    • discreta();
    • calc_delta_lambda(v, t, k);
    • compose_group(string);
    • GeneratorsPermGroup(grp, fname, deg);
    • compute_KM(g_label, t, k);
    • get_KM_matrix(km, t, k);
    • get_generators(km);
    • get_vtk(km);
    • get_orbit_representatives(km);
    • get_stabilizer_orders(km);
    • calc_orbit_length(stabilizer_order, gg);

    • do_LLL(km, lambda);
    • do_LLL1(f_with, KM_fname, c0, beta, p, lambda);
    • do_McKay(km, lambda);
    • get_solutions_from_solver(km, lambda);
    • get_number_of_solutions(km, lambda);
    • get_solutions(km, lambda, first, number_of_solutions);
    • get_designs(km, lambda, first, number_of_solutions);
    • span_design(grp, bb);
    • design_orbits(solution_vector);
    • check_solutions(km, lambda);
    • report(km);

    • get_plesken_matrix(km, t, k);
    • get_plesken_matrix_with_inverse(km, t, k);

    • action_on_blocks(km, i, perm);
    • fuse_orbits(km, group_fname, k);
    • fuse_orbits_by_representatives(rep, group_fname, k);

    • transversal_of_isomorphism_types(km, lambda);
    • write_bb_file(KM_fname, bb_fname, lambda, from, len);
    • geo_db_build_from_bb(generators_fname, bb_fname, db_prefix, f_create);
    • geo_db_get_ids(db_prefix);

    • export_magma_designs(fname, t, v, designs, magma_variable);
    • build_incidence_matrix(v, blocks);
    • export_designs_inc(fname, v, DD);

    Read("discreta.g");

    This reads in the GAP-part of the interface, "discreta.g". This must always be the first command!

    discreta();

    This function starts the MOTIF DISCRETA interface. The GAP prompt is lost!

    calc_delta_lambda(v, t, k);

    Computed $\Delta \lambda$ out of the integers $v, t$ and $k$. For a t-(v,k,lambda) design to exist, lambda must be a multiple of delta lambda!.

    compose_group(string);

    Builds a permutation group. There are a lot of ways to construct groups in DISCRETA. All of them are available through this function. string is a space separated string containing commands for constructing groups. The commands are as follows:

      Linear Groups:

    • PSL n q = projective special linear group of dimension n over the galois-field GF(q)
    • PGL n q = projective linear group of dimension n over the galois-field GF(q)
    • PSSL n q = projective special semi-linear group of dimension n over the galois-field GF(q)
    • PGGL n q = projective semi-linear group of dimension n over the galois-field GF(q)

      Well Known Groups:

    • S n = symmetric group on n points
    • A n = alternating group on n points
    • D n = dihedral group on n points
    • C n = cyclic group on n points
    • HolC n = holomorph of cyclic group on n points
    • Id n = trivial group on n points
    • HolCsubgroup n i = subgroup of holomorph of cyclic group on n points (of index i)
    • SnwrSm n m = wreath product of S_n with S_m

      Sporadic Simple Groups:

    • M11 = Mathieu group M11
    • M12 = Mathieu group M12
    • M23 = Mathieu group M23
    • M24 = Mathieu group M24
    • HS176 = Higman Sims group on 176 points

      Other Constructions:

    • file file_name = read generators form file

      Unary Operations:

    • [2] = induction on 2-subsets (degree ${n \choose 2}$)
    • (2) = induction on 2-tuples (degree $n^2$)
    • [2]i = induction on injective 2-tuples = ordered pairs (degree $n(n-1)$)
    • [3] = induction on 3-subsets (degree ${n \choose 3}$)
    • + = add a fixedpoint (in front)
    • - = stabilize first point (and remove the stabilized point)

      Binary Operations:

    • , = concatenate two generating systems
    • x = form the dirct sum of two permutation groups on disjoint sets
    • X = form the dirct product of two permutation groups on tuples $(a,b)$
    • wr = form the wreath product of two permutation groups
    • exp = form the exponential group of two permutation groups
    • ON_MAPPINGS = act on mappings

    Return Values:
    This function returns a vector containing two strings. The first string is a label for the group in ASCII, the second is the corresponding label in tex.

    Example 1: 

    gap> label := compose_group("PGGL 2 32");
discreta_batch compose_group discreta_batch_output.g discreta_tmp PGGL 2 32 
[ "PGGL_2_32", "{\rm P}Gamma {\rm L}_{2}(32)" ]
gap> g_label := label[1];
"PGGL_2_32"
gap> g_label_tex := label[2];
"{\rm P}Gamma {\rm L}_{2}(32)"
gap>

    Example 2: 

    gap> label := compose_group("PSL 2 17 C 2 X");
discreta_batch compose_group discreta_batch_output.g discreta_tmp PSL 2 17 C 2\
 X 
[ "PSL_2_17C2X", "{\rm PSL}_{2}(17){\bf C}_{2}\times" ]
gap>
    This composes a group on 36 points of order 4896, isomorphic to PSL(2,17) acting diagonally on 2 x 18 points.

    Example 3: 

    gap> label := compose_group("M12 -");
discreta_batch compose_group discreta_batch_output.g discreta_tmp M12 - 
[ "M12-", "{\bf M}_{12}-" ]
gap>
    Composes the point stabilizer of M12, that is, M11 of order 7920 on 10 points.

    Example 4: 

    gap> label := compose_group("file s5.txt");
discreta_batch compose_group discreta_batch_output.g discreta_tmp file s5.txt 
[ "file_s5.txt", "{\rm file s5.txt}" ]
gap>
    Reads the generators from a given file, here s5.txt. The format of this file is easy. The first integer is the number of generators r, the second integer is the degree d and the following r * d integers contain the images of 1..d under the r generators (as numbers from 1 to d). Here an example, defining S_5: 
    2 5
2 1 3 4 5
2 3 4 5 1
    This file is format free, that is whitespace characters may occur in arbitrary manner.

    GeneratorsPermGroup( grp, fname, deg);

    Writes generators for the GAP permutation group grp in DISCRETA format into the file fname. deg must be the degree of the group.

    compute_KM(group_label, t, k);

    Computes the Kramer-Mesner matrix for a given group and for integer parameters t and k (with $0 \le t \lt k \le d$, where $d$ is the degree of the permutation group). The result is written on a file (called KM-file) whose name is generated from the input parameters in the following way:

    KM_[group]_t[t]_k[k].txt

    where [group] is the label of the group and [t] and [k] stand for the values of t and k, respectively.

    Return Values:
    This function returns the name of the corresponding KM-file as a string

    Example:
    let g_label be "PGGL_2_32" from Example 1. 

    gap> km := compute_KM(g_label, 5, 6);
discreta_batch compute_KM discreta_batch_output.g discreta_tmp PGGL_2_32 PGGL_\
2_32 5 6 1 
"KM_PGGL_2_32_t5_k6.txt"
gap>
    Computes the Kramer-Mesner matrix for t=5, k=6 and the previously constructed group "PGGL_2_32". The KM-file which is created has the name KM_PGGL_2_32_t5_k6.txt. This file looks as follows: KM_PGGL_2_32_t5_k6.txt This file contains the following information:
    • a header containing general information about the group and the parameters of the design. Generators for the group are listed. 
      % this file:    KM_PGGL_2_32_t5_k6.txt
% group:        PGGL_2_32 
% group:        PGGL_2_32 
% order:        163680 
% degree:       33 
% # generators: 5 
% (3 4 6 10 18 7 12 22 15 28 19 9 16 30 31 33 29 21 5 8 14 26 23 17 32 27 25 13 24 11 20)
% (3 20 11 24 13 25 27 32 17 23 26 14 8 5 21 29 33 31 30 16 9 19 28 15 22 12 7 18 10 6 4)
% (2 3)(4 5)(6 7)(8 9)(10 11)(12 13)(14 15)(16 17)(18 19)(20 21)(22 23)(24 25)(26 27)(28 29)(30 31)(32 33)
% (1 3)(4 31)(5 21)(6 24)(7 10)(8 15)(9 17)(11 25)(12 19)(13 26)(14 16)(18 27)(20 30)(22 29)(23 33)(28 32)
% (4 6 18 15 29)(5 7 19 14 28)(8 22 31 24 27)(9 23 30 25 26)(10 12 16 32 21)(11 13 17 33 20)
% t, k:
% 5 6
    • The Kramer-Mesner matrix: 
      % m, n:
3 13
5 5 5 5 5 1 1 1 0 0 0 0 0 
0 4 4 8 0 0 0 0 4 4 4 0 0 
2 1 4 3 2 1 1 1 2 5 2 3 1
    • finally, the file contains some coded data, for example generators for the group 
      GENERATORS
ASCII 202
572050600<12102040608000:0<0>0012141618100:1<1>1027090305000?011;0=07191315170?1
12;1=160001210204130514021005031608170918061009071:0<1;0=1<0:100=0;1>002?01201>1
<111?160121000302050407060908000;0:0=0<0?0>0110100312151417161918100;1:1=1<1?1>1
120207601230201000?15181:0?01170910031:10180>090;1<000>150=11260;0=0211002614140
<171600<1210203060700021316171<0=0011100<1=10212?0>0;0:000?1>1;1:190805040009181
5141
ASCIIEND
    • representatives for the $i$-orbits 
      SET-REPRESENTATIVES
ASCII 240
572070207=1020>8101020108;20101010:3102010200>2010101020572010200<30101010203057
2010200<401010102030:3402030200>5010101020>030407020500010101020304050200>501010
1020>030408020=08;2060101010102030407001200<601010102030>04050602060001010102030
4050:00720601010103020304050>0200860101010203040<170<02060100010102030407071200>
601010102070304070;12000601010102030407083>020601010101020304050>1200<6010101020
30>040506120600010101020304050210720601010103020304080>0200860101010203040008012

ASCIIEND
    • stabilizer orders of all orbits 
      STABILIZER-ORDERS
ASCII 40
372051109120?7063106=91063>1==4050==4010==2020==1010==2050==5050==2010==20200<60

ASCIIEND
    • stabilizer orders of $k$-orbits in ASCII: 
      STABILIZER-ORDER-K-SETS
2 2 1 1 2 5 5 5 2 1 2 2 6
    • And coded KM-matrices: 
      KM-MATRICES
ASCII 81
572060;0<=101010=11012;0101<10101002;0<=101010=110?1;0101<101010>1;0<=3010107010
405041;007=03010105010505050501010108?4040801?4040400820104030201010001020502030
10
ASCIIEND
    • then, there may be an additional version of the KM-matrix which has its rows and columns permuted in some specific way. This is the so called "TDO-form" of the KM-matrix. 
      %
% TDO decomposition:
3 13
8 4 4 4 0 0 4 4 0 0 0 0 0 
5 5 5 0 5 5 0 0 0 1 1 1 0 
3 4 1 5 2 2 2 2 3 1 1 1 1 

%
% row decomposition:
% 1 1 1 
%
% column decomposition:
% 1 1 1 1 2 2 1 3 1 
%
% row permutation:
% 2 1 3 
%
% col permutation:
% 5 3 2 1 6 10 11 12 7 4 8 9 13
      The decompositions of rows and columns give hints about possible KM-matrix automorphisms.

    get_KM_matrix(km, t, k);

    Retrieves the KM-matrix for given t and k from the KM-file. t and k must not be the same as when the KM-file was computed but we must have $0 \le t \le k \le k_0$ (where k_0 is the value of k when the KM-file was created).

    Example: 

    gap> M := get_KM_matrix(km, 5, 6);
discreta_batch get_KM_matrix KM_PGGL_2_32_t5_k6.txt discreta_batch_output.g di\
screta_tmp 5 6 
[ [ 5, 5, 5, 5, 5, 1, 1, 1, 0, 0, 0, 0, 0 ], 
  [ 0, 4, 4, 8, 0, 0, 0, 0, 4, 4, 4, 0, 0 ], 
  [ 2, 1, 4, 3, 2, 1, 1, 1, 2, 5, 2, 3, 1 ] ]
gap>

    get_generators(km);

    Retrieves the generators for the group from the KM-file.

    Example: 

    gap> g := get_generators(km);
discreta_batch get_generators KM_PGGL_2_32_t5_k6.txt discreta_batch_output.g d\
iscreta_tmp 
[ ( 3, 4, 6,10,18, 7,12,22,15,28,19, 9,16,30,31,33,29,21, 5, 8,14,26,23,17,32,
     27,25,13,24,11,20), ( 3,20,11,24,13,25,27,32,17,23,26,14, 8, 5,21,29,33,
     31,30,16, 9,19,28,15,22,12, 7,18,10, 6, 4), 
  ( 2, 3)( 4, 5)( 6, 7)( 8, 9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)
    (22,23)(24,25)(26,27)(28,29)(30,31)(32,33), 
  ( 1, 3)( 4,31)( 5,21)( 6,24)( 7,10)( 8,15)( 9,17)(11,25)(12,19)(13,26)
    (14,16)(18,27)(20,30)(22,29)(23,33)(28,32), 
  ( 4, 6,18,15,29)( 5, 7,19,14,28)( 8,22,31,24,27)( 9,23,30,25,26)
    (10,12,16,32,21)(11,13,17,33,20) ]
gap> gg := Group(g, g[1]^0);
Group( ( 3, 4, 6,10,18, 7,12,22,15,28,19, 9,16,30,31,33,29,21, 5, 8,14,26,23,
 17,32,27,25,13,24,11,20), ( 3,20,11,24,13,25,27,32,17,23,26,14, 8, 5,21,29,
 33,31,30,16, 9,19,28,15,22,12, 7,18,10, 6, 4), ( 2, 3)( 4, 5)( 6, 7)( 8, 9)
(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25)(26,27)(28,29)(30,31)
(32,33), ( 1, 3)( 4,31)( 5,21)( 6,24)( 7,10)( 8,15)( 9,17)(11,25)(12,19)
(13,26)(14,16)(18,27)(20,30)(22,29)(23,33)(28,32), ( 4, 6,18,15,29)
( 5, 7,19,14,28)( 8,22,31,24,27)( 9,23,30,25,26)(10,12,16,32,21)
(11,13,17,33,20) )
gap> Size(gg);
163680
gap>

    get_vtk(km);

    Returns the parameters v, t and k as a vector [v,t,k].

    get_orbit_representatives(km);

    Retrieves a vector $k+1$ components. This vector contains the vector of orbit representatives of $i$-orbits in its $i+1$-th component.

    Example: 

    


    


     get_stabilizer_orders(km); 
     
     


Retrieves a vector $k+1$ components. 
This vector contains the vector of stabilizer orders of 
$i$-orbit representatives in its $i+1$-th component.


    

Example:

    


    



     calc_orbit_length(stabilizer_order, gg); 
     
     

    

Example:

    


    



     do_LLL(km, lambda); 
     
     

This function calls the LLL-solver of 
Alfred Wassermann
for a given 
KM-file and a given integer lambda. The 
KM-file is specified as a string (in this case km) holding the filename.


    

Return Values: 
    
This function returns nothing. The solution vectors are stored in a file "solution" in the 
current directory (as 0,1 vectors in ASCII). These solutions can be 
transfered into the KM-file by a call to get_solutions_from_solver.

    

Example:
We may assume that km holds the string "KM_PGGL_2_32_t5_k6.txt" 
from the previous example. 

    gap> do_LLL(km, 12);
discreta_batch do_LLL 1 KM_PGGL_2_32_t5_k6.txt 20 120 14 12 
gap> 

    
This call computes the 54 solutions corresponding to 5-(33,6,12) designs 
with PGGL(2,32) as automorphism group. 



     do_LLL1(f_with, KM_fname, c0, beta, p, lambda); 
     
    


This function calls the LLL-solver of 
Alfred Wassermann
for a given 
KM-file and a given integer lambda. The 
KM-file is specified as a string (in this case km) holding the filename.


    

Compared to do_LLL (see above), this function takes the 
additional arguments f_with, c0, beta and p. 
All are integer parameters, f_with boolean. 
if f_with is true, the solution file will be written. 
c0, beta and p are parameters for the LLL part of the solver. 


    

Return Values: 
    
This function returns nothing. The solution vectors are stored in a file "solution" in the 
current directory (as 0,1 vectors in ASCII). These solutions can be 
transfered into the KM-file by a call to get_solutions_from_solver.

    

Example:

    





     do_McKay(km, lambda); 
     
     

This function calls the backtrack-solver of 
Brendan D. McKay
for a given 
KM-file and a given integer lambda. The 
KM-file is specified as a string (in this case km) holding the filename.
We may assume that km holds the string "KM_PGGL_2_32_t5_k6.txt" 
from the previous example. 


    

This function is an alternative to the LLL-solver.
This solver is good for small values of lambda and if there are only few rows in the 
Kramer-Mesner system. 


    

Return Values: 
    
This function returns nothing. The solution vectors are stored in a file "solution" in the 
current directory (as 0,1 vectors in ASCII). These solutions can be 
transfered into the KM-file by a call to get_solutions_from_solver.

    

Example:

    












     get_solutions_from_solver(km, lambda); 
     
     


This function reads the solutions from the file "solutions" and appends them 
to the KM-file km (km is the file name). The value lambda is stored 
with the solutions and there can be one set of solutions for each value of 
lambda in each KM-file.


    

Example:

    gap> get_solutions_from_solver(km, 12);
discreta_batch get_solutions_from_solver KM_PGGL_2_32_t5_k6.txt 12 
gap> 

    
Transfers the 54 solutions for lambda = 12 into the KM-file "KM_PGGL_2_32_t5_k6.txt".



    






     get_number_of_solutions(km, lambda); 
     
     


Retrieves the number of solutions stored in the KM-file for a given value of lambda

    

Example:

    gap> no := get_number_of_solutions(km, 12);
discreta_batch get_number_of_solutions KM_PGGL_2_32_t5_k6.txt discreta_batch_o\
utput.g discreta_tmp 12 
54
gap> 

    


    






     get_solutions(km, lambda, first, number_of_solutions); 
     
     



    

Example:

    gap> s := get_solutions(km, 12, 1, no);
discreta_batch get_solutions KM_PGGL_2_32_t5_k6.txt discreta_batch_output.g di\
screta_tmp 12 1 54 
[ [ 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0 ], 
  [ 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0 ], 
  [ 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0 ], 
  [ 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0 ], 
  [ 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0 ], 
  [ 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0 ], 
  [ 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0 ], 
  [ 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0 ], 
  [ 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0 ], 
  [ 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0 ], 
  [ 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0 ], 
  [ 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0 ], 
  [ 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0 ], 
  [ 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0 ], 
  [ 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0 ], 
  [ 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0 ], 
  [ 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0 ], 
  [ 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0 ], 
  [ 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0 ], 
  [ 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0 ], 
  [ 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0 ], 
  [ 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0 ], 
  [ 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0 ], 
  [ 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 ], 
  [ 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0 ], 
  [ 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 ] ]
gap> s[1];
[ 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0 ]
gap> M * s[1];
[ 12, 12, 12 ]
gap> 

    
We retrieve all 54 solutions (numbers 1-54) from the KM-file 
and store them in a vector s. We check the solutions s[1] 
by multiplying it from the right to the KM-matrix M. 


    





     get_designs(km, lambda, first, number_of_solutions); 
     
     

Gets the solutions in the interval [first..first+len-1] and spans the complete 
designs. 
Each design is returned as a list of blocks. See 
span_design for remarks on how the blocks of the design are ordered.


    


Example:

    


    


     span_design( grp, bb); 
     
     

Spans the design given by a list of base blocks in bb under the group in grp.
Returns a list of blocks of the design. 
The blocks come in the order of orbits of the base-block vector bb. 
Thus, they are not lexicographically ordered.
There is no relabelling of points so the resulting incidence 
matrices still have the original group as group of automorphisms.


    


Example:

    


    




     design_orbits(solution_vector); 
     
     

Converts a solution vector to a list of orbit indices.

    

Example:

    gap> s[1];
[ 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0 ]
gap> O := design_orbits(s[1]);
[ 0, 3, 5, 7, 8, 11 ]
gap> 

    


    



     check_solutions(km, lambda); 
     
     


Checks the solutions in the file "solutions"

    

Example:

    


    



     report(km); 
     
     

Produces a report for the given KM-file. The report will be written in Latex 
and instantly translated (it is Latex2e). The result is displayed on the screen 
using xdvi.

    

Example:

    


    



     get_plesken_matrix(km, t, k); 
     
     


Computes the Plesken matrix for given t and k from the KM-file. 
t and k must not be the same as when the KM-file was computed 
but we must have $0 \le t \le k \le k_0$ (where k_0 is the value of k 
when the KM-file was created).  


    

Example:

    gap> P := get_plesken_matrix(km, 5, 6);
discreta_batch get_plesken_matrix KM_PGGL_2_32_t5_k6.txt discreta_batch_output\
.g discreta_tmp 5 6 
[ [ 1, 0, 0, 5, 5, 5, 5, 5, 1, 1, 1, 0, 0, 0, 0, 0 ], 
  [ 0, 1, 0, 0, 4, 4, 8, 0, 0, 0, 0, 4, 4, 4, 0, 0 ], 
  [ 0, 0, 1, 2, 1, 4, 3, 2, 1, 1, 1, 2, 5, 2, 3, 1 ], 
  [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ]
gap> 

    


    




     get_plesken_matrix_with_inverse(km, t, k); 
     
     



    

Example:

    gap> P1 := get_plesken_matrix_with_inverse(km, 5, 6);
discreta_batch get_plesken_matrix_with_inverse KM_PGGL_2_32_t5_k6.txt discreta\
_batch_output.g discreta_tmp 5 6 
[ [ [ 1, 0, 0, 5, 5, 5, 5, 5, 1, 1, 1, 0, 0, 0, 0, 0 ], 
      [ 0, 1, 0, 0, 4, 4, 8, 0, 0, 0, 0, 4, 4, 4, 0, 0 ], 
      [ 0, 0, 1, 2, 1, 4, 3, 2, 1, 1, 1, 2, 5, 2, 3, 1 ], 
      [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ], 
  [ [ 1, 0, 0, -5, -5, -5, -5, -5, -1, -1, -1, 0, 0, 0, 0, 0 ], 
      [ 0, 1, 0, 0, -4, -4, -8, 0, 0, 0, 0, -4, -4, -4, 0, 0 ], 
      [ 0, 0, 1, -2, -1, -4, -3, -2, -1, -1, -1, -2, -5, -2, -3, -1 ], 
      [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ], 
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ], 
  [ 0, 1, 2, 3, 4, 5, 8 ], [ 1, 1, 1, 1, 1, 3, 13 ] ]
gap> 

    


    


















     action_on_blocks(km, i, perm); 
     
     

Assume that p normalises the group $G$ of the KM-file. Then g permutes orbits of $G$ 
for any $i$ in $0 \le i \le k$. This function computes the permutation representation of p 
on the orbits of size $i$.


    

Example:

    


    





     fuse_orbits(km, group_fname, k); 
     
     


    

Example:

    


    



     fuse_orbits_by_representatives(rep, group_fname); 
     
     


    

Example:

    


    




     transversal_of_isomorphism_types(km, lambda); 
     
     

This function computes a transversal of the isomorphism types of the 
designs for the given value of lambda which are contained in the KM-file 
whose name is specified in km.
The transversal is given back as a vector of integers. 
These integers are in the range from 0 to nos -1 where nos is 
the number of solutions for the given value of lambda. 
The 0/1-solution vectors whose indices are in the returned vector 
form the transversal of isomorphism types of designs. 


    

Note that this function computes a canonical labelling of all incidence matrices 
of designs described by the 0/1-solution vectors in the KM-file. 
This may take a while and is feasible only for designs whose number 
of points or blocks is less than a few hundred.
During the processing, a database holding the transversal of designs 
is built. Afterwards, the indices of the designs in the transversal 
are given back.


    

There are some temporary files in the current directory created by this routine.


    

Example:

    


    




     write_bb_file(KM_fname, bb_fname, lambda, from, len); 
     
     


This function write a base-block-file for the specified solutions of the given KM-file. 
This is a file containing only the base blocks. 
The file is created with the name given in bb_fname. 
The solution vectors for the specified value of lambda and in the interval 
[from...from+len-1] are transferred into the base-block-file.
The base-block file does not contain information about the group 
so it should always be used in conjunction with other files. 
For example, the database creation routine gets the base-block-file 
together with a file containing generators for the group as its input.


    

The base-block-file can be used as input for the database of incidence systems 
maintained by DISCRETA. 
This routine is called from transversal_of_isomorphism_types.


    

A typical base-block-file containes three parts:
a header, a body and a footer. 
The header and footer are one line each. 
The header consists of three integers, v, nb_base_blocks, k.
v is the number of points of the designs, nb_base_block is the 
number of base blocks for each design and k is the blocksize. 
Note that we can handle even the case where the number of base blocks 
is not constant. 
If nb_base_blocks is -1 in the header, the number of base-blocks 
must appear in the body (see below).


    

In the body we have one block for each design. 
This block consists of nb_base_blocks rows listing the base blocks 
each as a k-subset of integers in [1...v].
If  nb_base_blocks is -1 in the header, the number of base blocks appears 
just before the first base block for each of the designs.


    

The footer consists of a -1.


    
A typical base-block file is the following:


    21 -1 3

4
1 2 20 
1 5 14 
1 6 16 
1 8 15 


4
1 2 20 
1 5 14 
1 6 12 
1 8 15 



-1

    


    

Example:

    


    



     geo_db_build_from_bb(generators_fname, bb_fname, db_prefix, f_create); 
     
     


This function is used to build a database of incidence geometries. 
The incidence geometries are in base-block-format, which is described above. 
The file generators_fname contains generators for a permutation group on v 
points and is used to span the design (the degree of the group must 
be the same as the number of points specified in the base-block-file). 
The string db_prefix is used as a prefix to the names of files of the database. 
The database has two files, 

    (db_prefix)geo_by_base_blocks.db
(db_prefix)geo_by_base_blocks.idx

    
The .db file contains the database, that is, the information about the geometries. 
The .idx-file provides a Bayer-tree and is used to access the data.
Note that the .db file is transferable between different Unix systems 
(little-endian/big-endian). One can reconstruct the .idx from the .db file. 


    

The flag f_create determines whether or not the database shall be created 
at the beginning of this call (you must create the database the first time 
you are using it). Otherwise, if there already exists a database 
of geometries (with the same db_prefix and the the same parameters of designs) 
then the geometries are only added to the existing ones. 
In any case, geometries are only added if they are not already contained 
in the database (this means if there is no isomorphic copy in the database). 


    

During the process of adding geometries, this function 
gives id-s to the datasets. Each new geometry gets a new id. 
This id is the number of the geometrie in the base-block-file 
and can be used later on for determining the transversal of 
designs.
 

    

This function is used for transversal_of_isomorphism_types().


    

Example:

    


    


     geo_db_get_ids(db_prefix); 
     
     


This function retrieves all ids of geometries contained in the database.
See geo_db_build_from_bb for the meaning of these numbers.


    

Example:

    


    


     export_magma_designs(fname, t, v, designs, magma_variable); 
     
     




    

Example:

    


    


     build_incidence_matrix(v, blocks); 
     
     




    

Example:

    


    


     export_designs_inc(fname, v, DD); 
     
     




    

Example:

    


    



    




     A Typical Session 
    


    

In a typical GAP / DISCRETA session, one would issue the following commands, for example: 


    Read("discreta.g");
label := compose_group("PGGL 2 32");
g_label := label[1];
g_label_tex := label[2];
km := compute_KM(g_label, 5, 6);
do_LLL(km, 12);
get_solutions_from_solver(km, 12);
intersection_matrix_Ik2(km);
M := get_KM_matrix(km, 5, 6);
P := get_plesken_matrix(km, 5, 6);
P1 := get_plesken_matrix_with_inverse(km, 5, 6);
g := get_generators(km);
gg := Group(g, g[1]^0);
Size(gg);
orb := get_orbit_representatives(km);
so := get_stabilizer_orders(km);
no := get_number_of_solutions(km, 12);
s := get_solutions(km, 12, 1, no);
O := design_orbits(s[1]);
Sel := [0,1,2,3,4,5,6,7,8,9,10,11,12];
intersection_matrix_Iknn(km, 0, Sel, "0");
V := get_intersection_matrix_Iknn(km, "0");
VV := V[4];
ol := calc_orbit_length(so[7], gg);
I := block_intersection_type(O, 1, VV, 0, 5, ol);
I := block_intersection_type_decomposed(O, 1, VV, 0, 5, ol);
Sel1 := [0,1,2];
Sel2 := [3,4,5,6,7,8,9,10,11,12];
intersection_matrix_Iknm(km, 0, Sel1, Sel2, "1");
W := get_intersection_matrix_Iknm(km, "1");

     





    

    

    

 back 
to the DISCRETA homepage 

    
last updated: September 14, 1998,  Anton Betten