Abstract

An asymptotic existence of balanced incomplete block (BIB) designs and pairwise balanced designs (PBD) has been discussed in [1] -[3] . On the other hand, the existence of additive BIB designs and pairwise additive BIB designs with and has been discussed with direct and recursive constructions in [4] -[8] . In this paper, an asymptotic existence of pairwise additive BIB designs is proved by use of Wilson’s theorem on PBD, and also for some and the exact existence of pairwise additive BIB designs with block size and is discussed.

Keywords:Incidence Matrix, Pairwise Balanced Design (PBD), Balanced Incomplete Block Design (BIBD), Additive BIB Design, Pairwise Additive BIB Design, Wilson’s Theorem

1. Introduction

A pairwise balanced design (PBD) of order with block sizes in a set is a system, where is a finite set (the point set) of cardinality and is a family of subsets (blocks) of such that 1) if, then and 2) every pair of distinct elements of occurs in blocks of [9] . This is denoted by. When, a is especially called a balanced incomplete block (BIB) design, where, each block contains different points and each point appears in different blocks [10] . This is denoted by or. It is well known that necessary conditions for the existence of a are

. (1.1)

Let be the incidence matrix of a BIB design, where or 0 for all and, according as the i-th point occurs in the j-th block or otherwise. Hence the incidence matrix satisfies the conditions: 1) for all, 2) for all, 3) for all. 

Let, where need not be an integer unlike other parameters. Further let. A set of is called pairwise additive BIB designs if corresponding incidence matrices  of the BIB design satisfy that is the incidence matrix of a BIBD() for any distinct. When, this is especially called additive BIB designs [6] [7] .

It is clear by the definition that the existence of pairwise additive implies the existence of pairwise additive for any. Hence, for given parameters, the larger is, the more difficult a construction problem of pairwise additive BIB designs is.

In pairwise additive, since a sum of any two incidence matrices yields a BIB design, it is seen [7] that

(1.2)

It follows from (1.2) that the existence of pairwise additive implies

Pairwise additive are said to be minimal if or according as is odd or even.

Some classes of pairwise additive are constructed in [4] -[8] . It is clear by the definition that. The purpose of this paper is to show that, for a given odd prime power and a given positive integer, the necessary conditions (1.1) for the existence of pairwise additive minimal are asymptotically sufficient on. In particular, for the existence of pairwise additive minimal, (1.1) is asymptotically sufficient, i.e., there are pairwise additive minimal for sufficiently larger, even if. Furthermore, as the exact existence, it is shown that there are 2 pairwise additive for any positive integer except possibly for 12 values.

2.

The existence of is reviewed along with necessary and asymptotically sufficient conditions.

Let be a set of positive integers and

Necessary conditions for the existence of a are known as follows.

Lemma 2.1 [2] Necessary conditions for the existence of a are

(2.1)

Wilson [3] proved the asymptotic existence as Theorem 2.2 below shows.

Theorem 2.2 The necessary conditions (2.1) for the existence of a are asymptotically sufficient.

For any set of positive integers and any positive integer, let denote the smallest integer such that there are for every integer satisfying (2.1). Then Theorem 2.2 states the existence of. On the other hand, some explicit bound for was provided as follows.

Lemma 2.3 [11] There are for all positive integers.

Especially, for a set being a set of prime powers of form, is shown as follows.

Lemma 2.4 ([12] Theorem 19.69) Let be a set of prime powers of form with a positive integer. Then there are for all positive integers, except possibly for

.

3. Construction by

In this section, a method of constructing pairwise additive BIB designs through is provided.

The following simple method is useful to construct pairwise additive BIB designs.

Lemma 3.1 The existence of a and pairwise additive for any implies the existence of pairwise additive.

Proof. Let be the and,. On the set, let a block set with all block size be formed by the pairwise additive for each. Then it follows that the

is the required BIB design.

For example, Lemma 3.1 yields the following.

Theorem 3.2 There are 4 pairwise additive for any integer.

Proof. It follows from the fact ([4] [6] ) that there are additive, 4 pairwise additive and additive. Hence Lemmas 2.3 and 3.1 can yield the required designs.

As the next case of block sizes, is considered. A concept of pairwise additive has been discussed as a compatibly nested minimal partition in [12] , which shows the existence of pairwise additive as follows.

Lemma 3.3 ([12] ; Theorem 22.12) Let be an odd prime power for a positive integer. Then there are pairwise additive.

Lemmas 2.4, 3.1 and 3.3 can produce the following.

Theorem 3.4 ([12] ; Theorem 22.13) There are 2 pairwise additive for all positive integers, except possibly for

.

Theorem 3.4 will be improved as in Theorem 6.7.

4. Some Class of Pairwise Additive

In this section, a necessary condition for the existence of pairwise additive being minimal is provided and then some classes of pairwise additive and (pairwise) additive are constructed.

Now (1.1) implies that necessary conditions for the existence of pairwise additive are

Furthermore, the following is given.

Theorem 4.1 When is an odd prime power, necessary conditions for the existence of pairwise additive are

(4.1)

Proof. Since and, when is an odd prime power, it is shown that either or. Hence implies.

When is an odd prime power, a class of pairwise additive is obtained as follows. This observation shows a generalization of Lemma 3.3.

Theorem 4.2 Let both and be odd prime powers for a positive integer. Then there are pairwise additive.

Proof. It can be shown that a development of the following initial blocks on yields incidence matrices of the required BIB design:

where is a primitive element of and.

Furthermore, the following is known to be provided by recursive constructions with affine resolvable BIB designs. This result will be used in the next section.

Theorem 4.3 [7] Let be an odd prime power. Then there are additive.

Especially, when, the further result is known.

Theorem 4.4 [8] There are additive B for any positive integer.

5. Asymptotic Existence of Pairwise Additive Minimal

In this section, when is an odd prime power, an asymptotic existence of pairwise additive is discussed, and it is shown that the necessary conditions (4.1) for the existence of pairwise additive are asymptotically sufficient for a given positive integer.

Dirichlet’s theorem on primes is useful for the present discussion.

Theorem 5.1 (Dirichlet) If, then a set of integers of the following form

contains infinitely many primes.

Now Theorem 5.1 yields the following.

Lemma 5.2 [13] For any positive even integer, there are primes and for which and.

In the proof of Lemma 5.2 (i.e., Lemma 3.4 in [13] ), primes and are obtained by using Theorem 5.1. Thus Lemma 5.2 implies the existence of sufficiently large primes and as follows.

Lemma 5.3 For a given odd prime power, there are primes and such that (a), (b)

, (c) and (d) for.

Proof. Let be an odd prime power. Then, for an even integer, Lemma 5.2 provides primes and

such that (a), (b) and. Hence it is seen that, and. 

Now let. Then

which imply (c) and (d).

Thus one of the main results of this paper is now obtained through conditions (a), (b), (c) and (d) given in Lemma 5.3.

Theorem 5.4 For a given odd prime power, (4.1) is a necessary and asymptotically sufficient condition for the existence of pairwise additive B.

Proof (sufficiency). Let and be primes as in Lemma 5.3 with. Then conditions (c) and (d) show that there are for sufficiently large satisfying (4.1), on account of Theorem 2.2. Conditions (a) and (b) show that there are pairwise additive, pairwise additive and additive, on account of Theorems 4.2 and 4.3. Hence the required designs can be obtained on account of Lemma 3.1.

Unfortunately, by use of Theorem 5.4 we cannot show the existence of pairwise additive for, since an additive means pairwise additive.

Next, for a given odd prime power and a given positive integer, even if, the existence of

pairwise additive is discussed for sufficiently large.

Lemma 5.5 For a given odd prime power and a given positive integer, there are primes and such that (a), (b) and (c).

Proof. Let be an odd prime power and be a positive integer. Then, for a positive integer, Lemma 5.2 provides primes p and q such that (a) p > q >, (b) and. Hence it is seen that and (c) holds.

Thus the following result is obtained through conditions (a), (b) and (c) as in Lemma 5.5.

Theorem 5.6 For a given odd prime power and a given positive integer, there are pairwise additive for sufficiently large.

Proof. Let and be primes as in Lemma 5.5. Then it follows from (c) that there are

for sufficiently large, on account of Theorem 2.2. Also Theorem 4.2 along with conditions (a) and (b) shows that there are pairwise additive and pairwise additive. Thus the required designs are obtained on account of Lemma 3.1.

6. Pairwise Additive

In this section, the existence of pairwise additive is discussed. At first it is shown that there are pairwise additive for sufficiently large, even if. Furthermore, the exact existence of 2 pairwise additive with is discussed by providing direct and recursive constructions of pairwise additive. Finally, it is shown that there are 2 pairwise additive for any except possibly for 12 values.

Three classes of pairwise additive are given as in Lemma 3.3 and Theorems 3.4 and 4.4. For, 15 is the smallest value of for which the existence of 2 pairwise additive is unknown in literature. Hence at first this case is individually considered here.

Lemma 6.1 There are 2 pairwise additive.

Proof. It can be shown that a development of the following initial blocks on with the index being fixed yields incidence matrices of the required BIB design:

with 15 elements. Here, in general.

Now, pairwise additive with sufficiently large are obtained as follows. This shows an extension of Theorem 5.4 with.

Theorem 6.2 For a given positive integer, even if, there are pairwise additive with sufficiently large.

Proof. Let be a positive integer satisfying. Then (pairwise) additive are constructed by Theorem 4.4, and there are primes and such that, and

, on account of Lemma 5.2. Furthermore, since and with, there are for sufficiently large, on account of Theorem 2.2. Hence pairwise additive for sufficiently large can be constructed by Lemma 3.1 with pairwise additive, pairwise additive

and additive.

Next, some recursive constructions of pairwise additive are provided. A combinatorial structure is here introduced. A transversal design, denoted by TD, is a triple such that 1) is a set of elements, 2) is a partition of into classes (groups), each of size, 3) is a family of k-subsets (blocks) of, 4) every unordered pair of elements from the same group is not contained in any block, and 5) every unordered pair of elements from other groups is contained in exactly blocks. When, we simply write, where [14] .

Since it is known [14] that the existence of a is equivalent to the existence of mutually orthogonal latin squares of order, the following result can be obtained, when.

Lemma 6.3 [14] There exists a for all except for and possibly for.

A method of construction is presented, similarly to a recursive construction given in [4] , by use of.

Theorem 6.4 The existence of pairwise additive, pairwise additive and a implies the existence of pairwise additive.

Proof. Let, , be block sets of pairwise additive and pairwise additive

respectively as

and let, and, denote an element which occurs in both the m-th block of a and the n-th group. Then it can be shown that the following incidence matrices yield the required pairwise additive BIB designs with elements denoted by for and:

where and.

Another recursive method is presented.

Theorem 6.5 The existence of pairwise additive, pairwise additive and a implies the existence of pairwise additive.

Proof. Let, , be a block set similarly to the proof of Theorem 6.4 and let, , be a block set of pairwise additive, where

with elements and. Also let, and, denote an element which occurs in both the m-th block of a and the n-th group. Then the following incidence matrices can yield the required pairwise additive BIB designs with elements denoted by for and, and:

where and.

Now 2 pairwise additive are more obtained.

Lemma 6.6 There are 2 pairwise additive for.

Proof. For, Theorem 6.5 with

provides the required BIB designs respectively, because 2 pairwise additive  and 2 pairwise additive are obtained by use of Theorems 3.4 and 4.4 and Lemma 6.1, and a is also obtained by Lemma 6.3.

Hence on account of Lemma 6.6, the following result can be obtained. This improves Theorem 3.4.

Theorem 6.7 There are 2 pairwise additive for any positive integer, except possibly for.

Unfortunately, we cannot clear such 12 values displayed in Theorem 6.7. Furthermore, the existence of 2 pairwise additive has not been known except for being and 15 in Theorem 4.4 and Lemma 6.1.

Remark. Since Theorem 4.2 can be valid for a given odd integer, Theorem 5.6 is extended for a given odd integer. On the other hand, when is an even prime power, an asymptotic existence of pairwise additive minimal is proved by some methods similar to Theorems 4.2, 4.3, 5.4 and 5.6. In particular, for, the complete existence of pairwise additive has been shown in [4] [5] . However, in general, the exact existence of pairwise additive minimal with (1.1) could not be shown in this paper.

References