[GAP Forum] Counting Latin squares using a package "DESIGN".
Leonard Soicher
L.H.Soicher at qmul.ac.uk
Mon Jul 25 16:37:33 BST 2016
Dear Arsene Galstyan, Dear GAP-Forum,
For positive integers n and k, the DESIGN package function call
SemiLatinSquareDuals(n,k) returns a list of the duals of a complete list
of isomorphism class representatives of the (n x n)/k semi-Latin squares,
such that two such squares are considered to be isomorphic if one can
be obtained from the other by a combination of renaming symbols, row
permutations, column permutations, and transposing. Thus, the isomorphism
class of a semi-Latin square S (with symbol set [1..n*k]) whose dual
is obtained from a call to SemiLatinSquareDuals(n,k) is the orbit of
S under the group generated by symbol permutations, row permutations,
column permutations, and transposing.
I've done this as shown in the appended log-file, obtaining the
correct numbers of Latin squares of orders 3, 4, and 5.
There are, however, much more efficient ways to find the *number* of
Latin squares of order n if you are just interested in the number rather
than all the Latin squares themselves.
By the way, for a block design B in the DESIGN package, the component
B.autSubgroup, if bound, is guaranteed to be a subgroup of the
(full) automorphism group of B.
Best wishes,
Leonard
---------------------------------------------------------------
gap>
gap> LoadPackage("design");
-----------------------------------------------------------------------------
Loading GRAPE 4.7 (GRaph Algorithms using PErmutation groups)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
Loading DESIGN 1.6 (The Design Package for GAP)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
Homepage: http://www.designtheory.org/software/gap_design/
-----------------------------------------------------------------------------
true
gap>
gap> SemiLatinSquareFromDual := function(D)
> local n,S,names,i,pt;
> n:=Length(D.blocks[1]);
> S:=List([1..n],x->List([1..n],y->[]));
> names:=D.pointNames;
> for i in [1..Length(D.blocks)] do
> for pt in D.blocks[i] do
> Add(S[names[pt][1]][names[pt][2]],i);
> od;
> od;
> return S;
> end;
function( D ) ... end
gap>
gap> OnSemiLatinSquares := function(S,g)
> # Returns the image T of the (n x n)/k semi-Latin square S under g,
> # where g acts by permuting the symbols [1..n*k], the rows
> # (labelled [n*k+1..n*k+n]) and the columns (labelled [n*k+n+1..n*k+2*n]),
> # and then possibly transposing the semi-Latin square.
> local n,k,i,j,newposition,T;
> n:=Length(S[1]);
> k:=Length(S[1][1]);
> T:=List([1..n],i->[]);
> for i in [1..n] do
> for j in [1..n] do
> newposition:=OnSets([i+n*k,j+n*k+n],g);
> T[newposition[1]-n*k][newposition[2]-n*k-n]:=OnSets(S[i][j],g);
> od;
> od;
> return T;
> end;
function( S, g ) ... end
gap>
gap> SemiLatinSquareIsomorphismClass := function(S)
> # Returns the full (weak) isomorphism class of the (n x n)/k
> # semi-Latin square S.
> local n,k,transposer,g_symbols,g_rows,g_columns,G,i;
> n:=Length(S[1]);
> k:=Length(S[1][1]);
> transposer:=Product(List([n*k+1..n*k+n],i->(i,i+n)));
> g_symbols:=GeneratorsOfGroup(SymmetricGroup([1..n*k]));
> g_rows:=GeneratorsOfGroup(SymmetricGroup([n*k+1..n*k+n]));
> g_columns:=GeneratorsOfGroup(SymmetricGroup([n*k+n+1..n*k+2*n]));
> G:=Group(Concatenation(g_symbols,g_rows,g_columns,[transposer]));
> return Set(Orbit(G,S,OnSemiLatinSquares));
> end;
function( S ) ... end
gap>
gap> n:=3;
3
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 2 ], [ 3 ], [ 1 ] ]
] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 12 ]
gap> Sum(L);
12
gap>
gap> n:=4;
4
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 4 ], [ 1 ], [ 2 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 1 ], [ 2 ] ], [ [ 2 ], [ 3 ], [ 4 ], [ 1 ] ] ],
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 1 ], [ 2 ] ], [ [ 4 ], [ 3 ], [ 2 ], [ 1 ] ] ] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 432, 144 ]
gap> Sum(L);
576
gap>
gap> n:=5;
5
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ],
[ [ 5 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ] ],
[ [ 4 ], [ 5 ], [ 1 ], [ 2 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 5 ], [ 1 ], [ 2 ] ],
[ [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 1 ] ] ],
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ],
[ [ 3 ], [ 1 ], [ 5 ], [ 2 ], [ 4 ] ],
[ [ 5 ], [ 4 ], [ 1 ], [ 3 ], [ 2 ] ],
[ [ 2 ], [ 5 ], [ 4 ], [ 1 ], [ 3 ] ],
[ [ 4 ], [ 3 ], [ 2 ], [ 5 ], [ 1 ] ] ] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 17280, 144000 ]
gap> Sum(L);
161280
gap>
On Fri, Jul 22, 2016 at 12:56:41PM +0300, Arsene Galstyan wrote:
>
>
> Dear GAP forum,
>
> I'm interested in function SemiLatinSquareDuals(n,k) that is included in the package "DESIGN". I would like to know it is possible to use this function that to find the number of Latin squares of a given order.
> As it is written in manual, this function " can classify semi-Latin squares with certain given properties, and return a list of their duals as block designs". Note that (nxn)/1 semi-Latin square (that is, for k = 1) is the same thing as a Latin square of order n.
> Thus, for k=1, function breaks set of Latin square of order n on the set non-isomorphic classes. Each record resulting list corresponds exactly to one of his class. For n=3, it returns the following:
>
> gap> SemiLatinSquareDuals(3,1);
> [ rec( autSubgroup := Group([ (2,4)(3,7)(6,8), (2,3)(4,7)(5,9)(6,8), (1,5,9)
> (2,6,7)(3,4,8), (1,4,7)(2,5,8)(3,6,9) ]), blockNumbers := [ 3 ],
> blockSizes := [ 3 ], blocks := [ [ 1, 5, 9 ], [ 2, 6, 7 ], [ 3, 4, 8 ] ]
> , isBinary := true, isBlockDesign := true, isSimple := true,
> pointNames := [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ],
> [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ], r := 1,
> tSubsetStructure := rec( lambdas := [ 1 ], t := 1 ), v := 9 ) ]
>
> That is, as I understand it, exist only one isomorphic class, i.e. the set of all Latin square of order 3 is one class. In other words, all Latin square of order 3 are pairwise isomorphic. That is, one can be obtained from the other by using composite of permutations of rows, columns and transposition operations.
> If I understand correctly, field "autSubgroup" is permutation subgroup which is a group of automorphisms of a class of Latin squares corresponding to this record. That is, each element of this group carries permutations of rows, or(and) columns, or(and) transposition of Latin square.
> In this way, as I think, you can act on one element of this class by all elements of the group of automorphisms of this class in course and get all the elements of the class, i.e., all Latin squares of order 3.
> Field "blocks" is binary block design, which dual of Latin square (with the first row is ordered), which belongs to the class of Latin squares corresponding to this record. As I understand, the square can be recovered from the block design in the following way. i-th block of block design corresponding i-th symbol of Latin square and each point of block design represents number of cells of Latin square.
> In this way, it is possible to write a function that transforms a block design of each record in the Latin square, corresponding to it, and then acts on each obtained square of all permutations of automorphism group that corresponds to him.
>
> This is text of function "ConclusionSquares":
>
> Print("Load 'ConclusionSquares(n)'","\n");
> ConclusionSquares:= function(n)
> local i, j, k, NumberClasses, SLSD, SubsidiaryArray, ListLatinSquares, LenList, SZ, permut, NumberRepetition, NumberRepetitionForEach, AutomSquare, AutomSquareForEach, NumberLatinSquareForEach;
> SLSD:= SemiLatinSquareDuals(n,1);
> NumberClasses:= Length(SLSD);
> ListLatinSquares:= [ ];
> #conclusion Latin square that corresponding of records
> for i in [1..NumberClasses] do
> ListLatinSquares[i]:= [ ];
> for j in [1..n] do
> for k in [1..n] do
> ListLatinSquares[i][SLSD[i].blocks[j][k]]:= j;
> od;
> od;
> SubsidiaryArray:= [ ];
> for j in [1..n] do
> SubsidiaryArray[j]:= [ ];
> for k in [1..n] do
> SubsidiaryArray[j][k]:= ListLatinSquares[i][n*(j-1) + k];
> od;
> od;
> Print(" ",i,")","\n");
> Display(SubsidiaryArray);
> Print("\n");
> od;
> #count of Latin squares
> LenList:= NumberClasses;
> NumberRepetition:= 0;
> AutomSquare:= 0;
> for i in [1..NumberClasses] do
> permut:= Difference(AsList(SLSD[i].autSubgroup),[()]);
> SZ:= Size(permut);
> NumberLatinSquareForEach:= 1;
> NumberRepetitionForEach:= 0;
> AutomSquareForEach:= 0;
> for j in [1..SZ] do
> SubsidiaryArray:= [ ];
> for k in [1..n*n] do
> SubsidiaryArray[k^permut[j]]:= ListLatinSquares[i][k];
> od;
> if (SubsidiaryArray in ListLatinSquares) then
> NumberRepetitionForEach:= NumberRepetitionForEach + 1; #number repetitions for each record
> if (SubsidiaryArray = ListLatinSquares[i]) then
> AutomSquareForEach:= AutomSquareForEach + 1; #number of permutetions which not change Latin square
> fi;
> else
> NumberLatinSquareForEach:= NumberLatinSquareForEach + 1; #number different Latin square for each record
> LenList:= LenList + 1;
> ListLatinSquares[LenList]:= [ ];
> ListLatinSquares[LenList]:= SubsidiaryArray;
> fi;
> od;
> Print ("[rec #",i,": Number elements in autSubgroup = ",SZ+1,"; Number Latin Squares = ",NumberLatinSquareForEach,"; Number repetition = ",NumberRepetitionForEach,"; Number automorfisms = ",AutomSquareForEach,"]","\n","\n");
> NumberRepetition:= NumberRepetition + NumberRepetitionForEach;
> AutomSquare:= AutomSquare + AutomSquareForEach;
> od;
> #conclusion list of Latin square
> for i in [NumberClasses+1..LenList] do
> SubsidiaryArray:= [ ];
> for j in [1..n] do
> SubsidiaryArray[j]:= [ ];
> for k in [1..n] do
> SubsidiaryArray[j][k]:= ListLatinSquares[i][n*(j-1) + k];
> od;
> od;
> Print(" ",i,")","\n");
> Display(SubsidiaryArray);
> od;
> return ["Length(ListLatinSquares)=",Length(ListLatinSquares)," NumberRepetition=",NumberRepetition," AutomSquare=",AutomSquare];
>
> end;
> Function result for n=3:
>
> gap> ConclusionSquares(3);
> 1)
> [ [ 1, 2, 3 ],
> [ 3, 1, 2 ],
> [ 2, 3, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 36; Number Latin Squares = 6; Number repetition =
> 30; Number automorfisms = 5]
>
> 2)
> [ [ 1, 3, 2 ],
> [ 2, 1, 3 ],
> [ 3, 2, 1 ] ]
> 3)
> [ [ 2, 1, 3 ],
> [ 3, 2, 1 ],
> [ 1, 3, 2 ] ]
> 4)
> [ [ 3, 1, 2 ],
> [ 2, 3, 1 ],
> [ 1, 2, 3 ] ]
> 5)
> [ [ 2, 3, 1 ],
> [ 1, 2, 3 ],
> [ 3, 1, 2 ] ]
> 6)
> [ [ 3, 2, 1 ],
> [ 1, 3, 2 ],
> [ 2, 1, 3 ] ]
>
> [ "Length(ListLatinSquares)=", 6, " NumberRepetition=", 30, " AutomSquare=", 5 ]
>
> So, we got exactly 6 different squares. But the number of Latin squares of order 3 is 12 pieces. Due to the fact that all first rows are different and the number is 3 !, there is an idea to mix all the rows from the second to last together. That is , multiplied by 2 !. Just get 3 ! * 2 ! = 12 . But this idea is crumbling at n=4:
>
> gap> ConclusionSquares(4);
> 1)
> [ [ 1, 2, 3, 4 ],
> [ 4, 1, 2, 3 ],
> [ 3, 4, 1, 2 ],
> [ 2, 3, 4, 1 ] ]
>
> 2)
> [ [ 1, 2, 3, 4 ],
> [ 2, 1, 4, 3 ],
> [ 3, 4, 1, 2 ],
> [ 4, 3, 2, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 64; Number Latin Squares = 8; Number repetition =
> 56; Number automorfisms = 7]
>
> [rec #2: Number elements in autSubgroup = 192; Number Latin Squares =
> 24; Number repetition = 168; Number automorfisms = 7]
>
> [ "Length(ListLatinSquares)=", 32, " NumberRepetition=", 224, " AutomSquare=", 14 ]
>
>
> Latin squares of order 4 exactly 576, but 32*3!=192. In this situation , of course, you can still guess as from 32 to receive 576 , because 576 divided by 32. But if n=5, then
>
> gap> ConclusionSquares(5);
> 1)
> [ [ 1, 2, 3, 4, 5 ],
> [ 5, 1, 2, 3, 4 ],
> [ 4, 5, 1, 2, 3 ],
> [ 3, 4, 5, 1, 2 ],
> [ 2, 3, 4, 5, 1 ] ]
>
> 2)
> [ [ 1, 2, 3, 4, 5 ],
> [ 3, 1, 5, 2, 4 ],
> [ 5, 4, 1, 3, 2 ],
> [ 2, 5, 4, 1, 3 ],
> [ 4, 3, 2, 5, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 200; Number Latin Squares =
> 20; Number repetition = 180; Number automorfisms = 9]
>
> [rec #2: Number elements in autSubgroup = 24; Number Latin Squares = 24; Number repetition =
> 0; Number automorfisms = 0]
>
> [ "Length(ListLatinSquares)=", 44, " NumberRepetition=", 180, " AutomSquare=", 9 ]
>
> Latin squares of order 5 exactly 161280 and 161280 is not divisible by 44.
> Therefore , from the number of Latin squares , so that you can get , it is impossible to find all the squares of a given order . That is, function SemiLatinSquareDuals does not answer the question about the number of Latin squares .
> The following questions . Am I right? Did I everything right and reasoned? If so, then the function SemiLatinskuare ( n , k) is not working properly or I did not understand then what it does .
> By the way, this function has a few optional parameters: SemiLatinSquareDuals(n,k,maxmult,blockintsize, isolevel). A ll these parameters in this case, for k=1, are not interesting , because we consider only Latin squares .
>
> Thank you very much!
>
> Best regards,
>
> Arsene Galstyan
> ares.1995 at mail.ru
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
More information about the Forum
mailing list