Jul 7, 2017 - If q â¡ 3 mod 4 is an odd prime power with q = 3, then there exists a strong starter S for Fq such that 1a, bl â S satisfy that a â...

0 downloads 2 Views 166KB Size

On two-quotient strong starters for Fq Carlos A. Alfaro∗ Banco de M´exico

Christian Rubio-Montiel† UMI LAFMIA CINVESTAV-IPN

‡ ´ Adri´an V´azquez-Avila

Subdirecci´ on de Ingenier´ıa y Posgrado Universidad Aeron´ autica en Quer´etaro

Abstract Let G be a finite additive abelian group of odd order n, and let G∗ = G \ {0} be the set of non-zero elements. A starter for G is a set S = {{xi , yi } : i = 1, . . . , n−1 } such that 2 n−1 2

1.

[

{xi , yi } = G∗ , and

i=1

2. {±(xi − yi ) : i = 1, . . . , n−1 } = G∗ . 2 = n−1 , then S is called a Moreover, if xi + yi : i = 1, . . . , n−1 2 2 strong starter for G. A starter S for G is a k quotient starter if there exists Q ⊆ G∗ of cardinality k such that yi /xi ∈ Q or xi /yi ∈ Q, for i = 1, . . . , n−1 . In this paper, we give examples of two-quotient 2 ∗ [email protected] † [email protected] ‡ [email protected]

1

strong starters for Fq , where q = 2k t + 1 is a prime power with k > 1 a positive integer and t an odd integer greater than 1.

Keywords. Strong starters, two-quotient starters, quadratic residues.

1

Introduction

Strong starters were first introduced by Mullin and Stanton in [20] in constructing of Room squares. Starters and strong starters have been useful to construct many combinatorial designs such as Room cubes [8], Howell designs [2, 15], Kirkman triple systems [15, 18], Kirkman squares and cubes [19, 21], and factorizations of complete graphs [1, 7, 9, 12, 13]. Moreover, there are some interesting results on strong starters for cyclic groups [15] and for finite abelian groups [9, 14]. A starter S is a k quotient starter if there exists Q ⊆ G∗ of cardinality k such that yi /xi ∈ Q or xi /yi ∈ Q, for i = 1, . . . , n−1 2 , see [6]. In particular if k = 1 the starter S is called one-quotient starer for G. In fact, an first example of a one-quotient strong starter S was given in [16] Lemma 1. Further information about quotient starters in [6]. Let QR(q) and N QR(q) denote the set of quadratic residues and the set of non-quadratic residues of the F∗q = Fq \ {0}, respectively. In this work, we prove the following: Theorem 1.1 (Main Theorem). Let q = 2k t + 1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then there exists a strong starter S for Fq which satisfies {a, b} ∈ S with a ∈ QR(q) and b ∈ N QR(q). Furthermore there exists two different elements β1 , β2 ∈ N QR(q) such that for every {a, b} ∈ S, with a ∈ QR(q) and b ∈ N QR(q), we have that b/a ∈ {β1 , β2 }. In the known results, there are constructions of strong starters for Fq (see [5, 6, 10, 16, 17]), but none of those constructions gives an explicit construction of strong starters which satisfy the conclutions of the Main Theorem. 2

This paper is organized as follows. In Section 2, we recall some basic properties about quadratic residues. In Section 3, we include an alternative proof when q ≡ 3 mod 4 and q 6= 3 (see [16]). In section 4, we present some previous results. Finally, in Section 5, we prove the main theorem and present some examples.

2

Quadratic residues

Let q be an odd prime power. An element x ∈ F∗q is called a quadratic residue if there exists an element y ∈ F∗q such that y 2 = x. If there is no such y, then x is called a non-quadratic residue. The set of quadratic residues of F∗q is denoted by QR(q) and the set of non-quadratic residues is denoted by N QR(q). It is well known that QR(q) is a cyclic subgroup of F∗q of cardinality q−1 2 (see [11] pg. 87), that is Theorem 2.1. Let q be an odd prime power, then QR(q) is a cyclic subgroup of F∗q . Furthermore, |QR(q)| = |N QR(q)| = q−1 2 . Corollary 2.2. Let q be an odd prime power, then 1. if either x, y ∈ QR(q) or x, y ∈ N QR(q), then xy ∈ QR(q), 2. if x ∈ QR(q) and y ∈ N QR(q), then xy ∈ N QR(q). The following theorems are well known results on quadratic residues. For more details of this kind of results the reader may consult [3] pg. 171, see also [11]. Theorem 2.3 (Eulers’ criterion). Let q be an odd prime and x ∈ F∗q , then 1. x ∈ QR(q) if and only if x

q−1 2

2. x ∈ N QR(q) if and only if x

= 1.

q−1 2

= −1.

Theorem 2.4. Let q be an odd prime power, then 1. −1 ∈ QR(q) if and only if q ≡ 1 mod 4. 3

2. −1 ∈ N QR(q) if and only if q ≡ 3 mod 4. Theorem 2.5. Let q be an odd prime. If q ≡ 1 mod 4, then 1. x ∈ QR if and only if −x ∈ QR. 2. x ∈ N QR if and only if −x ∈ N QR.

3

Case q ≡ 3 mod 4, with q 6= 3

Now, for the sake of completeness, we include a proof for the case q ≡ 3 mod 4, with q 6= 3, using different notation that in [16]. This notation will be used, of general way, in the main result of this paper. Lemma 3.1. If q ≡ 3 mod 4 is an odd prime power with q 6= 3, then there exists a strong starter S for Fq such that {a, b} ∈ S satisfy that a ∈ QR(q) and b ∈ N QR(q). Proof. Let α be a generator of QR(q) and β ∈ N QR(q) such that β + 1 6= 0. We claim that the following set: n o p−1 p−1 Sβ = {α, αβ}, {α2 , α2 β}, . . . , {α 2 , α 2 β} , q−1

is a strong starter for Fq . First we have that {α, α2 , . . . , α 2 } = QR(q) and q−1 {αβ, α2 β, . . . , α 2 β} = βQR = N QR(q) (by Corollary 2.2). Now we shall i = F∗q . Suppose that αi (β − 1) = prove that ±α (β − 1) : i = 0, . . . , q−1 2 ±αj (β − 1), then (β − 1)(αi ± αj ) = 0, for i 6= j ∈ {1, . . . , q−1 2 }, which it is a i j−i contradiction, since if i < j then α (1 + α ) 6= 0, that is, 1 + αj−i 6= 0 (by q−1 Theorem 2.4). Finally, we have that {αi (β + 1) : i = 0, . . . , q−1 2 } = 2 , q−1 i j since if i 6= j ∈ {1, . . . , 2 } then α (β + 1) 6= α (β + 1). To end this section, it is easy to see that Sβ is an example of one quotient strong starter for Fq . This kind of starters are called Dinitz starters for Fq , see [4], Theorem VI.55.22, page 624.

4

4

Previous results

To begin with, we introduce some terminology in order to simplify the description of the of existence of strong starters S for Fq with the property that if {a, b} ∈ S, then a ∈ QR(q) and b ∈ N QR(q). Let q = 2k t + 1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1 and α be a generator of QR(q). We define C0 = hα∆ i, where ∆ = 2k−1 , to be the subgroup of F∗q of order t. Let Cj = αj C0 , for j = 1, . . . , ∆1 − 1 with ∆1 = 2k−1 , and Cˆj = −Cj , for S∆1 −1 j = 0, . . . , ∆1 − 1 . Hence QR(q) = j=0 (Cj ∪ Cˆj ). On the other hand, ˆ j = β2 Cj , for let β1 ∈ N QR(q) and β2 ∈ β1 Cˆ0 . We define Dj = β1 Cj and D S∆1 −1 ˆ j = 0, . . . , ∆1 − 1. Hence N QR(q) = i=0 (Dj ∪ Dj ). Moreover, it is easy P P P P to see that a∈Cj a = 0, a∈Cˆj a = 0, a∈Dj a = 0 and a∈Dˆ j a = 0, for j = 1, . . . , ∆1 − 1. To prove the main theorem of this paper (see Theorem 1.1), we need to prove the following auxiliary lemma, which states the condition of existence of strong starters S for Fq with the property that if {a, b} ∈ S, then a ∈ QR(q) and b ∈ N QR(q), and wthe proof of this lemma is obtained from Lemmas 4.3 and 4.4. Lemma 4.1. Let q = 2k t+1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then there exist β1 ∈ N QR(q) and β2 ∈ β1 Cˆ0 , such that (β1 − 1)(β2 + 1) ∈ N QR(q) and (β1 + 1)(β2 − 1) ∈ N QR(q). We present the sketch of the proof of Main Theorem: Let α be a generator of QR(q), β1 ∈ N QR(q) and β2 ∈ β1 Cˆ0 such that (β1 − 1)(β2 + 1) ∈ N QR(q) and (β1 + 1)(β2 − 1) ∈ N QR(q) (by Lemma 4.1), then the ∆[ 1 −1 S(β1 , β2 )j is a strong starter for Fq , where following set S(β1 , β2 ) = i=0

S(β1 , β2 )j = {{x, β1 x}, {y, −β2 y} : x ∈ Cj , y ∈ Cˆj }, for j = 0, . . . , ∆1 − 1. S∆1 −1 We have that QR(q) = j=0 {{x} ∪ {y} : x ∈ Cj , y ∈ Cˆj } and N QR(q) = S∆1 −1 ˆ j=0 {{β1 x} ∪ {−β2 y} : x ∈ Cj , y ∈ Cj }. Moreover, if {a, b} ∈ S(β1 , β2 ), then a/b ∈ {β1 , −β2 } or b/a ∈ {β1 , −β2 }, which impliest that S(β1 , β2 ) is 5

a two-quotient strong starter for Fq . Moreover, if {a, b} ∈ S(β1 , β2 ), then a/b ∈ {β1 , −β2 } or b/a ∈ {β1 , −β2 }, which impliest that S(β1 , β2 ) is a two-quotient strong starter for Fq . To prove the following lemma, we needs the next definition: Let q = ef + 1 be a prime power and let H be the subgroup of F∗q of order f with {H = C0 , . . . , Ce−1 } the set of (multiplicative) cosets of H in F∗q (that is, Ci = g i C0 , where g is the least primitive element of Fq ). The cyclotomic number (i, j) is |{x ∈ Ci : x + 1 ∈ Cj }|. In particular, if e = 2 and f is f f f even, then (0, 0) = f −2 2 , (0, 1) = 2 , (1, 0) = 2 and (1, 1) = 2 , see [4], Table VII.8.50. Hence if C0 = QR(q) and C1 = N QR(q) are the cosets of QR(q) in F∗q , then we have the following: Lemma 4.2. Let q = 2k t+1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then there exist β1 , β2 ∈ N QR(q) such that 1. (β1 + 1) ∈ N QR(q) and (β2 + 1) ∈ QR(q). 2. (β1 − 1) ∈ N QR(q) and (β2 − 1) ∈ QR(q). Lemma 4.3. Let q = 2k t+1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then there exists β ∈ N QR(q) such that (β + 1)(β − 1) ∈ N QR(q). Proof. For each β ∈ N QR(q) define Aβ = {aβ1 , . . . , aβlβ }, where aβi ∈ N QR(q) and aβi+1 = aβi + 1, for all i = 1, . . . , lβ − 1. By Lemma 4.2, there exists β ∈ N QR(q) such that |Aβ | > 1. If β ∗ = aβlβ , then (β ∗ + 1) ∈ QR(q) and (β ∗ − 1) ∈ N QR(q). On the other hand, if β ∗ = β1 , then (β ∗ + 1) ∈ N QR(q) and (β ∗ − 1) ∈ QR(q). Hence (β ∗ + 1)(β ∗ − 1) ∈ N QR(q). Remark 1. According with the proof of Lemma 4.3, if there exists β ∈ N QR(q) such that |Aβ | = 1, then (β + 1) ∈ QR(q) and (β − 1) ∈ QR(q). Moreover, if there exists β ∈ N QR(q) such that |Aβ | > 2, then β ∗ = aβ2 is such that (β ∗ + 1) ∈ N QR(q) and (β ∗ − 1) ∈ N QR(q). Lemma 4.4. Let q = 2k t+1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then given β ∈ N QR(q) there exist β1 , β2 ∈ β Cˆ0 , such that (β1 − 1)(β2 − 1) ∈ N QR(q). 6

Proof. Suppose that given β1 ∈ β Cˆ0 is such that (β1 − 1) ∈ QR(q); the same argument is used if we suppose that (β1 − 1) ∈ N QR(q). Hence q−1 (β1 − 1) 2 = (β1 − 1)∆t = 1. Let A0 = β Cˆ0 , then X X (β1 − 1)∆t = t = (−βx − 1)∆t x∈C0

β1 ∈A0

X

=

(βx + 1)∆t =

x∈C0

x∈C0 ∆t X

=

i=0

∆t i X i β x, i

where X

i

x =

x∈Cj

Then 1=

∆t X X ∆t i i βx i i=0

x∈Cj

(

t if i = 0, t, . . . , ∆t, 0 otherwise.

∆ X ∆t st β , for all β ∈ N QR(q). st s=0

Hence, if N QR(q) = {β1 , . . . , β∆t }, then ∆t =

∆t ∆ X ∆t X st

s=0

Since ∆t X

βkst

k=1

then ∆t =

∆t = −∆t 0

k=1

if s = 0, if s = ∆, otherwise,

∆t ∆ X ∆t X s=0

st

βkst

βkst = 0,

k=1

which it is a contradiction. Furthermore, there exist β1 , β2 ∈ β Cˆ0 , such that (β1 − 1)(β2 − 1) ∈ N QR(q). Corollary 4.5. Let q = 2k t + 1 be a prime power with k > 1 a positive integer and t an odd integer greater than 1. Then given β ∈ N QR(q) there exist β1 , β2 ∈ β Cˆ0 such that (β1 + 1)(β2 + 1) ∈ N QR(q). 7

5

Proof of the main theorem

With the results presented before, we are ready to prove the main theorem, Theorem 1.1, of this paper: Proof. Let α be a generator of QR(q), β1 ∈ N QR(q) and β2 ∈ β1 Cˆ0 such that (β1 − 1)(β2 + 1) ∈ N QR(q) and (β1 + 1)(β2 − 1) ∈ N QR(q) (by Lemma S∆1 −1 4.1). We claim that the following set S(β1 , β2 ) = i=0 S(β1 , β2 )j is a strong starter for Fq ,where S(β1 , β2 )j = {{x, β1 x}, {y, −β2 y} : x ∈ Cj , y ∈ S∆1 −1 Cˆj }, for j = 0, . . . , ∆1 − 1. We have that QR(q) = j=0 {{x} ∪ {y} : x ∈ S∆1 −1 ˆ Cj , y ∈ Cj } and N QR(q) = j=0 {{β1 x} ∪ {−β2 y} : x ∈ Cj , y ∈ Cˆj }. Moreover, if {a, b} ∈ S(β1 , β2 ), then a/b ∈ {β1 , −β2 } or b/a ∈ {β1 , −β2 }, which impliest that S(β1 , β2 ) is a two-quotient strong starter for Fq . First we shall prove that F∗q =

S∆1 −1 j=0

(Ej ∪ Ej∗ ), where

Ej = {±x(β1 − 1) : x ∈ Cj } o n Ej∗ = ±y(β2 + 1) : y ∈ Cˆj for all j = 0, . . . , ∆1 − 1. Case (i): If xj (β1 −1) = ±x′j (β1 −1), for xj 6= x′j ∈ Cj , then (β1 −1)(xj ±x′j ) = 0, which it is a contradiction, since xj + x′j 6= 0. Case (ii): If xj (β1 − 1) = ±xi (β1 − 1), for xj ∈ Cj and xi ∈ Ci , then (β1 − 1)(xj ± xi ) = 0, which it is a contradiction, since Cj ∩ Ci = ∅, for i 6= j ∈ {0, . . . , ∆1 − 1} and xj + xi 6= 0. Case (iii): If yj (β2 +1) = ±yj′ (β2 +1), for yj 6= yj′ ∈ Cˆj , then (β2 +1)(yj ±yj′ ) = 0, which it is a contradiction, since yj + yj′ 6= 0. Case (iv): If yj (β2 + 1) = ±yi (β2 + 1), for yj ∈ Cˆj and yi ∈ Cˆi , then (β2 + 1)(yj ± yi ) = 0, which it is a contradiction, since Cˆj ∩ Cˆi = ∅, for i 6= j ∈ {0, . . . , ∆1 − 1} and yj + yi 6= 0. Case (v): As (β1 − 1)(β2 + 1) ∈ N QR(q) then xj (β1 − 1) 6= ±yi (β2 + 1), for xj ∈ Cj and yi ∈ Cˆi , since either xj (β1 − 1) ∈ N QR(q) and yi (β2 + 8

1) ∈ QR(q) or xj (β1 − 1) ∈ QR(q) and yi (β2 + 1) ∈ N QR(q). ∆[ 1 −1 ∗ (Pj ∪ Pj ) = ∆t, where Now, we shall prove that j=0 Pj = {x(β1 + 1) : x ∈ Cj } o n Pj∗ = −y(β2 − 1) : y ∈ Cˆj

for all j = 0, . . . , ∆1 − 1. Case (i): If xj (β1 +1) = x′j (β1 +1), for xj 6= x′j ∈ Cj , then (β1 +1)(xj −xi ) = 0, which it is a contradiction. Case (ii): If xj (β1 + 1) = xi (β1 + 1), for xj ∈ Cj and xi ∈ Ci , then (β1 + 1)(xj − xi ) = 0, which it is a contradiction, since Ci ∩ Cj = ∅, for i 6= j ∈ {0, . . . , ∆1 − 1}. Case (iii): If −yj (β2 −1) = −yj′ (β2 −1), for yj 6= yj′ ∈ Cˆj , then (β2 −1)(yj −yj′ ) = 0, which it is a contradiction. Case (iv): If −yj (β2 − 1) = −yi (β2 − 1), for yj ∈ Cˆj and yi ∈ Cˆi , then (β2 − 1)(yj − yi ) = 0, which it is a contradiction, since Cˆj ∩ Cˆi ∅, for i 6= j ∈ {0, . . . , ∆1 − 1}. Case (v): As (β1 + 1)(β2 − 1) ∈ N QR(q), then xj (β1 + 1) 6= −yi (β2 − 1), for xj ∈ Cj and yi ∈ Cˆi , since either xj (β1 + 1) ∈ N QR(q) and −yi (β2 − 1) ∈ QR(q) or xj (β1 + 1) ∈ QR(q) and −yi (β2 − 1) ∈ N QR(q). To end, it is not difficult to prove that β1 6= β2 , since if β1 = −β1 x, for some x ∈ C0 , then β1 (1 + x) = 0, which is a contradiction, since −1 ∈ Cˆ0 .

Corollary 5.1. If S(β1 , β2 ) is a two-quotient strong starter for Fq given by Theorem 1.1, then S(β2 , β1 ), S(−β1 , −β2 ) and S(−β2 , −β1 ) are twoquotient strong starters for Fq different from S(β1 , β2 ). 9

Let q = 4t + 1 be a prime power with an odd integer greater than 1, C0 ⊆ F∗q be the subgroup of order t and C0 , C1 , C2 , C3 be the multiplicative cosets of C0 . In [6] was proven then the following set ˆ 0 , a1 ) = {{x, a0 x}, {y, a1 y} : x ∈ C a0 , y ∈ Cˆ a1 }, S(a 1 0 where C0a0 = 1/(a0 − 1)C0 and C1a1 = 1/(a1 − 1)C1 , is a two-quotient strong starter for Fq . Hence if β1 ∈ N QR(q) and β2 ∈ β1 Cˆ0 are such that (β1 − 1)(β2 + 1) ∈ N QR(q), (β1 + 1)(β2 − 1) ∈ N QR(q) and (β0 − 1) ∈ C0 and −(β1 − 1) ∈ Cˆ0 , then ˆ 0 , −β1 ) = S(β

5.1

=

{{x, β0 x}, {y, −β1y} : x ∈ C0β0 , y ∈ Cˆ0β1 } {{x, β0 x}, {y, −β1y} : x ∈ C0 , y ∈ Cˆ0 }

=

S(β0 , β1 ).

Examples

In this subsection we give examples of strong starters for F(29) and F(41) given by Theorem 1.1 (main theorem). Let F29 = Z29 , then k = 2, t = 7, ∆ = 2, ∆1 = 0 and α = 4. We have QR(29) =

{1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28} and

N QR(29) =

{2, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27}.

Hence C0 = {1, 7, 16, 20, 23, 24, 25} and Cˆ0 = {4, 5, 6, 9, 13, 22, 28}. If β1 = 2 and β2 = 26 ∈ β1 Cˆ0 = {2, 10, 11, 15, 17, 21, 26}, then (β1 − 1)(β2 + 1) ∈ N QR(29) and (β1 + 1)(β2 − 1) ∈ N QR(29). Therefore S(2, 26) = S(2, 26)0 , where S(2, 26)0

= {{16, 3}, {13, 10}} ∪ {{24, 19}, {5, 15}} ∪ {{7, 14}, {22, 8}} ∪

{{25, 21}, {4, 12}} ∪ {{23, 17}, {6, 18}}

∪

{{20, 11}, {9, 27}} ∪ {{1, 2}, {28, 26}}

is a two-quotient strong starter for F29 . Moreover, by Corollary 5.1, we see that S(26, 2), S(27, 3) and S(3, 27) are two-quotient strong starters in F29 different from S(2, 26): 10

• S(26, 2) = S(26, 1)0 , where S(26, 1)0

= {{16, 10}, {13, 3}} ∪ {{24, 15}, {5, 19}} ∪ {{7, 8}, {22, 14}} ∪

{{25, 12}, {4, 21}} ∪ {{23, 18}, {6, 17}}

∪

{{20, 27}, {9, 11}} ∪ {{1, 26}, {28, 2}}

• S(27, 3) = S(27, 3)0 , where S(27, 3)0

= {{16, 26}, {13, 19}} ∪ {{24, 10}, {5, 14}} ∪ {{7, 15}, {22, 21}} ∪

{{25, 8}, {4, 17}} ∪ {{23, 12}, {6, 11}}

∪

{{20, 18}, {9, 2}} ∪ {{1, 27}, {28, 3}}

• S(3, 27) = S(3, 27)0 , where S(3, 27)0

= {{16, 19}, {13, 26}} ∪ {{24, 14}, {5, 10}} ∪ {{7, 21}, {22, 15}} ∪

{{25, 17}, {4, 8}} ∪ {{23, 11}, {6, 12}}

∪

{{20, 2}, {9, 18}} ∪ {{1, 3}, {28, 27}}

It can be verified that all of the starters in the following table are indeed two-quotient strong starters for F29 : S(β1 , β2 )

S(β2 , β1 )

S(−β1 , −β2 )

S(−β2 , −β1 )

S(2, 26) S(2, 10) S(3, 15) S(3, 12) S(8, 11) S(10, 14) S(10, 17)

S(26, 2) S(10, 2) S(15, 3) S(12, 3) S(11, 8) S(14, 10) S(17, 10)

S(27, 3) S(27, 19) S(26, 14) S(26, 17) S(21, 18) S(19, 15) S(19, 12)

S(3, 27) S(19, 27) S(14, 26) S(17, 26) S(18, 21) S(15, 19) S(12, 19)

As a second example, let F41 = Z41 , then k = 3, t = 5, ∆ = 4, ∆1 = 2 and α = 36. We have QR(41) = N QR(41) =

{1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40}, and {3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 29, 30, 34, 35, 38}. 11

Hence C0 = {10, 18, 16, 37, 1}, Cˆ0 = {31, 23, 25, 4, 40}, C1 = {32, 33, 2, 20, 36} and Cˆ1 = {9, 8, 39, 21, 5}. β1 = 3 then β2 = 12 ∈ β1 Cˆ0 = {11, 28, 34, 12, 38} is such that (β1 − 1)(β2 + 1) ∈ N QR(41) and (β1 + 1)(β2 − 1) ∈ N QR(41).Therefore S(3, 12) = S(3, 12)0 ∪ S(3, 12)1 , where S(3, 12)0 S(3, 12)1

=

{{10, 30}, {31, 38}} ∪ {{18, 13}, {23, 11}} ∪ {{16, 7}, {25, 28}}

∪

{{37, 29}, {4, 34}} ∪ {{1, 3}, {40, 12}}

=

{{32, 14}, {9, 15}} ∪ {{33, 17}, {8, 27}}, {{2, 6}, {39, 24}}

∪

{{20, 19}, {21, 35}} ∪ {{36, 26}, {5, 22}}

is a two-quotient strong starter for F41 . Moreover, by Corollary 4.8, we see that S(12, 3), S(38, 29) and S(29, 38) are two-quotient strong starters in F41 different from S(3, 12): • S(12, 3) = S(12, 3)0 ∪ S(12, 3)1 , where S(12, 3)0

= {{10, 38}, {31, 30}} ∪ {{18, 11}, {23, 13}} ∪ {{16, 28}, {25, 7}} ∪

S(12, 3)1

{{37, 34}, {4, 29}} ∪ {{1, 12}, {40, 3}}

= {{32, 15}, {9, 14}} ∪ {{33, 27}, {8, 17}} ∪ {{2, 24}, {39, 6}} ∪

{{20, 35}, {21, 19}} ∪ {{36, 22}, {5, 26}}

• S(38, 29) = S(38, 29)0 ∪ S(38, 29)1 , where S(38, 29)0 S(38, 29)1

=

{{10, 11}, {31, 3}} ∪ {{18, 28}, {23, 30}} ∪ {{16, 34}, {25, 13}}

∪

{{37, 12}, {4, 7}} ∪ {{1, 38}, {40, 29}}

=

{{32, 27}, {9, 26}} ∪ {{33, 24}, {8, 14}} ∪ {{2, 35}, {39, 17}}

∪

{{20, 22}, {21, 6}} ∪ {{36, 15}, {5, 19}}

12

• S(29, 38) = S(29, 38)0 ∪ S(29, 38)1 , where S(28, 39)0 S(28, 39)1

=

{{10, 3}, {31, 11}} ∪ {{18, 30}, {23, 28}} ∪ {{16, 13}, {25, 34}}

∪

{{37, 7}, {4, 12}} ∪ {{1, 29}, {40, 38}}

=

{{32, 26}, {9, 27}} ∪ {{33, 14}, {8, 24}} ∪ {{2, 17}, {39, 35}}

∪

{{20, 6}, {21, 22}} ∪ {{36, 19}, {5, 15}}

It can be verified that all of the starters in the following table are indeed two-quotient strong starters for F41 : S(β1 , β2 )

S(β2 , β1 )

S(−β1 , −β2 )

S(−β2 , −β1 )

S(3, 12) S(3, 28) S(14, 24) S(14, 22)

S(12, 3) S(28, 3) S(24, 14) S(22, 14)

S(38, 29) S(38, 13) S(27, 17) S(27, 19)

S(29, 38) S(13, 38) S(17, 27) S(19, 27)

Acknowledgment

The authors thank the referee for many constructive suggestions to improve this paper. C. R. research supported in part by a CONACyT-M´exico Postdoctoral fellowship and in part by the National scholarship programme of the Slovak republic. C. A. and A.V. supported by SNI and CONACyT.

References [1] B. A. Anderson, A class of starter induced 1-factorizations, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Springer, Berlin, 1974, pp. 180–185. Lecture Notes in Math., Vol. 406. 13

[2] B. A. Anderson, P. J. Schellenberg and D. R. Stinson, The existence of Howell designs of even side, J. Combin. Theory Ser. A 36 (1984), no. 1, 23–55. [3] D. M. Burton, Elementary number theory, sixth ed., McGraw-Hill, 2007. [4] C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, 2nd ed., Discrete mathematics and its applications, Chapman & Hall/Taylor & Francis, 2007. [5] J. F. Dillon and R. A. Morris, A skew Room square of side 257, Utilitas Math. 4 (1973), 187–192 [6] J. H. Dinitz, Room n-cubes of low order, J. Austral. Math. Soc. Ser. A 36 (1984), 237–252. [7] J. H. Dinitz and P. Dukes, On the structure of uniform onefactorizations from starters in finite fields, Finite Fields Appl. 12 (2006), no. 2, 283–300. . [8] J. H. Dinitz and D. R. Stinson, The spectrum of Room cubes, European J. Combin. 2 (1981), no. 3, 221–230. [9] J. H. Dinitz and D. R. Stinson, Some new perfect one-factorizations from starters in finite fields, J. Graph Theory, 13 (1989), no. 4, 405– 415. [10] K. B. Gross, Some new classes of strong starters, Discrete Math. 12 (1975), no. 3, 225–243. [11] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, sixth ed., Oxford University Press, Oxford, 2008, Revised by D. R. Heath-Brown and J. H. Silverman, With a foreword by Andrew Wiles. [12] J. D. Horton, Room designs and one-factorizations, Aequationes Math. 12 (1981), no. 1, 56–63.

14

[13] J. D. Horton, The construction of Kotzig factorizations, Discrete Math. 43 (1983), no. 2-3, 199–206. [14] J. D. Horton, Orthogonal starters in finite abelian groups, Discrete Math. 79 (1990), no. 3, 265–278. [15] W. L. Kocay, D. R. Stinson and S. A. Vanstone, On strong starters in cyclic groups, Discrete Math. 56 (1985), no. 1, 45–60. [16] R. C. Mullin and E. Nemeth, An existence theorem for room squares, Canad. Math. Bull. 12 (1969), 493–497. [17] R. C. Mullin and E. Nemeth, On furnishing Room squares, J. Combinatorial Theory 7 (1969), 266–272. [18] D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman’s schoolgirl problem, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), Amer. Math. Soc., Providence, R.I. (1971), 187–203. [19] A. Rosa and S. A. Vanstone, On the existence of strong Kirkman cubes of order 39 and block size 3, Algorithms in combinatorial design theory, North-Holland Math. Stud., vol. 114, North-Holland, Amsterdam (1985), no. 1, 309–319. [20] R. G. Stanton and R.C. Mullin, Construction of Room squares, Ann. Math. Statist. 39 (1968), 1540–1548. [21] D. R. Stinson and S. A. Vanstone, A Kirkman square of order 51 and block size 3, Discrete Math. 55 (1985), no. 1, 107–111.

15