Critical sets of Latin squares based on autoparatopisms
arXiv:2609.21532v1 [cs.CR] 18 Sep 2026
Manuel González-Regadera∗
Raúl M. Falcón†
Marı́a Dolores Frau ‡
Abstract In cryptography, critical sets of Latin squares have particularly been implemented to design secret sharing schemes. A main problem in these cryptographic protocols arises from absent holders of pieces of information that are common to different critical sets, because they become indispensable to recover the secret. This paper solves this problem by making use of the orbits of entries described by the autoparatopism group of the Latin square under consideration. To this end, we introduce the more general problem of computing critical sets of Latin squares having a given paratopism in their autoparatopism group. These critical sets depend only on the conjugacy class of the autoparatopism and the main class of the Latin square under consideration. Based on this fact, as an illustrative example, we determine the smallest and largest sizes of critical sets associated with autoparatopisms of Latin squares of order up to six. We implement this approach in the design of a new secret sharing scheme.
Keywords: Latin square, critical set, paratopism, isotopism, secret sharing scheme. 2020 MSC: 05B05; 20N05; 94A62.
1
Introduction
A partial Latin square of order n is an n × n partial array with nonempty entries in a given set of n symbols such that each symbol appears at most once per row and at most once per column. This is a Latin square if there are no empty entries in the array. ∗ Department of Applied Mathematics I, Universidad de Sevilla, Spain. [email protected] † Department of Applied Mathematics I, Universidad de Sevilla, Spain. [email protected] ‡ Department of Applied Mathematics I, Universidad de Sevilla, Spain. [email protected]
1
In cryptography, Latin squares and partial Latin squares have turned out to be useful in the design of new authentication schemes [1], block ciphers [2], cipher systems [3], cryptosystems [4], cryptographic primitives [5], encryption-decryption algorithms [6], error-correcting codes [7], image encryption [8], or pseudo-random sequences [9], among others. Of particular interest for the purposes of this paper, we highlight their implementation to design new secret sharing schemes [10–13]. These schemes were independently introduced by Shamir [14] and Blakley [15]. In this cryptographic protocol, a trusted dealer divides the key into pieces of information that are distributed among a group of participants. Any authorized subgroup that shares at least a predetermined number of pieces of information is sufficient to recover the key, while no subgroup that shares less than the threshold value can do so. Cooper, Donovan, and Seberry described [10] a secret sharing scheme in which the key is a given Latin square L, whose order is made public. Then, its entries are distributed to a group of participants so that, if L is the unique Latin square containing all the entries shared by a subgroup of participants, then they recover the key. Otherwise, they cannot do so. If the removal of any participant from this group makes this recovery impossible, then their entries constitute a critical set of L, a notion that plays a relevant role in this cryptographic protocol. In practice, the huge growth of the number of Latin squares when the order increases makes any brute-force attack unfeasible for discovering the key unless the attacker knows a wide amount of pieces of information. The problem of absent participants is addressed by considering multiple critical sets of different sizes that necessarily have one or more entries in common. The owners of these entries have a much higher hierarchy in the scheme, because they could even become indispensable to recover the key. This could be a handicap if they were disabled. This paper solves this problem by avoiding the need to search for different critical sets with common entries. More specifically, our approach makes use of the symmetries of the Latin square under consideration to get substitutes for these absent participants. To formally introduce our approach, let PL(n) and L(n) denote, respectively, the set of partial Latin squares of order n with nonempty entries in the set [n] := {1, . . . , n}, and its subset of Latin squares. Every partial Latin square P := (P [i, j]) ∈ PL(n) is uniquely identified with its set of nonempty entries Ent(P ) := {(i, j, P [i, j]) : i, j, P [i, j] ∈ [n]}. The cardinality of this set is the size of P . Furthermore, for each pair P1 , P2 ∈ PL(n), it is said that P1 contains P2 if Ent(P2 ) ⊆ Ent(P1 ). By abuse of notation, we denote this fact by P2 ⊆ P1 (or by P2 ⊂ P1 if Ent(P2 ) ⊂ Ent(P1 )). If P1 ∈ L(n), then P2 is completable to P1 , and P1 is a completion of P2 . If P2 is not completable to any other Latin square, then it is uniquely completable. If no partial Latin square P3 ⊂ P2 is also uniquely completable to P1 , then P2 is a critical set of P1 . This is minimal if there does not exist any other critical set of P1 of smaller size. 2
Both problems of deciding the existence of a completion and deciding whether a partial Latin square is uniquely completable are NP-complete [16, 17]. A greedy algorithm to find critical sets in Latin squares was described in [18]. We refer to [19] and [20] for a pair of comprehensive surveys on critical sets of Latin squares. Let L ∈ L(n). It is known [21, 22] the existence of critical sets of size cs(L) with n2 4
≤ cs(L) ≤
n2 − n . 2
The smallest and largest critical set of L are respectively denoted by scs(L) and lcs(L). Those ones of any given Latin square of order n are respectively denoted by scs(n) and lcs(n). Table 1 shows the known values of scs(n) and lcs(n) (see [23–28]). Table 1: Smallest and largest sizes of critical sets n
1
2
3
4
5
6
7
8
scs(n) lcs(n)
0 0
1 1
2 3
4 7
6 11
9 18
12
16
Some partial results concerning the exact value of scs(n) are also known for some families of Latin squares such as back-circulant [29,30] 1 or symmetric 1/3 ≤ ones [31].j More generally, it is known [23, 32–36] that n (log n) 2 k 2 ln(8π) 2 ln 2 2 scs(n) ≤ n4 and n2 1 − 2+ln + n 1 + − ln ln n ln n n ≤ lcs(n) ≤ n − 3n + 3. Both upper bounds are known to be reached for some values (see Table 1). That of scs(n) is conjectured to be always exact. The number and sizes of critical sets of a given Latin square depend only on its paratopism class [24]. Recall here that, if Sn denotes the symmetric group on the set [n], then a paratopism is any pair Θ := (π; f ) formed by a permutation π ∈ S3 and a triple f := (f1 , f2 , f3 ) ∈ Sn × Sn × Sn . Then, a partial Latin square P ∈ PL(n) is said to be paratopic to P Θ ∈ PL(n) if Ent(P Θ ) =
fπ(1) (eπ(1) ), fπ(2) (eπ(2) ), fπ(3) (eπ(3) ) : (e1 , e2 , e3 ) ∈ Ent(P ) .
(1)
The semidirect product S3 ≀ Sn := S3 ⋉ (Sn × Sn × Sn ) is a group under the composition of paratopisms (ρ; g)(π; f ) := (πρ; g π f ) , where g π := gπ−1 (1) , gπ−1 (2) , gπ−1 (3) . In particular, −1 (π; f )−1 := π −1 ; (f −1 )π .
3
(2)
(3)
The paratopism (π; f ) is an isotopism if π is the trivial permutation Id3 ∈ S3 ; and an isomorphism if, in addition, f1 = f2 = f3 . Furthermore, if f is trivial (that is, if its three components coincide with the trivial permutation Idn on the set [n]), then Θ is called a parastrophism from P to P Θ . If this is the case, then P and P Θ are said to be parastrophic. To be isotopic, isomorphic, parastrophic or paratopic constitute equivalence relations among partial Latin squares, which give respectively rise to the so-called isotopism, isomorphism, conjugacy and main classes of partial Latin squares. The distribution of Latin squares into these classes is known [37–39] for order up to 11, and that of partial Latin squares is known [40–43] for order up to six. A census of critical sets is known for every isotopism and main class of Latin squares of order up to six [27], while an example of a critical set is known for each main class of Latin squares of order seven [44]. An autoparatopism of a partial Latin square P ∈ PL(n) (respectively, autotopism) is a paratopism (respectively, isotopism) from P to itself. In this regard, autoparatopisms and autotopisms describe the symmetries of any partial Latin square. The set Apar(P ) (respectively, Atop(P )) formed by the autoparatopisms (respectively, autotopisms) of P is a group under the composition described in (2). In fact, every finite group is isomorphic to the autoparatopism group of at least one partial Latin square [45]. The concepts of completability and critical set of Latin squares have been extended [40] to those based on a given isotopism. More precisely, a partial Latin square P ∈ PL(n) is said to be f -completable, with f ∈ Sn × Sn × Sn , if there is a completion L ∈ L(n) of the former such that f ∈ Atop(L). If P is not f -completable to any other Latin square, then it is uniquely f completable. It is a f -critical set of L if no partial Latin square properly contained in P is also uniquely f -completable. If f is the trivial isotopism, then the classical notions of completability and critical set arise. A census of critical sets based on isotopisms is known [46] for all n ≤ 5. This paper further generalizes these concepts by dealing with critical sets of Latin squares containing a given paratopism in their autoparatopism group. The paper is organized as follows. In Section 2 we extend the concepts of completability and critical set from isotopisms to paratopisms. Then, we show how the orbits of entries induced by the autoparatopism under consideration constitute a first approach to construct these critical sets. In Section 3, we show that the set of critical sets based on a given autoparatopism of a Latin square depends only on the conjugacy class of the former and the main class of the latter. The study of cases concerning these conjugacy classes is carried out according to the cycle structures of their respective paratopisms. This enables us to compute the sizes of critical sets based on autoparatopisms of Latin squares of order up to six. Finally, in Section 4, we implement these critical sets based on paratopisms to design a generalization of the secret sharing scheme described in [10] that is not so dependent on the existence of absent but indispensable participants. 4
2
Critical sets based on autoparatopisms
In this section, we introduce the notions of completability and critical set of a Latin square with respect to a given paratopism Θ ∈ S3 ≀ Sn as a natural generalization of those based on isotopisms. To this end, we define the set L(Θ) := {L ∈ L(n) : Θ ∈ Apar(L)} . Definition 2.1. A partial Latin square P ∈ PL(n) is Θ-completable if it is completable to a Latin square L ∈ L(Θ). If P is not Θ-completable to any other Latin square, then it is uniquely Θ-completable. Moreover, it is a Θ-critical set of L if no partial Latin square properly contained in P is also uniquely Θ-completable. We denote by CSΘ (L) the set of Θ-critical sets of L. The smallest and largest Θ-critical set of L are respectively denoted by scsΘ (L) and lcsΘ (L). Those ones of any given Latin square of order n are respectively denoted by scsΘ (n) and lcsΘ (n). Classical critical sets of Latin squares arise for the trivial autoparatopism Θ = (Id3 ; (Idn , Idn , Idn )), whereas those based on a given isotopism do for Θ = (Id3 ; (f1 , f2 , f3 )) ∈ S3 ≀ Sn . Definition 2.1 also includes critical sets of symmetric Latin squares, which was introduced in [31] for even orders. This refers to Latin squares that are equal to their own transpose, and arises for Θ = ((12); (Idn , Idn , Idn )). In any case, the set CSΘ (L) is preserved by Θ. To see it, we first show the relationship among (uniquely) completable partial Latin squares of two paratopic Latin squares. Lemma 2.2. If P ∈ PL(n) is (uniquely) Θ-completable to L ∈ L(Θ), then P Θ is also (uniquely) Θ-completable to L. Proof. Since P Θ ⊆ LΘ = L, we have that P Θ is Θ-completable to L. Furthermore, if P is uniquely Θ-completable, but P Θ ⊆ L′ for some L′ ∈ Θ−1 −1 L(Θ) \ {L}, then P = P Θ ⊆ L′ Θ = L′ , which is a contradiction. Thus, P Θ is also uniquely Θ-completable. Proposition 2.3. Let L ∈ L(Θ) and P ∈ CSΘ (L). Then, P Θ ∈ CSΘ (L). Proof. From Lemma 2.2, P Θ is uniquely Θ-completable to L. Thus, P Θ ̸∈ CSΘ (L) if and only if it contains properly a partial Latin square Q that is −1 uniquely Θ-completable to L. But then, QΘ is properly contained in P . Moreover, it is Θ-completable to L from Lemma 2.2. This contradicts the fact that P ∈ CSΘ (L). Hence, P Θ ∈ CSΘ (L). From now on, we denote Θk := Θk−1 Θ for every positive integer k, where Θ0 is the trivial paratopism. It is well defined because S3 ≀ Sn is a group under the composition described in (2). The order of Θ is the smallest positive integer o(Θ) such that Θo(Θ) = Θ0 . 5
Lemma 2.4. Let L ∈ L(Θ) and let k ≤ o(Θ) be a non-negative integer. Every Θk -critical set of L contains a Θ-critical set of L. Proof. For any Latin square L′ , the set Apar(L′ ) is a group, so Θ ∈ Apar(L′ ) implies Θk ∈ Apar(L′ ). Thus, L(Θ) ⊆ L(Θk ). As a consequence, if P ∈ CSΘk (L), then the set of Θ-completions of P is a subset of the set of Θk completions of P . Since P is uniquely Θk -completable to L, we have that P is also uniquely Θ-completable to L. Since P is finite, the non-empty collection of subsets of P that are uniquely Θ-completable to L has a minimal element Q with respect to inclusion. By Definition 2.1, Q is a Θ-critical set of L, and Q ⊆ P . As an immediate consequence, the values described in Table 1 are upper bounds of scsΘ (L). In particular, this value is zero if n = 1, and 1 if n = 2. The same two trivial cases hold for lcsΘ (L), which can be checked directly. More generally, the next result holds readily from Lemma 2.4. Proposition 2.5. If L ∈ L(Θ), then scsΘ (L) ≤
min 0≤k<o(Θ)
{scsΘk (L)}
and
scsΘ (n) ≤
min 0≤k<o(Θ)
{scsΘk (n)} .
A first approach to understand much better all the notions described in Definition 2.1 consists of making use of the orbits of entries that are induced by the paratopism under consideration. Note in this regard from (1) that every autoparatopism Θ := (π; (f1 , f2 , f3 )) ∈ S3 ≀ Sn of a Latin square L ∈ L(n) acts faithfully on the set of entries Ent(L) so that Θ:
Ent(L) → Ent(L) e := (e1 , e2 , e3 ) 7→ Θ(e) := fπ(1) (eπ(1) ), fπ(2) (eπ(2) ), fπ(3) (eπ(3) ) .
The following definition generalizes in a natural way that one described in [46] about the orbits of entries induced by a given autotopism. The projection onto the first two coordinates of each entry gives rise, in fact, to the notion of cell orbit induced by a given autoparatopism, which was described in [47] (or by a given autotopism, in [48]). Definition 2.6. Let L ∈ L(Θ). The Θ-orbit of an entry e ∈ Ent(L) is the set n o OrbΘ (e) := Θk (e) : 0 ≤ k ≤ o(Θ) ⊆ Ent(L). We denote by OrbΘ (L) the set formed by all Θ-orbits in Ent(L). The next result illustrates the relevant role that the set OrbΘ (L) plays in the study of CSΘ (L). It holds readily from the fact that every Θ-orbit in L is uniquely determined by any of its entries.
6
Lemma 2.7. Every Θ-critical set of a Latin square L ∈ L(Θ) has at most one entry in each Θ-orbit of L. As a consequence, scsΘ (L) ≤ lcsΘ (L) ≤ |OrbΘ (L)|.
(4)
Taking into account the previous lemma, Algorithm 1 describes a procedure to determine all feasible sizes of Θ-critical sets of L. Algorithm 1 Feasible sizes in CSΘ (L). 1: procedure Sizes(Θ, L) ▷ Input: Θ ∈ S3 ≀ Sn and L ∈ L(Θ). 2: K := Empty list 3: E := e1 , . . . , e|OrbΘ (L)| such that OrbΘ (ei ) ̸= OrbΘ (ej ) if i ̸= j 4: for k ← 1, |OrbΘ (L)| do 5: Ek := {S ⊆ E : |S| = k} 6: end for 7: for k ← 1, |OrbΘ (L)| do 8: for S ∈ Ek do 9: if S ∈ CSΘ (L) then 10: K ← K ∪ {k} 11: break 12: end if 13: end for 14: end for 15: return K 16: end procedure As we have already mentioned in the introductory section, deciding unique completability of a partial Latin square is NP-complete in general [16, 17]. However, enforcing invariance under non-trivial autoparatopisms Θ drastically reduces the search space of candidate completions L(Θ). It allows us to search over Θ-orbits of entries rather than individual cells. In this regard, for a Latin square L ∈ L(n), Algorithm 1 filters subsets of representative entries from the orbit partition OrbΘ (L). So, the computational 2 complexity is 2|OrbΘ (L)| instead of 2n . At the end of this section, Example 2.10 shows that the upper bound in (4) can indeed be reached. Furthermore, to be in the same Θ-orbit is an equivalence relation among the entries of L, so OrbΘ (L) is a partition of Ent(L) and hence, of the cells of L. We visually represent this partition by coloring two cells of L with the same color if and only if they correspond to the same Θ-orbit. Of course, if Θ is the trivial paratopism, there are so many colors as cells. We term this representation a Θ-coloring of L. Example 2.8. We consider the paratopism Θ := ((12); (Id3 , (123), (12))) ∈ S3 ≀ S3 . 7
From (2), we have o(Θ) = 6 and the compositions Θ2 = (Id3 ; ((123), (123), Id3 )) , Θ4 = (Id3 ; ((132), (132), Id3 ))
Θ3 = ((12); ((123), (132), (12))) and
Θ5 = ((12); ((132), Id3 , (12))) .
We claim that 1 3 2 L ≡ 2 1 3 ∈ L Θk 3 2 1 for every positive integer k ≤ o(Θ). Since Apar(L) is a group, it is enough to prove this fact for k = 1. In this regard, note that Θ acts on the entries of L as follows. Θ
Θ
Θ
Θ
Θ
Θ
(1, 1, 1) − → (2, 1, 2) − → (2, 2, 1) − → (3, 2, 2) − → (3, 3, 1) − → (1, 3, 2) − → (1, 1, 1) Θ
Θ
Θ
(1, 2, 3) − → (3, 1, 3) − → (2, 3, 3) − → (1, 2, 3) Based on this action, we have the following Θk -colorings of L. 1 3 2 2 1 3 3 2 1 k ∈ {1, 5}
1 3 2 2 1 3 3 2 1 k ∈ {2, 4}
1 3 2 2 1 3 3 2 1 k=3
Now, we consider the partial Latin squares 1 P1 ≡
1 3 and
P2 ≡
.
In addition, let k ∈ {1, 3, 5} and l ∈ {0, 2, 4}. It is readily verified that P1 ∈ CSΘk (L) \ CSΘ0 (L). Moreover, P2 ∈ CSΘl (L) \ CSΘk (L), because P1 ⊂ P2 . In case of being interested in all the Θk -critical sets of L, the following study of cases arises. • For k ∈ {1, 5}, every partial Latin square in PL(3) that is formed by exactly one entry in OrbΘk ((1, 1, 1)) is a Θk -critical set of L. This is not the case for any subset of entries in OrbΘk ((1, 2, 3)), because the resulting partial Latin square would also be Θk -completable to 2 3 1 1 2 3 ∈ L Θk , 3 1 2 for which we have also described a Θk -coloring. As a consequence, scsΘk (L) = lcsΘk (L) = 1. 8
• For k ∈ {2, 4}, we note that every Θk -critical set of L is formed by two entries in different orbits. Thus, scsΘk (L) = lcsΘk (L) = 2. • For k = 3, we observe that every partial Latin square in PL(3) that is formed by exactly one entry in OrbΘk ((1, 1, 1)) ∪ OrbΘk ((1, 3, 2)) ∪ OrbΘk ((2, 1, 2)) is a Θk -critical set of L. Since the symbol appearing in the remaining Θk -orbits is mandatorily 3, we have that scsΘk (L) = lcsΘk (L) = 1. ◁ In Example 2.8, every Θk -critical set, with k ∈ {1, 5}, necessarily contains an entry in OrbΘk ((1, 1, 1)). In general, it is useful to know the existence of these types of orbits for which every critical set must contain one of its entries. We finish this section with some results in this regard. Previously, for each paratopism Θ := (π; f ) ∈ S3 ≀Sn , with f := (f1 , f2 , f3 ), and each triple e := (e1 , e2 , e3 ) ∈ [n]3 , we define the following sets. Fixrow (e) : = {(π; f ) ∈ S3 ≀ Sn : fπ(1) (eπ(1) ) = e1 } Fixcol (e) : = {(π; f ) ∈ S3 ≀ Sn : fπ(2) (eπ(2) ) = e2 } Fixsym (e) : = {(π; f ) ∈ S3 ≀ Sn : fπ(3) (eπ(3) ) = e3 } In addition, for each Latin square L ∈ L(n), we define the subgroup Apar(12) (L) := Atop(L) ∪ {((12); f ) ∈ Apar(L)} ≤ Apar(L). Theorem 2.9. Let L ∈ L(n) and Θ := (π; f ) ∈ Apar(12) (L) be such that there exist an entry e ∈ Ent(L) and a positive integer k0 ≤ o(Θ) such that (C1) Θ ∈ Fixrow (e) \ Fixcol (e); (C2) Θk0 ∈ Fixcol (e); and (C3) Θo(Θ)−k0 +1 ∈ Fixsym (e). Then, every Θ-critical set of L contains an entry in OrbΘ (e). The same happens if the first two conditions are respectively replaced by (C1’) Θ ∈ Fixcol (e) \ Fixrow (e). (C2’) Θk0 ∈ Fixrow (e). Proof. If P ⊂ L does not contain any entry in OrbΘ (e), then Theorem 3.2 in [49] implies that P is Θ-completable to the Latin square L′ ∈ L(Θ), where n o Ent(L′ ) = (Ent(L) \ OrbΘ (e)) ∪ Θk ((e1 , e2 , f3 (e3 ))) : 0 ≤ k < o(Θ) . Hence, P ̸∈ CSΘ (L), and the result holds. 9
Example 2.8 illustrates this theorem for e = (1, 1, 1) and k0 = 5. It is readily verified that Θ and Θ5 satisfy both conditions (C1’) and (C2’), and Θ holds condition (C3). Theorem 2.9 also enables us to find an example in which the upper bound in Lemma 2.7 is reached. Example 2.10. We consider the paratopism Θ := ((12); (Id4 , (1234), (12)(34))) ∈ S3 ≀ S4 and the Latin square 1 2 L≡ 4 3
3 1 2 4
4 3 1 2
2 4 ∈ L Θk 3 1
for which we describe a Θ-coloring. In particular, o(Θ) = 8 and Θ7 = ((12); ((1432), Id4 , (12)(34))) ∈ S3 ≀ S4 . It is readily verified that Θ and Θ7 satisfy both conditions (C1’) and (C2’) for both entries (1, 1, 1) and (1, 2, 3). Since Θ also holds Condition (C3), Theorem 2.9 implies that every Θ-critical set of L must contain an entry in OrbΘ ((1, 1, 1)) and also an entry in OrbΘ ((1, 2, 3)). Hence, scsΘ (L) = lcsΘ (L) = |OrbΘ (L)| = 2. ◁ The set OrbΘ (e) in Theorem 2.9 constitutes indeed the set of entries of a Latin trade of L. That is, a partial Latin square P ⊂ L such that there is another partial Latin square P ′ ⊂ L of the same size such that Ent(P ) ∩ Ent(P ′ ) = ∅; and (Ent(L) \ Ent(P )) ∪ Ent(P ′ ) is the set of entries of a new Latin square. (We refer again to Theorem 3.2 in [49] for more details.) From now on, we denote by τΘ (L) the number of distinct Latin trades in the set OrbΘ (L) whose entries satisfy the conditions described in Theorem 2.9. The following corollary follows readily from that theorem. Corollary 2.11. Let L ∈ L(n) and Θ := (π; f ) ∈ Apar(12) (L). Then, τΘ (L) ≤ scsΘ (L). Example 2.10 illustrates that this lower bound is reached. In addition, the next result shows that τΘ (L) is an invariant in the conjugacy class of the paratopism Θ within the subgroup Apar(12) (L) ≤ S3 ≀ Sn . (Recall here that two elements a and b in a group G are conjugate if there is a third element c ∈ G such that b = cac−1 .) Corollary 2.12. Let us consider a Latin square L ∈ L(n), and two conjugate autoparatopisms Θ1 := (π1 ; f1 ) and Θ2 := (π2 ; f2 ) in the group Apar(12) (L). Then τΘ1 (L) = τΘ2 (L). 10
Proof. Since Θ1 and Θ2 are conjugate within Apar(12) (L), there exists a third autoparatopism Θ3 := (π3 ; f3 ) ∈ Apar(12) (L) such that Θ2 = Θ3 Θ1 Θ−1 3 . Let us suppose that conditions (C1–C3) in Theorem 2.9 hold for an entry e ∈ Ent(L), a positive integer k0 ≤ o(Θ1 ), and the autoparatopism Θ1 . (A similar reasoning follows from conditions (C1’-C2’) and (C3).) Since Θ3 ∈ Apar(12) (L), we have π3 ∈ {Id3 , (12)}, so π3 (3) = 3. Since m m Θm 2 (Θ3 (e)) = Θ3 (Θ1 (e)) for m := o(Θ1 ) − k0 + 1, and Θ1 (e) agrees with e m in the third coordinate by (C3) for Θ1 , it follows that Θ2 (Θ3 (e)) agree with Θ3 (e) in the third component as well. That is, Condition (C3) holds for Θ2 , the entry Θ3 (e) ∈ Ent(L) and the positive integer k0 ≤ o(Θ2 ) = o(Θ1 ). In addition, both conditions (C1) and (C2) hold if π = Id3 , whereas both conditions (C1’) and (C2’) hold if π = (12). Hence, τΘ1 (L) ≤ τΘ2 (L). The reciprocal follows similarly and hence, the result holds. This last corollary is useful to determine whether two autoparatopisms in Apar(12) (L) are conjugate. The following example illustrates this fact. Example 2.13. The paratopisms Θ1 := ((12); ((45), (12)(3465), (12)(3465))) and Θ2 := ((12); ((12)(3465), (36), (12)(3465))), both of them in S3 ≀ S6 , are autoparatopisms of the Latin square L6.1 described in Figure 1, for which we have the following Θ1 - and Θ2 -colorings. 1 2 3 4 5 6
2 3 4 5 1 4 3 6 5 6 1 4 6 5 2 3 3 1 6 2 4 2 5 1 Θ1 -coloring
6 5 2 1 4 3
1 2 3 4 5 6
2 3 4 5 1 4 3 6 5 6 1 4 6 5 2 3 3 1 6 2 4 2 5 1 Θ2 -coloring
6 5 2 1 4 3
The only Latin trade of L whose entries satisfy the conditions described in Theorem 2.9 for Θ1 is formed by the entries of OrbΘ1 ((1, 1, 1)). In addition, there are three Latin trades of L satisfying these conditions for Θ2 . They are respectively formed by the entries of OrbΘ2 ((1, 1, 1)), OrbΘ2 ((3, 4, 1)) and OrbΘ2 ((5, 3, 1)). Hence, Corollary 2.12 implies that Θ1 and Θ2 are not conjugate within Apar(12) (L). By the way, after implementing Algorithm 1 in both cases, we obtain scsΘ1 (L6.1 ) = lcsΘ1 (L6.1 ) = 4
and
scsΘ2 (L6.1 ) = lcsΘ2 (L6.1 ) = 5.
We illustrate here a pair of Θ1 - and Θ2 -critical sets of L. 1
3
4
1
3
1
4 1
1 Θ1 -critical set
Θ2 -critical set
◁ 11
3
Conjugacy classes of autoparatopisms
In what follows, we prove that the smallest and largest sizes of critical sets based on a given autoparatopism Θ ∈ S3 ≀ Sn of a Latin square L ∈ L(n) depend only on the conjugacy class of Θ within the subgroup Apar(L) ≤ S3 ≀ Sn and the main class of L. First, we show that every paratopism Θ0 ∈ S3 ≀ Sn constitutes a one-to-one correspondence between the autoparatopism group of any partial Latin square P ∈ PL(n) and that of P Θ0 , which in turn preserves the conjugacy classes of their respective paratopisms. Lemma 3.1. If P ∈ PL(n) and Θ0 ∈ S3 ≀ Sn , then Apar P Θ0 = Θ0 Θ1 Θ−1 0 : Θ1 ∈ Apar(P ) . Θ Proof. First, if Θ1 ∈ Apar(P ), then Θ0 Θ1 Θ−1 0 ∈ Apar(P ), because
P
−1 Θ0 Θ0 Θ1 Θ0
=
P
−1 Θ0 Θ0
Θ1 !Θ0
= P Θ1
Θ0
= P Θ0 .
Similarly, if Θ2 ∈ Apar P Θ0 , then Θ−1 0 Θ2 Θ0 ∈ Apar(P ). Thus, the result −1 −1 holds because Θ2 = Θ0 (Θ0 Θ2 Θ0 )Θ0 . Then, we prove that both values scsΘ (L) and lcsΘ (L) depend only on the conjugacy class of Θ within Apar(L). Proposition 3.2. Let L ∈ L(n). If two autoparatopisms Θ1 , Θ2 ∈ Apar(L) are conjugate within Apar(L), then there is a one-to-one correspondence between both sets CSΘ1 (L) and CSΘ2 (L) so that scsΘ1 (L) = scsΘ2 (L)
and
lcsΘ1 (L) = lcsΘ2 (L) .
Proof. Since Θ1 and Θ2 are conjugate within Apar(L), there is a paratopism Θ3 ∈ Apar(L) such that Θ2 = Θ3 Θ1 Θ−1 3 . Then, the result follows from Lemma 3.1 and Definition 2.1. Example 2.13 illustrates that considering in Proposition 3.2 the conjugacy within the autoparatopism group is mandatory. Being conjugate within Apar(L) is an equivalence relation among the autoparatopisms of L, which we denote by ∼. By Proposition 3.2, if we want to compute all feasible sizes of critical sets based on autoparatopisms of L, then it suffices to implement Algorithm 1 on a representative paratopism of each class in the quotient group Apar(L)/ ∼. In addition, if one is interested in computing these values for all Latin squares in L(n), the following results show that it suffices to consider a representative Latin square of each main class.
12
Proposition 3.3. If two Latin squares L1 , L2 ∈ L(n) are paratopic, then there is a one-to-one correspondence between their respective sets of critical sets based on their autoparatopisms. Proof. Since L1 and L2 are paratopic, there is a paratopism Θ0 ∈ S3 ≀ Sn 0 such that LΘ 1 = L2 . Then, the result holds because Lemma 3.1, together with Definition 2.1, implies that P ∈ CSΘ1 (L1 ) for some Θ1 ∈ Apar(L1 ) if and only if P Θ0 ∈ CSΘ0 Θ1 Θ−1 (L2 ) for some Θ1 ∈ Apar(L1 ). 0
Theorem 3.4. If L ∈ L(Θ), then there is a paratopism Θ0 ∈ S3 ≀ Sn such that the paratopism Θ0 ΘΘ−1 0 is either an isotopism or a paratopism of one of the following two types. • Type I: ((12); (Idn , f2 , f3 )) ∈ S3 ≀ Sn . • Type II: ((123); (Idn , Idn , f3 )) ∈ S3 ≀ Sn . In particular, there is a one-to-one correspondence between the sets CSΘ (L) Θ 0 and CSΘ0 ΘΘ−1 L . 0
Proof. Theorem 2.2 in [50] implies the existence of the paratopism Θ0 . Then, the mentioned correspondence follows from Proposition 3.3. From now on, we denote by P(n) the subset of S3 ≀ Sn that is formed by isotopisms and paratopisms of types I or II. Algorithm 2 implements both Proposition 3.2 and Theorem 3.4 to determine the sets of feasible sizes of critical sets based on the quotient group Apar(L)/ ∼ for a representative Latin square L of a given main class. It uses the procedure Sizes described in Algorithm 1. Algorithm 2 Feasible sizes of critical sets based on Apar(L)/ ∼. 1: procedure MainSizes(L) ▷ Input: L ∈ L(n). 2: A := Apar(L)/ ∼ 3: K := ∅ 4: for Θ ∈ A do 5: if Θ ∈ P(n) then 6: K ← K ∪ {Θ, Sizes(Θ, L)} 7: else Θ0 8: K ← K ∪ Θ, Sizes Θ0 ΘΘ−1 , where Θ0 ΘΘ−1 ∈ 0 ,L 0 P(n) 9: end if 10: end for 11: return K 12: end procedure
13
We have implemented Algorithm 2 in the GAP system (Groups, Algorithms, Programming) [51] to determine all feasible sizes of critical sets based on paratopisms of Latin squares of order 3 ≤ n ≤ 6. (The case n < 3 is trivial.) The results are shown in Appendix A. In all tables therein, the column L refers to the main class of the Latin square. Their representatives are shown in Figure 1. The column class refers to the conjugacy class of the autoparatopism. The columns scs and lcs show, respectively, the smallest and largest values of any critical set in each case. The column time gives the computational time in seconds required to determine all the critical sets in each case on a 13th Gen Intel Core i9-13900H CPU @ 2.60GHz with 32 GB RAM. Specific examples of critical sets associated with each case are listed in Appendix B. Figure 2 illustrates the global elapsed time required for the computation of critical sets based on non-trivial autoparatopisms. 1 2 3 4
1 2 3 2 3 1 3 1 2 L3
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
L4.1
2 1 4 3
3 4 2 1
1 2 3 4 5
4 3 1 2
L4.2
2 3 4 3 4 5 4 5 1 5 1 2 1 2 3 L5.1
5 1 2 3 4
1 2 3 4 5
2 3 4 1 4 5 4 5 1 5 2 3 3 1 2 L5.2
5 3 2 1 4
1 2 3 4 5 6
2 1 5 6 3 4
3 4 5 4 3 6 6 1 4 5 2 3 1 6 2 2 5 1 L6.1
6 5 2 1 4 3
1 2 3 4 5 6
2 3 1 6 4 5
3 4 5 1 5 6 2 6 4 5 1 3 6 2 1 4 3 2 L6.2
6 4 5 2 3 1
1 2 3 4 5 6
2 3 1 6 4 5
3 4 5 1 5 6 2 6 4 5 3 2 6 1 3 4 2 1 L6.3
6 4 5 1 2 3
1 2 3 4 5 6
2 3 1 6 4 5
3 4 5 1 6 4 2 5 6 5 2 1 6 1 3 4 3 2 L6.4
6 5 4 3 2 1
1 2 3 4 5 6
2 3 4 1 6 5
3 4 5 1 6 4 5 2 6 6 5 2 2 3 1 4 1 3 L6.5
6 5 1 3 4 2
1 2 3 4 5 6
2 4 1 3 6 5
3 4 5 5 1 6 2 6 4 6 5 1 1 2 3 4 3 2 L6.6
6 3 5 2 4 1
1 2 3 4 5 6
2 4 1 5 6 3
3 4 5 5 1 6 2 6 4 6 2 3 4 3 1 1 5 2 L6.7
6 3 5 1 2 4
1 2 3 4 5 6
2 4 5 6 1 3
3 4 5 5 1 6 6 2 4 1 3 2 4 6 3 2 5 1 L6.8
6 3 1 5 2 4
1 2 3 4 5 6
2 4 6 3 1 5
3 4 5 5 1 6 4 2 1 6 5 2 2 6 3 1 3 4 L6.9
6 3 5 1 4 2
1 2 3 4 5 6
2 5 6 3 4 1
3 4 5 6 3 1 2 1 4 5 2 6 1 6 3 4 5 2 L6.10
6 4 5 1 2 3
1 2 3 4 5 6
2 6 5 3 4 1
3 4 5 4 3 1 6 1 2 5 2 6 1 6 3 2 5 4 L6.11
6 5 4 1 2 3
1 2 3 4 5 6
2 6 4 5 3 1
3 4 5 4 5 3 2 6 1 1 2 6 6 1 2 5 3 4 L6.12
6 1 5 3 4 2
Figure 1: Representative Latin squares of the main classes of L(n), with 3 ≤ n ≤ 6.
103
Global elapsed time (s)
102
101
100
10 1
.11
.12
L6
.9
L6
.10
.8
L6
L6
.7
Main class of the Latin square
L6
.6
.3
L6
L6
.2
L6
.5
.1
L6
L6
.2
L5
L6
.1
L5
.4
.2
L4
L6
.1
L3
L4
10 2
Figure 2: Global computational time for non-trivial autoparatopisms.
14
To avoid enumeration of all paratopisms, we carry out our study according to their cycle structures, which are represented in the column z of our tables. Recall here that the cycle structure of a permutation π ∈ Sn is the π π expression zπ := nλn . . . 1λ1 , where λπℓ is the number of cycles of length ℓ in the unique decomposition of π as a product of disjoint cycles. In practice, zero factors are omitted, and every factor of the form ℓ1 is written ℓ. Thus, for example, z(123)(456)(7) = 32 1. Then, the cycle structure of a paratopism Θ = (π; (f1 , f2 , f3 )) ∈ S3 ≀ Sn is the tuple zΘ := (zπ ; (zf1 , zf2 , zf3 )). Mendis and Wanless [47] determined the cycle structures of all autoparatopisms of types I and II of Latin squares of order up to 17. Those of all autotopisms of Latin squares of the same orders were already known [48, 52]. By Lemma 3.1, the set of cycle structures of paratopisms in P(n) that are conjugate to at least one paratopism in Apar(L)/ ∼ depends only on the main class of L. For each cycle structure z, we have calculated all feasible sizes of every critical set of L based on a paratopism in Apar(L)/ ∼ that is conjugate to one in P(n) with cycle structure z. These sizes were obtained in [46] for all autotopisms of Latin squares of order n ≤ 5. We have confirmed all these values except for the largest size of a critical set based on any autotopism of L5.2 with the cycle structure (13 ; (312 , 312 , 312 )). This value is five instead of six, which was indicated in Example 32 in [46].
4
A new secret sharing scheme
In this section, critical sets based on paratopisms are implemented to design a new secret sharing scheme customized for ℓ participants that is not so dependent on the existence of absent but indispensable participants. As a first approach, the dealer considers a pair (L, Θ) ∈ L(n) × Apar(L) such that there is some critical set P ∈ CSΘ (L) of size ℓ. Similarly to the scheme proposed in [10], the dealer distributes to each participant a distinct entry of P so that all of them must collaborate to recover the Latin square L, which is the key. Example 4.1. For ℓ = 3, the dealer can consider the autoparatopism Θ = (Id3 ; ((2354), (1243), (1243))) of the following Θ-colored Latin square. 1 2 L≡ 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
A Θ-critical set of L of size three is formed by the entries {(2, 2, 3), (2, 4, 5), (2, 5, 1)}. ◁
15
As a second approach, and again similarly to the scheme proposed in [10], our protocol can be considered a multilevel scheme if the dealer considers more than one Θ-critical set of the key under consideration, some of them even of distinct sizes. If their entries are distributed to the participants of this new scheme, those participants who have entries associated with longer orbits have more information about the key than those with entries in smaller orbits. In this regard, those orbits with a larger number of entries can be assigned to a higher level. A third approach, which justifies the use of critical sets that are based on paratopisms, consists of distributing to the participants more than one entry of each Θ-orbit. Those participants containing these entries play the same role in the scheme and hence, they become non-essential. Example 4.2. In a bank, there are four employees and one director. To open the safe, the requirement is that there must always be two employees and the director present. Therefore, they decide to divide the safe’s key using a secret sharing scheme. The protocol determines that critical sets of three entries will be sought, one for the director and two for two of the employees, who will be the main participants of the scheme. The remaining employees will be considered substitutes for the participating employees, so redundant entries from the orbits used with the other employees will be assigned to them. As an illustrative example, we can consider the autoparatopism Θ = (13 ; ((13)(45), (25)(34), (13)(45))) of the following Θ-colored Latin square. 1 2 L≡ 3 4 5
2 1 4 5 3
3 4 5 2 1
4 5 1 3 2
5 3 2 1 4
A Θ-critical set of L of size three is formed by the entries {(1, 4, 4), (4, 2, 5), (4, 4, 3)}. The entry (1, 4, 4) is given to the director, while each of the other two entries is, respectively, given to one of the other two participants. In addition, the third and fourth employees, who are not main participants in the scheme, receive, respectively, the entries (5, 5, 4) and (5, 3, 1). The role of the director is indispensable because, if the entry (1, 4, 4) is unknown, then the following alternative Latin square also has Θ as an autoparatopism. 4 2 5 1 3
1 3 4 5 2
3 5 2 4 1
2 4 1 3 5
5 1 3 2 4
Furthermore, the first and second employees are not indispensable because they can, respectively, be replaced by the third and fourth employees. This is due to the fact that each substitute has an alternative entry of the same Θ-orbit being considered. In this way, the director’s entry is superior in rank because it constitutes a non-redundant, indispensable piece of information required to achieve unique completion. ◁ 16
The security of these secret sharing schemes is primarily framed in terms of the brute-force search-space size. Note that the total number of Latin squares grows super-exponentially, with the known lower bound 2n 2 2 |L(n)| ≥ (n!)n2 ≥ n(n −o(n )) . More precisely, the exact number is known n for n ≤ 11 [37–39]. In particular, |L(10)| ≈ 9.9824 × 1036 ≤ 2128 ≤ 7.7696 × 1047 ≈ |L(11)|. Since 128 bits of effective security is the current threshold to consider an absolutely secure system against traditional brute-force attacks, our schemes are adequate for n ≥ 11. Our examples fall well short of this bound. They are not presented as real-world deployment examples, but only as a mere illustration of the described techniques. For an adversary who does not hold all the entries of a Θ-critical set, the relevant hardness is completing a partial Latin square with the missing entries unknown. This problem remains NP-complete in the worst case [17], although specific instances may be solved considerably faster using standard heuristics. For any authorized coalition (holding all the entries of a critical set, and having Θ public as part of the protocol), recovery does not require brute-force search over all Latin squares of order n. Since Θ is known, the coalition immediately fills every entry in OrbΘ (e) for each known entry e.
5
Conclusion and further work
In this paper, we have introduced the problem of determining critical sets of Latin squares containing a given non-trivial paratopism in their group of autoparatopisms. We have proved that the feasible sizes of these critical sets depend only on the conjugacy class of the paratopism and the main class of the Latin square under consideration. A pair of algorithms has been described to compute these sizes for Latin squares. As an illustrative example, we have implemented them to determine the sizes of critical sets based on autoparatopisms of Latin squares of order up to six. We have also described a new secret sharing scheme arising from critical sets based on an autoparatopism of a given Latin square, which is the key. This cryptographic protocol reduces the complexity when searching for critical sets for a given Latin square by incorporating an autoparatopism that determines the orbits of the entries within that set. It reduces the number of assumptions that need to be made for the remaining empty entries. It also allows for the use of multilevel secret sharing schemes without the need to employ more than one critical set. This is because the use of orbits of the elements related to the mentioned set allows us to assign entries related to longer orbits (more information) to individuals with higher rank, or alternatively, reduce the number of entries that are distributed to assign redundant entries to the substitutes.
17
Acknowledgements This paper has partially been supported by the Research and Innovation Project PPIT-FEDER 2023 “Modeling small-world, scale-free networks from combinatorial designs based on quasigroup digraphs”, co-financed by the EU - Ministry of Finance and Public Administration - European Funds - Andalusian Regional Government - Ministry of University, Research and Innovation.
18
Appendix A
Bounds for critical sets
This appendix collects our computational results of implementing Algorithm 2 in GAP concerning the smallest and largest sizes of critical sets based on autoparatopisms of Latin squares of order n ∈ {3, 4, 5, 6}. Table 2: Smallest and largest sizes of critical sets based on isotopisms. L
z
class
scs
lcs
time (s)
L3
(13 , 13 , 13 ) (13 , 3, 3) (21, 21, 21) (3, 3, 3) (14 , 14 , 14 ) (14 , 22 , 22 ) (212 , 212 , 212 ) (212 , 4, 4) (22 , 22 , 22 ) (31, 31, 31) (14 , 14 , 14 ) (14 , 22 , 22 ) (14 , 4, 4) (212 , 212 , 212 ) (212 , 22 , 22 ) (22 , 4, 4) (15 , 15 , 15 ) (5, 5, 15 ) (22 1, 22 1, 22 1) (41, 41, 41) (5, 5, 5) (15 , 15 , 15 ) (22 1, 22 1, 22 1) (312 , 312 , 312 ) (16 , 16 , 16 ) (16 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (22 12 , 23 , 23 ) (16 , 16 , 16 ) (16 , 23 , 23 ) (16 , 32 , 32 ) (22 12 , 22 12 , 22 12 ) (23 , 23 , 22 12 ) (23 , 32 , 6) (313 , 313 , 313 ) (32 , 32 , 313 ) (313 , 6, 6) (6, 6, 22 12 ) (16 , 16 , 16 ) (16 , 32 , 32 ) (22 12 , 23 , 23 ) (22 12 , 6, 6) (313 , 313 , 313 ) (32 , 32 , 313 ) (16 , 16 , 16 ) (16 , 23 , 23 )
c3.1 c3.2 c3.3 c3.4 c4.1.1 c4.1.2 c4.1.3 c4.1.4 c4.1.5 c4.1.6 c4.2.1 c4.2.2 c4.2.3 c4.2.4 c4.2.5 c4.2.6 c5.1.1 c5.1.2 c5.1.3 c5.1.4 c5.1.5 c5.2.1 c5.2.2 c5.2.3 c6.1.1 c6.1.2 c6.1.3 c6.1.4 c6.2.1 c6.2.2 c6.2.3 c6.2.4 c6.2.5 c6.2.6 c6.2.7 c6.2.8 c6.2.9 c6.2.10 c6.3.1 c6.3.2 c6.3.3 c6.3.4 c6.3.5 c6.3.6 c6.4.1 c6.4.2
2 2 1 1 5 4 4 2 3 2 4 4 3 4 3 2 6 4 3 3 2 7 3 5 11 9 7 7 12 9 8 7 7 4 8 6 3 4 11 8 6 4 8 6 9 9
3 2 2 1 7 4 4 2 3 2 6 4 3 4 3 2 10 4 5 3 2 11 5 51 17 10 10 8 18 10 8 10 9 4 9 7 3 4 16 8 8 4 9 6 17 10
0.06 0.00 0.00 0.00 1.72 0.02 0.03 0.00 0.00 0.00 1.37 0.01 0.00 0.03 0.01 0.00 3,483.17 0.00 0.36 0.00 0.00 4,069.39 0.45 0.09 >36,000.00 36.87 104.11 27.64 >36,000.00 57.44 0.23 133.55 64.95 0.02 23.59 0.22 0.03 0.00 >36,000.00 0.22 43.19 0.01 20.41 0.20 >36,000.00 9.14
L4.1
L4.2
L5.1
L5.2
L6.1
L6.2
L6.3
L6.4
19
L
z
class
scs
lcs
time (s)
L6.4
(16 , 32 , 32 ) (16 , 6, 6) (22 12 , 22 12 , 22 12 ) (22 12 , 23 , 23 ) (32 , 32 , 32 ) (32 , 6, 23 ) (32 , 6, 6) (16 , 16 , 16 ) (16 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (22 12 , 23 , 23 ) (313 , 32 , 32 ) (313 , 6, 6) (16 , 16 , 16 ) (214 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (313 , 32 , 32 ) (321, 6, 6) (412 , 412 , 412 ) (51, 51, 51) (16 , 16 , 16 ) (16 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (23 , 23 , 22 12 ) (32 , 32 , 32 ) (32 , 6, 6) (16 , 16 , 16 ) (214 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (412 , 412 , 412 ) (16 , 16 , 16 ) (22 12 , 23 , 23 ) (16 , 16 , 16 ) (214 , 23 , 23 ) (22 12 , 22 12 , 22 12 ) (16 , 16 , 16 ) (22 12 , 22 12 , 22 12 ) (16 , 16 , 16 ) (16 , 32 , 32 ) (214 , 23 , 23 ) (214 , 6, 6) (22 12 , 22 12 , 22 12 ) (313 , 313 , 313 ) (313 , 32 , 32 ) (321, 6, 6)
c6.4.3 c6.4.4 c6.4.5 c6.4.6 c6.4.7 c6.4.8 c6.4.9 c6.5.1 c6.5.2 c6.5.3 c6.5.4 c6.5.5 c6.5.6 c6.6.1 c6.6.2 c6.6.3 c6.6.4 c6.6.5 c6.6.6 c6.6.7 c6.7.1 c6.7.2 c6.7.3 c6.7.4 c6.7.5 c6.7.6 c6.8.1 c6.8.2 c6.8.3 c6.8.4 c6.9.1 c6.9.2 c6.10.1 c6.10.2 c6.10.3 c6.11.1 c6.11.2 c6.12.1 c6.12.2 c6.12.3 c6.12.4 c6.12.5 c6.12.6 c6.12.7 c6.12.8
8 5 7 6 4 4 3 10 9 7 6 4 3 11 7 7 4 2 5 3 11 9 7 6 4 3 10 7 7 5 10 6 10 7 7 10 7 11 8 7 4 7 8 6 3
8 5 9 8 5 4 3 17 10 9 8 6 3 17 9 9 6 3 6 4 17 10 9 8 5 3 17 10 9 6 17 8 17 9 9 17 9 17 8 9 5 9 9 7 3
0.11 0.00 114.09 34.78 0.42 0.00 0.02 >36,000.00 22.70 120.77 32.84 0.53 0.01 >36,000.00 36.36 117.95 0.53 0.01 0.45 0.05 >36,000.00 9.45 113.36 33.03 0.45 0.00 >36,000.00 31.92 119.67 0.48 >36,000.00 33.30 >36,000.00 32.16 122.47 >36,000.00 123.72 >36,000.00 0.12 32.52 0.00 129.17 31.50 0.67 0.00
L6.5
L6.6
L6.7
L6.8
L6.9 L6.10
L6.11 L6.12
Table 3: Smallest and largest sizes of critical sets based on paratopisms of Type I. L L3
L4.1
L4.2
L5.1
L5.2 L6.1
L6.2
L6.3
L6.4
z
class 3
3
3
(1 , 1 , 1 ) (13 , 13 , 21) (13 , 3, 21) (13 , 3, 3) (14 , 14 , 14 ) (14 , 14 , 212 ) (14 , 22 , 212 ) (22 , 22 , 14 ) (14 , 22 , 4) (14 , 31, 31) (14 , 14 , 14 ) (14 , 14 , 212 ) (14 , 22 , 212 ) (14 , 22 , 22 ) (14 , 4, 22 ) (14 , 4, 4) (15 , 15 , 15 ) (15 , 15 , 22 1) (15 , 22 1, 41) (15 , 5, 22 1) (15 , 5, 5) (15 , 15 , 213 ) (15 , 22 1, 41) (16 , 16 , 214 )
c3.5 c3.6 c3.7 c3.8 c4.1.7 c4.1.8 c4.1.9 c4.1.10 c4.1.11 c4.1.12 c4.2.7 c4.2.8 c4.2.9 c4.2.10 c4.2.11 c4.2.12 c5.1.6 c5.1.7 c5.1.8 c5.1.9 c5.1.10 c5.2.4 c5.2.5 c6.1.5 c6.1.6 (16 , 23 , 42) c6.1.7 c6.1.8 (16 , 16 , 214 ) c6.2.11 c6.2.12 (16 , 23 , 42) c6.2.13 c6.2.14 (16 , 313 , 321) c6.2.15 (16 , 32 , 321) c6.2.16 c6.2.17 (16 , 32 , 214 ) c6.2.18 (16 , 6, 42) c6.2.19 (16 , 16 , 214 ) c6.3.7 (16 , 23 , 42) c6.3.8 (16 , 32 , 321) c6.3.9 (16 , 6, 42) c6.3.10 (16 , 16 , 16 ) c6.4.10
scs lcs time (s) L 2 1 1 1 4 3 3 3 2 1 3 3 3 3 2 1 4 3 3 2 1 4 3 6 7 4 5 7 8 4 5 4 4 4 5 2 6 4 4 2 6
2 1 1 1 6 4 3 3 2 1 4 4 3 3 2 1 6 4 3 2 1 6 3 9 10 4 5 10 11 4 5 4 4 5 5 2 9 5 4 2 10
0.00 0.00 0.00 0.00 0.03 0.03 0.00 0.00 0.00 0.00 0.03 0.02 0.00 0.00 0.00 0.00 1.86 0.59 0.02 0.00 0.00 1.59 0.00 446.11 146.87 0.03 0.05 247.89 175.30 0.05 0.03 0.17 0.00 0.01 0.02 0.00 275.06 0.00 0.00 0.00 184.14
20
L6.4
L6.5
L6.6
L6.7
L6.8
L6.9 L6.10
L6.11 L6.12
z
class 6
6
2 2
(1 , 1 , 2 1 ) (16 , 23 , 23 ) (16 , 32 , 22 12 ) (16 , 32 , 32 ) (16 , 6, 23 ) (16 , 6, 6) (16 , 16 , 214 )
c6.4.11 c6.4.12 c6.4.13 c6.4.14 c6.4.15 c6.4.16 c6.5.7 c6.5.8 (16 , 32 , 321) c6.5.9 c6.5.10 (16 , 16 , 16 ) c6.6.8 (16 , 16 , 214 ) c6.6.9 (16 , 16 , 22 12 ) c6.6.10 (16 , 22 12 , 412 ) c6.6.11 (16 , 32 , 313 ) c6.6.12 (16 , 32 , 321) c6.6.13 (16 , 51, 51) c6.6.14 (16 , 16 , 16 ) c6.7.7 (16 , 16 , 22 12 ) c6.7.8 (16 , 23 , 23 ) c6.7.9 (16 , 32 , 32 ) c6.7.10 (16 , 6, 6) c6.7.11 (16 , 16 , 16 ) c6.8.5 (16 , 16 , 214 ) c6.8.6 (16 , 16 , 22 12 ) c6.8.7 (16 , 6, 51) c6.8.8 (16 , 16 , 214 ) c6.9.3 (16 , 23 , 42) c6.9.4 (16 , 16 , 16 ) c6.10.4 (16 , 16 , 214 ) c6.10.5 c6.10.6 (16 , 16 , 22 12 ) c6.10.7 (16 , 16 , 214 ) c6.11.3 (16 , 22 12 , 412 ) c6.11.4 (16 , 16 , 16 ) c6.12.9 (16 , 16 , 214 ) c6.12.10 c6.12.11 (16 , 16 , 22 12 ) c6.12.12 (16 , 313 , 321) c6.12.13 (16 , 32 , 214 ) c6.12.14 (16 , 32 , 313 ) c6.12.15 (16 , 32 , 22 12 ) c6.12.16 (16 , 32 , 321) c6.12.17
scs lcs time (s) 6 6 4 3 3 2 7 6 4 2 8 7 6 5 3 4 1 7 6 6 3 2 7 7 6 5 6 4 6 6 7 7 6 5 7 6 7 7 4 5 4 4 4
9 6 5 3 3 2 10 10 4 41 151 11 9 6 4 4 1 10 9 6 3 2 11 9 9 6 10 5 9 10 10 10 10 6 10 10 111 10 4 5 4 5 5
255.98 0.05 0.00 0.02 0.00 0.00 242.23 263.39 0.02 0.02 235.75 258.42 265.03 0.20 0.01 0.02 0.00 167.67 215.67 0.05 0.02 0.00 279.34 252.94 214.11 0.22 241.41 0.06 252.11 281.40 289.14 251.95 182.61 0.19 243.44 314.14 261.97 276.50 0.20 0.02 0.01 0.02 0.02
Table 4: Smallest and largest sizes of critical sets based on paratopisms of Type II. L L3 L4.1
L4.2 L5.1
L5.2
z
class 3
3
3
(1 , 1 , 1 ) (13 , 13 , 21) (14 , 14 , 14 )
c3.9 c3.10 c4.1.13 c4.1.14 (14 , 14 , 212 ) c4.1.15 (14 , 14 , 22 ) c4.1.16 (14 , 14 , 14 ) c4.2.13 (14 , 14 , 212 ) c4.2.14 (15 , 15 , 15 ) c5.1.11 (15 , 15 , 22 1) c5.1.12 (15 , 15 , 41) c5.1.13 (15 , 15 , 15 ) c5.2.6 c5.2.7 c5.2.8 (15 , 15 , 22 1) c5.2.9
Appendix B
scs lcs time (s) L 1 0 3 2 2 1 2 2 2 1 1 3 3 4 1
1 0 3 3 2 1 3 2 4 1 1 5 6 5 1
0.00 0.00 0.00 0.02 0.00 0.00 0.02 0.00 0.01 0.00 0.00 0.03 0.09 0.02 0.00
L6.1 L6.2
L6.3 L6.4
L6.7 L6.9 L6.11
z
class 6
6
6
(1 , 1 , 1 ) c6.1.9 (16 , 16 , 22 12 ) c6.1.10 (16 , 16 , 16 ) c6.2.20 (16 , 16 , 22 12 ) c6.2.21 (16 , 16 , 313 ) c6.2.22 (16 , 16 , 16 ) c6.3.11 (16 , 16 , 313 ) c6.3.12 (16 , 16 , 16 ) c6.4.17 c6.4.18 (16 , 16 , 22 12 ) c6.4.19 (16 , 16 , 16 ) c6.7.12 (16 , 16 , 22 12 ) c6.7.13 (16 , 16 , 16 ) c6.9.5 (16 , 16 , 16 ) c6.11.5
scs lcs time (s) 4 3 5 3 3 4 3 3 5 3 5 3 4 4
7 4 7 4 3 7 3 51 6 4 7 4 8 7
1.81 0.03 1.80 0.03 0.00 0.80 0.02 0.52 1.55 0.03 1.62 0.03 1.94 1.87
Examples of critical sets based on nontrivial autoparatopisms
This appendix provides examples of critical sets associated with non-trivial autoparatopisms of the Latin squares considered in this paper. For each conjugacy class listed in Tables 2–4, we provide a representative non-trivial autoparatopism together with one critical set for each cardinality occurring in that class. The labels coincide with those used in the main tables. Furthermore, we represent each entry (r, c, s) in a critical set as rcs.
21
Table 5: Critical sets based on non-trivial isotopisms (I). L
Class
Autotopism
L3
c3.2 c3.3
(Id3 ; (Id3 , (123), (123))) (Id3 ; ((23), (23), (23)))
Size
Critical set {111, 212} {223} {122, 212} {111}
c3.4
(Id3 ; ((123), (123), (132)))
2 1 2 1
L4.1
c4.1.2 c4.1.3 c4.1.4 c4.1.5 c4.1.6
(Id3 ; (Id4 , (12)(34), (12)(34))) (Id3 ; ((34), (34), (34))) (Id3 ; ((34), (1324), (1324))) (Id3 ; ((12)(34), (13)(24), (14)(23))) (Id3 ; ((243), (243), (243)))
4 4 2 3 2
{111, 133, 313, 432} {111, 133, 313, 331} {111, 313} {111, 122, 313} {122, 212}
L4.2
c4.2.2 c4.2.3 c4.2.4 c4.2.5 c4.2.6
(Id3 ; (Id4 , (12)(34), (12)(34))) (Id3 ; (Id4 , (1324), (1324))) (Id3 ; ((34), (34), (34))) (Id3 ; ((34), (13)(24), (13)(24))) (Id3 ; ((12)(34), (1324), (1423)))
4 3 4 3 2
{111, 133, 313, 431} {111, 212, 313} {111, 133, 313, 332} {111, 122, 332} {111, 313}
L5.1
c5.1.2 c5.1.3
(Id3 ; (Id5 , (12345), (12345))) (Id3 ; ((25)(34), (25)(34), (25)(34)))
c5.1.4 c5.1.5
(Id3 ; ((2354), (2354), (2354))) (Id3 ; ((12345), (12345), (13524)))
4 3 4 5 3 2
{111, 212, 313, 414} {223, 245, 352} {122, 212, 223, 335} {122, 133, 212, 223, 313} {122, 212, 223} {111, 122}
c5.2.2
(Id3 ; ((13)(45), (25)(34), (13)(45)))
c5.2.3
(Id3 ; ((345), (345), (345)))
3 4 5 5
{133, 155, 451} {111, 122, 144, 451} {111, 122, 133, 425, 432} {111, 133, 234, 313, 352}
c6.1.2
(Id3 ; (Id6 , (12)(35)(46), (12)(35)(46)))
9 10 (Id3 ; ((36)(45), (36)(45), (36)(45))) 7 8 9 10 (Id3 ; ((36)(45), (12)(34)(56), (12)(34)(56))) 7 8
{111, 133, 144, 234, 313, 341, 414, 531, 645} {111, 133, 144, 234, 243, 313, 336, 442, 616, 632} {111, 133, 313, 341, 354, 435, 453} {111, 133, 144, 234, 313, 341, 435, 453} {111, 133, 144, 234, 313, 325, 414, 442, 453} {111, 133, 144, 234, 325, 362, 414, 426, 442, 461} {111, 133, 155, 313, 336, 341, 453} {111, 133, 155, 313, 325, 336, 453, 461}
(Id3 ; (Id6 , (14)(25)(36), (14)(25)(36)))
9 10 8 7 8 9 10 (Id3 ; ((14)(26)(35), (14)(25)(36), (23)(56))) 7 8 9 (Id3 ; ((123)(456), (14)(25)(36), (153426))) 4 (Id3 ; ((456), (456), (456))) 8 9 (Id3 ; ((123)(456), (123)(465), (132))) 6 7 (Id3 ; ((456), (152634), (152634))) 3 (Id3 ; ((153624), (152634), (23)(45))) 4
{111, 122, 133, 212, 223, 313, 435, 524, 634} {111, 122, 133, 212, 223, 231, 313, 321, 435, 524} {111, 144, 212, 245, 414, 441, 515, 643} {111, 122, 212, 231, 256, 536, 563} {111, 122, 155, 212, 264, 426, 536, 563} {111, 122, 155, 212, 245, 426, 515, 551, 563} {111, 122, 155, 212, 264, 453, 515, 524, 542, 551} {111, 122, 133, 212, 264, 321, 346} {111, 122, 133, 144, 212, 231, 354, 365} {111, 122, 133, 155, 231, 245, 256, 321, 332} {111, 122, 414, 435} {111, 144, 223, 245, 414, 426, 441, 453} {111, 122, 144, 212, 245, 414, 426, 441, 453} {111, 144, 155, 414, 426, 441} {111, 122, 144, 155, 414, 435, 441} {111, 212, 426} {111, 122, 144, 155}
c6.3.6
(Id3 ; (Id6 , (123)(465), (123)(465))) 8 (Id3 ; ((23)(56), (15)(24)(36), (15)(24)(36))) 6 7 8 (Id3 ; ((23)(56), (143526), (143526))) 4 (Id3 ; ((456), (456), (456))) 8 9 (Id3 ; ((123)(456), (123)(465), (132))) 6
{111, 144, 212, 245, 414, 443, 515, 642} {111, 122, 212, 223, 515, 562} {111, 122, 133, 212, 223, 414, 541} {111, 122, 133, 212, 245, 414, 426, 541} {111, 212, 414, 515} {111, 144, 223, 245, 414, 426, 443, 452} {111, 122, 144, 212, 245, 414, 426, 443, 452} {111, 144, 155, 414, 426, 443}
c6.4.2
(Id3 ; (Id6 , (16)(25)(34), (16)(25)(34)))
{111, 122, 133, 212, 223, 313, 426, 435, 536} {111, 122, 133, 212, 223, 313, 321, 414, 435, 536} {111, 144, 212, 246, 414, 442, 515, 643} {111, 212, 313, 414, 515} {111, 122, 144, 212, 246, 435, 442} {111, 122, 144, 212, 246, 414, 426, 442} {111, 122, 144, 212, 246, 414, 442, 463, 625} {111, 122, 133, 231, 435, 451} {111, 122, 133, 212, 231, 426, 634} {111, 122, 133, 212, 223, 246, 435, 616} {111, 144, 414, 442} {111, 122, 144, 426, 451} {111, 122, 414, 426} {111, 122, 426}
L5.2
L6.1
c6.1.3
c6.1.4 L6.2
c6.2.2 c6.2.3 c6.2.4
c6.2.5 c6.2.6 c6.2.7 c6.2.8 c6.2.9 c6.2.10 L6.3
c6.3.2 c6.3.3 c6.3.4 c6.3.5
L6.4
c6.4.3 c6.4.4 c6.4.5 c6.4.6 c6.4.7 c6.4.8 c6.4.9
(Id3 ; (Id6 , (123)(465), (123)(465))) (Id3 ; ((23)(56), (23)(56), (23)(56)))
9 10 (Id3 ; (Id6 , (123)(465), (123)(465))) 8 (Id3 ; (Id6 , (142635), (142635))) 5 (Id3 ; ((23)(45), (23)(45), (23)(45))) 7 8 9 (Id3 ; ((23)(45), (14)(25)(36), (14)(25)(36))) 6 7 8 (Id3 ; ((123)(465), (123)(465), (132)(456))) 4 5 (Id3 ; ((123)(465), (142635), (16)(25)(34))) 4 (Id3 ; ((123)(465), (153624), (142635))) 3
22
Table 6: Critical sets based on non-trivial isotopisms (II). L
Class
Autotopism
L6.5
c6.5.2
(Id3 ; (Id6 , (15)(24)(36), (15)(24)(36)))
Critical set
c6.5.6
9 10 (Id3 ; ((12)(45), (23)(46), (12)(45))) 7 8 9 (Id3 ; ((12)(45), (15)(26)(34), (14)(25)(36))) 6 7 8 (Id3 ; ((345), (123)(465), (123)(465))) 4 5 6 (Id3 ; ((345), (143526), (143526))) 3
{111, 122, 133, 212, 223, 335, 421, 532, 616} {111, 122, 133, 212, 223, 231, 313, 421, 616, 634} {111, 144, 313, 324, 421, 463, 641} {111, 122, 144, 313, 324, 342, 421, 463} {111, 122, 133, 155, 313, 445, 452, 625, 641} {111, 122, 133, 324, 421, 616} {111, 122, 133, 313, 324, 414, 625} {111, 122, 133, 144, 414, 436, 616, 625} {111, 246, 313, 356} {111, 144, 212, 324, 356} {111, 144, 212, 246, 324, 616} {111, 212, 313}
c6.6.2
(Id3 ; ((45), (15)(26)(34), (15)(26)(34)))
c6.6.3
(Id3 ; ((23)(45), (16)(25), (16)(25)))
c6.6.4
(Id3 ; ((345), (142)(356), (142)(356)))
c6.6.5
(Id3 ; ((12)(345), (152346), (162543)))
c6.6.6
(Id3 ; ((2345), (1364), (1364)))
c6.6.7
(Id3 ; ((12345), (26543), (12345)))
{111, 122, 212, 414, 436, 625, 634} {111, 122, 133, 212, 313, 414, 436, 625} {111, 122, 133, 212, 224, 235, 313, 414, 625} {111, 122, 133, 212, 224, 445, 451} {111, 122, 133, 212, 224, 235, 451, 462} {111, 122, 133, 212, 224, 235, 263, 414, 451} {111, 235, 321, 365} {111, 133, 212, 313, 365} {111, 133, 212, 235, 313, 616} {111, 321} {111, 313, 616} {111, 122, 212, 224, 241} {111, 122, 212, 224, 235, 256} {111, 122, 133} {122, 133, 144, 155}
c6.7.2
(Id3 ; (Id6 , (15)(26)(34), (15)(26)(34)))
c6.5.3 c6.5.4 c6.5.5
L6.6
Size
7 8 9 7 8 9 4 5 6 2 3 5 6 3 4
c6.7.6
9 10 (Id3 ; ((23)(46), (16)(25), (16)(25))) 7 8 9 (Id3 ; ((23)(46), (12)(34)(56), (12)(34)(56))) 6 7 8 (Id3 ; ((123)(456), (164)(235), (136)(254))) 4 5 (Id3 ; ((123)(456), (124563), (146532))) 3
{111, 122, 133, 212, 224, 313, 425, 436, 631} {111, 122, 133, 212, 224, 313, 321, 414, 436, 631} {111, 122, 133, 212, 256, 414, 442} {111, 122, 133, 212, 224, 241, 414, 442} {111, 122, 133, 212, 224, 235, 414, 453, 526} {111, 133, 212, 235, 263, 425} {111, 133, 155, 224, 235, 425, 461} {111, 133, 155, 224, 235, 414, 436, 461} {111, 122, 133, 414} {111, 133, 144, 166, 461} {111, 122, 425}
c6.8.2
(Id3 ; ((24), (14)(23)(56), (14)(23)(56)))
c6.8.3
(Id3 ; ((12)(34), (14)(36), (24)(56)))
c6.8.4
(Id3 ; ((1234), (2653), (1234)))
{111, 122, 212, 256, 325, 616, 651} {111, 122, 155, 212, 235, 313, 515, 651} {111, 122, 155, 212, 235, 313, 325, 616, 651} {111, 122, 155, 224, 263, 313, 325, 354, 515, 521} {111, 155, 336, 342, 515, 521, 534} {111, 122, 133, 313, 336, 515, 521, 632} {111, 122, 133, 144, 313, 336, 515, 521, 534} {111, 122, 166, 515, 521} {111, 122, 133, 155, 515, 521}
L6.9
c6.9.2
(Id3 ; ((12)(34), (16)(25)(34), (13)(26)(45))) 6 7 8
{111, 122, 133, 313, 334, 532} {111, 122, 133, 144, 326, 334, 515} {111, 122, 133, 144, 326, 515, 532, 631}
L6.10
c6.10.2
(Id3 ; ((12), (14)(26)(35), (13)(24)(56)))
c6.10.3
(Id3 ; ((12)(34), (25)(36), (12)(34)))
7 8 9 7 8 9
{111, 122, 133, 326, 423, 515, 634} {111, 122, 133, 155, 332, 423, 531, 616} {111, 122, 133, 313, 326, 524, 616, 621, 634} {111, 122, 133, 326, 332, 515, 524} {111, 122, 133, 166, 332, 354, 515, 524} {111, 122, 133, 326, 365, 515, 524, 531, 621}
L6.11
c6.11.2
(Id3 ; ((12)(35), (12)(56), (16)(34)))
7 8 9
{111, 133, 155, 313, 341, 435, 654} {111, 122, 133, 155, 336, 364, 414, 435} {111, 122, 133, 155, 325, 336, 364, 435, 616}
L6.12
c6.12.2 c6.12.3
(Id3 ; (Id6 , (126)(345), (126)(345))) (Id3 ; ((12), (13)(25)(46), (14)(23)(56)))
c6.12.4
(Id3 ; ((45), (132465), (132465)))
c6.12.5
(Id3 ; ((12)(45), (26)(35), (12)(45)))
c6.12.6
(Id3 ; ((345), (345), (345)))
c6.12.7
(Id3 ; ((345), (126)(354), (126)(354)))
c6.12.8
(Id3 ; ((12)(345), (136425), (146523)))
8 7 8 9 4 5 7 8 9 8 9 6 7 3
{111, 133, 212, 234, 313, 332, 414, 536} {111, 122, 144, 324, 425, 515, 643} {111, 122, 133, 324, 346, 425, 616, 643} {111, 122, 133, 144, 313, 425, 616, 621, 643} {111, 212, 313, 414} {111, 212, 414, 431, 616} {111, 122, 133, 313, 425, 431, 635} {111, 122, 133, 155, 313, 324, 425, 431} {111, 122, 133, 144, 313, 324, 425, 442, 456} {111, 133, 226, 234, 313, 324, 332, 346} {111, 122, 133, 212, 234, 313, 324, 332, 346} {111, 133, 212, 313, 332, 635} {111, 133, 212, 234, 313, 324, 332} {111, 133, 313}
L6.7
c6.7.3 c6.7.4 c6.7.5
L6.8
23
7 8 9 10 7 8 9 5 6
Table 7: Critical sets based on non-trivial paratopisms of type I (I). L
Class
Autoparatopism
L3
c3.5 c3.6 c3.7 c3.8
((23); (Id3 , (23), (23))) ((23); ((23), Id3 , Id3 )) ((23); ((23), (123), (123))) ((23); ((123), (23), (13)))
Size Critical set
L4.1 c4.1.7 ((13); (Id4 , Id4 , Id4 )) c4.1.8 ((13); ((34), (34), (34))) c4.1.9 ((13); ((12), (12), (34))) c4.1.10 ((13); ((12)(34), (12)(34), Id4 )) c4.1.11 ((13); ((1324), (1324), (34))) c4.1.12 ((13); ((243), (243), (243))) L4.2 c4.2.7 ((23); (Id4 , (34), (34))) c4.2.8 ((23); ((34), Id4 , Id4 )) c4.2.9 ((23); ((34), (1324), (1324))) c4.2.10 ((23); ((12)(34), (34), (12))) c4.2.11 ((23); ((13)(24), Id4 , (1423))) c4.2.12 ((23); ((13)(24), (34), (14)(23))) L5.1 c5.1.6 ((13); ((25)(34), Id5 , (25)(34))) c5.1.7 ((13); (Id5 , (25)(34), Id5 )) c5.1.8 ((13); ((2453), (2354), (2453))) c5.1.9 ((13); ((12345), (12)(35), Id5 )) c5.1.10 ((13); ((12)(35), (12345), (25)(34))) L5.2 c5.2.4 ((23); ((45), (12)(35), (12)(35))) c5.2.5 ((23); ((1345), (12354), (152))) L6.1 c6.1.5 ((23); ((45), (12)(36)(45), (12)(36)(45)))
c6.1.6 ((23); ((45), (34)(56), (34)(56)))
c6.1.7 ((23); ((12)(3465), (35)(46), (12)(36)(45))) c6.1.8 ((23); ((12)(3465), (12), (34)(56))) L6.2 c6.2.11 ((13); ((23)(56), (56), (23)(56)))
c6.2.12 ((13); ((14)(25)(36), (56), (14)(25)(36)))
c6.2.13 ((13); ((14)(26)(35), (14)(2536), (23)(56))) c6.2.14 ((13); (Id6 , (14)(2536), (14)(25)(36))) c6.2.15 ((13); ((143625), (123)(46), (153426))) c6.2.16 ((13); ((12)(46), (123)(46), (23)(56))) c6.2.17 ((13); ((16)(24)(35), (123)(46), (14)(25)(36))) c6.2.18 ((13); ((153426), (56), (153426))) c6.2.19 ((13); ((123)(456), (14)(2536), (153426))) L6.3 c6.3.7 ((13); ((23)(56), (46), (23)(56)))
c6.3.8 ((13); ((152634), (14)(2635), (123)(456))) c6.3.9 ((13); ((12)(46), (123)(45), (23)(56))) c6.3.10 ((13); ((143625), (14)(2635), Id6 ))
24
2 1 1 1
{111, 212} {212} {212} {111}
4 5 6 3 4 3 3 2 1
{111, 122, 234, 313} {111, 122, 133, 212, 313} {122, 133, 144, 234, 243, 324} {111, 133, 313} {111, 133, 234, 423} {111, 133, 313} {111, 133, 313} {111, 122} {122}
3 4 3 4 3 3 2 1
{111, 234, 313} {111, 133, 234, 414} {111, 234, 313} {111, 133, 313, 324} {111, 313, 332} {111, 133, 313} {111, 212} {111}
4 5 6 3 4 3 2 1
{111, 122, 234, 245} {111, 122, 133, 212, 352} {111, 122, 133, 144, 313, 324} {122, 133, 245} {122, 133, 144, 234} {122, 133, 245} {111, 133} {111}
4 5 6 3
{111, 234, 313, 425} {111, 133, 212, 324, 432} {111, 133, 212, 324, 335, 451} {111, 122, 155}
6 7 8 9 7 8 9 10 4 5
{111, 234, 313, 426, 435, 645} {111, 133, 212, 234, 313, 414, 645} {111, 133, 212, 221, 234, 313, 426, 645} {111, 133, 212, 234, 313, 336, 354, 414, 663} {111, 133, 256, 313, 414, 426, 645} {111, 122, 234, 265, 313, 426, 435, 645} {111, 122, 133, 234, 265, 313, 414, 435, 453} {111, 133, 155, 234, 265, 336, 414, 435, 453, 461} {111, 133, 313, 336} {111, 133, 155, 313, 336}
7 8 9 10 8 9 10 11 4 5 4 4 4 5 5 2
{111, 122, 155, 245, 354, 515, 536} {111, 122, 133, 155, 212, 264, 536, 625} {111, 122, 133, 155, 166, 212, 256, 536, 625} {111, 122, 133, 155, 166, 212, 223, 256, 515, 536} {111, 122, 133, 212, 245, 256, 346, 453} {111, 122, 133, 155, 212, 223, 231, 346, 453} {111, 122, 133, 155, 212, 223, 332, 346, 441, 563} {111, 122, 133, 155, 212, 223, 231, 313, 321, 332, 453} {111, 122, 166, 212} {111, 122, 166, 212, 313} {111, 122, 144, 441} {111, 144, 155, 414} {111, 144, 155, 441} {111, 122, 133, 144, 441} {111, 122, 133, 155, 453} {111, 122}
6 7 8 9 4 5 4 2
{111, 122, 245, 354, 426, 435} {111, 122, 133, 144, 365, 426, 435} {111, 122, 133, 144, 212, 256, 414, 426} {111, 122, 133, 144, 166, 212, 264, 414, 426} {111, 122, 133, 264} {111, 122, 133, 212, 332} {111, 144, 155, 414} {111, 122}
Table 8: Critical sets based on non-trivial paratopisms of type I (II). L
Class
Autoparatopism
Size Critical set
L6.4 c6.4.10 ((23); (Id6 , (23)(45), (23)(45)))
c6.4.11 ((23); ((23)(45), Id6 , Id6 ))
c6.4.12 ((23); ((14)(25)(36), (123)(465), (142635))) c6.4.13 ((23); ((23)(45), (123)(465), (123)(465))) c6.4.14 ((23); ((123)(465), (23)(45), (13)(46))) c6.4.15 ((23); ((14)(25)(36), Id6 , (153624))) c6.4.16 ((23); ((142635), (23)(45), (15)(26)(34))) L6.5 c6.5.7 ((23); ((45), (13)(56), (13)(56)))
c6.5.8 ((23); ((45), (16)(24)(35), (16)(24)(35)))
c6.5.9 ((23); ((12)(345), Id6 , (132)(456))) c6.5.10 ((23); ((12)(345), (15)(24)(36), (162534)))
6 7 8 9 10 6 7 8 9 6 4 5 3 3 2
{111, 144, 223, 345, 426, 515} {111, 122, 144, 212, 356, 435, 524} {111, 122, 144, 212, 254, 313, 435, 524} {111, 122, 144, 212, 254, 313, 414, 435, 515} {111, 166, 223, 254, 414, 435, 515, 524, 616, 625} {111, 212, 246, 435, 625, 634} {111, 122, 212, 223, 246, 426, 634} {111, 122, 133, 212, 246, 414, 435, 451} {111, 122, 133, 212, 223, 231, 246, 414, 463} {111, 122, 212, 223, 231, 321} {212, 246, 414, 616} {111, 212, 246, 414, 442} {111, 144, 414} {111, 212, 313} {111, 122}
7 8 9 10 6 7 8 9 10 4 2 4
{111, 122, 246, 335, 421, 445, 616} {111, 122, 144, 212, 335, 414, 421, 616} {111, 122, 144, 212, 231, 313, 414, 436, 625} {111, 122, 155, 231, 335, 356, 414, 436, 445, 463} {111, 231, 342, 452, 616, 625} {111, 122, 212, 313, 324, 361, 445} {111, 122, 212, 223, 324, 361, 421, 653} {111, 122, 212, 223, 313, 361, 414, 452, 625} {111, 122, 313, 324, 335, 342, 414, 452, 625, 653} {111, 144, 313, 324} {111, 313} {111, 144, 324, 616}
{111, 122, 212, 313, 451, 625, 634, 643} {111, 122, 212, 224, 321, 451, 515, 634, 643} {111, 122, 212, 224, 321, 515, 616, 643, 652, 661} {111, 122, 212, 224, 321, 332, 414, 451, 515, 531, 643} {111, 122, 133, 212, 224, 241, 313, 321, 332, 414, 423, 451, 515, 531, 542} 7 {111, 133, 212, 346, 414, 451, 625} 8 {111, 133, 144, 212, 346, 414, 423, 625} 9 {111, 133, 144, 212, 224, 321, 423, 445, 616} 10 {111, 133, 144, 212, 224, 313, 321, 414, 445, 451} 11 {111, 133, 144, 212, 224, 313, 321, 414, 423, 436, 451} 6 {111, 133, 212, 224, 445, 625} 7 {111, 122, 133, 212, 224, 235, 451} 8 {111, 122, 155, 212, 224, 235, 451, 643} 9 {111, 122, 155, 224, 235, 256, 462, 634, 643} 5 {111, 122, 212, 224, 241} 6 {111, 122, 212, 224, 235, 256} 3 {111, 212, 321} 4 {111, 212, 313, 616} 4 {111, 133, 313, 321} 1 {111}
L6.6 c6.6.8 ((23); (Id6 , (16)(25)(34), (16)(25)(34)))
8 9 10 11 15
c6.6.9 ((23); ((45), (12)(56), (12)(56)))
c6.6.10 ((23); ((23)(45), (34), (34)))
c6.6.11 ((23); ((2345), (1463)(25), (1463)(25))) c6.6.12 ((23); ((345), (132645), (132645))) c6.6.13 ((23); ((12)(345), (124), (365))) c6.6.14 ((23); ((12345), (162)(35), (156)(24))) L6.7 c6.7.7 ((23); (Id6 , (12)(56), (12)(56)))
c6.7.8 ((23); ((23)(46), (34), (34)))
c6.7.9 ((23); ((14)(26)(35), (123)(456), (142536))) c6.7.10 ((23); ((123)(456), (2463), (1453))) c6.7.11 ((23); ((142536), (1354), (15)(2463))) L6.8 c6.8.5 ((23); (Id6 , (15)(23)(46), (15)(23)(46)))
c6.8.6 ((23); ((24), (16)(45), (16)(45))) c6.8.7 ((23); ((13)(24), (153462), (126435)))
c6.8.8 ((23); ((1234), (15246), (13645)))
25
7 8 9 10 6 7 8 9 6 3 2
{111, 133, 144, 212, 346, 425, 623} {111, 133, 144, 212, 224, 313, 425, 645} {111, 133, 144, 212, 224, 256, 321, 414, 534} {111, 133, 144, 212, 224, 313, 321, 414, 425, 623} {111, 133, 212, 414, 442, 526} {111, 122, 133, 212, 224, 414, 425} {111, 122, 133, 212, 224, 235, 425, 461} {111, 122, 133, 224, 263, 414, 436, 442, 461} {111, 122, 212, 224, 235, 321} {111, 122, 425} {111, 133}
7 8 9 10 11 7 8 9 6 7 8 9 5 6
{111, 122, 212, 431, 515, 623, 664} {111, 122, 212, 224, 336, 515, 651, 664} {111, 122, 212, 224, 313, 414, 534, 546, 651} {111, 122, 212, 224, 313, 414, 616, 623, 632, 664} {111, 122, 212, 224, 313, 354, 414, 431, 515, 521, 534} {111, 122, 212, 235, 313, 645, 651} {111, 122, 133, 212, 235, 313, 515, 651} {111, 122, 133, 212, 235, 256, 361, 616, 623} {111, 122, 256, 515, 623, 632} {111, 122, 133, 212, 515, 521, 632} {111, 122, 133, 155, 224, 515, 534, 623} {111, 122, 133, 155, 212, 224, 515, 521, 534} {111, 122, 133, 515, 521} {111, 144, 155, 166, 515, 521}
Table 9: Critical sets based on non-trivial paratopisms of type I (III). L
Class
Autoparatopism
Size Critical set
L6.9
c6.9.3
((23); ((34), (12)(35), (12)(35)))
c6.9.4
((23); ((1324)(56), (13526), (3654)))
6 7 8 9 10 4 5
{111, 133, 235, 326, 546, 625} {111, 133, 144, 224, 313, 515, 625} {111, 133, 144, 212, 224, 313, 334, 625} {111, 133, 144, 212, 224, 235, 326, 342, 625} {111, 133, 166, 212, 235, 256, 313, 351, 365, 616} {111, 122, 133, 532} {111, 122, 133, 144, 515}
6 7 8 9 6 7 8 9 10 7 8 9 10 7 8 9 10
{122, 332, 414, 515, 621, 634} {111, 122, 212, 332, 423, 524, 616} {111, 122, 212, 225, 313, 461, 515, 634} {111, 122, 212, 225, 313, 332, 423, 616, 621} {111, 122, 236, 332, 524, 616} {111, 122, 133, 212, 332, 531, 616} {111, 122, 133, 212, 251, 332, 515, 634} {111, 122, 133, 212, 236, 313, 332, 515, 531} {111, 122, 144, 326, 354, 365, 515, 524, 546, 616} {111, 133, 313, 332, 553, 616, 621} {111, 122, 133, 155, 332, 515, 634, 663} {111, 122, 133, 155, 313, 423, 515, 553, 634} {111, 122, 144, 326, 515, 524, 546, 616, 621, 652} {111, 122, 313, 341, 515, 524, 652} {111, 122, 133, 313, 332, 524, 553, 616} {111, 122, 133, 155, 332, 354, 524, 553, 616} {111, 122, 166, 326, 332, 341, 365, 531, 553, 645}
6 7 8 9 10 5 6
{111, 212, 234, 414, 621, 645} {111, 122, 212, 243, 414, 621, 645} {111, 122, 212, 226, 243, 423, 645, 654} {111, 122, 212, 226, 234, 414, 461, 645, 654} {111, 122, 212, 226, 414, 423, 616, 621, 632, 654} {111, 122, 144, 414, 435} {122, 133, 144, 155, 414, 435}
7 8 9 10 6 7 8 9 10 7 8 9 11 7 8 9 10 4 5 4 4 5 4 5
{111, 122, 313, 346, 414, 552, 621} {111, 122, 212, 313, 332, 425, 536, 654} {111, 122, 212, 313, 324, 414, 431, 515, 552} {111, 122, 212, 313, 324, 332, 414, 425, 515, 552} {111, 133, 313, 442, 643, 662} {111, 122, 133, 212, 332, 456, 643} {111, 122, 133, 212, 253, 313, 332, 456} {111, 122, 133, 212, 253, 313, 324, 456, 662} {111, 122, 133, 313, 332, 431, 456, 463, 635, 662} {111, 133, 324, 442, 616, 621, 662} {111, 122, 133, 313, 425, 616, 621, 662} {111, 122, 133, 313, 425, 616, 643, 654, 662} {111, 133, 313, 324, 332, 414, 425, 442, 515, 523, 552} {111, 122, 313, 324, 414, 456, 635} {111, 122, 313, 324, 414, 425, 442, 635} {111, 122, 133, 313, 324, 332, 414, 425, 442} {111, 122, 133, 313, 324, 332, 414, 425, 431, 463} {111, 133, 313, 324} {111, 133, 313, 414, 515} {111, 212, 313, 332} {111, 414, 431, 616} {111, 133, 313, 414, 431} {111, 133, 313, 616} {111, 133, 313, 324, 332}
L6.10 c6.10.4
((23); (Id6 , (16)(23)(45), (16)(23)(45)))
c6.10.5
((23); ((34), (15)(46), (15)(46)))
c6.10.6
((23); ((12), (152)(346), (125)(364)))
c6.10.7
((23); ((12)(34), (162453), (135426)))
L6.11 c6.11.3
c6.11.4 L6.12 c6.12.9
((23); ((23), (16)(23)(45), (16)(23)(45)))
((23); ((1253), (2453), (154623))) ((23); (Id6 , (13)(25)(46), (13)(25)(46)))
c6.12.10 ((23); ((45), (26)(35), (26)(35)))
c6.12.11 ((23); ((12), (162)(354), (126)(345)))
c6.12.12 ((23); ((12)(45), (132465), (156423)))
c6.12.13 c6.12.14 c6.12.15 c6.12.16
((23); ((12)(345), (126)(354), (345))) ((23); ((12), Id6 , (162)(354))) ((23); ((345), (136425), (136425))) ((23); ((12)(45), (14)(25)(36), (132465)))
c6.12.17 ((23); ((12)(345), (345), (162)))
26
Table 10: Critical sets based on non-trivial paratopisms of type II. L
Class
Autoparatopism
L3
c3.9 c3.10
((123); (Id3 , (23), (23))) ((123); ((23), Id3 , Id3 ))
1 0
{111} {}
L4.1
c4.1.13 c4.1.14
((132); (Id4 , Id4 , Id4 )) ((132); ((243), (243), (243)))
c4.1.15 c4.1.16
((132); ((34), (34), (34))) ((132); ((123), (243), (123)))
3 2 3 2 1
{111, 122, 133} {122, 133} {111, 122, 234} {111, 133} {111}
L4.2
c4.2.13
((123); (Id4 , (34), (34)))
c4.2.14
((123); ((34), Id4 , Id4 ))
2 3 2
{111, 234} {111, 133, 144} {111, 133}
L5.1
c5.1.11
((132); ((25)(34), Id5 , (25)(34)))
c5.1.12 c5.1.13
((132); (Id5 , (25)(34), Id5 )) ((132); ((2453), (2354), (2453)))
2 3 4 1 1
{223, 352} {111, 223, 234} {111, 122, 155, 223} {223} {223}
c5.2.6
((123); ((12)(345), (12), (354)))
c5.2.7
((123); ((12), (12)(354), (345)))
c5.2.8
((123); ((12)(354), (12)(345), Id5 ))
3 4 5 3 4 5 6 4 5 1
{111, 133, 245} {111, 133, 144, 234} {212, 234, 245, 253, 335} {111, 133, 245} {111, 133, 144, 234} {133, 144, 155, 212, 335} {133, 144, 212, 335, 443, 554} {111, 133, 212, 234} {111, 133, 234, 245, 253} {133}
4 5 6 7 3 4
{111, 133, 256, 354} {111, 133, 144, 221, 256} {111, 133, 144, 155, 234, 243} {133, 144, 155, 221, 256, 336, 663} {111, 133, 234} {111, 133, 144, 243}
5 6 7 3 4 3
{111, 122, 133, 144, 256} {111, 122, 133, 144, 155, 245} {111, 245, 256, 264, 346, 354, 365} {111, 122, 223} {111, 122, 155, 453} {111, 144, 245}
4 5 6 7 3
{111, 122, 245, 354} {111, 122, 144, 231, 256} {111, 122, 144, 155, 231, 354} {122, 144, 155, 166, 245, 256, 264} {111, 144, 245}
3 5 5 6 3 4
{111, 144, 356} {111, 133, 144, 246, 254} {111, 122, 133, 254, 345} {111, 122, 144, 223, 265, 332} {111, 122, 254} {111, 144, 223, 246}
5 6 7 3 4
{122, 133, 155, 224, 332} {111, 122, 133, 155, 263, 346} {111, 122, 133, 144, 166, 263, 346} {111, 133, 321} {111, 122, 321, 534}
L5.2
L6.1
L6.2
Size
c5.2.9
((123); ((1342), (1243), (14)(35)))
c6.1.9
((123); (Id6 , (12)(36), (12)(36)))
c6.1.10
((123); (Id6 , (3564), (3564)))
c6.2.20
((132); ((23), Id6 , (23)))
c6.2.21
((132); ((14)(2635), Id6 , (14)(2635)))
Critical set
c6.2.22
((132); ((12)(465), Id6 , (12)(465)))
c6.3.11
((132); ((13)(456), (456), (13)(456)))
c6.3.12
((132); ((12)(465), (456), (12)(465)))
c6.4.17
((123); (Id6 , (12)(56), (12)(56)))
c6.4.18
((123); (Id6 , (23)(45), (23)(45)))
c6.4.19
((123); ((23)(45), Id6 , Id6 ))
c6.7.12
((123); ((26)(34), (2463), (2463)))
c6.7.13
((123); ((24)(36), (132546), (132546)))
L6.9
c6.9.5
((123); ((25364), (23456), (23456)))
4 5 6 7 8
{111, 155, 334, 445} {111, 122, 166, 224, 445} {111, 122, 133, 235, 256, 423} {111, 122, 133, 144, 256, 334, 423} {111, 122, 133, 224, 256, 263, 334, 423}
L6.11
c6.11.5
((123); ((26435), (24563), (24563)))
4 5 6 7
{144, 243, 336, 645} {111, 122, 226, 243, 435} {111, 122, 133, 144, 226, 645} {111, 122, 133, 144, 234, 524, 645}
L6.3
L6.4
L6.7
27
References [1] J. Dénes and A. D. Keedwell. A new authentication scheme based on Latin squares. Discrete Math., 106/107:157–161, 1992. [2] D. R. Stinson. Generalized mix functions and orthogonal equitable rectangles. Des. Codes Cryptogr., 45(3):347–357, 2007. [3] J. Kong. The role of Latin square in cipher systems: a matrix approach to model encryption modes of operation. UCLA Computer Science Department Technical Report number 030038. [4] A. Desoky, H. Ammar, G. Fahmy, S. El-Sappagh, A. Hendawi, and S. H. Basha. A novel keyless cryptosystem based on Latin square and cognitive artificial intelligence for blockchain and covert communications. Int. J. Appl. Cryptogr., 4(3-4):219–237, 2024. [5] A. Mileva. Cryptographic primitives with quasigroup transformations. Math. Balkanica (N.S.), 24(3-4):207–216, 2010. [6] Behrouz Zolfaghari and Khodakhast Bibak. Combinatorial Cryptography and Latin Squares, pages 37–55. Springer International Publishing, Cham, 2022. [7] K. C. Gupta, S. K. Pandey, and I. G. Ray. Applications of design theory for the constructions of MDS matrices for lightweight cryptography. J. Math. Cryptol., 11(2):85–116, 2017. [8] H. Shen, X. Shan, M. Xu, and Z. Tian. A new chaotic image encryption algorithm based on transversals in a Latin square. Entropy, 24(11):Paper No. 1574, 2022. [9] R. M. Falcón, V. Álvarez, and F. Gudiel. A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares. Adv. Comput. Math., 45(4):1769–1792, 2019. [10] J. Cooper, D. Donovan, and J. Seberry. Secret sharing schemes arising from Latin squares. Bull. Inst. Combin. Appl., 12:33–43, 1994. [11] L. F. Fitina and S. P. Lal. Access schemes based on perfect critical set partitions and transformations. Australas. J. Combin., 34:229–237, 2006. [12] C. S. Chum and X. Zhang. The Latin squares and the secret sharing schemes. Groups Complex. Cryptol., 2(2):175–202, 2010. [13] D. M. Donovan, J. G. Lefevre, T. A. McCourt, N. J. Cavenagh, and A. Khodkar. Identifying flaws in the security of critical sets in Latin squares via triangulations. Australas. J. Combin., 52:243–268, 2012. 28
[14] A. Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 1979. [15] G. R. Blakley. Safeguarding cryptographic keys. In 1979 International Workshop on Managing Requirements Knowledge (MARK), pages 313– 318, 1979. [16] C. J. Colbourn, M. J. Colbourn, and D. R. Stinson. The computational complexity of recognizing critical sets. Lect. Notes Math., 1073:248–253, 1984. [17] C. J. Colbourn. The complexity of completing partial Latin squares. Discrete Appl. Math., 8(1):25–30, 1984. [18] C. Hamalainen. New 2-critical sets in the abelian 2-group. J. Combin. Math. Combin. Comput., 61:193–219, 2007. [19] A. D. Keedwell. Critical sets in latin squares and related matters: an update. Util. Math., 65:97–131, 2004. [20] N. J. Cavenagh. The theory and application of Latin bitrades: a survey. Math. Slovaca, 58(6):691–718, 2008. [21] D. Donovan and A. Howse. Towards the spectrum of critical sets. Australas. J. Combin., 21:107–130, 2000. [22] R. Bean and D. Donovan. Closing a gap in the spectrum of critical sets. Australas. J. Combin., 22:191–200, 2000. [23] D. Curran and G. H. J. Van Rees. Critical sets in Latin squares. Congress. Numer., XXII:165–168, 1979. [24] D. Donovan, J. Cooper, D. J. Nott, and J. Seberry. Latin squares: critical sets and their lower bounds. Ars Combin., 39:33–48, 1995. [25] J. A. Bate and G. H. J. van Rees. The size of the smallest strong critical set in a Latin square. Ars Combin., 53:73–83, 1999. [26] P. Adams and A. Khodkar. Smallest critical sets for the Latin squares of orders six and seven. J. Combin. Math. Combin. Comput., 37:225–237, 2001. [27] P. Adams, R. Bean, and A. Khodkar. A census of critical sets in the Latin squares of order at most six. Ars Combin., 68:203–223, 2003. [28] R. Bean. The size of the smallest uniquely completable set in order 8 Latin squares. J. Combin. Math. Combin. Comput., 52:159–168, 2005. [29] A. Howse. Minimal critical sets for some small Latin squares. Australas. J. Combin., 17:275–288, 1998. 29
[30] J. A. Bate and G. H. J. van Rees. Minimal and near-minimal critical sets in back-circulant Latin squares. Australas. J. Combin., 27:47–61, 2003. [31] D. A. Mojdeh and N. J. Rad. Critical sets in Latin squares given that they are symmetric. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 18:38–45, 2007. [32] B. Smetaniuk. On the minimal critical set of a Latin square. Utilitas Math., 16:97–100, 1979. [33] N. J. Cavenagh. A superlinear lower bound for the size of a critical set in a Latin square. J. Combin. Des., 15(4):269–282, 2007. [34] R. Bean and D. Donovan. Closing a gap in the spectrum of critical sets. Australas. J. Combin., 22:191–200, 2000. [35] R. Bean and E. S. Mahmoodian. A new bound on the size of the largest critical set in a Latin square. Discrete Math., 267(1-3):13–21, 2003. [36] H. Hatami and E. S. Mahmoodian. A lower bound for the size of the largest critical sets in Latin squares. Bull. Inst. Combin. Appl., 38:19– 22, 2003. [37] A. Hulpke, P. Kaski, and P. R. J. Östergård. The number of Latin squares of order 11. Math. Comp., 80(274):1197–1219, 2011. [38] G. Kolesova, C. W. H. Lam, and L. Thiel. On the number of 8 × 8 Latin squares. J. Combin. Theory Ser. A, 54(1):143–148, 1990. [39] B. D. McKay, A. Meynert, and W. Myrvold. Small Latin squares, quasigroups, and loops. J. Combin. Des., 15(2):98–119, 2007. [40] R. M. Falcón. The set of autotopisms of partial Latin squares. Discrete Math., 313(11):1150–1161, 2013. [41] R. M. Falcón. Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method. European J. Combin., 48:215–223, 2015. [42] R. M. Falcón, O. J. Falcón, and J. Núñez. Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers. Math. Methods Appl. Sci., 41(17):7236–7262, 2018. [43] R. M. Falcón and R. J. Stones. Enumerating partial Latin rectangles. Electron. J. Combin., 27(2):Paper No. 47, 2020. [44] D. Donovan and A. Howse. Critical sets for Latin squares of order 7. J. Combin. Math. Combin. Comput., 28:113–123, 1998. 30
[45] D. S. Stones. Symmetries of partial Latin squares. European J. Combin., 34(7):1092–1107, 2013. [46] R. M. Falcón, L. Johnson, and S. Perkins. A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five. AIMS Math., 6(1):261–295, 2021. [47] M. J. L. Mendis and I. M. Wanless. Autoparatopisms of quasigroups and Latin squares. J. Combin. Des., 25(2):51–74, 2017. [48] D. S. Stones, P. Vojtěchovský, and I. M. Wanless. Cycle structure of autotopisms of quasigroups and Latin squares. J. Combin. Des., 20(5):227–263, 2012. [49] N. J. Cavenagh and R. M. Falcón. Latin bitrades derived from quasigroup autoparatopisms. J. Algebraic Combin., 62(2):30, 2025. [50] M. J. L. Mendis and I. M. Wanless. Latin squares with a unique intercalate. J. Combin. Des., 24(6):279–293, 2016. [51] The GAP Group. GAP–Groups, Algorithms, and Programming, Version 4.16.1, 2026. [52] R. M. Falcón. Cycle structures of autotopisms of the Latin squares of order up to 11. Ars Combin., 103:239–256, 2012.
31