Let us have g factors, at m_{1}, ..., m_{g} levels.
Strength 3 means that each of the m_{i}m_{j}m_{k}
combinations of symbols in columns i, j and k occurs equally often,
that is, N/m_{i}m_{j}m_{k} times.
This quotient must be an integer, and our assumption is that
N is not more than 100. This restricts the possible values of the
m_{i}.

If g=3 then the only possibility is the trivial design: for some constant m we take each combination of the symbols m times. So assume g > 3.

Let us say that we have a factors at two levels, b factors at three levels,
and c factors at four levels. Then we are left with the following
possibilities for the m_{i}:

N | m_{1}...m_{g} | existence |

8 | 2^{a} | a <= 4 (H) |

16 | 4 2^{a} | a <= 3 (M) |

16 | 2^{a} | a <= 8 (H) |

24 | 6 2^{a} | a <= 3 (M) |

24 | 3 2^{a} | a <= 4 |

24 | 2^{a} | a <= 12 (H) |

27 | 3^{b} | b <= 4 |

32 | 8 2^{a} | a <= 3 (M) |

32 | 4 4 2^{a} | a <= 4 (*) |

32 | 4 2^{a} | a <= 7 (M) |

32 | 2^{a} | a <= 16 (H) |

36 | 3 3 2 2 | (T) |

40 | 10 2^{a} | a <= 3 (M) |

40 | 5 2^{a} | a <= 6 (X) |

40 | 2^{a} | a <= 20 (H) |

48 | 12 2^{a} | a <= 3 (M) |

48 | 6 4 2^{a} | a <= 2 (O) |

48 | 6 2^{a} | a <= 7 (M) |

48 | 4 3 2^{a} | a <= 4 |

48 | 4 2^{a} | a <= 11 (M) |

48 | 3 2^{a} | a <= 9 |

48 | 2^{a} | a <= 24 (H) |

54 | 6 3^{b} | b <= 3 |

54 | 3^{b} | b <= 5 |

54 | 3^{b} 2 | b <= 5 |

56 | 14 2^{a} | a <= 3 (M) |

56 | 7 2^{a} | a <= 6 (X) |

56 | 2^{a} | a <= 28 (H) |

60 | 5 3 2 2 | (T) |

64 | 16 2^{a} | a <= 3 (M) |

64 | 8 4 2^{a} | a <= 4 |

64 | 8 2^{a} | a <= 7 (M) |

64 | 4^{c} | c <= 6 (L) |

64 | 4 4 4 4 4 2^{a} | a <= 2 (R) |

64 | 4 4 4 4 2^{a} | a <= 6 |

64 | 4 4 4 2^{a} | a <= 8 (R) |

64 | 4 4 2^{a} | a <= 12 (**) |

64 | 4 2^{a} | a <= 15 (M) |

64 | 2^{a} | a <= 32 (H) |

72 | 18 2^{a} | a <= 3 (M) |

72 | 9 2^{a} | a <= 6 (X) |

72 | 6 6 2^{a} | a <= 2 (O) |

72 | 6 3 2^{a} | a <= 4 (O') |

72 | 6 2^{a} | a <= 11 (M) |

72 | 4 3 3 2 | (T) |

72 | 3 3 2^{a} | ? |

72 | 3 2^{a} | ? |

72 | 2^{a} | a <= 36 (H) |

80 | 20 2^{a} | a <= 3 (M) |

80 | 10 4 2^{a} | a <= 2 (O) |

80 | 10 2^{a} | a <= 7 (M) |

80 | 5 4 2^{a} | ? |

80 | 5 2^{a} | ? |

80 | 4 2^{a} | a <= 19 (M) |

80 | 2^{a} | a <= 40 (H) |

81 | 9 3^{b} | b <= 4 (***) |

81 | 3^{b} | b <= 10 |

84 | 7 3 2 2 | (T) |

88 | 22 2^{a} | a <= 3 (M) |

88 | 11 2^{a} | a <= 6 (X) |

88 | 2^{a} | a <= 44 (H) |

90 | 5 3 3 2 | (T) |

96 | 24 2^{a} | a <= 3 (M) |

96 | 12 4 2^{a} | a <= 4 |

96 | 12 2^{a} | a <= 7 (M) |

96 | 8 6 2^{a} | a <= 2 (O) |

96 | 8 3 2^{a} | a <= 4 (O') |

96 | 8 2^{a} | a <= 11 (M) |

96 | 6 4 4 2^{a} | ? |

96 | 6 4 2^{a} | ? |

96 | 6 2^{a} | a <= 15 (M) |

96 | 4 4 3 2^{a} | ? |

96 | 4 4 2^{a} | a <= 20 |

96 | 4 3 2^{a} | ? |

96 | 4 2^{a} | a <= 23 (M) |

96 | 3 2^{a} | ? |

96 | 2^{a} | a <= 48 (H) |

100 | 5 5 2 2 | (T) |

Let us first worry about existence for each of these 78 lines.
Assume that the m_{i} are sorted in nonincreasing order.

If all m_{i} are 2, then g is at most N/2, and in case of
equality we have a Hadamard matrix, and conversely Hadamard matrices
do give orthogonal arrays of strength 3 whenever N is a multiple of 8.
The corresponding rows have been labeled (H).
That settles existence for 12 cases, leaving 66.

If g=4 and N is a multiple of the product of the m_{i}, then
at least the trivial design exists; there may be others as well.
The corresponding rows have been labeled (T).
This settles existence in 6 more cases, leaving 60.

Given a design with g factors at m_{1}, ..., m_{g} levels
and N runs, we can form a design at e.m_{1}, ..., m_{g} levels
and eN runs, for any positive integer e. Let us call this construction (M),
with M for multiply. It settles existence in 23 more cases, leaving 37.

When m_{1} = 3 (so that all m_{i} are 2 or 3) then
no label is given, and the result is quoted from the previous section.
This settles 5 more cases, leaving 32.

(*) The case N=32 with groupsizes 4,4,2,2,2,2 follows by taking a Latin square of order 4 (that is, an orthogonal array of strength 2 and N=16 of type 4,4,4) and a Hadamard matrix H of order 4, and replacing the symbol i in the third column of the OA by the i-th row of H and by its complement.

Alternatively, take the binary code spanned by

00 1111 01 0011 02 0101 10 0011 20 0101where the first two positions are quaternary (with alphabet Z2xZ2) and the remaining four positions are binary.

(**) The case N=64 with groupsizes 4^{2} 2^{12} follows
by taking the binary code spanned by

00 111111110000 00 000011111111 01 001100110011 02 010101010101 10 001100111100 20 010101011010where the first two positions are quaternary (with alphabet Z2xZ2) and the remaining twelve positions are binary.

(***) The case N=81 with groupsizes 9,3,3,3,3 follows by taking the ternary code spanned by

0 1011 0 0112 1 0010 3 0001where the first position is 9-ary (with alphabet Z3xZ3) and the remaining four positions are ternary.

(X) Applying the Rao bound to the derived designs of
N=8s with groups s 2^{a}, we find a <= 7.
For even s we already found these with (M), but for odd s
there is no system with a = 7. Indeed, all s derived designs
are essentially Fano planes, and have 7 triples of columns
where half of the combinations occur twice and half of the
combinations occur not at all. We need a matching, where
each time 000 occurs twice in one Fano plane, it occurs
not at all in some other Fano plane. But 7s is odd, and
no such matching exists.

On the other hand, such designs exist with a = 6 when s is at least 5.
Indeed, juxtaposing a design with N=8s for s 2^{6} and one
with N=16 for 2^{7} we get one with N=8(s+2) for (s+2) 2^{6},
so it suffices to do the case s=5, N=40. We need five designs on 8 rows
and six columns. Make them by fixing the first column and cyclically
permuting the remaining five, starting from

000001 111001 100010 011010 001100 110100 101111 010111

(R) One can always replace a 4-level factor by two 2-level factors.
Thus, from 4^{6} one gets 4^{5} 2^{2}.

This is best possible for N=64, since no 4^{5} 2^{3} exists:
The strength 2 derived structure with N=16 and groups 4^{4} 2^{3}
is unique (the affine plane of order 4 together with the three ways of
partitioning its four parallel classes into two sets of two).
Parallel lines have the same binary tail. But that means that for a given
run 00000 000 there are 15 runs (0xxxx) 000 with nonzero x, and the
tail 000 occurs 16 times (instead of 8).

(L) stands for linear code. The quaternary [6,3,4] code
gives N=64, 4^{6}.

(O) is the label given for a <= 2 in case m.n.2^{a} where
N = 2mn and m and n are even, and n/2 is odd.
Indeed "even sum" gives a solution for m.n.2^{2}, and
no OA(2n, n.2^{3}, 2) exists.

(O') is the label given for a <= 4 in case m.3.2^{a} where
N = 12m and m is even. Indeed, no OA(12,3.2^{5},2) exists.
On the other hand, juxtaposing solutions for m=4 and m=6 one finds
solutions for all m > 2.

Corrections and improvements are welcome.

Andries Brouwer - aeb@cwi.nl

Next Previous Contents