Gröbner bases and the number of Latin squares related to autotopisms of order ≤7

Gr¨obner bases and the number of Latin squares related to autotopisms of order ≤7. R. M. Falc´on Department of Geometry and Topology. University of Seville. Avda. Reina Mercedes s/n - 41080, Seville (Spain). J. Mart´ın-Morales Department of Mathematics. University of Zaragoza. C/ Pedro Cerbuna, 12 - 50009, Zaragoza (Spain). Abstract Latin squares can be seen as multiplication tables of quasigroups, which are, in general, noncommutative and non-associative algebraic structures. The number of Latin squares having a fixed isotopism in their autotopism group is at the moment an open problem. In this paper, we use Gr¨obner bases to describe an algorithm that allow one to obtain the previous number. Specifically, this algorithm is implemented in Singular to obtain the number of Latin squares related to any autotopism of Latin squares of order up to 7. Key words: Autotopism Group, Gr¨obner Basis, Latin Square. 1. Introduction Aquasigroup (Albert, 1943) is a nonempty set Gendowed with a product ·, such that if any two of the three symbols a, b, c in the equation a·b=care given as elements of G, the third one is uniquely determined as an element of G. It is equivalent to say that Gis endowed with left and right division. Specifically, quasigroups are, in general, non-commutative and non-associative algebraic structures. Two quasigroups (G, ·) and (H, ◦) are isotopic (Bruck, 1944) if there are three bijections α, β, γ from Hto G, such that γ(a◦b) = α(a)·β(b), for all a, b ∈H. The triple Θ = (α, β, γ) is called an isotopism from (G, ·) to (H, ◦). Email addresses: [email protected] (R. M. Falc´on), [email protected] (J. Mart´ın-Morales). URLs: http://www.personal.us.es/raufalgan (R. M. Falc´on), http://www.grupo.us.es/gmcedm (J. Mart´ın-Morales). Preprint submitted to Elsevier July 2, 2007 The multiplication table of a quasigroup is a Latin square. A Latin square Lof order nis an n×narray with elements chosen from a set of ndistinct symbols {x1, ..., xn}, such that each symbol occurs precisely once in each row and each column. The set of Latin squares of order nis denoted by LS(n). The number of Latin squares of order n is denoted by Nn. A partial Latin square,P, of order n, is a n×narray with elements chosen from a set of nsymbols, such that each symbol occurs at most once in each row and in each column. The set of partial Latin squares of order nis denoted as PLS(n). An exhaustive study about Latin squares and their applications is given by Laywine and Mullen (1998). n2 3 4 5 6 7 Nn2 12 576 161280 812851200 61479419904000 Table 1. Number of Latin squares of order 2 ≤n≤7. In this paper, for any given n∈N, we denote by [n] the set {1,2, ..., n}. Specifically, we assume that the set of symbols of any Latin square of order nis [n]. The symmetric group on [n] is denoted by Sn. Given a permutation δ∈Sn, it is defined the set of its fixed points Fix(δ) = {i∈[n]|δ(i) = i}. The cycle structure of δis the sequence lδ= (lδ 1,lδ 2, ..., lδ n), where lδ iis the number of cycles of length iin δ, for all i∈ {1,2, ..., n}. On the other hand, given L= (li,j)∈LS(n), the orthogonal array representation of Lis the set of n2 triples {(i, j, li,j)|i, j ∈[n]}. The previous set is identified with Land then, it is written (i, j, li,j)∈L, for all i, j ∈[n]. Analogosly, any P∈PLS(n) will be identified with the set {(i, j, li,j)|i, j ∈[n], li,j =∅}. Given σ∈S3, one defines the conjugate Latin square Lσ∈LS(n) of L, such that if T= (i, j, li,j)∈L, then (πσ(1)(T), πσ(2)(T), πσ(3)(T)) ∈Lσ, where πigives the ith coordinate of T, for all i∈[3]. In this way, each Latin square Lhas six conjugate Latin squares associated with it: LId =L,L(12) =Lt,L(13),L(23),L(123) and L(132). Since a Latin square is the multiplication table of a quasigroup, an isotopism of a Latin square L∈LS(n) is therefore a triple Θ = (α, β, γ)∈ In=Sn×Sn×Sn. In this way, α, β and γare permutations of rows, columns and symbols of L, respectively. The resulting square LΘis also a Latin square and it is said to be isotopic to L. In particular, if L= (li,j), then LΘ={(i, j, γ (lα−1(i),β−1(j))|i, j ∈[n]}. If γ=ϵ, the identity map on [n], Θ is called a principal isotopism. The cycle structure of an isotopism Θ=(α, β, γ)∈ Inis the triple (lα,lβ,lγ), where lδis the cycle structure of δ, for all δ∈ {α, β, γ}. The set of isotopisms of Latin squares of order nhaving (lα,lβ,lγ) as their cycle structures is denoted by In(lα,lβ,lγ).              L1=  1234 2143 3412 4321   Θ = ((12)(34),(23), ϵ)∈ I4((0,2,0,0),(2,1,0,0),(4,0,0,0)) ⇒LΘ 1=     2 4 1 3 1 3 2 4 4 2 3 1 3 1 4 2     Figure 1. Isotopism permuting 1st with 2nd and 3rd with 4th rows and 2nd with 3rd columns. 2 An isotopism which maps Lto itself is an autotopism. (ϵ, ϵ, ϵ) is called the trivial autotopism. The possible cycle structures of the set of non-trivial autotopisms of Latin squares of order up to 11 have been obtained by Falc´on (2007). The stabilizer subgroup of Lin Inis its autotopism group,U(L) = {Θ∈ In|LΘ=L}. Given L∈LS(n), Θ = (α, β, γ)∈ U(L) and σ∈S3, it is verified that Θσ= (πσ(1)(Θ), πσ(2)(Θ), πσ(3)(Θ)) ∈ U(Lσ), where πigives the ith component of Θ, for all i∈[3]. Given Θ ∈ In, the set of all Latin squares Lsuch that Θ ∈ U(L) is denoted by LS(Θ) and the cardinality of LS(Θ) is denoted by ∆(Θ). The computation of ∆(Θ) for any isotopism Θ ∈ Inis at the moment an open problem having relevance in secret sharing schemes related to Latin squares and only studied in some cases where Θ is a principal autotopism (Falc´on, 2006). Although ∆(Θ) can be studied in a combinatorial way, in this paper we see that Gr¨obner bases turn out to be useful to obtain this number. Specifically, given a Θ = (α, β, γ)∈ In, we see that, if kα≤nis the number of cycles of α, then LS(Θ) can be obtained starting from a set of Latin rectangles of order kα·n, that is to say, a set of kα×narrays, with elements chosen from [n], such that each symbol occurs precisely once in each row. This set of Latin rectangles can be seen as the vector space associated with the solution of an algebraic system of polynomial equations related to the isotopism Θ, which can be solved using Gr¨obner bases. We follow the ideas implemented by Bayer (1982) (see also Adams and Loustaunau, 1994) to solve the problem of n-colouring a graph, since every Latin square of order nis equivalent to an n-coloured bipartite graph Kn,n (Laywine and Mullen, 1998). A similar argument has been used by Gago et al. (2006) (see also Mart´ın-Morales, 2006) to give an algorithm to solve Sudokus, which are indeed a particular case of Latin squares. The structure of the paper is as follows. In Section 2, we study the set of Latin squares having an isotopism with a given cycle structure in their autotopism group. Specifically, we prove that ∆(Θ) only depends on the cycle structure of Θ. In Section 3, we use Gr¨obner bases to define an algorithm that allow one to obtain ∆(Θ). Finally, in Section 4, this algorithm is implemented in Singular (Greuel, Pfister and Sch¨onemann, 2005) to get the number of Latin squares of order ≤7 related to any autotopism. 2. Cycle structures of Latin square autotopisms Every permutation of Sncan be written as the composition of pairwise disjoint cycles. So, from now on, given Θ = (α, β, γ)∈ In, we will assume that, for all δ∈ {α, β, γ}: δ=Cδ 1◦Cδ 2◦... ◦Cδ kδ,(1) where: i) For all i∈[kδ], one has Cδ i=(cδ i,1cδ i,2... cδ i, λδ i), with λδ i≤nand cδ i,1= minj{cδ i,j}. If λδ i= 1, then Cδ iis a cycle of lenght 1 and so, cδ i,1∈Fix(δ). ii) ∑iλδ i=n. iii) For all i, j ∈[kδ], one has λδ i≥λδ j, whenever i≤j. iv) Given i, j ∈[kδ], with i < j and λδ i=λδ j, one has cδ i,1< cδ j,1. From now on, for a given δ∈ {α, β, γ}and i∈[kδ], we will write a∈Cδ iif there exists j∈[λδ i] such that a=cδ i,j. The following results hold: 3 Proposition 1 Let Θ = (α, β, γ)∈ Inbe such that ∆(Θ) >0. Let L= (li,j)∈LS(Θ) be such that all the triples of one of the following two Latin subrectangles of Lare known: i) RL={(cα r,1, cβ s,v, lcα r,1,cβ s,v )|r∈[kα], s ∈[kβ]and v∈{[λβ s],if λα r>1, [1],if λα r= 1.}. ii) R′ L={(cα r,u, cβ s,1, lcα r,u,cβ s,1)|r∈[kα], s ∈[kβ]and u∈{[λα r],if λβ s>1, [1],if λβ s= 1.}. Then, all the triples of Lare known. Proof. We will prove the result in case are known the elements of RL, the other case follows analogously. Let (i, j, li,j )∈Lbe such that i∈ Fix(α) and let r0∈[kα], u0∈ [λα r0], s0∈[kβ] and v0∈[λβ s0] be such that cα r0,u0=iand cβ s0,v0=j. From the hypothesis, the triple (cα r0,1, β1−u0(cβ s0,v0), lcα r0,1,β1−u0(cβ s0,v0)) is known. Thus, li,j =lcα r0,u0,cβ s0,v0 = γu0−1(lcα r0,1,β1−u0(cβ s0,v0)) and therefore, the triple (i, j, li,j) is known. By the other way, let (i, j, li,j)∈Lbe such that i∈Fix(α) and let r0∈[kα], s0∈[kβ] and v0∈[λβ s0] be such that cα r0,1=iand cβ s0,v0=j. From the hypothesis, the triple (cα r0,1, cβ s0,1, lcα r0,1,cβ s0,1) is known. Thus, li,j =lcα r0,1,cβ s0,v0 =γv0−1(lcα r0,1,cβ s0,1) and therefore, the triple (i, j, li,j) is known. 2 Proposition 2 Let (lα,lβ,lγ)be the cycle structure of a Latin square isotopism and let us consider Θ1= (α1, β1, γ1),Θ2= (α2, β2, γ2)∈ In(lα,lβ,lγ). Then, ∆(Θ1) = ∆(Θ2). Proof. Since Θ1and Θ2have the same cycle structure, we can consider the isotopism Θ = (σ1, σ2, σ3)∈ In, where: i) σ1(cα1 i,j ) = cα2 i,j , for all i∈[kα1] and j∈[λα1 i], ii) σ2(cβ1 i,j) = cβ2 i,j, for all i∈[kβ1] and j∈[λβ1 i], iii) σ3(cγ1 i,j) = cγ2 i,j, for all i∈[kγ1] and j∈[λγ1 i]. Now, let us see that ∆(Θ1)≤∆(Θ2). If ∆(Θ1) = 0, the result is immediate. Otherwise, let L1= (li,j)∈LS(Θ1) and let us see that LΘ 1= (l′ i,j)∈LS(Θ2). Specifically, we must prove that (α2(i), β2(j), γ2(l′ i,j)) ∈LΘ 1, for all (i, j, l′ i,j)∈LΘ 1. So, let us consider (i0, j0, l′ i0,j0)∈LΘ 1and let r0∈[kα2], u0∈[λα2 r0], s0∈[kβ2], v0∈[λβ2 s0], t0∈[kγ2] and w0∈[λγ2 t0] be such that cα2 r0,u0=i0, cβ2 s0,v0=j0,and cγ2 t0,w0=l′ i0,j0. Thus: (cα1 r0,u0, cβ1 s0,v0, cγ1 t0,w0) = (σ−1 1(i0), σ−1 2(j0), σ−1 3(l′ i0,j0)) ∈L1. Next, since L1∈LS(Θ), we have that (α1(cα1 r0,u0), β1(cβ1 s0,v0), γ1(cγ1 t0,w0)) ∈L1. Therefore: (α2(i0), β2(j0), γ2(l′ i0,j0)) = (α2(cα2 r0,u0), β2(cβ2 s0,v0), γ2(cγ2 t0,w0)) = = (σ1(α1(cα1 r0,u0)), σ2(β1(cβ1 s0,v0)), σ3(γ1(cγ1 t0,w0)) ∈LΘ 1. Analogously, it is verified that L(σ−1 1,σ−1 2,σ−1 3) 2∈LS(Θ1), for all L2∈LS(Θ2), and hence, the result follows. 2 4 From Proposition 2, the number of Latin squares having a fixed isotopism Θ ∈ In in its autotopism group only depends on the cycle structure of Θ. Hence, from now on, ∆(lα,lβ,lγ) will denote the number of Latin squares having a fixed autotopism Θ ∈ In(lα,lβ,lγ) in its autotopism group. Specifically, the following results are verified: Proposition 3 Let (lα,lβ,lγ)be the cycle structure of a Latin square autotopism Θ = (α, β, γ)and let us consider σ∈S3. Then, ∆(lα,lβ,lγ) = ∆(lπσ(1)(Θ),lπσ(2)(Θ),lπσ(3)(Θ)), where πigives the ith component of Θ, for all i∈[3]. Proof. Since Θ is a Latin square autotopism, it must be ∆(Θ) >0. Let L∈LS(Θ) and consider the isotopism Θσ= (πσ(1)(Θ), πσ(2)(Θ), πσ(3)(Θ)), then it is verified that Θσ∈ In(lπσ(1)(Θ),lπσ(2)(Θ),lπσ(3)(Θ)) and Lσ∈LS(Θσ). Thus, ∆(Θ) ≤∆(Θσ). Moreover, if L′∈LS(Θσ), then L′σ−1∈LS(Θ). Therefore, ∆(Θ) = ∆(Θσ) and thus, from Proposition 2, ∆(lα,lβ,lγ) = ∆(lπσ(1)(Θ),lπσ(2)(Θ),lπσ(3)(Θ)). 2 Corollary 4 (lα,lβ,lγ)is the cycle structure of a Latin square autotopism if and only if there exists a permutation σ∈S3such that (lπσ(1)(Θ),lπσ(2)(Θ),lπσ(3)(Θ))is the cycle structure of a Latin square autotopism, such that kπσ(1)(Θ) ≤kπσ(2)(Θ) ≤kπσ(3)(Θ). Proof. Since (lα,lβ,lγ) is the cycle structure of a Latin square autotopism if and only if ∆(lα,lβ,lγ)>0, the result is an immediate consequence of Proposition 3. 2 Remark 5 From Proposition 2 and Corollary 4, if we want to obtain the number ∆(Θ) related to an autotopism Θ = (α, β, γ)∈ In, we can suppose that kα≤kβ≤kγ. Otherwise, we would find a permutation σ∈S3such that (lπσ(1)(Θ),lπσ(2)(Θ),lπσ(3)(Θ))is the cycle structure of a Latin square autotopism, such that kπσ(1)(Θ) ≤kπσ(2)(Θ) ≤kπσ(3)(Θ) and we would work with the autotopism Θσ. Moreover, from Proposition 2, we can suppose that the autotopism Θis such that cδ r,1=r, for all r∈[kα]and for all δ∈ {α, β, γ}. To simplify the calculus of ∆(Θ), it is useful to study previously the symmetry of the autotopism Θ. Specifically, we can find a partial Latin square P∈PLS(n) such that there exists cP>0 verifying that ∆(Θ) = cP·|LSP(Θ)|, where LSP(Θ) = {L∈LS(Θ) | P⊆L}. The number cPwill be called P-coefficient of symmetry of Θ. The following result is immediate: Lemma 6 Let Θ∈ In. Given i, j ∈[n], it is verified that: LS(Θ) = ⊔ k∈[n] LS{(i,j,k)}(Θ) = ⊔ k∈[n] LS{(i,k,j)}(Θ) = ⊔ k∈[n] LS{(k,i,j)}(Θ). ∆(Θ) = ∑ k∈[n] |LS{(i,j,k)}(Θ)|=∑ k∈[n] |LS{(i,k,j)}(Θ)|=∑ k∈[n] |LS{(k,i,j)}(Θ)|. 2 The following results will be useful in our study: 5 Proposition 7 Let Θ = (α, β, γ)∈ Inbe such that ∆(Θ) >0and lα 1·lβ 1>0and let us consider L0= (li,j)∈LS(Θ). Let i∈F ix(α)and j∈Fix(β). Then, li,j ∈Fix(γ). As a consequence, ∆(Θ) is a multiple of the number of Latin squares of order lα 1. Proof. It is enough to observe that γ(li,j) = lα(i),β(j)=li,j . To prove the consequence, let us observe that, from Theorem 1 of McKay, Meynert and Myrvold (2007), since lα 1·lβ 1>0, it must be lα=lβ=lγ. Specifically, lα 1=lβ 1=lγ 1is the number of fixed points of α, β and γ. Therefore, the subsquare R0= (ri,j) of L0verifying that its row indices are fixed points of αand its column indices are fixed points of βmust be a Latin subsquare of L0with elements chosen from the set Fix(γ) of fixed points of γ. Moreover, if we interchange in L0the subsquare R0with any Latin subsquare R1∈LS(lα 1) of the same order with elements chosen from Fix(γ), we obtain a different Latin square of LS(Θ). Indeed, it must be |LSR0(Θ)|=|LSR1(Θ)|and, therefore, we finally obtain that ∆(Θ) = Nlα 1· |LSR0(Θ)|.2 Theorem 8 Let Θ = (α, β, γ)∈ Inbe a non-trivial autotopism verifying the conditions of Remark 5 such that ∆(Θ) >0. Given δ∈ {α, β, γ}, let hδbe the cardinality of the set {i∈[n]|lδ i>0}. The following asserts are verified: a) If hα=hβ= 1, then ∆(Θ) = n· |LS{(1,1,1)}(Θ)|. b) Let us suppose that there exists i0∈[n]\ {1}such that lα i0=lβ i0= 0. If lα 1=lβ 1>0 and hα=hβ= 2, then: ∆(Θ) = lα i0−1 ∏ k=0 (n−lα 1−k·i0)2· |LS{(i,i,kα),(kα,i,i)|i∈[kα−lα 1]}(Θ)|. ∆(Θ) = lα i0−1 ∏ k=0 (n−lα 1−k·i0)2· |LS{(i,i,kα),(i,kα,i)|i∈[kα−lα 1]}(Θ)|. Proof. Let L= (li,j)∈LS(Θ). The first assert is immediate because, in this case, |LS{(1,i,1)}(Θ)|=|LS{(1,j,1)}(Θ)|, for all i, j ∈[n]. Let us see the second assert. We will prove the first expression, the other one follows analogously. Since lα 1·lβ 1>0 and Θ verifies the conditions of Remark 5, it must be kα∈Fix(α) = Fix(β) = Fix(γ). Now, from Proposition 7 and the symmetry of Θ, |LS{(1,i,kα)}(Θ)|= 0, for all i∈Fix(β) and |LS{(1,i,kα)}(Θ)|=|LS{(1,j,kα)}(Θ)|, for all i, j ∈ Fix(β). Thus, from Lemma 6, ∆(Θ) = (n−lα 1)·|LS{(1,1,kα)}(Θ)|. Now, it must be |LS{(1,1,kα),(2,i,kα)}(Θ)|= 0, for all i∈Fix(β)∪ Cβ 1and |LS{(1,1,kα),(2,i,kα)}(Θ)|=|LS{(1,1,kα),(2,j,kα)}(Θ)|, for all i, j ∈ Fix(β)∪Cβ 1. So, ∆(Θ) = (n−lα 1)·(n−lα 1−i0)· |LS{(1,1,kα),(2,2,kα)}(Θ)|. Analogously, it can be proven that ∆(Θ) = ∏lα i0−1 k=0 (n−lα 1−k·i0)· |LS{(i,i,kα)|i∈[kα−lα 1]}(Θ)|. Let P={(i, i, kα)| i∈[kα−lα 1]} ∈ PLS(n). Next, it must be lkα,1∈ F ix(γ) and |LSP∪{(kα,1,i)}(Θ)|= |LSP∪{(kα,1,j)}(Θ)|, for all i, j ∈ Fix(γ). So, ∆(Θ) = (n−lα 1)·∏lα i0−1 k=0 (n−lα 1−k·i0)· |LSP∪{(kα,1,1)}(Θ)|. Now, it must be lkα,2∈ Fix(γ)∩Cγ 1and |LSP∪{(kα,1,1),(kα,2,i)}(Θ)|= |LSP∪{(kα,1,1),(kα,2,j)}(Θ)|, for all i, j ∈ Fix(γ)∩Cγ 1. So, ∆(Θ) = (n−lα 1)·(n−lα 1−i0)· ∏lα i0−1 k=0 (n−lα 1−k·i0)· |LSP∪{(kα,1,1),(kα,2,2)}(Θ)|. Analogously, it can be finally proven that ∆(Θ) = ∏lα i0−1 k=0 (n−lα 1−k·i0)2· |LSP∪{(kα,i,i)|i∈[kα−lα 1]}(Θ)|.2 6 3. Gr¨obner bases and Latin square autotopisms Gr¨obner bases can be used to obtain the set LS(n) of Latin squares of order nby following the ideas of Bayer (1982) (see also Adams and Loustaunau, 1994), since every Latin square of order nis equivalent to an n-coloured bipartite graph Kn,n (Laywine and Mullen, 1998). In particular, given a generic Latin square L= (li,j)∈LS(n), we can consider the set of n2variables {xi,j |i, j ∈[n]}, where xi,j corresponds to the triple (i, j, li,j)∈L, for all i, j ∈[n]. Then, we define: F(x) = n ∏ m=1 (x−m), G(x, y) = F(x)−F(y) x−y. Thus, given i, i′, j, j′∈[n] such that i=i′and j=j′, it must follow that F(li,j) = 0 = G(li,j, li′,j) = G(li,j , li,j′), because L∈LS(n). Thus, if we define the following ideal of Q[x] = Q[x1,1, ..., xn,n]: I=⟨F(xi,j), G(xi,j, xi′,j), G(xi,j , xi,j′)|i, i′, j, j′∈[n], i =i′and j=j′⟩ generated by n2+∑(i,j)∈[n]×[n]((n−i) + (n−j)) polynomials, it is verified that the set of zeros of I, noted by V(I), corresponds to the set LS(n). Remark 9 Once we know that the polynomial F(x1,1)∈I, it is easy to see that the rest of the polynomials F(xi,j),(i, j)= (1,1), are redundant so we can delete them. The ideal Ican be generated by 1 + ∑(i,j)∈[n]×[n]((n−i)+(n−j)) polynomials. Remark 10 It is well know that, as ideals Iproduced by Latin squares are radical (Cox et al., 1997, Ch. 2, Prop. 2.7.), the number of elements in V(I)is equal to the dimension of the Q-vector space Q[x]/I, and this number can be computed with any Gr¨obner basis with respect to any term ordering. Now, let Θ = (α, β, γ)∈ In(lα,lβ,lγ) be a Latin square autotopism verifying the conditions of Remark 5. In this section, we are interested in obtaining the number ∆(Θ). The following set will be useful: SΘ={(i, j)|i∈[kα], j ∈{[n],if i∈ Fix(α), [kβ],if i∈Fix(α).}. Remark 11 From Proposition 1, we can eliminate some of the polynomials defining the above-defined ideal Ito obtain the Latin squares of LS(Θ). In particular, if we consider the first case of that result, we can restrict our study to those polynomials in which only appear some of the (kα−lα 1)·n+lα 1·kβvariables xi,j, where (i, j)∈SΘ. Hence, we are interested in the following ideal of Q[xi,j |(i, j)∈SΘ]: I′=⟨F(x1,1), G(xi,j, xi′,j), G(xi,j, xi,j′)|i, i′∈[kα], j, j′∈[n], i =i′and j=j′⟩+ ⟨G(xi,j, xi′,j), G(xi,j, xi,j′)|i∈Fix(α), i′∈[n], j, j′∈[kβ], i =i′and j=j′⟩. Next, let P= (pi,j)∈PLS(n) be such that pi,j =∅, for all (i, j)∈ SΘand let cP be the P-coefficient of symmetry of Θ. Thus, we know that ∆(Θ) = cP· |LSP(Θ)|and we will calculate |LSP(Θ)|starting from the set of solutions of an algebraic system of polynomial equations related to Θ and P. Specifically, we obtain the following algorithm: 7 Algorithm 1 Lst (computing the number of Latin squares having a fixed isotopism) Input: Θ = (α, β, γ)∈ In, an isotopism verifying the conditions of Remark 5; kα, the number of cycles of α; v=(v1, v2, ..., v(kα−lα 1)·n+lα 1·kβ)corresponding to triples of a partial Latin square P∈PLS(n) such that pi,j =∅, for all (i, j)∈ SΘ; c, the P-coefficient of symmetry of Θ. Output: ∆(Θ), the number of Latin squares having Θ as an autotopism; I′:= ⟨F(x1,1), G(xi,j, xi′,j), G(xi,j, xi,j′)|i, i′∈[kα], j, j′∈[n], i =i′and j=j′⟩+ ⟨G(xi,j, xi′,j), G(xi,j, xi,j′)|i∈Fix(α), i′∈[n], j, j′∈[kβ], i =i′and j=j′⟩; I′:= I′+⟨xi,j −vi,j |(i, j)∈SΘ, vi,j = 0 ⟩; GI′:= Gr¨obner basis of I′with respect to any term ordering; t:= dimQ(Q[x]/I); ◃ t is the cardinality of V(I′) SOL := V(I′); ◃list of all elements in V(I′) Delta := 0; ◃the output is c·Delta for l= 1 to tdo L:= the n×narray associated with SOL[ l]; ◃see Proposition 1 if Lis a Latin square then Delta ←Delta +1; end if end for return c·Delta; Proof. (Correctness of the algorithm). i) Given a partial Latin square P∈PLS(n) such that pi,j =∅, for all (i, j)∈ SΘ, we will consider the vector vsuch that:                v(i−1)·n+j={pi,j,if pi,j =∅, 0,if pi,j =∅,and i∈ Fix(α), j ∈[n] v(kα−lα 1)·n+(i−kα+lα 1−1)·kβ+j={pi,j,if pi,j =∅, 0,if pi,j =∅,and i∈Fix(α), j ∈[kβ] ii) The first definition of I′corresponds to the ideal defined in Remark 11. The second one is obtained by adding the polynomials associated to the filled cells of P. iii) From Proposition 1, we are not interested in V(I′), but in the subset {RL|L∈ LSP(Θ)} ⊆ V(I′), because its cardinality is equal to |LSP(Θ)|. Thus, finally, once we have obtained V(I′), we must check how many of its elements are in the previous subset. Specifically: iii.1) Given an element of V(I′), we follow the proof of Proposition 1 to define the n×narray associated with it. iii.2) Then, the obtained array belongs to the set LSP(Θ) if and only if it is a Latin square. iv) The final output is therefore ∆(Θ) = cP· |LSP(Θ)|. 2 8 Let us see some examples: Example 12 Let Θ = ((1234),(1234),(12)) ∈ I4((0,0,0,1),(0,0,0,1),(2,1,0,0)). Then: F(x) = 4 ∏ m=1 (x−m), G(x, y) = F(x)−F(y) x−y. Let us consider the ideal of Q[x11, x12, x13, x14]: I′=⟨F(x11), G(x11, x12), G(x11, x13), G(x11, x14), G(x12, x13), G(x12, x14), G(x13, x14)⟩, which Gr¨obner basis with respect to the degree reverse lexicographical ordering is: {x3 13 +x2 13x14 +x13x2 14 +x3 14 −10x2 13 −10x13x14 −10x2 14 + 35x13 + 35x14 −50, x2 12 +x12x13 +x2 13 +x12x14 +x13x14 +x2 14 −10x12 −10x13 −10x14 + 35, x4 14 −10x3 14 + 35x2 14 −50x14 + 24, x11 +x12 +x13 +x14 −10 }. It can be proven that the algebraic system of polynomial equations given by the previous Gr¨obner basis has 24 solutions. However, only 8 of them correspond to a Latin square by following the proof of Proposition 1. Therefore, ∆(Θ) = 8. Moreover: ∆((0,0,0,1),(0,0,0,1),(2,1,0,0)) = 8. Example 13 Let Θ = (ϵ, (12345),(12345)) ∈ I5((5,0,0,0,0),(0,0,0,0,1),(0,0,0,0,1)). In this case, kα= 5 >1 = kβ=kγ. Let us consider, for example, the permutation (13) ∈S3and let us define the principal isotopism Θ′= Θ(13) = ((12345),(12345), ϵ)∈ I5((0,0,0,0,1),(0,0,0,0,1),(5,0,0,0,0)). From Proposition 3, ∆(Θ) = ∆(Θ′). Now: F(x) = 5 ∏ m=1 (x−m), G(x, y) = F(x)−F(y) x−y. Then, let us consider the ideal of Q[x11, x12, x13, x14, x15]: I′=⟨F(x11), G(x11, x12), G(x11, x13), G(x11, x14), G(x11, x15), G(x12, x13), G(x12, x14), G(x12, x15), G(x13, x14), G(x13, x15), G(x14, x15)⟩. which Gr¨obner basis with respect to the degree reverse lexicographical ordering is: {x3 13 +x2 13x14 +x13x2 14 +x3 14 +x2 13x15 +x13x14x15 +x2 14x15 +x13x2 15 +x14x2 15 +x3 15− −15x2 13 −15x13x14 −15x2 14 −15x13x15 −15x14x15 −15x2 15 + 85x13 + 85x14 + 85x15 −225, x2 12 +x12x13 +x2 13 +x12x14 +x13x14 +x2 14 +x12x15 +x13x15 +x14x15 +x2 15 −15x12− −15x13 −15x14 −15x15 + 85, x5 15 −15x4 15 + 85x3 15 −225x2 15 + 274x15 −120, x4 14 +x3 14x15 +x2 14x2 15 +x14x3 15 +x4 15 −15x3 14 −15x2 14x15 −15x14x2 15 −15x3 15 + 85x2 14+ +85x14x15 + 85x2 15 −225x14 −225x15 + 274, x11 +x12 +x13 +x14 +x15 −15 }. It can be proven that the algebraic system of polynomial equations given by the previous Gr¨obner basis has 120 solutions. Indeed, each one of them corresponds to a Latin square by following the proof of Proposition 1. Therefore, ∆(Θ) = ∆(Θ′) = 120. Moreover: ∆((5,0,0,0,0),(0,0,0,0,1),(0,0,0,0,1)) = ∆((0,0,0,0,1),(0,0,0,0,1),(5,0,0,0,0)) = 120. 9