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.1...@mail.ru
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
