[GAP Forum] Counting Latin squares using a package "DESIGN".
Arsene Galstyan
ares.1995 at mail.ru
Fri Jul 22 10:56:41 BST 2016
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
More information about the Forum
mailing list