Des. Codes Cryptogr. (2008) 48:59–68 DOI 10.1007/s10623-008-9198-2
2-idempotent 3-quasigroups with a conjugate invariant subgroup consisting of a single cycle of length four L. Ji
Received: 1 February 2007 / Revised: 4 February 2008 / Accepted: 7 February 2008 / Published online: 4 March 2008 © Springer Science+Business Media, LLC 2008
Abstract A ternary quasigroup (or 3-quasigroup) is a pair (N , q) where N is an n-set and q(x, y, z) is a ternary operation on N with unique solvability. A 3-quasigroup is called 2-idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x) = y. A conjugation of a 3-quasigroup, considered as an OA(3, 4, n), (N , B), is a permutation of the coordinate positions applied to the 4-tuples of B. The subgroup of conjugations under which (N , B) is invariant is called the conjugate invariant subgroup of (N , B). In this paper, we will complete the existence proof of the last undetermined infinite class of 2-idempotent 3-quasigroups of order n, n ≡ 1 (mod 4) and n > 9, with a conjugate invariant subgroup consisting of a single cycle of length four. Keywords
3-quasigroup · Orthogonal array · Quadruple system
AMS Classification
05B15
1 Introduction A ternary quasigroup (or 3-quasigroup) is a pair (N , q) where N is an n-set and q(x, y, z) is a ternary operation on N with unique solvability; that is, in the equation w = qx, y, z if values for any three of x, y, z, w are given, the value of the remaining variable is uniquely determined. Alternately, a 3-quasigroup of order n can be defined as an OA(3, 4, n), (N , B), with B a collection of ordered 4-tuples (x, y, z, q(x, y, z)) for all choices of x, y, z ∈ N . A 3-quasigroup is called 2-idempotent if it satisfies the generalized idempotent law: q(x, x, y) = q(x, y, x) = q(y, x, x) = y.
Communicated by L. Teirlinck. L. Ji (B) Department of Mathematics, Suzhou University, Suzhou, China e-mail:
[email protected]
123
60
L. Ji
A conjugation of a 3-quasigroup, considered as an OA(3, 4, n), (N , B), is a permutation σ of the coordinate positions applied to the 4-tuples of B by replacing each ordered tuple (x1 , x2 , x3 , x4 ) by (xσ (1) , xσ (2) , xσ (3) , xσ (4) ). The subgroup of conjugations under which (N , B) is invariant is called the conjugate invariant subgroup of (N , B). Clearly, the conjugate invariant subgroup of a 3-quasigroup is a subgroup of S4 , S4 the symmetric group. 2-idempotent 3-quasigroups are related to ordered designs ODλ (t, k, n) and λ-fold t-wise balanced designs (tBD) Sλ (t, K , n) as follows. An ordered design ODλ (t, k, n) is a k-N array A, |N | = n, all of whose rows contain k distinct elements, such that, if we run t fingers down any t columns, we find every ordered t-subset of S exactly λ times. The subgroup of conjugations under which a k-N array A is invariant is called the conjugate invariant subgroup of A. If an ODλ (t, k, n) has a conjugate invariant subgroup G, then it is denoted by G-ODλ (t, k, n). Consider a 2-idempotent 3-quasigroup as an OA(3, 4, n), (N , B), and discard all ordered quadruples (x, y, z, w) with {x, y, z, w}| ≤ 2. Then the resulting array is an OD(3, 4, n). Conversely, adding ordered quadruples (x, x, x, x) (x ∈ N ) and (x, x, y, y), (x, y, x, y), (x, y, y, x) (x, y ∈ N , x = y) to the 4-N array of an OD(3, 4, n) produces a 2-idempotent 3-quasigroup. Clearly, a 2-idempotent 3-quasigroup of order n with a conjugate invariant subgroup G is equivalent to a G-OD(3, 4, n). Let K be a set of positive integers. A λ-fold t-wise balanced design (λ-fold tBD) Sλ (t, K , n) is a set X of cardinality n and a collection B of subsets of X (called blocks) each of cardinality from K such that every t-subset of X is contained in exactly λ blocks. In this paper we use the convention that if λ is not specified, then λ = 1. When K = {k}, we simply write k for K . An Sλ (3, 4, n) is called a λ-fold quadruple system (briefly by QS(n, λ)) and a QS(n, 1) is called a Steiner quadruple system (briefly by SQS(n)). Let (N , q) be a 2-idempotent 3-quasigroup with a conjugate invariant subgroup G, and let Bq denote the collection of quadruples obtained by replacing each 4-tuple (x, y, z, w) in q with the corresponding subset {x, y, z, w} and discarding all 1-subsets and 2-subsets. Then (N , Bq ) is a QS(n, 24), and the multiplicity of each block B ∈ Bq is a multiple of |G|. Removing |G| multiple copies of each block gives a QS(n, 24/|G|). Let (N , Bq∗ ) denote the resulting quadruple system, let Bq denote the 4-tuples in q that correspond to the blocks in Bq∗ (i.e., |Bq∗ | = |Bq |). Then (N , Bq ) is defined to be a G-ordered quadruple system or briefly a G-QS(n). A necessary condition for the existence of a G-QS(n) is that |G| · gcd(n − 3, 12) must divide 24 [8]. For G = S4 , S4 -QS(n) is in 1-1 correspondence with SQS(n). The spectrum was determined by Hanani [2]. Doyen and Vandensavel [1] determined the spectrum for S3 -QS(n). Hartman and Phelps [4] determined the spectrum for A4 -QS, A4 the alternating group. Teirlinck [8] constructed a 2-idempotent 3-quasigroup of order n for all n, n = 3 and possibly 7. A computer search by Colbourn revealed that there is no 2-idempotent 3-quasigroup of order 7, which was pointed out in [9]. Furthermore, Teirlinck [8] determined the spectrum for G-QS(n) for D4 (the dihedral group), K 4 (the Klein 4-group), and G 2 = (13)(24). We summarize these existence results in the following theorem. Theorem 1.1 (1) There exists a 2-idempotent 3-quasigroup of order n for all n, n = 3, 7 [8]. (2) There exists an S4 -QS(n) for n ≡ 2, 4 (mod 6) [2]. (3) There exists an S3 -QS(n) for n ≡ 2, 4 (mod 6) [1]. (4) There exists an A4 -QS(n) for n ≡ 1, 2, 4, 5, 8, 10 (mod 12) [4]. (5) There exists a D4 -QS(n) for all even n or n = 1 [8]. (6) There exists a K 4 -QS(n) for n ≡ 0, 1, 2 (mod 4) [8].
123
2-idempotent 3-quasigroups with a conjugate invariant subgroup
61
(7) There exists a (13)(24)-QS(n) for all n, n = 3, 7 [8]. There remains the spectrum for G-QS(n) to be completed, where G is conjugate to C3 = (123)(4) or C4 = (1234). For C3 , the only open cases are for orders n ≡ 7, 11 (mod 12). For C4 , the only open cases are for orders n ≡ 1 (mod 4), n > 9 [8]. Theorem 1.2 [8] There exists a C4 -QS(n) if n ≡ 0, 2 (mod 4) or n = 9, and there does not exist a C4 -QS(5). In this paper, we are interested in C4 -QS(n), which is equivalent to a C4 -OD(3, 4, n). For this purpose, we introduce a G-ordered candelabra quadruple system (briefly G-CQS) and establish a recursive construction for G-CQSs via 3BD in Sect. 2. Two constructions for C4 -CQSs are also presented in Sect. 3. Section 4 determines the spectrum for C4 -OD(3, 4, n).
2 C4 -ordered candelabra quadruple systems Candelabra quadruple systems are useful in the construction of SQS(v), see for example [5]. In this section we introduce a similar configuration, i.e., an ordered candelabra quadruple system. An ordered candelabra quadruple system of order v with a candelabra of type (g1a1 · · · gkak : s) is a 4-X array A with a branch set G and a stem S where X is a set of v = s + 1≤i≤k ai gi points, S is an s-subset of X , and G = {G 1 , G 2 , . . .} is a partition of X \ S of type g1a1 · · · gkak , all of whose rows contain 4 distinct elements, such that, if we run 3 fingers down any 3 columns, we find every ordered triple T = (a, b, c) of X with |{a, b, c} ∩ (S ∪ G i )| < 3 for all i exactly once and no ordered triples of S ∪ G i for any i. If the array A is invariant under the action of the group of conjugations G, then it is denoted by G-CQS(g1a1 · · · gkak : s). For G = A4 , the concept of G-CQS has been introduced in [7]. Lemma 2.1 There is a C4 -CQS(43 : 1) and a C4 -CQS(24 : 1). Proof A C4 -CQS(43 : 1) will be constructed on (Z 4 × Z 3 ) ∪ {∞} with a branch set {Z 4 × {i} : i ∈ Z 3 } and a stem {∞}. Firstly, we construct the following 4-tuples, where i ∈ Z 3 , x, y, z ∈ Z 4 and x + y + z ≡ 0 (mod 4). ((x, 0), (x + 2, 0), (y + 1, 1), (z, 2)) ((y, 1), (y + 2, 1), (x + 2, 0), (z, 2)) ((z, 2), (z + 2, 2), (x + 1, 0), (y, 1)) ((x, 0), (y, 1), (x + 2, 0), (z, 2)) ((z, 2), (x, 0), (z + 2, 2), (y + 2, 1)) (∞, (y, 1 + i), (x, i), (z + 3 + i, 2 + i)) ((x + 1, i), (x, i), (y + 1, i + 1), (y, i + 1))
((x, 0), (x + 2, 0), (z, 2), (y + 1, 1)) ((y, 1), (y + 2, 1), (z, 2), (x + 2, 0)) ((z, 2), (z + 2, 2), (y, 1), (x + 1, 0)) ((y, 1), (z, 2), (y + 2, 1), (x, 0)) (∞, (z, 2 + i), (x, i), (y + i + 1, i + 1)) ((x, i), (x + 1, i), (y, i + 1), (y + 1, i + 1)) ((x, i), (y, i + 1), (x + 1, i), (y + 1, i + 1))
Applying the permutation of the coordinate positions (1 2 3 4) to the above 384 4-tuples gives the required 4-tuples of a C4 -CQS(43 : 1). The construction of a C4 -CQS(24 : 1) is displayed in the Appendix. A holey ordered design ODλ (t, k, n) with a hole of size h is a k-N array A with a hole H , |N | = n, H an h-subset of N , all of whose rows contain k distinct elements, such that, if we run t fingers down any t columns, we find every ordered t-subset T of N that is not an ordered t-subset of H exactly λ times and no ordered t-subsets of H . Further, if the array A is invariant under the group of conjugations G, then it is shortly denoted by G-HOD(t, k, n; h).
123
62
L. Ji
In the Appendix, we construct the following C4 -HODs. Lemma 2.2 There is a C4 -HOD(3, 4, 13; 5), a C4 -HOD(3, 4, 17; 5) and a C4 -HOD (3, 4, 21; 10). Using G-CQS, G-HOD and G-OD, we have the following. Lemma 2.3 Suppose that there is a G-CQS(g01 g1a1 · · · grar : s). If there is a G-OD(3, 4, g0 + s) and a G-HOD(3, 4, gi + s; s) for 1 ≤ i ≤ r , then there is a G-OD(3, 4, s + g0 + 1≤i≤r ai gi ). Proof Let A be the set of 4-tuples of the given G-CQS on X with a branch set G and a stem S. Take a branch G ∈ G such that |G| = g0 . Construct a G-OD(3, 4, g0 +s) on G ∪ S and denote the set of 4-tuples by BG . For any G ∈ G with G = G, construct a G-HOD(3, 4, |G |+s; s) . Such input designs exist by assumption. Then with a hole S. Denote the set of 4-tuples by BG A ∪ BG ∪ (∪G ∈G , G =G BG ) is the set of 4-tuples of a G-OD(3, 4, s + g0 + 1≤i≤r ai gi ) on X . We shall use s-fan designs to obtain some G-CQSs. An s-fan design is an (s + 3)-tuple (X, G , B1 , B2 , . . . , Bs , T ), where X is a finite set of points, G , Bi (1 ≤ i ≤ s) and T are all sets of subsets of X with the property that (X, G ) s B ) ∪ T ) is a 3BD. is a 1BD, each (X, G ∪ Bi ) is a 2BD for 1 ≤ i ≤ s, and (X, G ∪ (∪i=1 i s The members of G and (∪i=1 Bi ) ∪ T are called branches and blocks, respectively. Let the type of (X, G ) be g1a1 g2a2 · · · grar . If block sizes of Bi and T are from K i (1 ≤ i ≤ s) and K T respectively, then the s-fan design is denoted by s-FG(3, (K 1 , K 2 , . . . , K s , K T ), ri=1 ai gi ) of type g1a1 g2a2 · · · grar . a1 a2 ar An ordered transverse quadruple system of order v and type (g1 g2 · · · gr ) is a 4-X array A with a group set G where |X | = v = 1≤i≤r ai gi , G = {G 1 , G 2 , . . .} a partition of X of type g1a1 · · · grar , all of whose rows contain 4 distinct elements, such that, if we run 3 fingers down any 3 columns, we find every ordered triple T = (a, b, c) of X with |{a, b, c}∩ G i | ≤ 1 for all i exactly once and no other type of ordered triples. If the array A is invariant under the action of the subgroup of conjugations G, then it is denoted by G-TRQS(g1a1 · · · gkak ). Clearly, a G-OD(3, 4, n) is also a G-TRQS(1n ). Lemma 2.4 Suppose that there exists an s-FG(3, (K 1 , . . . , K s , K T ), v) of type g1a1 · · · grar . If there exists a G-TRQS(bk ) for any k ∈ K T , a G-TRQS(bki +1 ) for any ki ∈ K i (2 ≤ i ≤ s) and a G-CQS(bk1 : e) for any k1 ∈ K 1 , then there exists a G-CQS((bg1 )a1 · · · (bgr )ar : e + sb − b). Proof Let (X, G , B1 , B2 , . . . , Bs , T ) be the given s-FG. We shall construct a G-CQS((bg1 )a1 · · · (bgr )ar : e + sb − b) on X = (X × Z b ) ∪ S having a branch set G = {G × Z b : G ∈ G } and a stem S, where S = {∞1 , ∞2 , . . . , ∞e+sb−b }. Denote S1 = {∞1 , ∞2 , . . . , ∞e }, Si = {∞e+ib−2b+1 , ∞e+ib−2b+2 , . . . , ∞e+ib−b } for 2 ≤ i ≤ s. For each block B ∈ T , construct a G-TRQS(b|B| ) on B × Z b with groups {x} × Z b (x ∈ B). Denote its set of 4-tuples by A B . For each block Bi ∈ Bi (2 ≤ i ≤ s), construct a G-TRQS(b|Bi |+1 ) on (Bi × Z b ) ∪ Si with groups {x} × Z b (x ∈ B), and Si . Denote its set of 4-tuples by A Bi . For each block B1 ∈ B1 , construct a G-CQS(b|B1 | : e) on (B1 × Z b ) ∪ S1 with {x} × Z b (x ∈ B1 ) as its branches and S1 as its stem. Denote its set of 4-tuples by A B1 . These input designs exist by assumption. Let F = (∪ B∈T A B ) ∪ (∪ Bi ∈Bi , 1≤i≤s A Bi ).
123
2-idempotent 3-quasigroups with a conjugate invariant subgroup
63
Then F is the set of 4-tuples of a G-CQS((bg1 )a1 · · · (bgr )ar : e + sb − b).
Lemma 2.5 If there is a C4 -TRQS(g n ), then there is C4 -TRQS((mg)n ) for any positive integer m. Proof Let A be the set of 4-tuples of a given C4 -TRQS(g n ) on N with a group set G . Let B consist of the following 4-tuples: ((x1 , y1 ), (x2 , y2 ), (x3 , y3 ), (x4 , y4 )), where (x1 , x2 , x3 , x4 ) ∈ A, y1 , y2 , y3 , y4 ∈ Z m , and y1 + y2 + y3 + y4 ≡ 0 (mod m). It is routine to check that B is the set of 4-tuples of a C4 -TRQS((mg)n ) on N × Z m with the group set G = {G × Z m : G ∈ G }. Lemma 2.6 There is a C4 -OD(3, 4, 24k + 9) for any non-negative integer k. Proof For k = 0, it exists by Theorem 1.2. For any positive integer k, start with a 1-FG(3, (4, 4), 12k + 4) of type 43k+1 , which exists from the proof of [6, Theorem 1.3]. Apply Lemma 2.4 with G = C4 , known C4 -CQS (24 : 1) by Lemma 2.1 and a C4 -TRQS(24 ). The last input design can be obtained by applying Lemma 2.5 with the known C4 -TRQS(14 ) in Theorem 1.2. We then obtain a C4 -CQS(83k+1 : 1). The conclusion follows from Lemma 2.3 with the known C4 -OD (3, 4, 9). Lemma 2.7 There is a C4 -OD(3, 4, 8k + 5) for any positive integer k. Proof For k = 1, a C4 -OD(3, 4, 8k + 5) is displayed in the Appendix. For k = 2, a C4 -OD(3, 4, 21) is obtained by filling the hole of an C4 -HOD(3, 4, 21; 10) by Lemma 2.2 with the known C4 -OD(3, 4, 10) in Theorem 1.2. For each given k ≥ 3, let (X, G , B1 , B2 , B3 ) be a 2-FG(3, (3, 3, {4, 6}), 2k) of type 2k−2 41 if 2k ≡ 4 (mod 6), or of type 2k if 2k ≡ 0, 2 (mod 6), which exists in the proof of [4, Theorem 2.7]. Applying Lemma 2.4 with G = C4 , known C4 -CQS(43 : 1) by Lemma 2.1, a C4 -TRQS(44 ) and a C4 -TRQS(46 ). The last two input designs can be obtained by applying Lemma 2.5 with the known C4 -TRQS(16 ) and C4 -TRQS(14 ) in Theorem 1.2. We then obtain a C4 -CQS(8k−2 161 : 5) or a C4 -CQS(8k : 5). The conclusion follows from Lemma 2.3 with the known C4 -OD(3, 4, 13), C4 -OD(3, 4, 21) and C4 -HOD(3, 4, 13; 5) by Lemma 2.2.
3 Two constructions for C4 -ODs In this section, we shall obtain C4 -OD(3, 4, 12k + 1)’s and C4 -OD(3, 4, 12k + 5)’s. Lemma 3.1 There is a C4 -OD(3, 4, 25) and a C4 -OD(3, 4, 17). Proof We first construct a C4 -CQS(83 : 1) on (Z 8 × Z 3 )∪{∞} with branches Z 8 ×{i}, i ∈ Z 3 and a stem {∞}. Its 4-tuples are generated by the permutation of the coordinate positions
123
64
L. Ji
(1 2 3 4) to the following 4-tuples, where i ∈ Z 3 , x, y, z ∈ Z 8 and x + y + z ≡ 0 (mod 8). ((x, i), (x + 4, i), (y, i + 1), (z, i + 2)) ((x, i), (y + 2, i + 1), (x + 4, i), (z, i + 2)) ((x, i), (z + 2, i + 2), (x + 1, i), (y, i + 1)) ((x, i), (z + 5, i + 2), (x + 2, i), (y, i + 1)) ((z + 1, 2 + i), (y, 1 + i), (x, i), ∞) ((x + 1, i), (x, i), (y + 1, i + 1), (y, i + 1)) ((x + 2, i), (x, i), (y + 2, i + 1), (y, i + 1)) ((x + 3, i), (x, i), (y + 3, i + 1), (y, i + 1))
((x, i), (x + 4, i), (z, i + 2), (y + 4, i + 1)) ((x, i), (y, i + 1), (x + 1, i), (z + 6, i + 2)) ((x, i), (y, i + 1), (x + 2, i), (z + 1, i + 2)) ((x, i), (y + 5, i + 1), (z, 2 + i), ∞) ((x, i), (x + 1, i), (y, i + 1), (y + 1, i + 1)) ((x, i), (x + 2, i), (y, i + 1), (y + 2, i + 1)) ((x, i), (x + 3, i), (y, i + 1), (y + 3, i + 1)) ((x, i), (y, i + 1), (x + 3, i), (y + 3, i + 1))
Then we obtain a C4 -OD(3, 4, 25) from Lemma 2.3 with known C4 -OD(3, 4, 9) in Theorem 1.2. The construction of a C4 -OD(3, 4, 17) is displayed in the Appendix. Lemma 3.2 There is a C4 -OD(3, 4, 12k + 1) for any integer k ≥ 3. Proof Let (X, G , B1 , B2 , B3 ) be a 2-FG(3, (3, 3, {4, 6}), 2k) of type 2k−2 41 if 2k ≡ 4 (mod 6), or of type 2k if 2k ≡ 0, 2 (mod 6), which exists in the proof of [4, Theorem 2.7]. We construct the desired design on X = (Z 6 × X ) ∪ {∞}. For each block B ∈ B3 , construct a C4 -TRQS(6|B| ) on the point set Z 6 × B with groups Z 6 × {x}, x ∈ B. Such a design can be obtained by Lemma 2.5 with known C4 -TRQS(1|B| ) in Theorem 1.2. For each block B = {t0 , t1 , t2 } ∈ B2 , construct a C4 -OD(3, 4, 4) on each of the following quadruple of Z 6 × B. {(x, ti ), (x+1, ti ), (y, ti+1 ), (z, ti−1 )}, where i ∈ Z 3 , x, y, z ∈ Z 6 , x+y+z ≡ 2i (mod 6) Note that if we run 3 fingers down any 3 columns, we find every ordered triple T = (u 1 , u 2 , u 3 ) with {u 1 , u 2 , u 3 } ∈ T B2 exactly once and no other ordered triples of Z 6 × B, where T B2 = {{(a, t0 ), (b, t1 ), (c, t2 )} : a, b, c ∈ Z 6 } ∪ {{(a, ti ), (a + 1, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 }. For each block B = {t0 , t1 , t2 } ∈ B1 , construct the following 4-tuples and apply the permutation of the coordinate positions (1 2 3 4) to these 4-tuples, where i ∈ Z 3 , x, y, z ∈ Z 6 , x + y + z ≡ 0 (mod 6). ((x, ti ), (x+3, ti ), (y+i, ti+1 ), (z, ti−1 )) ((z, ti−1 ), (x, ti ), (z+3, ti−1 ), (y+3−i, ti+1 )) ((x, t0 ), (z, t2 ), (x+2, t0 ), (y+1, t1 )) ((y, t1 ), (z, t2 ), (y+2, t1 ), (x, t0 )) ((z, t2 ), (x, t0 ), (z+2, t2 ), (y+2, t1 )) ((x+2, ti ), (x, ti ), (y+2, ti+1 ), (y, ti+1 )) (∞, (z, ti−1 ), (y, ti+1 ), (x+1+i, ti ))
((x, ti ), (x+3, ti ), (z, ti−1 ), (y+i, ti+1 )) ((x, t0 ), (y, t1 ), (x+2, t0 ), (z+4, t2 )) ((y, t1 ), (x, t0 ), (y+2, t1 ), (z+3, t2 )) ((z, t2 ), (y, t1 ), (z+2, t2 ), (x+5, t0 )) ((x, ti ), (x+2, ti ), (y, ti+1 ), (y+2, ti+1 )) (∞, (x, ti ), (y, ti+1 ), (z+4+i, ti−1 ))
Note that if we run 3 fingers down any 3 columns, we find every ordered triple T = (u 1 , u 2 , u 3 ) with {u 1 , u 2 , u 3 } ∈ T B1 exactly once and no other ordered triple of (Z 6 ×B)∪{∞}, where T B1 = {{(a, t0 ), (b, t1 ), (c, t2 )} : a, b, c ∈ Z 6 } ∪ {{(a, ti ), (a + d, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 , d = 2 or 3} ∪ {{∞, (a, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 }. Then all these 4-tuples form the set of 4-tuples of a C4 -CQS((12)k−2 241 : 1) or a C4 -CQS(12k : 1). (Detailed verification of this construction is left to the reader.) The
123
2-idempotent 3-quasigroups with a conjugate invariant subgroup
65
conclusion follows from Lemma 2.3 with known C4 -OD(3, 4, 13) by Lemma 2.7 and C4 OD(3, 4, 25) by Lemma 3.1. Lemma 3.3 There is a C4 -OD(3, 4, 12k + 5) for any integer k ≥ 3. Proof Let (X, G , B1 , B2 , B3 ) be a 2-FG(3, (3, 3, {4, 6}), 2k) of type 2k−2 41 if 2k ≡ 4 (mod 6), or of type 2k if 2k ≡ 0, 2 (mod 6), which exists in the proof of [4, Theorem 2.7]. We construct the desired design on X = (Z 6 × X ) ∪ {(∞, i) : i ∈ Z 5 }. For each block B ∈ B3 , construct a C4 -TRQS(6|B| ) on the point set Z 6 × B with groups Z 6 × {x}, x ∈ B. For each block B = {t0 , t1 , t2 } ∈ B2 , construct the following 4-tuples on the point set (Z 6 × B) ∪ {(∞, 0), (∞, 1), (∞, 2)} and apply the permutation of the coordinate positions (1 2 3 4) to these 4-tuples, where i ∈ Z 3 , x, y, z ∈ Z 6 , x + y + z ≡ 0 (mod 6). ((x, ti ), (x+3, ti ), (y, ti+1 ), (z+i, ti−1 )) ((z, ti−1 ), (x, ti ), (z+3, ti−1 ), (y+3−i, ti+1 )) ((∞, i), (z, ti−1 ), (y, ti+1 ), (x+1+i, ti )) ((∞, i), (y, ti+1 ), (x, ti ), (z+2i, ti−1 )) ((∞, i), (x, ti ), (z, ti−1 ), (y+5+2i, ti+1 ))
((x, ti ), (x+3, ti ), (z, ti−1 ), (y+i, ti+1 )) ((∞, i), (x, ti ), (y, ti+1 ), (z+4+i, ti−1 )) ((∞, i), (y, ti+1 ), (z, ti−1 ), (x+2+2i, ti )) ((∞, i), (z, ti−1 ), (x, ti ), (y+3+2i, ti+1 ))
Note that if we run 3 fingers down any 3 columns, we find every ordered triple T = (u 1 , u 2 , u 3 ) with {u 1 , u 2 , u 3 } ∈ T B2 exactly once and no other ordered triples of (Z 6 × B) ∪ {(∞, 0), (∞, 1), (∞, 2)}, where T B2 = {{(a, t0 ), (b, t1 ), (c, t2 )} : a, b, c ∈ Z 6 } ∪ {{(a, ti ), (a + 3, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 } ∪ {{(∞, k), (a, ti ), (b, t j )} : i, j, k ∈ Z 3 , i = j, a, b ∈ Z 6 }. For each block B = {t0 , t1 , t2 } ∈ B1 , let ({0, 2, 4} × B, G , A, T ) be a 1-FG(3, (3, 4), 9) where G = {{0, 2, 4} × {ti } : i ∈ Z 3 }, which exists in [3]. For each block {(yi , t ji ) : i ∈ Z 4 } ∈ T , construct a C4 -TRQS(24 ) on {(yi , t ji ) : i ∈ Z 4 } ∪ {(yi + 3, t ji ) : i ∈ Z 4 } with groups {(yi , t ji ), (yi + 3, t ji )}, i ∈ Z 4 . For each block {(yi , t ji ) : i ∈ Z 3 } ∈ A, construct a C4 -TRQS(24 ) on {(yi , t ji ) : i ∈ Z 3 }∪{(yi +3, t ji ) : i ∈ Z 3 }∪{(∞, 3), (∞, 4)} with groups {(yi , t ji ), (yi +3, t ji )}, i ∈ Z 3 and {(∞, 3), (∞, 4)}. Note that if we run 3 fingers down any 3 columns, we find every ordered triple T = (u 1 , u 2 , u 3 ) with {u 1 , u 2 , u 3 } ∈ T B1 exactly once and no other ordered triples of (Z 6 × B) ∪ {(∞, 3), (∞, 4)}, where T B1 = {{(a, t0 ), (b, t1 ), (c, t2 )} : a, b, c ∈ Z 6 } ∪ {{(a, ti ), (a + d, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 , d = 1 or 2} ∪ {{(∞, k), (a, ti ), (b, t j )} : i, j ∈ Z 3 , i = j, a, b ∈ Z 6 , k = 3 or 4}. Then all these 4-tuples form the set of 4-tuples of a C4 -CQS((12)k−2 241 : 5) or a C4 -CQS(12k : 5). (Detailed verification of this construction is left to the reader.) The conclusion follows from Lemma 2.3 with known C4 -OD(3, 4, 17) by Lemma 3.1, C4 -OD(3, 4, 29) by Lemma 2.7 and C4 -HOD(3, 4, 17; 5) by Lemma 2.2.
4 Conclusion Combining Theorem 1.2, Lemmas 2.6, 2.7, and 3.1–3.3, we then obtain the main result of this paper. Theorem 4.1 There is a C4 -OD(3, 4, n) if and only if n ≡ 0, 1, 2 (mod 4) and n = 5.
123
66
L. Ji
Remark Although Lemma 2.3 works for C3 -OD(3, 4, n), there is some difficulty to find small key input designs. It is worth studying C3 -OD(3, 4, n). Acknowledgments The author would like to thank the referees for many helpful comments. This research was supported by NSFC Grant 10701060.
Appendix In this Appendix, we list some small C4 -ODs and C4 -HODs. For each design, we list its points set, an automorphism group H , and a set of base 4-tuples. The base 4-tuples, when developed by the permutation of the coordinate positions (1 2 3 4) and the automorphism group H , will yields the 4-tuples of the design. Note that the 4-tuples with a star in the list will occur more than once under the automorphism group H and the permutation of the coordinate positions (1 2 3 4). We will take each only once. D1 A C4 -CQS(24 : 1) on Z 9 with branch set G = {{i, i + 4} : i ∈ Z 4 } and a stem {8}. H = (0 1 2 3 4 5 6 7)(8). (0 1 2 4) (0 1 4 2) (0 1 5 3) (0 1 6 5) (0 1 7 8) (0 1 8 6) (0 2 1 6) (0 2 5 4) (0 2 7 5) (0 2 8 1) (0 3 6 8) (0 3 7 4) (0 4 3 2) (0 5 2 8) (0 6 5 8) D2 A C4 -OD(3, 4, 13). H = (0 1 2 3 4 5 6 7 8 9 10 11 12), (0)(1 3 9)(2 6 5))(4 12 10)(7 8 11). (0 1 2 4) (0 1 5 6) (0 1 6 11) (0 1 7 2) (0 1 9 8) (0 1 10 5) (0 1 11 3) (0 2 1 5) (0 2 7 6) (0 2 10 1) (0 4 8 2) D3 A C4 -OD(3, 4, 17). H = (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16). (0 1 2 4) (0 1 9 8) (0 1 15 14) (0 2 8 6) (0 2 16 9) (0 3 13 7) (0 4 9 5) (0 4 16 11) (0 5 14 9) (0 7 1 10)
(0 1 4 2) (0 1 10 9) (0 1 16 15) (0 2 9 12) (0 3 6 12) (0 3 14 4) (0 4 11 8) (0 5 2 7) (0 6 2 10) (0 9 5 2)
(0 1 5 3) (0 1 11 10) (0 2 1 15) (0 2 10 14) (0 3 7 11) (0 3 15 5) (0 4 12 3) (0 5 10 4) (0 6 3 11) (0 10 6 2)
(0 1 6 5) (0 1 12 11) (0 2 5 4) (0 2 12 7) (0 3 10 2) (0 3 16 8) (0 4 13 10) (0 5 11 6) (0 6 13 4) (0 10 7 4)
(0 1 7 6) (0 1 13 12) (0 2 6 8) (0 2 13 11) (0 3 11 9) (0 4 1 7) (0 4 14 12) (0 5 12 10) (0 6 14 7) (0 11 6 4)
(0 1 8 7) (0 1 14 13) (0 2 7 5) (0 2 14 10) (0 3 12 6) (0 4 3 2) (0 4 15 6) (0 5 13 8) (0 6 15 8) (0 11 8 3)
D4 A C4 -HOD(3, 4, 13; 5) on Z 8 ∪ {x, y, z, w, u} with a hole {x, y, z, w, u}. H = (0 2 4 6)(1 3 5 7)(x) (y)(z)(w)(u). (0 1 2 3) (0 1 3 2) (0 1 4 x) (0 1 5 4) (0 1 7 5) (0 1 x 6) (0 1 y z) (0 1 z y) (0 1 w u) (0 1 u w) (0 2 1 3) (0 2 5 7) (0 2 6 1) (0 2 7 4) (0 2 x 5) (0 2 y w) (0 2 z u) (0 2 w y) (0 2 u z) (0 3 1 2) (0 3 4 1)
123
2-idempotent 3-quasigroups with a conjugate invariant subgroup
(0 3 6 5) (0 4 1 y) (0 4 u 7) (0 5 w 1) (0 7 3 1) (0 x 1 z) (0 y 1 w) (0 z 3 y) (0 w 1 5) (0 u 7 w) (1 3 z u) (1 7 u z)
(0 3 7 x) (0 4 2 z) (0 5 1 u) (0 5 u 3) (0 7 4 y) (0 x 2 w) (0 y 3 7) (0 z 4 w) (0 w 3 u) (0 u x 3) (1 3 w y) (1 x 3 w)
(0 3 x 7) (0 4 3 w) (0 5 3 z) (0 6 4 u) (0 7 5 w) (0 x 5 3) (0 y 5 u) (0 z 5 x) (0 w 7 y) (0 u y 7) (1 3 u 5) (1 x 7 y)
(0 3 y u) (0 4 x u) (0 5 6 w) (0 6 5 z) (0 7 6 u) (0 x 6 y) (0 y 7 z) (0 z 7 3) (0 w z 3) (0 u w 5) (1 5 y 3) (1 z 5 u)
(0 3 z w) (0 4 y 2) (0 5 7 2) (0 6 x w) (0 7 x z) (0 x 7 u) (0 y z 1) (0 z x 1) (0 w u 1) (1 3 7 z) (1 5 w x) (1 z 7 w)
67
(0 3 w z) (0 4 z 5) (0 5 x y) (0 6 y x) (0 7 y 3) (0 x y 1) (0 y u 5) (0 z y 5) (0 u 1 x) (1 3 x w) (1 7 x u) (0 2 4 6)∗
(0 3 u y) (0 4 w x) (0 5 z x) (0 6 w 3) (0 7 u x) (0 x z 7) (0 z 2 u) (0 z w 7) (0 u 5 y) (1 3 y x) (1 7 y w) (1 3 5 7)∗
D5 A C4 -HOD(3, 4, 17; 5) on Z 12 ∪ {x, y, z, w, u} with a hole {x, y, z, w, u}. H = (0 1 2 3 4 5 6 7 8 9 10 11)(x)(y)(z)(w)(u) (0 1 2 4) (0 1 11 10) (0 2 4 7) (0 2 y z) (0 3 10 7) (0 4 3 w) (0 4 u 3) (0 5 u 2) (0 7 2 y) (0 8 y 1) (0 10 w x) (0 y 1 w) (0 1 6 7)∗
(0 1 4 2) (0 1 x y) (0 2 6 3) (0 2 z u) (0 3 11 z) (0 4 8 y) (0 5 3 x) (0 6 2 u) (0 7 6 u) (0 8 w 2) (0 10 u 1) (0 y 3 z)
(0 1 5 3) (0 1 y x) (0 2 7 4) (0 2 w y) (0 3 x w) (0 4 9 5) (0 5 4 z) (0 6 5 y) (0 7 z 1) (0 9 x z) (0 11 10 x) (0 y 8 u)
(0 1 7 5) (0 1 z w) (0 2 8 5) (0 2 u w) (0 3 y u) (0 4 10 z) (0 5 10 y) (0 6 x 5) (0 7 w z) (0 9 y w) (0 x 1 y) (0 z 4 u)
(0 1 8 6) (0 1 w u) (0 2 9 x) (0 3 2 8) (0 3 z 6) (0 4 11 u) (0 5 x u) (0 6 y 3) (0 8 4 x) (0 9 z x) (0 x 4 w) (0 z 7 w)
(0 1 9 8) (0 1 u z) (0 2 x 8) (0 3 7 x) (0 3 w 5) (0 4 z 2) (0 5 z 4) (0 6 w 4) (0 8 5 u) (0 9 w 1) (0 x 7 z) (0 w 7 u)
(0 1 10 9) (0 2 1 6) (0 2 11 9) (0 3 9 4) (0 3 u y) (0 4 w 7) (0 5 w 6) (0 6 u x) (0 8 6 y) (0 10 z y) (0 x 10 u) (0 3 6 9)∗
D6 A C4 -HOD(3, 4, 21; 10). on Z 21 with a hole Z 10 . H = (0)(1)(2)(3)(4)(5)(6)(7)(8)(9) (10 11 12 13 14 15 16 17 18 19 20), (0 2 4 6 8)(1 3 5 7 9)(10)(11 13 19 15 14)(12 16 17 20 18). (0 1 10 11) (0 7 10 17) (0 10 4 15) (0 10 13 5) (1 7 10 19) (10 11 14 19)
(0 2 10 12) (0 8 10 19) (0 10 5 17) (0 10 16 7) (1 9 10 16) (10 11 16 13)
(0 3 10 14) (0 9 10 18) (0 10 7 19) (0 10 17 16) (1 10 3 15) (10 11 19 15)
(0 4 10 13) (0 10 1 11) (0 10 9 20) (0 10 19 9) (1 10 5 18)
(0 5 10 15) (0 10 2 12) (0 10 11 1) (1 3 10 17) (1 10 19 11)
(0 6 10 16) (0 10 3 14) (0 10 12 3) (1 5 10 12) (10 11 12 14)
References 1. Doyen J., Vandensavel M.: Nonisomorphic Steiner quadruple systems. Bull. Soc. Math. Belg. 23, 393–410 (1971). 2. Hanani H.: On quadruple systems. Canad. J. Math. 12, 145–157 (1960). 3. Hanani H.: A class of three-designs. J. Combin. Theory A 26, 1–19 (1979). 4. Hartman A., Phelps K.T.: Tetrahedral quadruples systems. Utilitas Math. 37, 181–189 (1990). 5. Hartman A., Phelps K.T.: Steiner quadruple systems. In: Dinitz J.H., Stinson D.R. (eds.), Contemporary Design Theory, pp. 205–240. Wiley, New York (1992). 6. Ji L.: Existence of Steiner quadruple systems with a spanning block design. Discrete Math. (to appear). 7. Ji L.: Purely tetrahedral quadruple systems. Sci. China Ser. A 49, 1327–1340 (2006).
123
68
L. Ji
8. Teirlinck L.: Generalized idempotent orthogonal arrays. In: Ray-Chaudhuri D. (ed.), Coding Theory and Design Theory Part II, pp. 368–378. Springer-Verlag, New York (1990). 9. Teirlinck L.: Large sets of disjoint designs and related structures. In: Dinitz J.H., Stinson D.R. (eds.), Contemporary Design Theory, pp. 561–592. Wiley, New York (1992).
123
