The Construction of Pairwise Additive Minimal BIB Designs with Asymptotic Results ()
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.