Construction Procedure for Non-trivial T-designs
John Chibayi^{1}, David Alila^{2}, Fredrick Onyango^{1}
^{1}Department of Statistics and Actuarial Science, MasenoUniverisity, Nairobi, Kenya
^{2}Department of Mathematics, MasindeMuliro University of Science and Technology, Nairobi, Kenya
Email address:
To cite this article:
John Chibayi, David Alila, Fredrick Onyango. Construction Procedure for Non-trivial T-designs. American Journal of Theoretical and Applied Statistics. Vol. 6, No. 1, 2016, pp. 52-60. doi: 10.11648/j.ajtas.20170601.17
Received: July 20, 2016; Accepted: August 8, 2016; Published: January 22 , 2017
Abstract: A t-design is a generation of balanced incomplete block design (BIBD) where λ is not restricted to the blocks in which a pair of treatments occurs but to the number of blocks in which any treatments (t = 2,3...) occurs. The problem of finding all parameters (t, v, k, λ_{t}) for which t-(v, k, λ_{t}) design exists is a long standing unsolved problem especially with λ=1 (Steiner System) as no Steiner t-designs are known for t ≥ 6 when v > k. The objective of this study therefore to develop new methods of constructing t-designs with t ≥ 3 and λ ≥ 1. In this study t-design is constructed by relating known BIB designs, combinatorial designs and algebraic structures with t-designs.
Keywords: Block Designs, Steiner Systems, T-designs
1. Introduction
design is an incidence structure of points and blocks with the following properties; there are points, each block is incident with points, any point is incident with blocks, and any points are incident to common blocks. Where and are all positive integers and . The four numbers and determine (blocks) and and four numbers themselves cannot be chosen arbitrarily. For a design and is any -element subset of , with , then the number of blocks containing is given by:
(1)
particular, . Since in equation above needs to be an integer, only the values of and that make an integer for all are admissible parameters for a design. A tuple is said to be admissible if the arithmetic conditions aforementioned hold and is said to be feasible if a design exists, hence a feasible tuple is necessarily admissible [2]. The converse is not true. That is, admissibility conditions are necessary but they are not sufficient, there exist several cases of parameters that satisfy the admissibility conditions and yet no design with these parameters exists. However, it is conjectured that admissibility conditions would be sufficient, if the point set is large. This is known as large existence conjecture or ''asymptotic existence''conjecture.
The incidence structure associated with a design can be represented by a matrix. The point-block incidence matrix , associated with a design with blocks is a matrix of rows and columns. The elements of are where is the point, is the block and
There is a generalization of Fisher's inequality to designs which is due to [1]. If a design exists, where is even, then the number of blocks . A design in which is called Steiner system. For example a is a Steiner triple system (STS) and a design is a Steiner quadruple system (SQS). A design is called a balanced incomplete block design (BIBD). A t-design is said to have repeated blocks if there are two blocks incident with the same set of k points. A t-design with no repeated blocks is said to be simple [6].
A design with are known for only a few values of and . For there are several infinite families known. For instance, for any prime power and for any , there exists a design known as inversive geometry. When , these designs are known as inversive planes. A Steiner quadruple system is also known to exist for all . Some simple designs, have been constructed for . Construction of a design remains one of the outstanding open problems in the study of t-designs. Even for and , only a few examples of designs are known. In this study we construct some designs, with much emphasis on t , by identifying BIB designs which are also designs.
2. Literature Review
The main problem in designs is the question of existence and the construction of those solutions, given admissible parameters. That is, finding all parameters for which design exists. There are many known Steiner designs but constructing Steiner it has proved to be much harder. Wilson (1972a,1972b) building upon the work of many including ([3], [7], [10], and [11]) proved for , fixed k and sufficiently large v satisfying arithmetic conditions designs exist. There is no similar existence result yet for . In the case of , [4] has shown thatthere is design if andonly if the necessary arithmetic conditions are satisfied. But for larger k, even , the result is far from complete. For the problem is wide open. All these constructions bear a distinct algebraic flavor in the sense that the underlying set upon which the design is constructed has a nice algebraic structure. Algebraic construction requires that a certain fixed (big) group to act as a group of automorphisms for the desired design. This technique was first formulated on paper by [11].
However this method culminates in a computer or computer-like brute-force search which cannot take us very far in quest for new designs (especially Steiner designs). Cameron et al. [5] simplified this method, by coming up with a technique that employs transitive actions of groups. They showed that, if a group acts transitively on subsets of size tthe orbits for that group yield designs.
Stinson [15] came up with block spreading method for and for prime power index. Let be a positive integer and let be a prime power. Suppose that there exists a design satisfying . Then there exists a group divisible design (GDD) of group type with block size and index one, whenever . This method has application in the construction of Steiner designs. Blanchard ([3], [7], [14]) generalizes Hartman's [14] results for as follows: (The ''block spreading'' method for and for prime power index). Let and be positive integers, , and let be a prime power. Then there exists a number such that for any design satisfying _{,} there is a GDD of group type with block size and index one whenever . More so, ([5], [8]) generalizes Blanchard's construction for general index (the ''block spreading'' method for and general index). Let and be a positive integers . Then there exists a number such that for any design with prime power decomposition satisfying ; ; there is a GDD of group type with block size and index one whenever . This generalized ''block spreading'' construction has several application such as constructing new Steiner designs and new group divisible designs with index one. Limitation of this method is that the bounds on are too large.
Magliveras et al. [9] constructed some new large sets of t-designs, using recursive construction described by Qiu-rong Wu [14]. Wu [14] showed that if there exists large sets , , ,), then there exists a large set . He went on to show that also, if there exist a large sets and then there exist large sets for all .
Mohácsy and Ray-Chaudhuri [12] constructed designs from known wise balanced designs. In his works he showed that, given a positive integer and a design , with all blocks-sizes occurring in and , the construction produces a design , with . Onyango [13] on his part constructed designs with and from balanced incomplete block design.
3. Construction of Some Designs with
The properties of designs include:
(2)
(3)
Replacing in equation (2) we have:
(4)
Now when we have:
(5)
This implies
(6)
Given that are all integers and is a rational number which we will represent by where are positive integers. Thus the equations (5) become:
and (7)
Case 1: When
Then (6) becomes: ,
,
Theorem 1: If , where is an integer then there are only three non- trivial designs which are:
Proof: From (2), (3), and (7)
(8)
This implies: and . For this design to be design and from (1) it implies
That is:
(9)
which is a positive integer. Expanding and simplifying equation (9), we obtain
(10)
The last term of equation (10), that is
(11)
will be an integer if . The only values for in which this is possible are 1 and 2. In this case Equation (11) is not an integer. Thus both Equations (10) and (11) will be integers if takes the values 2, 3, 5 and 11. The table below gives corresponding values of .
λ_{2} | k | λ_{1} | v | b |
2 | 3 | 3 | 4 | 4 |
3 | 4 | 7 | 8 | 14 |
5 | 6 | 21 | 22 | 77 |
11 | 12 | 111 | 112 | 1036 |
The required designs are; . A is trivial given , but it is required that , hence is not included and our proof is completed.
Case 2: When
In this case Equation (6) becomes
and
Where is a positive integer and both are divisible by .
From Equation (1) we get as follows;
,
and
(12)
Using for this design to be design then:
(13)
That is
(14)
which is a positive integer. Expanding and simplifying equation (14), we obtain
(15)
Equation (15) will be and integer ifthe last term is an integer. Thus can take any of the following values 3,4,6,8,10,18,28,32,38,58, and 118. But must be divisible by 2. So 3 is not a possibility. We give corresponding values of in the Table 2 below.
λ_{2} | k | λ_{1} | v | b |
4 | 3 | 10 | 6 | 20 |
6 | 4 | 26 | 14 | 91 |
8 | 5 | 50 | 26 | 260 |
10 | 6 | 82 | 42 | 574 |
18 | 10 | 290 | 146 | 4234 |
22 | 12 | 442 | 222 | 8177 |
28 | 15 | 730 | 366 | 17812 |
38 | 20 | 1370 | 686 | 46991 |
58 | 30 | 3250 | 1626 | 176150 |
118 | 60 | 13690 | 6846 | 1562029 |
Thefollowing designs can then be obtain from BIB designs given below
For , the possible values are: 6,9,15,18,21,33,39,60,69,81,123,165,249, and 501. The corresponding values of in the Table 3 below.
λ_{2} | k | λ_{1} | v | b |
6 | 3 | 21 | 8 | 56 |
9 | 4 | 57 | 20 | 285 |
15 | 6 | 183 | 62 | 1891 |
18 | 7 | 273 | 92 | 3588 |
21 | 8 | 381 | 128 | 6096 |
33 | 12 | 993 | 332 | 27473 |
39 | 14 | 1407 | 470 | 47235 |
60 | 21 | 3423 | 1142 | 186146 |
69 | 24 | 4557 | 1520 | 288610 |
81 | 28 | 6321 | 2108 | 475881 |
165 | 56 | 26733 | 8912 | 4254366 |
249 | 84 | 61257 | 20420 | 14891285 |
501 | 168 | 249501 | 83168 | 123514876 |
Again we obtain designs from BIB designs below:
For , and using similar arguments as before we obtain possible values of as follows:8,12,16,20,28,32,36,....which give the values of as follows:
λ_{2} | k | λ_{1} | v | b |
8 | 3 | 36 | 10 | 120 |
12 | 4 | 100 | 26 | 650 |
16 | 5 | 196 | 50 | 1960 |
20 | 6 | 324 | 82 | 4428 |
28 | 8 | 676 | 170 | 14365 |
32 | 9 | 900 | 226 | 22600 |
36 | 10 | 1156 | 290 | 33524 |
The desired designs are obtained from the following BIB designs:
Remark: this construction can go on and on by simply varying the values of for each case, but as values of increases the designs obtained have large parameters making them not practical.
4. Construction of Designs with t=3 and λ_{ t }≥1
We extend the work in [10] by constructing designs with , that is for general indexand Steiner designs. When and from Equation (2) we have:
and
(16)
Where is a rational number since are all positive integers hence, we will represent it by where are positive integers.
Case I,
Then Equation (15) becomes:
and (17)
For this design to be design and from ; it implies
(18)
That is,
(19)
Expanding and simplification of Equation (19)we obtain
(20)
Which will be an integer if divides . For , that is , the only possible values for in which this is possible are 1 and 2. Thus Equation (20) will be an integer if takes only of the following values; 2 and 5. The table below gives corresponding values of
λ_{2} | k | λ_{1} | v | b |
2 | 3 | 2 | 3 | 2 |
5 | 6 | 11 | 12 | 22 |
The first does not exist hence we have only one design in this case.
This is identified with this BIB design .
CASE II,
In this case Equation (17) becomes:
and (21)
Using similar argument as before:
Will be integer if Equation (22) is and integer
(22)
We give the corresponding values of in Table 6 below;
λ_{2} | k | λ_{1} | v | b |
4 | 3 | 6 | 4 | 8 |
6 | 4 | 14 | 8 | 28 |
10 | 6 | 42 | 22 | 154 |
14 | 8 | 86 | 44 | 473 |
22 | 12 | 222 | 112 | 2072 |
46 | 24 | 1014 | 508 | 21463 |
The following designs; can be obtained from designs given below:
For and using similar arguments as before we give the values of as in Table 7 below:
λ_{2} | k | λ_{1} | V | B |
6 | 3 | 12 | 5 | 20 |
12 | 5 | 57 | 20 | 228 |
15 | 6 | 93 | 32 | 496 |
27 | 10 | 327 | 110 | 3597 |
We get the desired designs from BIB designs below:
For and using the same methods we give the table of values of; as follows:
λ_{2} | k | λ_{1} | v | b |
8 | 3 | 20 | 6 | 40 |
12 | 4 | 52 | 14 | 182 |
16 | 5 | 100 | 26 | 520 |
20 | 6 | 168 | 42 | 1126 |
36 | 10 | 580 | 146 | 8468 |
44 | 12 | 884 | 222 | 16354 |
56 | 15 | 1460 | 366 | 35624 |
Similarly, for the values of we give them as in the Table 9 below:
λ_{2} | k | λ_{1} | v | b |
10 | 3 | 30 | 7 | 70 |
20 | 5 | 155 | 32 | 992 |
25 | 6 | 255 | 52 | 2210 |
30 | 7 | 380 | 77 | 4180 |
65 | 14 | 1955 | 392 | 54740 |
Now, for and applying the same methods, we give values of in table 10 below respectively.
λ_{2} | k | λ_{1} | v | b |
6 | 3 | 9 | 4 | 12 |
9 | 4 | 21 | 8 | 42 |
15 | 6 | 63 | 22 | 231 |
24 | 9 | 171 | 58 | 1102 |
51 | 18 | 819 | 274 | 12467 |
λ_{2} | k | λ_{1} | v | b |
12 | 3 | 30 | 6 | 60 |
18 | 4 | 78 | 14 | 273 |
24 | 5 | 150 | 26 | 780 |
30 | 6 | 246 | 42 | 1722 |
Also for and using similar arguments, we give values of in the Tables below respectively.
λ_{2} | k | λ_{1} | v | b |
4 | 3 | 4 | 3 | 4 |
6 | 4 | 8 | 5 | 10 |
10 | 6 | 22 | 12 | 44 |
22 | 12 | 112 | 57 | 532 |
The first design is trivial.
λ_{2} | k | λ_{1} | v | b |
12 | 4 | 28 | 8 | 56 |
20 | 6 | 84 | 22 | 308 |
28 | 8 | 172 | 44 | 946 |
λ_{2} | k | λ_{1} | v | b |
18 | 4 | 60 | 11 | 165 |
24 | 5 | 114 | 20 | 456 |
30 | 6 | 186 | 32 | 992 |
When and using similar methods the values of we give them in the tables below respectively.
λ_{2} | k | λ_{1} | v | b |
15 | 4 | 35 | 8 | 70 |
20 | 5 | 65 | 14 | 182 |
25 | 6 | 105 | 22 | 385 |
45 | 10 | 365 | 74 | 2701 |
λ_{2} | k | λ_{1} | v | b |
30 | 4 | 130 | 14 | 455 |
40 | 5 | 250 | 26 | 1300 |
50 | 6 | 410 | 42 | 2870 |
or we get the following tables respectively.
λ_{2} | k | λ_{1} | v | b |
15 | 6 | 33 | 12 | 66 |
24 | 9 | 87 | 30 | 290 |
51 | 18 | 411 | 138 | 3151 |
λ_{2} | k | λ_{1} | v | b |
18 | 4 | 42 | 8 | 84 |
30 | 6 | 126 | 22 | 462 |
42 | 8 | 258 | 44 | 1419 |
Also for we get the following table:
λ_{2} | k | λ_{1} | v | b |
21 | 4 | 49 | 8 | 98 |
35 | 6 | 147 | 22 | 539 |
42 | 7 | 217 | 32 | 992 |
Lastly, for we also get the following tables respectively.
λ_{2} | k | λ_{1} | v | b |
12 | 4 | 16 | 5 | 20 |
20 | 6 | 44 | 12 | 88 |
28 | 8 | 88 | 23 | 253 |
44 | 12 | 224 | 57 | 1064 |
λ_{2} | k | λ_{1} | v | b |
24 | 4 | 56 | 8 | 112 |
40 | 6 | 168 | 22 | 616 |
56 | 8 | 344 | 44 | 1892 |
88 | 12 | 888 | 112 | 8288 |
Case III,
Letting
and (23)
Where are positive integers and are divisible by and substituting these values of in:
We obtain as follows:
, and (24)
Using for this to be design then
That is Equation (24) is a positive integer
(25)
Expanding and simplifying Equation (24) we obtain
(26)
Under this case and using similar method we find exists if Equation (26) is an integer:
(27)
Taking in this case there is only one non-trivial and would take the values 5 or 35 with corresponding values of in the table below.
λ_{2} | k | λ_{1} | v | b |
5 | 3 | 5 | 3 | 5 |
35 | 15 | 230 | 93 | 1426 |
For , we get the following table:
λ_{2} | k | λ_{1} | v | b |
7 | 3 | 7 | 3 | 7 |
21 | 7 | 56 | 17 | 136 |
5. Construction of 4-(v,k,1) Designs
The same technique that has been used to construct is applied. When and , we have;
and (28)
Given are all integers, and is a rational number which we will represent by where are positive integers.
Case 1
Equation (28) becomes;
and (29)
Using Equation (29) and (30) we obtain
Which implies;
and (30)
For this design to be and from it means
Hence Equation (31) is a positive integer
(31)
Expanding Equation (31) we obtain
(32)
Equation (32) will be integer whenever Equation (33) is an integer
(33)
Using Equation (33), corresponding values of will be generated as shown in Table 12:
λ_{3} | λ_{2} | λ_{1} | k | v | b |
2 | 3 | 4 | 4 | 5 | 5 |
5 | 21 | 77 | 7 | 23 | 253 |
The first design is trivial. The is the only non trivial. This is then identified with the following BIB designs; and
Case 2,
In this case Equation (29) becomes
and (34)
For this design to be and from it means
Hence, equation (34) is a positive integer
(35)
Thus takes any of the following values 2 and 4. But must be greater than 2, hence 2 is not a possibility. We give corresponding values of in the table below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
4 | 10 | 20 | 4 | 7 | 35 |
This design is trivial. Hence, for there is no nontrivial design.
For , takes only 6 as its value. The corresponding values of are given in the table 26 below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
6 | 21 | 56 | 4 | 9 | 126 |
This design is trivial. Hence, also for there is no nontrivial design.
For , takes the values 8 and 28. The corresponding values of are given in the table below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
8 | 36 | 120 | 4 | 11 | 330 |
28 | 676 | 14365 | 9 | 171 | 272935 |
We obtain the desired designs from BIB designs below:
For and using similar arguments as before, the possible values of are as follows: which gives the values of as in the table below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
10 | 55 | 220 | 4 | 13 | 715 |
15 | 155 | 1240 | 5 | 33 | 8184 |
20 | 305 | 3782 | 6 | 63 | 39711 |
Case 3,
In this case Equation (28) can be rewritten as
, and ,(36)
Using Equation (28) we have
Which implies
(37)
For this design to be and from it means
That is Equation (38) is a positive integer
(38)
Using similar argument as before Equation (38) will be integer if Equation (39) is an integer
(39)
The corresponding values of is given in the table below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
3 | 6 | 10 | 4 | 6 | 15 |
This design is trivial. Hence, for there is no nontrivial design
Also for there is no non-trivial , the following table gives the corresponding values of .
λ_{3} | λ_{2} | λ_{1} | k | v | b |
5 | 6 | 35 | 4 | 8 | 70 |
In this case there is only one non- trivial . The following table gives the corresponding values of .
λ_{3} | λ_{2} | λ_{1} | k | v | b |
4 | 12 | 30 | 5 | 11 | 66 |
For equation (28) becomes
And the corresponding values of are as shown below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
4 | 10 | 20 | 4 | 7 | 35 |
6 | 26 | 91 | 5 | 15 | 273 |
8 | 50 | 260 | 6 | 27 | 1170 |
10 | 82 | 574 | 7 | 43 | 3526 |
22 | 442 | 8177 | 13 | 223 | 140267 |
For equation (3.4.3.2) becomes
In this case there is only one non- trivial . The following table gives the corresponding values of .
λ_{3} | λ_{2} | λ_{1} | k | v | b |
7 | 35 | 140 | 5 | 17 | 476 |
For equation (3.4.3.2) becomes
Also in this case, there is only one non- trivial . The following table gives the corresponding values of
λ_{3} | λ_{2} | λ_{1} | k | v | b |
40 | 1496 | 52547 | 17 | 563 | 1740233 |
For equation (3.4.3.2) becomes
And the corresponding values of are as shown below.
λ_{3} | λ_{2} | λ_{1} | k | v | b |
6 | 21 | 56 | 4 | 9 | 126 |
9 | 57 | 285 | 5 | 21 | 1197 |
15 | 183 | 1891 | 7 | 63 | 17019 |
6. Conclusion
In this study a new recursive technique has been developed for the construction of designs. Thus, the study has presented an alternative method that is simpler and unified for the construction of BIBDs that are very important in the experimental designs. As it provides designs for different values of , unlike many methods that provide designs for a single value of . More so, it provides both Steiner and non-Steiner designs.
Recommendations
Although this study has provided a technique for the construction of designs, it is still clear that construction method of designs is not known in general. In fact, it is not clear how one might construct designs with arbitrary block size. We therefore invite researchers to come up with ''additive theorems'' or this construction to make it general for any value of as this may bring in new techniques and ideas. There is also need for obtaining a theorem which would give all values of x and y for the case three in this construction in order to see new Steiner designs. Lastly, if there is a computer package that could be incorporated in the method to aid in calculations.
References