Title Cyclic resolvability of cyclic Steiner 2-designs( 本文(Fulltext) )
Author(s) GENMA, Masaki; MISHIMA, Miwako; JIMBO, Masakazu
Citation [Journal of Combinatorial Designs] vol.[5] no.[3] p.[177]-[187]
Issue Date 1997
Rights
Version 著者版 (author version) preprint
URL http://hdl.handle.net/20.500.12099/26306
Cyclic resolvability of cyclic Steiner 2-designs
Masaki Genma
Development Department II, Fujitsu Limited, Kanagawa, 222, Japan
Miwako Mishima and Masakazu Jimbo
Department of Electronics and Computer Engineering, Gifu University, Gifu, 501-11, Japan
Abstract
In this paper, direct and recursive constructions for a cyclically resolvable cyclic Steiner 2-design are given.
1
Introduction and preliminary results
Let V be a v-set and B be a collection of k-subsets of V . The elements of V and B are called points and blocks, respectively. A pair (V, B) is called a balanced incomplete
block (BIB) design, or a 2-design denoted by (v, k, λ)-BIB design, if every pair of distinct
elements of V is contained in precisely λ blocks of B. A BIB design with λ = 1 is called a Steiner 2-design.
For a BIB design (V, B), let σ be a permutation on V . For a block B = {b1, . . . , bk} ∈ B
and a permutation σ on V , let Bσ = {bσ
1, . . . , bσk}. If Bσ = {Bσ | B ∈ B} = B, then σ is
called an automorphism of (V, B). If there is an automorphism σ of order v = |V |, then the BIB design is said to be cyclic. For a cyclic (v, k, λ)-BIB design, the set of points V can be identified with Zv, the residue group of integers modulo v. In this case, the design
has an automorphism σ : i 7→ i + 1 (modv).
For a cyclic Steiner 2-design (V, B), let B = {b1, . . . , bk} be a block. The block orbit
containing B is defined by the set of distinct blocks
B + i = {b1+ i, . . . , bk+ i} (mod v)
for i ∈ Zv. If a block orbit has v blocks, then the block orbit is said to be full, otherwise
short. Choose an arbitrary block from each block orbit and call it a base block. A base
block is also referred to as a starter block or an initial block. The block orbit which contains the following block is called a regular short orbit
( 0,v k, 2v k , . . . , (k − 1)v k ) .
It is easy to show that a block orbit of a cyclic (v, k, 1)-BIB design must be full or the regular short orbit. In this case, it can be shown that a necessary condition for the existence of a cyclic (v, k, 1)-BIB design is that
A cyclic (v, k, 1)-BIB design with v ≡ 1 (modk(k − 1)) has no short orbit, while a cyclic (v, k, 1)-BIB design with v ≡ k (modk(k − 1)) has a single regular short orbit as well as full orbits. Now, we define a multiset ∆B = {bs− bt | s, t = 1, . . . , k; s 6= t} for a
base block B = {b1, . . . , bk}. Let {Bi | i ∈ I} be all base blocks full orbits of a cyclic
(v, k, 1)-BIB design, where I is a set of indices. Then
∪i∈I∆Bi = Zv\ {0} if v ≡ 1 (mod k(k − 1)), Zv\ n 0,v k, . . . , (k−1)v k o if v ≡ k (mod k(k − 1)) (1.1)
holds. In case of v ≡ 1 (modk(k − 1)), a family of base blocks F = {Bi | i ∈ I} is called
a (v, k, 1)-simple difference family (briefly (v, k, 1)-DF) in Zv.
A BIB design (V, B) is said to be resolvable if the collection of blocks B can be parti-tioned into classes R1, R2, . . . , Rr such that every point of V is contained in precisely one
block of each class. The classes Ri are called resolution classes and R= {R1, R2, . . . , Rr}
is called a resolution. For a resolution class Ri, let Rσi = {Bσ | B ∈ Ri}. If a resolvable
design has a non-trivial automorphism σ of order v = |V | which preserves the resolution, that is, ifRσ = {Rσ1, . . . , Rσr} =Rholds, then it is called cyclically resolvable with respect
to σ, or we say that it has a cyclic resolution with respect to σ. In this paper, we shall treat
a Steiner 2-design which is cyclic with respect to an automorphism σ : i 7→ i + 1 (modv) and which is also cyclically resolvable with respect to the same automorphism σ. We call such cyclic Steiner 2-designs cyclically resolvable cyclic Steiner 2-designs. For a cyclically resolvable cyclic (v, k, 1)-BIB design, we can define an orbit of resolution classes similar to the case of a block orbit.
For a resolvable (v, k, 1)-BIB design, clearly, the number of blocks in a resolution class must equal v/k, therefore k must divide v. A necessary condition for the existence of a resolvable cyclic (v, k, 1)-BIB design is
v ≡ k (mod k(k − 1)). (1.2)
Example 1.1 Here is an example of a cyclically resolvable cyclic (21, 3, 1)-BIB design. In this example, we have {1, 4, 16}, {19, 20, 3}, {1, 11, 19} and {0, 7, 14} as base blocks.
R0: { 1, 4, 16} { 8, 11, 2} {15, 18, 9} {19, 20, 3} { 5, 6, 10} {12, 13, 17} { 0, 7, 14} R1: { 2, 5, 17} { 9, 12, 3} {16, 19, 10} {20, 0, 4} { 6, 7, 11} {13, 14, 18} { 1, 8, 15} R2: { 3, 6, 18} {10, 13, 4} {17, 20, 11} { 0, 1, 5} { 7, 8, 12} {14, 15, 19} { 2, 9, 16} R3: { 4, 7, 19} {11, 14, 5} {18, 0, 12} { 1, 2, 6} { 8, 9, 13} {15, 16, 20} { 3, 10, 17} R4: { 5, 8, 20} {12, 15, 6} {19, 1, 13} { 2, 3, 7} { 9, 10, 14} {16, 17, 0} { 4, 11, 18} R5: { 6, 9, 0} {13, 16, 7} {20, 2, 14} { 3, 4, 8} {10, 11, 15} {17, 18, 1} { 5, 12, 19} R6: { 7, 10, 1} {14, 17, 8} { 0, 3, 15} { 4, 5, 9} {11, 12, 16} {18, 19, 2} { 6, 13, 20} R0 0: { 1, 11, 9} { 4, 14, 12} { 7, 17, 15} {10, 20, 18} {13, 2, 0} {16, 5, 3} {19, 8, 6} R0 1: { 2, 12, 10} { 5, 15, 13} { 8, 18, 16} {11, 0, 19} {14, 3, 1} {17, 6, 4} {20, 9, 7} R0 2: { 3, 13, 11} { 6, 16, 14} { 9, 19, 17} {12, 1, 20} {15, 4, 2} {18, 7, 5} { 0, 10, 8}
Each rectangle implies an orbit of a base block, that is, there are three full orbits and one regular short orbit. Each row implies a resolution class and it is easy to see that
{R0, . . . , R6} is one orbit of resolution classes and {R00, R01, R02} is another orbit.
In connection with a cyclic BIB design, a (v, k, 1)-BIB design is said to be 1-rotational if it has an automorphism of order v − 1 with one fixed point. Some constructions for a cyclically resolvable 1-rotational BIB design are known. For example, the relation between points and lines of an affine geometry derived from a finite field forms a cyclically resolvable 1-rotational BIB design. Jimbo and Vanstone [10] gave a recursive construction for cyclically resolvable 1-rotational Steiner 2-designs. Recently, Anderson and Finizio [1] considered constructions of cyclically resolvable 1-rotational (v, 4, 1)-BIB designs. But as far as the authors know, no constructions for cyclically resolvable cyclic BIB designs are available.
In Section 2, we shall derive a necessary condition for the existence of a cyclically resolvable cyclic (kv, k, 1)-BIB design when v is a prime. Furthermore, a direct construc-tion for a cyclically resolvable cyclic Steiner 2-design is given. In Secconstruc-tion 3, a recursive construction for a cyclically resolvable cyclic Steiner 2-design is given.
2
A direct construction
In this section, we consider the existence problem of a cyclically resolvable cyclic (kv, k, 1)-BIB design in the case when v is a prime. Firstly, we present a necessary condition for the existence of such designs.
Theorem 2.1 When v is a prime, if a cyclically resolvable cyclic (kv, k, 1)-BIB design
exists, then v ≡ 1 (modk(k − 1)) holds.
Proof. A cyclically resolvable cyclic (kv, k, 1)-BIB design has one regular short orbit D = {D + i | i = 0, . . . , v − 1}, where D = {0, v, 2v, . . . , (k − 1)v}, while the other orbits
are all full. Let R be a resolution class which contains D. Then there are the following two cases for R since v is a prime:
(i) R contains all blocks of D,
(ii) R does not contain any blocks of D except for D.
In case of (i), let R0 be a resolution class different from R. Let t be the minimum
positive integer which satisfies R0 + t = R0. Then t | kv must hold. Furthermore the
number of blocks in R0 which belongs to the same orbit is kv/t. There are v blocks in
R0. Thus the number of blocks v in R0 is divisible by kv/t, that is, k | t holds. Hence
we have t = k or t = kv since v is a prime. In case of t = kv, we need at least v base blocks of full orbits, which is impossible since the number of base blocks of full orbits is (v − 1)/(k − 1). Thus t = k must hold for all resolution classes except for R. Let R0 be
any resolution class with t = k. Then it is easy to show that R0 can be represented by a
block B = {b0, . . . , bk−1} as follows:
R0 = {B + ki (mod kv) | i ∈ Z
Thus we have bj 6≡ bj0 (modk) for j 6= j0. That is, no multiple of k is contained in ∆B. Thus we can not construct a cyclic BIB design only by using these base blocks B and D. In case of (ii), note that the number of resolution classes which contain one block of
D is v. Each of these resolution classes has v − 1 blocks whose orbits are full. Thus, v − 1 ≡ 0 (modk). On the other hand, kv ≡ k (modk(k − 1)) holds by (1.2), that is,
v ≡ 1 (modk − 1). Hence we have v ≡ 1 (modk(k − 1)). 2
Before stating about a direct construction, we review the concept of radical difference
family (RDF), which is used in the construction. It was introduced by Buratti [5] as a
particular class of simple difference family.
Let k be an odd integer and v ≡ 1 (modk(k − 1)) be a prime. We denote by H the multiplicative group of Zv = GF (v). A (v, k, 1)-DF F = {Bi | i ∈ I} is said to be radical
if each base block is a coset of the k-th roots of unity in H.
Now, we shall construct a cyclically resolvable cyclic Steiner 2-design by using a kind of difference method similar to that of Wilson [13] and Buratti [5].
Theorem 2.2 If there exists a (v, k, 1)-radical difference family with v prime and k odd,
then there exists a cyclically resolvable cyclic (kv, k, 1)-BIB design.
Proof. Let k = 2m+1 and v = nk(k−1)+1. Let α be a primitive element of GF (v) = Zv.
It is easy to show that there exists an element ¯α in Zkv such that ¯α ≡ 1 (modk) and
¯
α ≡ α (modv) since v and k are relatively prime. Let ε = ¯α2mn in Z
kv, then ε is a
primitive k-th root of unity in GF (v) since ¯α ≡ α (modv) holds and α2mn is a primitive
k-th root of unity in GF (v).
Let F = {Aj ≡ αjH2mn (modv) | j ∈ I} be a (v, k, 1)-radical difference family
in Zv, where H2mn = {ε0, ε1, . . . , εk−1} (modkv) and where I is a suitable subset of
{0, 1, . . . , 2mn − 1}. Note that, in Zv, H2mn is the group of 2mn-th powers. Then
∪j∈I∆Aj = Zv \ {0} holds by (1.1). For a base block Aj ≡ αjH2mn, let ¯Aj ≡ ¯αjH2mn
in Zkv. Then we can show that ∪j∈I∆ ¯Aj = {k, 2k, . . . , (v − 1)k} (modkv) holds since
ε = ¯α2mn ≡ 1 (modk) holds.
Next, we construct the following 2mn base blocks:
Bi = {¯αi+ 0v, ε¯αi+ 1v, . . . , ε2mα¯i+ 2mv} (mod kv)
for i = 0, 1, . . . , 2mn − 1. We shall show that every element of
[Zkv\ {0, k, . . . , (v − 1)k}] \ {0, v, . . . , (k − 1)v} (2.1)
occurs exactly once in ∪2mn−1
i=0 ∆Bi. Now
∆Bi= {¯αi(εs− εt) + (s − t)v | s, t = 0, 1, . . . , 2m; s 6= t}
= {¯αi(εa− 1)εb+ av | a = 1, 2, . . . , 2m; b = 0, 1, . . . , 2m}
holds. Letting f (i, a, b) = ¯αi(εa− 1)εb + av, we can show the following with respect to
(i) k | (εa− 1) and k - av hold since gcd(v, k) = 1. Thus f (i, a, b) 6∈ {0, k, . . . , (v − 1)k}.
Furthermore, v -α¯i(εa−1)εb holds since εa6≡ 1 (modv) and v is a prime. Thus f (i, a, b) 6∈
{0, v, . . . , (k − 1)v}.
(ii) In case of a 6= a0, f (i, a, b) 6= f (i0, a0, b0) (modk) holds since ε ≡ 1 (modk) and
gcd(v, k) = 1.
(iii) In case of a = a0, assume that f (i, a, b) = f (i0, a, b0) (modkv) holds. Then we have
¯
αiεb = ¯αi0
εb0
(modv) since εa 6≡ 1 (modv). Hence, i = i0 and b = b0 must hold. Thus if
(i, a, b) 6= (i0, a0, b0), then f (i, a, b) 6= f (i0, a0, b0) (modkv).
There are 2mnk(k − 1) number of ways to choose i, a and b, which coincides with the number of elements in (2.1). Thus each element of (2.1) occurs exactly once among
f (i, a, b)’s.
Hence the base blocks ¯Aj’s and Bi’s generate a cyclic (kv, k, 1)-BIB design (Zkv, B)
together with the base block D = {0, v, . . . , (k − 1)v} of the regular short orbit.
It remains to show that the design is cyclically resolvable. Let ¯I = {0, 1, . . . , 2mn −
1} \ I and
R0 = { ¯Aj+ lv, Bi+ lv (mod kv) | j ∈ I; i ∈ ¯I; l = 0, . . . , k − 1} ∪ {D}.
The number of blocks contained in R0 is nk + (2mn − n)k + 1 = v. Then for any j ∈ I and i ∈ ¯I, ¯Aj ∩ Bi = φ holds and neither ¯Aj nor Bi contain 0. It is also obvious that
¯
Aj ∩ ¯Aj0 = φ and Bi∩ Bi0 = φ hold. Thus we have
(∪j∈IA¯j) ∪ (∪i∈ ¯IBi) = Zv\ {0} (mod v).
Hence, among the blocks ¯Aj + lv (modkv) and Bi+ lv (modkv), every element of Zkv\
{0, v, . . . , (k − 1)v} occurs exactly once, which implies that every element of Zkv occurs
exactly once in R0. Let Rh = R0+ h (modkv) for h ∈ Zv. Then Rh’s are also resolution
classes and these classes are mutually disjoint. Note that every block developed from the base block ¯Aj (j ∈ I) or Bi (i ∈ ¯I) is contained in one of Rh’s.
Further, let
R0
j0 = {Bj+ hk (mod kv) | h ∈ Zv}
for j ∈ I. Note that
Bj = {¯αj + 0v, ε¯αj+ v, . . . , ε2mα¯j + 2mv}
≡ {¯αj + 0v, ¯αj+ v, . . . , ¯αj + (k − 1)v}
≡ {0, 1, . . . , k − 1} (mod k)
holds since gcd(k, v) = 1 and ε ≡ 1 (modk). Then we can show that every point of Zkv
occurs exactly once in R0
j0. Thus by adding 0, 1, . . . , k − 1 to each R0j0, we can obtain nk
resolution classes
R0
jl= R0j0+ l (mod kv)
for j ∈ I; l = 0, 1, . . . , k − 1. These resolution classes Rh and R0jl partition the set of all
Example 2.3 We shall construct a cyclically resolvable cyclic (21, 3, 1)-BIB design of Example 1.1 according to the construction in the proof of Theorem 2.2. In this case,
v = 7, k = 3, n = 1 and m = 1. Let α = 5, then ¯α = 19, ε = 4 in Z21 and we can choose {1, 4, 2} in Z7 as a base block of a (7, 3, 1)-RDF. The following base blocks form a cyclically resolvable cyclic (21, 3, 1)-BIB design:
¯
A0= { 1, 4, 16},
B0= { 1, 11, 9},
B1= { 19, 20, 3},
D = { 0, 7, 14}.
Resolution classes are constructed as follows:
R0 = { ¯A0, ¯A0+ v, ¯A0+ 2v, B1, B1+ v, B1+ 2v, D} (mod kv) R1 = R0+ 1, R2 = R0+ 2, ... R6 = R0+ 6. R000= {B0, B0+ k, B0+ 2k, . . . , B0+ 6k} (mod kv) R0 01= R000+ 1, R0 02= R000+ 2. In Example 1.1 R0
00, R001 and R002 are denoted by R00, R01 and R02 respectively. Then a cyclically resolvable cyclic (21, 3, 1)-BIB design is constructed as in Example 1.1.
In connection with the assumption of Theorem 2.2, Buratti [5] gave the following theorem with respect to the existence of a (v, k, 1)-RDF, which is an improved version of Wilson’s theorem [13].
Theorem 2.4 (Buratti [5, Theorem 10]) Let k = 2m + 1, let v = nk(k − 1) + 1 be a
prime, let ε be a primitive k-th root of unity in Zv and let S = {ε − 1, . . . , εm − 1}. A
sufficient condition for the existence of a (v, k, 1)-RDF in Zv is that there exists a chain
of divisors of mn of the form
d0 = 1 | d1 | d2 | · · · | d2τ | d2τ +1= mn such that n = Y 0≤t≤τ d2t+1 d2t hence m = d2τ +1 n = Y 0≤t≤τ d2t d2t−1 , Φ(S) ⊂ [ 0≤t≤τ (Hd2t−1\Hd2t) ∪ {1},
where Φ(S) = {xy−1 | x, y ∈ S} and Hd is the group of d-th powers of Z v.
Remark. Buratti [5] stated Theorem 2.4 also for the case of v prime power. We however
restrict only for the case of v prime since the resulting design is cyclic only in that case. Further, he also showed the similar result for k even, which cannot be used as a “seed design” in Theorem 2.2.
In the proof of Theorem 2.4, Buratti [5] gave the explicit form of base blocks of a (v, k, 1)-RDF as follows : F = {αjH2mn | j ∈ I} (mod v), (2.2) where I = ( τ X t=0 d2tit| 0 ≤ it< d2t+1 d2t , t = 0, 1, . . . τ ) .
Using the result of Buratti [5] and Theorem 2.2, we have the following corollary. Corollary 2.5 Under the same assumption as Theorem 2.4, the base blocks in (2.2)
generate a cyclically resolvable cyclic (kv, k, 1)-BIB design.
In case of k = 3, the following can be obtained since m = 1 in Theorem 2.2.
Corollary 2.6 Let v be a prime such that v ≡ 1 (mod6). Then there exists a cyclically
resolvable cyclic (3v, 3, 1)-BIB design.
Furthermore, in case of k = 5, we can obtain the following by using the condition for the existence of a (v, 5, 1)-RDF (see Buratti [4, Theorem 2.1]).
Corollary 2.7 Let v be a prime such that v ≡ 1 (mod20) and (11 + 5√5)/2 is not a
2e+1-th power (modv) where 2e is the highest power of 2 in (v − 1)/20. Then there exists
a cyclically resolvable cyclic (5v, 5, 1)-BIB design.
3
A recursive construction
In this section, a recursive construction for a cyclically resolvable cyclic Steiner 2-design is given.
A (u, t, λ)-difference matrix Σ = (σij) is defined to be a t×λu matrix whose entries are
elements of Zu such that, among the differences of the corresponding elements of any two
rows, each element of Zu occurs exactly λ times. Note that the property of the difference
matrix is conserved even if we add a constant to any columns or any rows. Thus, without loss of generality, we assume that σ0j = σi0 = 0 for any i and j. Then every row contains
each element of Zu exactly λ times except for the 0-th row. A difference matrix is also
referred to as a row difference scheme in Jimbo and Kuriki [8].
For a construction of cyclic BIB designs, the notion of ‘difference matrix’ is useful (see Jimbo and Kuriki [8], Jimbo [9], Colbourn and Colbourn [6], Grannel and Griggs [7], Jungnikel [11], [12]). Here we shall show that the notion of ‘difference matrix’ is also effective for the construction of a cyclically resolvable cyclic BIB design.
For a cyclically resolvable cyclic (kv, k, 1)-BIB design (Zkv, B), let D = {0, v, . . . , (k −
1)v} and let D = {D + i (modkv) | i = 0, 1, . . . , v − 1}. Note that the cyclically resolvable cyclic (kv, k, 1)-BIB design constructed in Theorem 2.2 has the following properties (P1) and (P2):
(P1) The resolution class containing D does not contain any other blocks of D.
(P2) Let R be any resolution class which does not contain blocks of D. Then the minimum positive number t satisfying R + t = R is k.
In the sequel, we restrict our attention only to the cyclically resolvable cyclic Steiner 2-design with properties (P1) and (P2).
Lemma 3.1 For a cyclically resolvable cyclic (kv, k, 1)-BIB design with Properties (P1)
and (P2),
v ≡ 1 (mod k(k − 1)) holds.
Proof. There are v blocks in a resolution class. The resolution class containning D has v − 1 blocks except for D. These v − 1 blocks can be partitioned into classes with k blocks
each, according with the orbits in which these blocks belong. Thus, k|(v − 1) holds. On the other hand, since kv ≡ k(mod k(k − 1)), we have (k − 1)|(v − 1), which implies that
k(k − 1)|(v − 1) holds. 2.
We shall construct a cyclically resolvable cyclic Steiner 2-design from two cyclically resolvable cyclic Steiner 2-designs by using a difference matrix.
Theorem 3.2 If there are
(i) a cyclically resolvable cyclic (kv, k, 1)-BIB design with properties (P1) and (P2), (ii) a cyclically resolvable cyclic (ku, k, 1)-BIB design with properties (P1) and (P2)
and
(iii) a (u, k + 1, 1) difference matrix,
then there exists a cyclically resolvable cyclic (kuv, k, 1)-BIB design with properties (P1) and (P2).
Proof. Let v = nk(k − 1) + 1 and u = n0k(k − 1) + 1. Further let Σ = (σ
st) (s =
0, 1, . . . , k, t = 0, 1, . . . , u − 1) be a (u, k + 1, 1)-difference matrix. We assume that the 0-th row is all-zero. We delete the 0-th row of Σ and denote it by Σ0 = (σ
st) (s = 1, . . . , k, t =
0, 1, . . . , u − 1). Then every element of Zu occurs exactly once in each row of Σ0.
Let {P0, . . . , Pv−1, P000 , P010 , . . . , Pn−1 k−10 } be a resolution of the cyclically resolvable
cyclic (kv, k, 1)-BIB design with (P1) and (P2) such that
P0= {Ai+ lv (mod kv) | i = 0, . . . , n(k − 1) − 1; l = 0, 1, . . . , k − 1} ∪ {D},
Pj00 = {A0j + hk (mod kv) | h ∈ Zv} (j = 0, 1, . . . , n − 1),
where Ai, A0j are base blocks of full orbits and D is a base block of the regular short orbit.
Now, for a base block of a full orbit Ai = {ai1, ai2, . . . , aik} of this design, construct the
following u base blocks:
for t = 0, 1, . . . , u − 1. Similarly we define A0(t)j for each base block A0 j.
Furthermore, let {Q0, . . . , Qu−1, Q000, Q001, . . . , Q0n0−1 k−1} be a resolution of the cycli-cally resolvable cyclic (ku, k, 1)-BIB design such that
Q0= {Bi+ lu (mod ku) | i = 0, . . . , n0(k − 1) − 1; l = 0, 1, . . . , k − 1} ∪ {D0},
Q0
j0= {Bj0 + hk (mod ku) | h ∈ Zu} (j = 0, 1, . . . , n0− 1),
where Bi, Bj0 are base blocks of full orbits and D0 is a base block of the regular short orbit.
Now, for a base block of a full orbit Bi = {bi1, bi2, . . . , bik} of this design, let
vBi = {vbi1, vbi2, . . . , vbik} (mod kuv)
be also a base block of the desired design and similarly let vB0
j’s and vD0 be also base
blocks of the design.
Then it is known that the blocks developed from the base blocks A(t)i , A0(t)j , vBi, vBj0
and vD0 construct a cyclic (kuv, k, 1)-BIB design (see Jimbo and Kuriki [8]).
In the sequel, we shall now construct resolution classes for this cyclic (kuv, k, 1)-BIB design. The classes can be classified into three types.
I) The resolution classes of the first type are constructed as follows. Let
R0= { A(t)i + luv (mod kuv) | t = 0, 1, . . . , u − 1;
i = 0, 1, . . . , n(k − 1) − 1; l = 0, 1, . . . , k − 1} ∪ vQ0.
Then the number of blocks contained in R0 is uk(k − 1)n + u = uv. We show that every point of Zkuv occurs in R0. Since Q0 is a resolution class of the (ku, k, 1)-BIB design, every point of {0, v, . . . , (ku − 1)v} is contained in vQ0. Now we shall show the following:
{A(t)i (mod uv) | t = 0, 1, . . . , u − 1; i = 0, 1, . . . , n(k − 1) − 1} = Zuv\ {0, v, . . . , (u − 1)v}.
(3.1) Let A(t)i = {a(t)is | s = 1, 2, . . . , k} for t = 0, 1, . . . , u − 1 and for i = 0, 1, . . . , n(k − 1) − 1,
where a(t)is = a(0)is + σstkv (moduv).
(i) In case of i = i0, s = s0 and t 6= t0, it follows that σ
stkv 6≡ σst0kv (moduv), since
σst 6= σst0. Hence a(t)is 6≡ a(t 0)
is (moduv).
(ii) In case of i 6= i0 or s 6= s0, we have a(0)
is 6= a(0)i0s0. Hence, a(t)is 6≡ a(t 0)
i0s0 (modv) since
σstkv ≡ σs0t0kv (modv).
Thus, each element of Zuv\ {0, v, . . . , (u − 1)v} occurs exactly once among a(t)is’s in (i)
and (ii). Hence (3.1) holds, which implies that
{A(t)i + luv (mod kuv) | t = 0, 1, . . . , u − 1;
i = 0, 1, . . . , n(k − 1) − 1; l = 0, 1, . . . , k − 1}
= Zkuv \ {0, v, . . . , (ku − 1)v}
Therefore, every point of Zkuv occurs exactly once in R0. That is, R0 is a resolution class of the design. Thus we can obtain uv resolution classes
Rh = R0+ h (mod kuv)
for h = 0, 1, . . . , uv − 1.
II) The resolution classes of the second type are constructed as follows. Let
R0(ju+t)k = {A0(t)j + hk (mod kuv) | h = 0, 1, . . . , uv − 1} for t = 0, 1, . . . , u − 1 and j = 0, 1, . . . , n − 1. Since A0
j ≡ {0, 1, . . . , k − 1} (modk), A0(t)j ≡
{0, 1, . . . , k − 1} (modk) holds. Thus ∪B∈R0
(ju+t)kB = Zkuv for each t = 0, 1, . . . , u − 1 and
j = 0, 1, . . . , n − 1. Therefore we can obtain nuk resolution classes R0
(ju+t)k+l = R0(ju+t)k + l (mod kuv) for l = 0, 1, . . . , k − 1.
III) The resolution classes of the third type are constructed as follows. Let
R00
jk = {vBj0 + hk (mod kuv) | h = 0, 1, . . . , uv − 1}
for j = 0, 1, . . . , n0 − 1. Since B0
j ≡ {0, 1, . . . , k − 1} (modk) and v is relatively prime
to k, vB0
j ≡ {0, 1, . . . , k − 1} (modk) holds by Lemma 3.1. Thus ∪B∈R00
jkB = Zkuv for
j = 0, 1, . . . , n0− 1. Therefore we can obtain n0k resolution classes
R00jk+l = R00jk + l (mod kuv) for l = 0, 1, . . . , k − 1.
Thus a cyclically resolvable cyclic (kuv, k, 1)-BIB design is obtained. 2
In the construction given in Theorem 3.2, the existence of a difference matrix is as-sumed. There are two types of constructions for a difference matrix. Firstly, Colbourn and Colbourn [6] showed the following construction of a difference matrix.
Lemma 3.3 Let u and t be positive integers such that u is relatively prime to (t − 1)!.
Let σij = ij (modu) for i = 0, 1, . . . , t − 1 and j = 0, 1, . . . , u − 1. Then Σ = (σij) is a
(u, t, 1)-difference matrix. In particular, if u is a prime, there exists a (u, t, 1)-difference
matrix for any integer t(≤ u).
By virtue of Theorem 3.2 and Lemma 3.3, the following is obtained.
Corollary 3.4 Let ui ≡ 1 (modk(k − 1)) for i = 1, . . . , n and u2, u3, . . . , un be primes.
If there are cyclically resolvable cyclic (kui, k, 1)-BIB designs for any i, then there exists
a cyclically resolvable cyclic (ku1u2· · · un, k, 1)-BIB design with properties (P1) and (P2).
Corollary 3.5 Let u be prime such that u ≡ 1 (modk(k − 1)). Then the existence of
a cyclically resolvable cyclic (ku, k, 1)-BIB design implies the existence of a cyclically resolvable cyclic (kum, k, 1)-BIB design with properties (P1) and (P2) for any integer m.
The following corollaries are direct consequences of Corollaries 2.6, 2.7 and Theorem 3.2.
Corollary 3.6 Assume that ui’s are primes such that ui ≡ 1 (mod6) for i = 1, . . . , n.
Then there exists a cyclically resolvable cyclic (v, 3, 1)-BIB design with properties (P1) and (P2) for v = 3u1u2· · · un.
Corollary 3.7 Assume that ui’s are primes such that ui ≡ 1 (mod20) for i = 1, . . . , n.
Then there exists a cyclically resolvable cyclic (v, 5, 1)-BIB design with properties (P1) and (P2) for v = 5u1u2· · · un.
By Theorems 2.2, 3.2 and their corollaries, we can obtain infinite sequences of cyclically resolvable cyclic (kv, k, 1)-BIB designs. For k = 3, 5, 7, small values of v in which there exists a cyclically resolvable cyclic (kv, k, 1)-BIB design, by these theorems, are listed below: k = 3, v ≤ 100; v = 7, 13, 19, 31, 37, 43, 49, 91 k = 5, v ≤ 1000; v = 41, 61, 241, 281, 401, 421, 601, 641, 661, 701, 761, 821, 881 k = 7, v ≤ 1000; v = 337, 421, 463, 883. Acknowledgments
The authors would like to thank the referees for their valuable suggestions. In particular, it was pointed out by the referee that the previous version of Theorem 2.2 and Corollary 2.7 could be improved by using the notion of radical difference family.
References
[1] I. Anderson and N.J. Finizio, Cyclically Resolvable Designs and Triple Whist
Tour-naments, J. Combin. Designs 1 (1993), 347-358.
[2] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Bibliograpishes Institut, Zurich, 1985. (also printed in Cambridge Univ. Press, Cambridge, 1986).
[3] R.C. Bose, On the construction of balanced incomplete block designs, Ann. Eugenics. 9 (1939), 353-399.
[4] M. Buratti, Improving two theorems of Bose on difference families, J. Combin. De-signs 3 (1995), 15-24.
[5] M. Buratti, On simple radical difference families, J. Combin. Designs 3 (1995), 161-168.
[6] M.J. Colbourn and C.J. Colbourn, Recursive constructions for cyclic block designs, J. Statist. Plann. Inference 10 (1984), 97-103.
[7] M.J. Grannell and T.S. Griggs, Product constructions for cyclic block designs: Steiner
2-designs, J. Combin. Theory Ser. A 42 (1986), 179-183.
[8] M. Jimbo and S. Kuriki, On a composition of cyclic 2-designs, Discrete Math. 46 (1983), 249-255.
[9] M. Jimbo, Recursive constructions for cyclic BIB designs and their generalizations, Discrete Math. 116 (1983), 79-95
[10] M. Jimbo and S.A. Vanstone, Recursive constructions for resolvable and doubly
re-solvable 1-rotational Steiner 2-designs, Utilitas Math. 26 (1984), 46-61.
[11] D. Jungnickel, Composition theorems for difference families and regular planes, Dis-crete Math. 23 (1978), 151-158.
[12] D. Jungnickel, On difference matrices, resolvable transversal designs and generalized
Hadamard matrices, Math. Z. 167 (1979), 49-60.
[13] R.M. Wilson, Cyclotomy and difference families in elementary Abelian groups, J. Number Theory 4 (1972), 17-47.
