The set of autotopisms of partial Latin squares

The set of autotopisms of partial Latin squares R. M. Falc´on School of Building Engineering, University of Seville, Avda. Reina Mercedes 4 A, 41012 - Seville, Spain. Abstract Symmetries of a partial Latin square are primarily determined by its autotopism group. Analogously to the case of Latin squares, given an isotopism Θ, the cardinality of the set PLSΘof partial Latin squares which are invariant under Θ only depends on the conjugacy class of the latter, or, equivalently, on its cycle structure. In the current paper, the cycle structures of the set of autotopisms of partial Latin squares are characterized and several related properties studied. It is also seen that the cycle structure of Θ determines the possible sizes of the elements of PLSΘand the number of those partial Latin squares of this set with a given size. Finally, it is generalized the traditional notion of partial Latin square completable to a Latin square. Keywords: Partial Latin square, autotopism group, cycle structure. 05B15, 20N05, 20D45 1. Introduction. Every permutation πof the symmetric group Sncan be uniquely decomposed into product of disjoint cycles. Let nπbe the number of these cycles. The numbers λπ iof cycles of length iin this decomposition determine its cycle structure as the expression zπ=nλπ n·. . . ·1λπ 1, where any term of the form i0 is omitted and any term of the form i1is replaced by i. The cardinality of the set CSnof possible cycle structures of Snis equal to the number p(n) of partitions of n. Two permutations are conjugate if and only if they have the same cycle structure. Given π∈Sn, let λπand π∞be respectively its length and the union of its 1-cycles written in natural order. Hereafter, we suppose πto be represented by following its decomposition into a product π1. . . πnπ of disjoint cycles in order of decreasing length, where each cycle πiis written as (pi,1. . . pi,λπi), with pi,1= minj{pi,j}and where pi,1< pj,1whenever i < j Preprint submitted to Discrete Mathematics October 27, 2011 and λπi=λπj. Finally, given a∈[n] = {1, . . . , n}, we write a∈πiif there exists j∈[λπi] such that a=pi,j. Analogously, a∈π∞means π(a) = a. ALatin square of order nis an n×narray with elements chosen from a set of ndistinct symbols such that each symbol occurs precisely once in each row and each column. Hereafter, [n] is assumed to be this set of symbols and LSndenotes the set of Latin squares of order n. Given L= (lrc)∈ LSn, its orthogonal representation O(L) is the set of n2triples {(r, c, lrc): r, c ∈[n]}defined by the rows r, columns cand symbols lrc of L. This set satisfies the Latin square condition, that is, given two triples of O(L) which coincide in two components, then the third component is also the same. Given π∈S3, it is defined the Latin square Lπsuch that O(Lπ) = {(lπ(1), lπ(2), lπ(3)): (l1, l2, l3)∈O(L)}, which is said to be parastrophic to L. Permutations of rows, columns and symbols also give rise to new Latin squares. Specifically, given three permutations α, β, γ of the symmetric group Sn, the triple Θ = (α, β, γ)∈In=S3 nis called an isotopism and LΘis said to be isotopic to L, where O(LΘ) = {(α(r), β(c), γ(s)): (r, c, s)∈O(L)}. To be isotopic is an equivalence relation, which will be denoted by ∼, and the set of Latin squares isotopic to Lis its isotopism class [L]. The number of Latin squares and isotopism classes of LSnare known for n≤11 [24, 18]. A list of representatives of isotopism classes for n≤8 is given in [25]. The cycle structure of Θ is the triple zΘ= (zα, zβ, zγ). Hereafter, given a subset S⊆In,CSSdenotes the set of cycle structures of the elements of S. Given z= (z1, z2, z3)∈ CSS, where zi=nzin ·. . . ·1zi1, then nzidenotes the number of cycles of zi, that is, nzi=∑j∈[n]zij. Finally, the parastrophic class of zis the set [z] = {zπ= (zπ(1), zπ(2), zπ(3)): π∈S3}. If LΘ=L, then Θ is said to be an autotopism of L. If α=β=γ, then Θ is an automorphism of Land Θ = αis written instead of (α, α, α). Let LSΘ,∆(Θ), Anand Andenote respectively the set of Latin squares which have Θ as an autotopism, its cardinality and the sets of autotopisms and automorphisms of at least one Latin square of order n. Necessary conditions for an isotopism to be an autotopism were given in [26, 24, 10, 29] and An was studied in [32, 1, 19, 20, 29]. If π∈S3and L∈ LSΘ, then Lπ∈ LSΘπ, so permutations on the components of Θ preserve ∆(Θ). Moreover, this cardinality only depends on the conjugacy class of Θ [10] or, equivalently, on its cycle structure, so we also denote it by ∆(zΘ). A classification of CSAnis known for all n≤17 [10, 29]. Given z∈ CSAn, let Iz={Θ∈In:zΘ=z} and LSz=∪Θ∈IzLSΘ. 2 An incidence structure is a triple (P, B, I), where Pand Brespectively are finite sets of points and blocks and I⊆P×Bis an incidence relation. It is r-uniform if every block contains exactly rpoints and it is s-regular if every point is in exactly sblocks. Two blocks are equivalent if they contain the same set of points and the multiplicity of a block is the size of its equivalence class. In the study of Latin squares, it can be defined a natural incidence relation Inbetween LSnand In, where, given L∈ LSnand Θ ∈In, then (L, Θ) ∈In if and only if L∈ LSΘ. Hence, given z∈ CSAn, the triple (LSz,Iz, In) is a ∆(z)-uniform incidence structure such that every block have the same multiplicity [9]. Moreover, given L∈ LSn, the triple ([L],Iz, In) is a uniform and regular incidence structure, where every block contains ∆[L](z) elements, whose exact value is known for order up to 6. Although a general expression for the values of ∆(z) and ∆[L](z) remains unknown, some general and explicit formulas were given for the former [22, 23, 7, 27] and Gr¨obner bases were used to know its exact value for all autotopisms of Latin squares of order up to 7 [12]. For higher orders, Gr¨obner bases have problem with the exponential growth of data storage and the time of computation, for which the use of new combinatorial tools seems to be the key. Thus, for example, given Θ = (α, β, γ)∈Iz, Gr¨obner bases were used in [13] to obtain the value of ∆(z) for the majority of the cycle structures of autotopisms of A8and A9, by solving the linear equation system formed after adding the constraints xrcs =xα(r)β(c)γ(s), for all r, c, s ∈[n], to those related to the planar 3-index assignment problem [6]: min ∑r,c,s∈[n]wrcs ·xrcs, subject to ∑r∈[n]xrcs = 1,∀c, s ∈[n], ∑c∈[n]xrcs = 1,∀r, s ∈[n], ∑s∈[n]xrcs = 1,∀r, c ∈[n], xrcs ∈ {0,1},∀r, c, s ∈[n], (3PAPn) where wrcs are real weights for all r, c, s ∈[n] and whose set of feasible solutions are in 1 −1 correspondence with LSnif we define the Latin square L= (lrc) such that lrc =sif and only if xrcs = 1. All the previous concepts can be naturally extended to partial Latin squares, which are square arrays in which each cell is either empty or contains one element chosen from a set of nsymbols, such that each symbol occurs at most once in each row and in each column. The size of a partial Latin square Pis the number of its non-blank cells and is denoted by 3 |P|. Let PLSnand PLSn,s denote respectively the set of non-empty partial Latin squares of order nand its subset of arrays of size s. An upper bound of the elements of PLSn,s is given in [14]. The orthogonal representation of P∈ PLSnis the set O(P) of |P|triples related to the non-blank cells of P. Parastrophic partial Latin squares have therefore the same size. Given Θ = (α, β, γ)∈In, it is defined the partial Latin square PΘsuch that O(PΘ) = {(α(r), β(c), γ(s)): (r, c, s)∈O(P)}, which is said to be isotopic to Pand [P] denotes its isotopism class. Thus, |PΘ|=|P|. Θ is said to be an autotopism of Pif PΘ=P. Let APnand PLSΘdenote respectively the set of autotopisms of at least one partial Latin square of order nand that of non-empty partial Latin squares which have Θ as an autotopism. Besides, given z∈ CSAPn,PLSzdenotes the set ∪Θ∈IzPLSΘ. A partial Latin square P∈ PLSncan be completed to a Latin square L∈ LSnif O(P)⊆O(L). Given Θ ∈ CSAn, the subset of LSΘof Latin squares to which Pcan be completed is denoted by LSΘ,P . The computation of ∆(z) can be then simplified [12] if a multiplicative factor cP∈Nis found such that ∆(z) = cP· |LSΘ,P |. Although this factor, which is called P-coefficient of symmetry of Θ, becomes crucial in the processing of high orders, no exhaustive study has been developed in this regard. Indeed, a comprehensive analysis of APnand PLSΘhas not been properly done until now. The present paper deals with this last question. It is organized as follows: In Section 2, the set CSAPnis characterized and several related results exposed. In Section 3, given z∈ CSAPn, it is dealt with the possible sizes of a partial Latin square P∈ PLSz. In Section 4, analogously to the case of Latin squares, it is proven that the number of partial Latin squares related to an autotopism only depends on the cycle structure of the latter, in such a way that the elements of PLSnand Incan be respectively considered as points and blocks of incidence structures whose uniformity and regularity are studied. Moreover, new constraints are imposed to the 3PAPnin order to obtain the set PLSz,s of partial Latin squares of size s∈[n] related to an autotopism of cycle structure z∈ CSAPn. Besides, by using Gr¨obner bases, its cardinality ∆s(z) is obtained for n≤4. In Section 5, a theoretical ground for the coefficient of symmetry is exposed. Specifically, given Θ ∈In, it is studied the set of partial Latin squares of PLSΘwhich can be completed to Latin squares of LSΘ. Finally, since the current paper has a high dependence on notation, a glossary of symbols is shown in Appendix A. 4 2. The set CSAPn. Autotopisms of partial Latin squares are uniquely determined by their cycle structures: Lemma 2.1. Θ∈APnif and only if zΘ∈ CSAPn. Proof. The necessary condition holds by definition of CSAPn. Now, if z∈ CSAPn, then there must exist Θ0∈Izand P∈ PLSΘ0. Hence, given Θ∈Iz, Θ and Θ0are conjugate and therefore there exists Θ′∈Insuch that Θ = Θ′Θ0Θ′−1. As a consequence, PΘ′∈ PLSΘand Θ ∈APn. Let us define the set: LCMn={(i, j, k)∈[n]3: lcm(i, j) = lcm(i, k) = lcm(j, k) = lcm(i, j, k)}. The next result characterizes the set CSAPnand can be considered as an immediate generalization for partial Latin squares of the necessary condition given by Stones, Vojtˇechovsk´y and Wanless in [29] for membership in An: Lemma 2.2. Given z= (z1, z2, z3)∈ CSIn, we have z∈ CSAPnif and only if there exists (i, j, k)∈LCMnsuch that z1i·z2j·z3k>0. Proof. If z∈ CSAPn, then there must exist Θ = (α, β, γ)∈Izand P∈ PLSΘ. Given (r, c, s)∈O(P), let (u, v, w)∈[nα]×[nβ]×[nγ] be such that r∈αu,c∈βvand s∈γw. Since Θ is an autotopism of P, it must be (αt u(r), βt v(c), γt w(s)) ∈O(P), for all t∈N. The necessary condition is then a consequence of the Latin square condition, by considering i, j, k to be, respectively, the lengths of αu,βvand γw. To prove the converse, let Θ = (α, β, γ)∈Izand let αu, βvand γwbe, respectively, i-, j- and k-cycles of α,βand γ. Let r, c, s be, respectively, elements of αu, βvand γw. The set of triples {(αt u(r), βt v(c), γt w(s)): t∈ [lcm(i, j, k)]}satisfies the Latin square condition because of being (i, j, k)∈ LCMnand therefore it is the orthogonal representation of a partial Latin square P∈ PLSΘ. Given n > 1, Lemma 2.2 implies APnto be a proper subset of In, because, for instance, (1n,1n, n1)∈ CSAPn. Analogously, Anis a proper subset of APn, because, for example, (2,2,2) ∈ CSAP2and (2 ·1n−2,2·1n−2,1n)∈ CSAPn, for n > 2, but neither of them are cycle structures of an autotopism of Latin square. Thus, the next claim is verified: 5 Proposition 2.3. An⊂APn⊂In,∀n > 1. Moreover, APnand Inhave asymptotically the same size. To see it, it is enough to assure that the cardinalities of the sets of their cycle structures coincide in the limit, which is proven in Theorem 2.6. Although CSAPncan be explicitly obtained for any order n∈Nby implementing Lemma 2.2 in a computer procedure, a lower bound of its cardinality is determined by studying the following sets which partition CSn: CSn,m ={nzn·. . . ·1z1∈ CSn:zm>0 and zi= 0,∀i∈[m−1]}, where m∈[n]. The following results hold: Lemma 2.4. |CSn,m|=     1,if m=n, 0,if m∈ {⌊n 2⌋+ 1, . . . , n −1}, p(n−m)−∑m−1 i=1 |CSn−m,i|,otherwise. Proof. The cases m≥ ⌊n 2⌋+1 are straightforward verified. Let m≤ ⌊n 2⌋. Given z∈ CSn,m, it is zm>0 and therefore it must be zn−m+i= 0, for all i∈[m]. Hence, we can define z′∈ CSn−msuch that z′ i=z, for all i∈[n−m]− {m}and z′ m=zm−1. Specifically, since z∈ CSn,m, it must be z′ i= 0, for all i∈[m−1]. Thus, z′∈∪n−m i=mCSn−m,i =CSn−m−∪m−1 i=1 CSn−m,i and the claim is verified.  Proposition 2.5. |CSAPn| ≥ ∑(i,j,k)∈LCMn|CSn,i| · |CSn,j| · |CSn,k|. Proof. Since the sets CSn,m constitute a partition of CSn, the result is consequence of Lemma 2.2.  Theorem 2.6. limn→∞ |CSAPn| |CSIn|= 1. Proof. Since (1,1,1) ∈LCMn, Proposition 2.5 implies that |CSAPn| ≥ |CSn,1|3and thus, from Lemma 2.4, |CSAPn| ≥ p(n−1)3. Now, since p(n) is equivalent to eπ√2n/3 4n√3when ntends to infinity [17] and |CSAPn| ≤ |CSIn|= p(n)3, it is verified that: 6 n|CSAn| |CSn,m| |CSAPn| |[CSAPn]|m 1 2 3 4 5 6 7 8 1 1 1 1 2 4 1 5 3 3 6 2 15 7 4 19 3 1 65 22 5 8 5 1 223 60 6 45 7 2 1 869 197 7 12 11 2 1 2535 526 8 87 15 4 1 1 7663 1492 9 43 22 4 2 1 21156 3937 10 89 30 7 2 1 1 60264 10850 11 21 42 8 3 1 1 150953 26628 12 407 56 12 4 2 1 1 385538 66984 13 27 77 14 5 2 1 1 915452 157398 14 141 101 21 6 3 1 1 1 2193225 374127 15 150 135 24 9 3 2 1 1 4928696 836154 16 503 176 34 10 5 2 1 1 1 11209311 1893607 17 40 231 41 13 5 3 1 1 1 24406191 4110132 Table 1: Cardinality of the sets of cycle structures, for n≤17 and m≤ ⌊n 2⌋. 1≥lim n→∞ |CSAPn| |CSIn|≥lim n→∞ p(n−1)3 p(n)3= 1.  For n≤17, Table 1 shows the values |CSn,m|and |CSAPn|, where m≤ ⌊n 2⌋, in comparison with those of |CSAn|, which can be obtained by using the classification given in [10, 29]. The number |[CSAPn]|of parastrophic classes of CSAPnis also shown. 7 3. The size of a partial Latin square related to an autotopism. Given z= (z1, z2, z3)∈ CSAPnand Θ = (α, β, γ)∈Iz, any partial Latin square P∈ PLSΘcan be decomposed into nz1·nz2blocks Pij whose rows and columns are respectively determined by the elements of the cycle αiof αand the cycle βjof β, that is, O(Pij) = {(r, c, s)∈O(P): r∈αiand c∈βj}. It will be called the Θ-decomposition of P. Specifically, zdetermines not only the number of these blocks, but also their possible sizes and, consequently, a pair of bounds for the size of P. To see it, let us define the set: LCMz={(i, j)∈[n]2:∃k∈[n] s.t. (i, j, k)∈LCMnand z1i·z2j·z3k>0}. The following results hold: Lemma 3.1. Given z∈ CSAPn,Θ∈Iz,P∈ PLSΘand an i×j-block B of the Θ-decomposition of P, there exists ωB∈[gcd(i, j)] ∪ {0}such that |B|=ωB·lcm(i, j). Furthermore, ωB= 0 if (i, j)∈ LCMz. Proof. Analogously to the proof of Lemma 2.2, the Latin square condition implies |B|= 0, whenever (i, j)∈ LCMz. Besides, given (r, c, s)∈O(B), its orbit by the action of the group generated by Θ = (α, β, γ) is the set of triples (αt(r), βt(c), γt(s)) ∈O(B), for all t∈[lcm(i, j)]. Thus, the Latin square condition implies |B|to be a multiple of lcm(i, j). Finally, since there are i·jcells in B, the multiplicative factor must be at most gcd(i, j).  Proposition 3.2. Given z= (z1, z2, z3)∈ CSAPn, let z(23) = (z1, z3, z2)and z(13) = (z3, z2, z1). Then, given P∈ PLSz, it is lz≤ |P| ≤ uz, where: lz= min (i,j)∈LCMz {lcm(i, j)}, uz= min{∑ (i,j)∈LCMz z1i·z2j·i·j, ∑ (i,k)∈LCMz(23) z1i·z3k·i·k, ∑ (k,j)∈LCMz(13) z2j·z3k·j·k}. Proof. Let Θ ∈Izbe such that P∈ PLSΘand let Bbe a block of the Θ-decomposition of Psuch that |B|>0. From Lemma 3.1, if Bis an i×j-block, where (i, j)∈LCMz, then lcm(i, j)≤ |B| ≤ i·jand thus lz≤ |P| ≤ ∑(i,j)∈LCMzz1i·z2j·i·j. Since the size of a partial Latin square is invariant by parastrophism and Pπ∈ PLSΘπfor all π∈S3, the number uzis an upper bound of |P|. 8 From the previous results, it is deduced that the possible sizes of the elements of PLSzmust be in the set: Sizes(z) =   ∑ (i,j)∈LCMz ωij ·lcm(i, j)≤uz:ωij ∈[z1i·z2j·gcd(i, j)]   . As an example, let us consider z= (6,3·2·1,4·2) ∈ CSAP6and Θ = ((123456),(123)(45)(6),(1234)(56)) ∈ PLSz. The Θ-decomposition of any partial Latin square P∈ PLSΘis then formed by three blocks, P11, P12 and P13, whose cells are respectively indicated by the symbols ·,∗and ◦in the following diagram:        ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦        . Besides, LCMz={(6,3)}, LCMz(23) ={(6,2)}and LCMz(13) ={(2,3)}. Hence, from Proposition 3.2, it must be 6 ≤ |P| ≤ min{18,12,6}= 6. Thus, Sizes(z) = {6}and |P|= 6. Specifically, there are six possibilities for P:        5· · · · · ·6· · · · · · 5··· 6· · · · · ·5· · · · · · 6···        ,        6· · · · · ·5· · · · · · 6· · · 5· · · · · ·6· · · · · · 5· · ·        ,        ·5· · · · · · 6··· 5· · · · · ·6· · · · · · 5··· 6· · · · ·        ,        ·6· · · · · · 5··· 6· · · · · ·5· · · · · · 6··· 5· · · · ·        ,        · · 5· · · 6· · · · · ·5· · · · · · 6· · · 5· · · · · ·6· · · ·        ,        · · 6··· 5· · · · · ·6· · · · · · 5··· 6· · · · · ·5· · · ·        . 4. The number of partial Latin squares related to an autotopism. Given z∈ CSAPn, Θ ∈Iz,P∈ PLSΘand s∈[n], let us define the sets: PLSΘ,[P]=PLSΘ∩[P],PLSΘ,s =PLSΘ∩ PLSn,s. In the current section, given Θ ∈In, the cardinality of the set PLSΘ is studied. The following result implies that it only depends on the cycle structure of Θ: 9 z ∆s(z) ∆P(z)s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (4,4,4) 16 48 32 0 96 (4,4,3·1) 4 4 (4,4,22) 16 56 32 8 112 (4,4,2·12) 16 64 64 8 152 (4,4,14) 16 72 96 24 208 (3·1,3·1,3·1) 1 18 18 90 90 165 165 99 99 9 9 763 (3·1,3·1,2·12) 2 6 12 6 12 38 (3·1,3·1,14) 4 12 48 36 144 24 96 364 (3·1,22,22) 8 8 16 (3·1,22,2·12) 4 4 (3·1,2·12,2·12) 4 4 8 4 20 (3·1,2·12,14) 8 12 20 (3·1,14,14) 16 72 96 24 208 (22,22,22) 32 352 1664 3552 3328 1408 256 32 10624 (22,22,2·12) 32 360 1792 4152 4416 2048 384 32 13216 (22,22,14) 32 368 1920 4800 5760 3264 768 96 17008 (22,2·12,2·12) 24 192 640 880 416 32 2184 (22,2·12,14) 16 72 96 24 208 (2·12,2·12,2·12) 8 32 136 336 752 1440 1904 2856 2400 2608 1504 1056 448 224 64 16 15784 (2·12,2·12,14) 16 88 272 736 1344 1632 1728 1008 6824 (2·12,14,14) 32 384 2208 6504 9792 7104 2112 216 28352 (14,14,14) 64 1728 25920 239760 1437696 5728896 15326208 27534816 32971008 25941504 13153536 4215744 847872 110592 9216 576 127545136 Table 3: ∆s(z) and ∆P(z) for each parastrophic class of CSAP4. 16 observe that Θ-completability is a particular case of the F-completability defined in [8], where Fis a set of autotopisms of partial Latin squares. A specific case of Θ-completability is the cyclically completability studied by Gr¨uttm¨uller in [15, 16], where Θ would be a cyclic automorphism. Another case of Θ-completability is given in [3], where authors study the completion of Latin rectangles that admit an autotopism (Id, α, β) to a Latin square related to such an autotopism. If Pis Θ-completable, it is not mandatory for Θ to be an autotopism of P. Thus, for instance, if Θ = ((12),(12),Id) ∈A2, the partial Latin square of orthogonal representation {(1,1,1)}is Θ-completable but does not belong to PLSΘ. Indeed, it can be easily checked that every partial Latin square of order n≤2 is Θ-completable whenever Θ is non-trivial. An example of non-trivial isotopism for which there exists a related partial Latin square which is neither Θ-completable nor traditionally completable is Θ = ((12)(3),(12)(3),(12)(3)) ∈A3. A partial Latin square in such conditions is:   3·2 ·3 1 2 1 ·  . An example where it is possible to observe the difference between both concepts is given if Θ = ((12)(34),(12)(34),(12)(3)(4)) ∈A4. In this case, the following partial Latin square is not Θ-completable, but it is completable in the traditional way:     3 4 · · 4 3 · · · · · · · · · ·     . Finally, let us observe that, unlike traditional completability, Θ-com- pletability is not invariant under isotopism. Thus, for instance, if Θ = (123)(4)(5)(6) ∈ A6, then it can be checked that the first of the following two isotopic partial Latin squares of PLSΘis Θ-completable, but the second is not:        · · · · · · · · · · · · · · · · · · · · · 4· · · · · · 5· · · · · · 6        ,        1· · · · · ·2· · · · · · 3· · · · · · · · · · · · · · · · · · · · ·        . 17 Let CΘdenote the set of Θ-completable partial Latin squares and let CΘ,s =CΘ∩ PLSΘ,s. The cardinalities of these sets only depend on the parastrophic class of the cycle structure of Θ: Lemma 5.1. Let Θ1,Θ2∈Inbe such that [zΘ1]=[zΘ2]. Then, |CΘ1,s|= |CΘ2,s|, for all s∈[n2]. As a consequence, |CΘ1|=|CΘ2|. Proof. Let π∈S3be such that zΘ1=zΘπ 2. Given s∈[n2] and P∈CΘ1,s, there exists L∈ LSΘ1such that O(P)⊆O(L). Besides, since Θ1and Θπ 2 are conjugate, then there exists Θ ∈Insuch that Θπ 2= ΘΘ1Θ−1. Thus, (PΘ)π−1∈ PLSΘ2, (LΘ)π−1∈ LSΘ2and O((PΘ)π−1)⊆O((LΘ)π−1). Since |(PΘ)π−1|=|P|, it is verified that |CΘ1,s|≤|CΘ2,s|. The opposite inequality is analogously proven and the consequence is immediate, because |CΘ1|= ∑s∈[n2]|CΘ1,s|=∑s∈[n2]|CΘ2,s|=|CΘ2|. From the previous result, it is natural to define the numbers czand cz,s as the respective cardinalities of CΘand CΘ,s, for any Θ ∈Iz. Specifically, in the case of cyclic automorphisms, the results of Gr¨uttm¨uller in [15] imply that c(n,n,n)= 0 if nis even and c(n,n,n),k·n= ∆k·n((n, n, n)), for all nodd and k≤2. Although it is not true in general if k≥3 [16], some partial results have been studied in this regard in [2, 30]. For a general cycle structure, the following result holds: Theorem 5.2. Given z∈ CSAPnand Θ∈Iz, let Ibe the ideal related to PLSΘ,n2according to Corollary 4.9. Given P∈ PLSΘ, it is verified that: P∈CΘ⇔dimQ(Q[xn]/(I+⟨xrcs −1: (r, c, s)∈O(P)⟩)) = 0. Proof. From Corollary 4.9, the affine variety of the ideal I+⟨xrcs − 1: (r, c, s)∈O(P)⟩coincides with LSΘ,P . This ideal is radical by Proposition 2.7 of [4], because contains its intersection with Q[xrcs], for all r, c, s ∈ [n]. Specifically, this intersection is either ⟨xrcs −1⟩if (r, c, s)∈O(P) or ⟨xrcs ·(xrcs −1) ⟩, otherwise. The result follows from Theorem 2.10 of [4].  Gr¨obner bases have then been used to determine the numbers cz,s and cz(Table 4) for each non-trivial parastrophic class of CSAn, where n≤4. Specifically, given Θ ∈Iz, the procedure PLST of [11] has been applied in order to obtain the partial Latin squares of PLSΘ,s and the dimension of each affine variety of Theorem 5.2. 18 n z cz,s cz s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 (1,1,1) 1 1 2 (2,2,12) 4 2 6 3 (3,3,3) 9 9 3 21 (3,3,13) 9 18 6 33 (2·1,2·1,2·1) 1 10 10 24 24 16 16 4 4 109 4 (4,4,22) 16 40 32 8 96 (4,4,2·12) 16 40 32 8 96 (4,4,14) 16 72 96 24 208 (3·1,3·1,3·1) 1 18 18 90 90 90 90 45 45 9 9 505 (22,22,22) 32 352 1408 2144 1792 896 256 32 6912 (22,22,2·12) 32 336 1344 2144 1792 896 256 32 6832 (22,22,14) 32 368 1728 3792 4224 2496 768 96 13504 (2·12,2·12,2·12) 8 24 104 200 528 784 1328 1560 1760 1568 1248 800 448 192 64 16 10632 Table 4: cz,s and czfor each non-trivial parastrophic class of CSAn, where n≤4. Given z∈ CSAPnand Θ ∈Iz, a set {P1, . . . , Pm}of Θ-completable partial Latin squares will be said to be a basis of LSΘif ∪i∈[m]LSΘ,Pi=LSΘand LSΘ,Pi∩ LSΘ,Pj=∅, whenever i=j. In this case, ∆(z) = ∑i∈[m]|LSΘ,Pi|. Let us observe that, from a computational point of view, it is interesting to determine a basis of LSΘsuch that the sizes of its elements are as great as it is possible, because then, for each Pi, it would be feasible to add to the constraints of Proposition 4.8, all those of the form xrcs = 1, whenever (r, c, s)∈O(Pi). The calculus of the corresponding Gr¨obner basis would be then more efficient and it would allow to obtain new values ∆(z). The next result holds: Lemma 5.3. Let S⊆[n]2and Θ=(α, β, γ)∈An. The following sets are bases of LSΘ: SRC ={P∈CΘ: (r, c, s)∈O(P)⇔(r, c)∈S}, SRS ={P∈CΘ: (r, c, s)∈O(P)⇔(r, s)∈S}, SCS ={P∈CΘ: (r, c, s)∈O(P)⇔(c, s)∈S}. Proof. Let us prove that SRC is a basis of LSΘ; the other cases are similar. Since Θ ∈An, it must be LSΘ=∅. Now, given L∈ LSΘ, let P∈SRC be such that O(P) = {(r, c, s)∈O(L): (r, c)∈S}. Thus, L∈ LSΘ,P and hence LSΘ=∪Q∈SRC LSΘ,Q. Finally, given two distinct elements Qand Q′in SRC, it must exist (r, c)∈Sand s∈[n] such that (r, c, s)∈ 19 O(Q)−O(Q′). It implies that LSΘ,Q ∩ LSΘ,Q′=∅and therefore SRC is a basis of LSΘ. A special case appears when |LSΘ,Pi|=|LSΘ,Pj|, for all i, j ∈[m]. Such a basis will be called homogeneous and it follows that ∆(z) = m·|LSΘ,Pi|, for all i∈[m]. The cardinality mof the homogeneous basis would be therefore the Pi-coefficient of symmetry of Θ, for all i∈[m]. Although a comprehensive study should be developed in this regard, let us finish the current paper with a result with gives a theoretical support to the majority of the coefficients of symmetry which were used in [12]: Theorem 5.4. Let z= (z1, z2, z3)∈ CSAnbe such that z11 ·z21 ·z31 = 0. Let Θ=(α, β, γ)∈Izand S={(i, j)∈[n]2:i∈α∞, j ∈β∞}. It is verified that SRC is an homogeneous basis of LSΘof cardinality |LSz11 |. Proof. From the hypothesis, it must be z11 =z21 =z31 ([24], Theorem 1). Furthermore, given P∈ PLSΘ, the corresponding block P∞∞ of the Θ-decomposition of Pis a z11 ×z11-array, such that each of its non-filled cells must contain one of the z11 fixed symbols of γ, that is, it is a Latin subsquare of Pof order z11. Thus, since Θ ∈An, Lemma 5.3 implies the set SRC to be a basis of LSΘof |LSz11 |elements. Now, let us consider two distinct elements Q, Q′∈SRC. Given L∈ LSΘ,Q, let us define the Latin square L′∈ LSnsuch that O(L′) = {(r, c, s)∈[n]3: (r, c, s)∈O(Q′) if (r, c)∈S, or (r, c, s)∈ O(L),otherwise}, that is, the only difference of L′with respect to Lis the block L′ ∞∞, which is Q′instead of Q. Since L∈ LSΘand Q′∈ PLSΘ, it must be L′∈ LSΘ. Hence, |LSΘ,Q| ≤ |LSΘ,Q′|. The opposite inequality is analogously proven and therefore SRC is homogeneous.  6. Final remarks and further work. In the current paper, it has been dealt with the set of autotopisms of partial Latin squares in order to develop further techniques which allow to improve some results about the set of autotopisms of Latin squares, such as those related with the obtaining of the values ∆(z). In Section 2, the cardinality of CSAPnwas studied and a lower bound was determined. Although it can be obtained by an exhaustive search once Lemma 2.2 is implemented in a computer procedure, it raises the question of whether it is possible to obtain a general formula for |CSAPn|. A similar question appears in Section 4 with 20 the values ∆[P](z), for which a comprehensive study of isotopism classes of PLSnwould be necessary. It would also be useful in order to improve the computation and increase the order n≤4 which has been used in the examples of the present paper. Finally, once a theoretical basis has been exposed in Section 5 for the concept of coefficient of symmetry of an autotopism, it seems that an exhaustive study in this regard would be necessary to solve some of the problems of computation related to the calculus of the values ∆(z). Acknowledgements. The author is very grateful to the referees for their valuable comments and suggestions which have improved the original version of the current paper. References [1] D. Bryant, M. Buchanan and I. M. Wanless, The spectrum for quasigroups with cyclic automorphisms and additional symmetries, Discrete Math. 304 (2009), no. 4, 821-833. [2] N. J. Cavenagh, C. Hamalainen and A. M. Nelson, On completing three cyclically generated transversals to a latin square, Finite Fields Appl. 15 (2009), no. 3, 294–303. [3] N. J. Cavenagh and D. S. Stones, Near-automorphisms of Latin squares, J. Combin. Des. 19 (2011), no. 1, pp. 365–377. [4] D. A. Cox, J. B. Little and D. O’Shea, Using Algebraic Geometry, Springer-Verlag, New York, 1998. [5] W. Decker, G.-M. Greuel, G. Pfister and H. Sch¨onemann, Singular 3-1-3. A computer algebra system for polynomial computations, 2011. http://www.singular.uni-kl.de. [6] R. Euler, R. E. Burkard and R. Grommes, On Latin squares and the facial structure of related polytopes, Discrete Math. 62 (1986), no. 2, 155-181. [7] R. M. Falc´on, Latin squares associated to principal autotopisms of long cycles. Application in Cryptography, Proceedings of Transgressive Computing 2006: a conference in honor of Jean Della Dora (2006), 213 - 230. 21 [8] R. M. Falc´on, Study of Critical Sets in Latin Squares by using the Autotopism Group, Electronic Notes in Discrete Mathematics 29 (2007), 503–507. [9] R. M. Falc´on, Designs based on the cycle structure of a Latin square autotopism, Proceedings of 1st Hispano-Moroccan Days on Applied Mathematics and Statistics (2008), 479–484. [10] R. M. Falc´on, Cycle structures of autotopisms of the Latin squares of order up to 11, Ars Comb. (in press). Available from http://arxiv.org/abs/0709.2973. [11] R. M. Falc´on, Singular library, http://personal.us.es/raufalgan/LS/pls.lib. [12] R. M. Falc´on and J. Mart´ın-Morales, Gr¨obner bases and the number of Latin squares related to autotopisms of order ≤7, J. Symbolic Comput. 42 (2007), no. 11–12, 1142–1154. [13] R. M. Falc´on and J. Mart´ın-Morales, The 3-dimensional planar assignment problem and the number of Latin squares related to an autotopism, Proceedings of XI Spanish Meeting on Computational Algebra and Applications (2008), 89–92. [14] M. Ghandehari, H. Hatami and E. S. Mahmoodian, On the size of the minimum critical set of a Latin square, Discrete Math. 293 (2005), no. 1-3, 121–127. [15] M. Gr¨uttm¨uller, Completing partial latin squares with two cyclically generated prescribed diagonals, J. Combin. Theory Ser. A 103 (2003), no. 2, 349–362. [16] M. Gr¨uttm¨uller, Completing partial latin squares with prescribed diagonals, Discrete Appl. Math. 138 (2004), no. 1–2, 89–97. [17] G. H. Hardy, S. and Ramanujan, Asymptotic Formulae in Combinatory Analysis, Proc. London Math. Soc. 17 (1918), 75–115. [18] A. Hulpke, P. Kaski and P. R. J. ¨ Osterg˚ard, The number of Latin squares of order 11, Math. Comp. 80 (2011), no. 274, 1197–1219. 22 [19] B. Kerby and J. D. H. Smith, Quasigroup automorphisms and symmetric group characters, Comment. Math. Univ. Carol. 51 (2010), no. 2, 279– 286. [20] B. Kerby and J. D. H. Smith, Quasigroup automorphisms and the Norton-Stein complex, Proc. Amer. Math. Soc. 138 (2010), no. 9, 3079– 3088. [21] S. R. Kumar, A. Russell and R. Sundaram, Approximating Latin square extensions, Algorithmica 24 (1999), no. 2, 128–138. [22] C. Laywine, An expression for the number of equivalence classes of Latin squares under row and column permutations, J. Combin. Theory Ser. A 30 (1981), no. 3, 317–321. [23] C. Laywine and G. L. Mullen, Latin cubes and hypercubes of prime order, Fibonacci Quart. 23 (1985), no. 2, 139–145. [24] B. D. McKay, A. Meynert and W. Myrvold. Small Latin Squares, Quasigroups and Loops, J. Combin. Des. 15 (2007), no. 2, 98– 119. [25] B. D. McKay. http://cs.anu.edu.au/∼bdm/data/latin.html. [26] A. A. Sade, Autotopies des quasigroupes et des syst`emes associatives, Arch. Math. 4 (1968), no. 1, 1–23. [27] D. S. Stones, The parity of the number of quasigroups, Discrete Math. 310 (2010), no. 21, 3033–3039. [28] D.S. Stones, On the number of Latin rectangles, Ph.D. Thesis, Monash University, 2010. Available from http://arrow.monash.edu.au/hdl/1959.1/167114. [29] D. S. Stones, P. Vojtˇechovsk´y and I. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares. Preprint avaliable from http://www.du.edu/media/documents/nsm/mathematics/preprints/ m1101.pdf [30] D. S. Stones and I. M. Wanless, Compound orthomorphisms of the cyclic group, Finite Fields Appl. 16 (2010), no. 4, 277– 289. 23 [31] D. S. Stones and I. M. Wanless, A congruence connecting Latin rectangles and partial orthomorphisms, Ann. Comb., to appear. [32] I. M. Wanless, Diagonally cyclic Latin squares, European J. Combin. 25 (2004), no. 3, 393–413. Appendix A. Glossary of symbols. AnSet of automorphisms of at least one Latin square of order n. AnSet of autotopisms of at least one Latin square of order n. APnSet of autotopisms of at least one partial Latin square of order n. CSnCycle structures of Sn. CSSCycle structures of S⊆In. CSn,m {nzn·. . . ·1z1∈ CSn:zm>0 and zi= 0,∀i∈[m−1]}. CΘΘ-completable partial Latin squares. CΘ,s CΘ∩ PLSΘ,s. czCardinality of CΘ, for all Θ ∈Iz. cz,s Cardinality of CΘ,s, for all Θ ∈Iz. InIsotopisms of nelements. IP,Q Isotopisms between two partial Latin squares Pand Q. IzIsotopisms with cycle structure z. LCMn{(i, j, k)∈[n]3: lcm(i, j) = lcm(i, k) = lcm(j, k) = lcm(i, j, k)}. LCMz{(i, j)∈[n]2:∃k∈[n] s.t. (i, j, k)∈LCMnand z1i·z2j·z3k>0}. LSnLatin squares of order n. LSzLatin squares related to Iz. LSΘLatin squares related to Θ ∈An. LSΘ,P Latin squares of LSΘto which P∈ PLSncan be completed. lzLower bound of the size of any P∈ PLSz(Proposition 3.2). [n]{1,. . . ,n}. nzNumber of cycles of z∈ CSn. nπNumber of cycles of π∈Sn. O(P) Orthogonal representation of P∈ PLSn. |P|Size of P∈ PLSn. [P] Isotopism class of P∈ PLSn. p(n) Number of partitions of n. PπParastrophic partial Latin square of P∈ PLSnw.r.t. π∈S3. PΘIsotopic partial Latin square of P∈ PLSnw.r.t. Θ ∈In. 24 PLSnNon-empty partial Latin squares of order n. PLSn,s Partial Latin squares of order nand size s. PLSzPartial Latin squares related to Iz. PLSΘPartial Latin squares related to Θ ∈An. PLSΘ,[P]PLSΘ∩[P]. PLSΘ,s PLSΘ∩ PLSn,s, where Θ ∈In. SnSymmetric group of nelements. uzUpper bound of the size of any P∈ PLSz(Proposition 3.2). zΘCycle structure of Θ ∈In. [zΘ] Parastrophic class of the cycle structure of Θ ∈In. ∆(z)|LSΘ|, for any Θ ∈Iz. ∆[P](z)|PLSΘ,[P]|, for any Θ ∈Iz. ∆s(z)|PLSΘ,s|, for any Θ ∈Iz. ∆P(z)|PLSΘ|, for any Θ ∈Iz. π∞Union of 1-cycles of π∈Snwritten in natural order. ∼Equivalence relation between isotopic partial Latin squares. 25