Orthogonal arrays of strength three from regular 3-wise balanced designs

Charles J. Colbourn Computer Science

University of Vermont Burlington, Vermont 05405

D. L. Kreher Mathematical Sciences

Michigan Technological University Houghton, Michigan 49931-1295

J. P. McSorley Dept. of Mathematics

Southern Illinois University Carbondale, Illinois

D. R. Stinson

Combinatorics and Optimization

University of Waterloo Waterloo, Ontario CANADA N2L 3G1

Abstract

The construction given in [4] is extended to obtain new infinite families of orthogonal arrays of strength 3. Regular 3-wise balanced designs play a central role in this construction.

1 Introduction

An orthogonal array of size N, with k constraints (or of degree k), s levels (or of order s), and strength t, denoted OA(N, k, s, t), is a k × N array with entries from a set of s ≥ 2 symbols, having the property that in every t × N submatrix, every t×1 column vector appears the same number λ = \frac{N}{s^{t}} times. The parameter λ is the index of the orthogonal array. An OA(N, k, s, t) is also denoted by OA_{λ}(t, k, s); in this notation, if t is omitted it is understood to be 2, and if λ is omitted it is understood to be 1. A parallel class in an OA_{λ}(t, k, s) is a set of s columns so that each row contains all s symbols within these s columns. A resolution of the orthogonal array is a partition of its columns into parallel classes, and an OA with such a resolution is termed resolvable. An OA_{λ}(t, k, n) is class-regular or regular if some group Γ of order n acts regularly on the symbols of the array. A class-regular OA_{λ}(t, k, n) is resolvable. See [1] for a brief survey on orthogonal arrays of strength at least 3.

In [4] a construction for orthogonal arrays of strength 3 is given that starts from resolvable 3-(v, k, λ) designs and uses 3-transitive groups. The conditions on the resolvable 3-design ingredient can be relaxed and a more general theorem can be stated using a resolvable set system (X, B) such that:

1. the number of blocks containing three points x, y, z ∈ X, x ≠ y ≠ z ≠ x, is a constant λ_{3} that does not depend on the choice of x, y, z;

2. the number of blocks containing two points x, y ∈ X but disjoint from a third point z ∈ X, x ≠ y ≠ z ≠ x, is a constant b_{2}^{1} that does not depend on the choice of x, y, z.

We allow (X, B) to contain blocks of any size, including 1, 2, 3 and |X|.

If x, y ∈ X, x ≠ y, then the number of blocks containing x and y is λ_{2} = b_{2}^{1} + λ_{3} independent of the choice of x and y. These set systems need not be balanced for points. For example, the set system

\begin{cases}\{1, 2, 3, 4\}, \{1, 2, ∞\}, \{1, 3, ∞\}, \{1, 4, ∞\}, \{2, 3, ∞\}, \{2, 4, ∞\}, \\ \{3, 4, ∞\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \end{cases}\}

has λ_{3} = 1, λ_{2} = 3, points 1, 2, 3, 4 each occur in 7 blocks, but ∞ in 6 blocks. If resolvability is required, then every point must occur in the same number λ_{1} = r of blocks. Kageyama [3] called a t-wise balanced design that is also i-balanced for each i < t a regular t-wise balanced design.

Theorem 1.1 (Kageyama [3]) Let (X, B) be a regular 3-wise balanced design with at most two distinct block sizes, k_{1}, k_{2}. Then the subdesigns

B_{k_{i}} = {B ∈ B : |B| = k_{i}}

are each 2-designs, i = 1, 2.

If λ_{3} ≠ 0, and the block size is constant, then such a design is a 3design. But these conditions are not necessary. For example, the edges of the complete graph K_{v} when v is even have λ_{3} = 0, λ_{2} = 1, and λ_{1} = v − 1. Furthermore K_{v} has a 1-factorization and so this set system is resolvable.

A 3-(v, K, Λ) design of width w is a pair (X, B) where X is a v-element set of points and B is a collection of subsets of X called blocks satisfying:

1. the size of every block is in K;

2. Λ = [λ_{1}, λ_{2}, λ_{3}] and every i-element subset is in λ_{i} blocks, i = 1, 2, 3 and

3. the blocks can be partitioned into λ_{1} resolution classes using no more than w blocks in any one class.

The revised theorem is then:

Theorem 1.2 Let G act 3-transitively on the (n + 1)-element set Ω and let m(n^{3} − n) be the order of G. If a 3-(v, K, Λ) design of width w exists such that n = (λ_{1} − λ_{3})/(λ_{2} − λ_{3}) − 2 with w ≤ n + 1 and λ_{3}(n + 1) ≤ λ_{2}, then a resolvable OA_{m(n−1)(λ_{2}−λ_{3})}(3, v, n + 1) also exists.

Proof: This is exactly the same as in the proof of Theorem 2.1 in [4]. Resolvability of the OA follows from the transitivity of the action of G (this was not pointed out in [4]). □

2 Applications of the Construction

As in [4] we apply Theorem 1.2 with sharply 3-transitive groups, so that n = q is a power of a prime, and m = 1.

Lemma 2.1 Let q be an odd prime power. Then there exists an OA_{q−1}(3, q+ 3, q + 1).

Proof: Set v = q +3. Then a 1-factorization of K_{v} is a 3-(v, {2}, [v −1, 1, 0]) design of width w = v/2 = (q + 3)/2. Then w − 1 ≤ q and (λ_{1} − λ_{3})/(λ_{2} − λ_{3}) − 2 = (v − 1 − 0)/(1 − 0) − 2 = v − 3 = q, and the result follows from Theorem 1.2. □

Theorem 2.2 For all x ≥ 2 there exists a 3-(4x, {2, 4, 2x}, [1+2(x−1)(2x− 1), 2x − 1, 1]) design of width 2(x − 1).

Proof: The construction is essentially the doubling construction for Steiner quadruple systems (see [2], for example). Let A and B be two disjoint sets of size 2x and let {a_{1}, a_{2}, …, a_{2x−1}} and {b_{1}, b_{2}, …, b_{2x−1}} be one factorizations of A and B respectively. Take as blocks

1. the sets A and B each of size 2x;

2. the x^{2} 4-element subsets in each of the 2x − 1 families: {α ∪ β : α ∈ a_{i}, β ∈ b_{i}}, for all i = 1, 2, …, 2x − 1; and

3. all the 2\binom{2x}{2} pairs that are either in A or in B each repeated x − 2 times.

Arrange the blocks into resolution classes with at most 2(x − 1) blocks each, to produce the required design. □

If we use P GL_{2}(q) and the 3-(v, K, Λ) designs constructed in Theorem 2.2 as ingredients to Theorem 1.2 then

q = \frac{(λ_{1} − λ_{3})}{(λ_{2} − λ_{3})} − 2
= \frac{(1 + 2(x − 1)(2x − 1) − 1)}{2(x − 1)} − 2
= 2x − 3.

Consequently, the following arrays are obtained.

Lemma 2.3 An OA_{q^{2}−1}(3, 2(q + 3), q + 1) exists for every odd prime power q.

Another way to construct 3-(v, K, Λ) designs is given next.

Theorem 2.4 If there exists an OA_{μ}(3, n, yw), then there exists a 3-(n, K, Λ) design of width w with

Λ = [μy^{3}w^{3}, μy^{3}w^{2}, μy^{3}w].

Proof: Let A be an OA_{μ}(3, n, v). We think of A as an n × μv^{3} array defined on symbol set X, |X| = yw. Partition X into subsets Y_{i}, i = 1, 2, …, w with each |Y_{i}| = y. We define a 3-(n, K, Λ) design of width w with wμv^{3} blocks, as follows: for i = 1, 2, …, w and each column j of A, define a block B_{i,j} = {h : A[h, j] ∈ Y_{i}}. Then ({1, …, n}, {B_{ij}}) is a 3-(n, K, Λ) design of width w with Λ = [μy^{3}w^{3}, μy^{3}w^{2}, μy^{3}w]. □

If D_{i} is a 3-(v, K_{i}, Λ_{i}) design of width w_{i}, for i = 1, 2, …, n then for natural numbers α_{i}, the union with repeated blocks ∪_{i=1}^{n}α_{i}D_{i} of α_{i} copies of D_{i}, 1, 2, …, n is a 3-(v, ∪_{i}K_{i}, ∑_{i} α_{i}Λ_{i}) design of width w = max_{i}w_{i}. We illustrate this idea next.

Theorem 2.5 Let q be a prime power and choose integers a, b, m ≥ 1 such that

1. q + 3 = m(a + b);

2. ma ≥ 4;

3. m(a + 2b) ≡ 0 (mod 4); and

4. (m(a + 2b) − 4)/4 ≡ 0 (mod b).

Then an OA\frac{(a + b)}{4b}(q − 1 + mb)(q − 1)(3, (\frac{a + 2b}{a + b}) (q + 3), q + 1) exists.

Proof: Let x = m(a + 2b)/4. Then x ≥ 2 is a positive integer and by Theorem 2.2 there is 3-(4x, {2, 4, 2x}, [1 + 2(x − 1)(2x − 1), 2x − 1, 1]) design D_{1} of width 2(x − 1). Also the edges of the complete graph K_{4x} (see the proof of Corollary 2.1) form a 3-(4x, {2}, [4x − 1, 1, 0]) design D_{2} of width w = 2x. Take one copy of D_{1} and \frac{a}{b}(x − 1) copies of D_{2} to form a

3- (4x, \{2, 4, 2x\}, [1 + \frac{(x − 1)(4(a + b)x − (a + 2b))}{b}, \frac{(x − 1)(a + 2b)}{b}, 1])

design D of width w = 2x. The conditions of Theorem 1.2 are satisfied. □

The main applications of Theorem 1.2 rest on finding suitable regular 3-wise balanced designs. We have illustrated in this section the applications of some easily constructed designs of this type, but expect that further constructions can lead to more existence results for orthogonal arrays.

Acknowledgments

The authors’ research is supported as follows: ARO grant DAAG55-98-1-0272 (Colbourn), NSA grant MDA904-97-1-0072 (Kreher) and NSA grant MDA904-96-1-0084 (Stinson).

References

[1] J. Bierbrauer and C.J. Colbourn, Orthogonal arrays of strength more than two, in: CRC Handbook of Combinatorial Designs, CRC Press, 1996, 179-184.

[2] A. Hartman and K.T. Phelps, Steiner quadruple systems, in: Contemporary Design Theory: A Collection of Surveys (J.H. Dinitz, D.R. Stinson; eds.) John Wiley & Sons, New York, 1992, 205-240.

[3] S. Kageyama, A property of t-wise balanced designs, Ars Combinatoria, 31, (1991), 237-238.

[4] D.L. Kreher, Orthogonal Arrays of Strength 3, Journal of Combinatorial Designs 4 (1996), 67-69.