Abstract

An alternate formulation is given for index one orthogonal arrays based on computer searches. Orthogonal arrays in diagonal form, and their elements' products, powers, and orders, are derived from first column vectors which result from the searches. Mapping operators relating the first column vectors for each number of levels (m) are described. A scheme for factoring the mapping operators is suggested also. Results are given for values of m which are primes, prime powers, and prime power products. An association between first column vectors and irreducible monic polynomials is made for selected prime power values of m.

Permutation vectors which extend the formulation to groups with orders of powers of m are defined for values of m which are primes and prime powers. Properties of the permutation vectors are described. A formulation is given for strength two covering arrays based on the permutation vectors. These arrays have wm²-(w-1)m rows and (m^w+1-1)/(m-1) columns for values of w which are positive integers. A sliding levels technique is suggested to include values of m which are prime power products.

Zero sum arrays are constructed using the permutation vectors. A recursive construction for strength three covering arrays is given for m equal to two. Alternatively, the cats program is used to find strength three and four covering arrays by removing redundant rows from covering arrays of permutation vectors.

For values of m which are primes and prime powers, another formulation describes sets of permutation vectors which do not cover. The formulation is used to find covering arrays of strength greater than two, by forming arrays of permutation vectors in which each combination of columns contains a combination of permutation vectors which is not noncovering. Resulting covering arrays of strengths l=3 and l=4 have zm^l-(z-1)m rows for values of z which are positive integers. The numbers of columns found are consistent with the conjecture that arrays of this form can have m+1 columns for z=1 and m^z columns for z>1.

For values of m which are primes and prime powers, and for strengths greater than two, a narrower, recursive search is described for index one orthogonal arrays of permutation vectors. The search results suggest a formula for orthogonal arrays with m+1 columns, and strengths up to m+1. Selected results are given for strengths up to four.

Preface

Four years ago I started a mathematical journey. These are my travel notes. They document my search for ways to construct covering arrays using various computer search techniques. The computer search has been a heuristic tool for me, with results leading to improved searches, as well as to the mathematical patterns described here.

I suppose the reader who is interested in orthogonal arrays and covering arrays may desire a rigorous mathematical deduction of results. That is not the purpose of these notes. I have included some informal logical illustrations, but the emphasis here is on pattern recognition and description, rather than formal proof. The reader will not find a clear boundary drawn between derivation and conjecture. Instead, I invite the reader who travels these paths to join in the logical development of the ideas, to add the rigor where it fits.

AT&T Labs provided computer facilities supporting this work. (A Sun Microsystems Ultra 5 workstation executed the searches described here.) Also, I would like to acknowledge the interest and support of several people in my earlier work on the Constrained Array Test System (which was one of the motivators of the present work). These colleagues include:

In particular, Colin and Neil showed me there was new ground to explore here. Finally I want to thank my family – Ann, Jeffrey, Andrew, and Daniel – for their patience and understanding during my travels.

Have a good trip!
George Sherwood
March 2002

Table of Contents

Table of Symbols

Table of Covering Arrays

Definitions

Dot Vectors

This section defines Dot Vectors and Dot Operators.

For each of the m levels h=0, 1, ..., m-1, define the vector h. given by repeating the value of h m times. For example, for m=3, the dot vectors are:

The unary dot operator acts on an array to replace each element with its corresponding dot vector. The result is an array with m times the number of rows compared to the original array. Thus,

Similarly, the raised dot operator replaces each element of an array with its corresponding dot vector transposed. The result is an array with m times the number of columns compared to the original array:

The number of levels m for a dot vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the dot (e.g. h._{3}). When the number of columns c<m, the dot vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the dot (e.g. h·^{2/6} when m=6).

Plus Vectors

This section defines Plus Vectors and Plus Operators for three cases:

• m=prime (p)
• m=prime power (p^a)
• m=prime power product (p₀^a₀ p₁^a₁ ... p_b-1^a_b-1)

In all cases the zero plus vector 0_+{m} is defined to contain all m levels in ascending order:

Note that the definitions given in this section are not the only choice leading to the formulations given here. Later sections will illustrate two cases in which alternate plus vector definitions can affect results. However, a systematic study of all choices of plus vectors is beyond the current scope.

Plus Vectors for m=prime

Construct the modulo m=p addition table (p=prime) for the m order cyclic group. Each table element in row j=0, 1, ..., m-1 and column k=0, 1, ..., m-1 has the value j+k (mod m).

For example, for m=3, the table is

Now define the m vectors k₊ given by the table columns. In this example, they are

The unary plus operator acts on an array to replace each element with its corresponding plus vector. The result is an array with m times the number of rows compared to the original array. Thus,

Similarly, the raised plus operator replaces each element of an array with its corresponding plus vector transposed. The result is an array with m times the number of columns compared to the original array:

The number of levels m for a plus vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the plus (e.g. h_+{3}). When c<m, the plus vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the plus (e.g. h^+{2/6} when m=6).

Plus Vectors for m=prime power

For m=p^a, in which p=prime and a>1, the plus vectors are defined in terms of the p^a-1 plus vectors. Thus, plus vectors for m=p^a can be found recursively from those of p. An R function associates each of the m levels with a row in an m-by-a level representation array. The R function is given by

Here R(0_+{p}) is defined to be 0_+{p}. So for m=9, p=3, and a=2,

and

The addition table for m=p^a is constructed by modulo p addition of elements from the level representation array. For each table element in the j^th row, there is a corresponding row J in the level representation array, with values J₀, ..., J_a-1. For each table element in the k^th column, there is a corresponding row K in the level representation array, with values K₀, ..., K_a-1. The j,k table element is found by vector addition of the two level representation rows (mod p), and then finding the position of the row with the resulting sum J₀+K₀, ... , J_a-1+K_a-1. The j,k table element is

Here R(j) gives the j^th row of the level representation array, and R^-1 is defined as the function which gives the position of each row of the level representation array.

For example, for m=9, j=4, and k=5, the rows to add are 1 2 and 2 0. The resulting row is 0 2 which is represented by the level 6. So the 4+5 element in the addition table is 6. The complete addition table for this example is

Now define the m vectors k₊ given by the table columns.

In this example, they are

Similarly, for m=27, p=3, and a=3, R(0_+{27})=(0._{9} R(0_+{9}))_+{3} and

The k₊ vectors for m=27 are

As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.

Plus Vectors for m=prime power product

When m>1, and is divisible by b>1 distinct primes, m can be expressed as a product of b primaries, which contain the prime factors of m raised to the appropriate powers: m=p₀^a₀ p₁^a₁ ... p_b-1^a_b-1. In this case, the plus vectors are defined in terms of the plus vectors of the b primaries. An R function associates each of the m levels with a row in an m-by-b level representation array. The R function is given by

Each column of the level representation array consists of repetitions of the zero plus vectors of one of the primaries. The number of repetitions is chosen to form a total of m rows. So for m=12, b=2, p₀=2, a₀=2, p₁=3, and a₁=1.

The addition table for m is constructed by addition of elements from the level representation array using the addition tables as defined above for the corresponding primaries. For each table element in the j^th row, there is a corresponding row J in the level representation array, with values J₀, ..., J_b-1. For each table element in the k^th column, there is a corresponding row K in the level representation array, with values K₀, ..., K_b-1. The j,k table element is found by addition of the corresponding level representation row elements, using the addition table for the primary of each column, and then finding the position of the row with the resulting sum J₀+K₀, ... , J_b-1+K_b-1. The j,k table element is R^-1(J+K_{addition tables}).

For example, for m=12, j=4, and k=5, the rows to add are 0 1 and 1 2, using the addition tables for p₀^a₀ = 2² = 4

and p₁^a₁ = 3¹ = 3

respectively. The resulting row is 1 0 which is represented by the level 9. So the 4+5 element in the addition table is 9. The complete addition table for this example is

Now define the m vectors k₊ given by the table columns.

In this example, they are

As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.

Composite Vector Operators

Each of the addition tables of the previous section defines the addition operation for a group of order m. The sum of j+k is given by the table element in the j^th row and the k^th column. 0 is the identity element, and inverses are identified by row-column pairs whose sum is 0.

The plus vectors associated with each table, and their composite vector operation, also form a group of order m. Each of these vector groups is isomorphic to the corresponding integer addition group of order m.

In the following definition vectors are described as functions of their positions or subscripts. That is, for a vector A of order m, the element in the j^th row is given by

Similarly, all the elements of A can be expressed as

The composite vector operation is the binary operation of one vector on another. It is defined¹ by

The elements of the A * B vector are those of the B vector arranged according to the values of the A vector elements. The j^th element of A * B is found by using the j^th element of A as the position of B. The resulting value is the j^th element of A * B. For example, if A = 4_+{12} and B = 5_+{12}, then A * B = 9_+{12}, as follows.

The plus vectors form abelian groups in that

However generally vectors will not commute in the composite vector operation:

A more general definition of the composite vector operation will be needed below. Consider two arrays of vectors A and B with r rows and c columns. That is, the element of A in the i^th row and the k^th column A_ik is a vector. Similarly the element of B in the i^th row and the k^th column B_ik is a vector. For such arrays the composite vector operation A * B is defined to be the r-by-c array of vectors C whose elements are given by

for all rows i and columns k. The composite vector operation is also called the vector product here.

1. This definition differs from the usual composite function definition because the order of the functions A and B is reversed. The order of functions in this definition is chosen to be consistent with the left-to-right order of operations implied by the dot, plus and cross operations.

Preparation

Orthogonal Array Search Criterion

Consider an m-by-c array of vectors A which forms an orthogonal array of strength¹ l=2 and index one². That is, each pair of distinct columns k and k' contains each pair of levels h and h' once. (Here, h and h' may be equal; k and k' cannot be.) Suppose each vector A_ik is of order m and contains each of the m levels once. Thus, each vector can be expressed as a bijective function of its position

and there is an inverse function which gives the position for each of the levels

Consider a pair of distinct columns k and k'. Each is composed of m vectors of order m. The vector elements with position j in the i^th row of vectors are A_ik(j) = h and A_ik'(j) = h'. The pair of levels h and h' can appear only once, in this i^th row of vectors. Consider also a pair of vectors in the same columns k and k', but in a different row of vectors i'. The vectors are A_i'k and A_i'k' as illustrated below.

Select the position j' such that

Since the pair of levels h and h' occur in k and k' in the i^th row of vectors and that pair of levels cannot occur more than once, the corresponding elements in column k must be different:

And since

substitution yields

Application of A_i'k^-1 gives

and the definition of the composite vector operation yields

This is the criterion to be used to find orthogonal arrays of vectors, for all distinct i and i', and all distinct k and k'.

For a given set of vectors, say h₊, h=0, ... , m-1, a table of m² products h₊ * h'₊^-1 can be computed for reference. Then the search can be done over an m-by-c array of vectors, which is faster than a more general search over an m²-by-c array of levels.

1. An orthogonal array with index one has strength l (greater than or equal to 0, and less than or equal to c) if every r-by-l subarray contains each l-tuple of levels exactly once as a row.
2. Generally the term position (rather than index) is used here to mean the subscript of a vector or array, or its independent variable when considered as a function. The index of an orthogonal array refers to the number of times each l-tuple occurs.

Standard Form

To narrow its scope and thus improve its speed, the orthogonal array search will require found arrays to be in standard form. A strength l=2 array of plus vectors is in standard form when

1. its 0^th column consists of m 0₊ vectors;
2. its 1^st column consists of the m i₊ vectors in ascending order, i=0, 1, ... , m-1;
3. its 0^th row consists of c 0₊ vectors; and
4. its 1^st row consists of c plus vectors in ascending order.

Requiring these conditions poses no loss of generality due to well known properties of orthogonal arrays¹. To illustrate this point consider an orthogonal array of plus vectors A_ik in some other, arbitrary form. The following four transformations can be applied to the array to produce an orthogonal array in standard form. Conversely, an orthogonal array in standard form can lead to many other forms by similar transformations in reverse.

1. To make the 0^th column consist of 0₊ vectors, apply to each row of vectors, the inverse of the vector in the 0^th column. Each row i of vectors is transformed as follows.

   Ai0-1 ·{c/m} * (Ai0

   Ai1

   ...

   Ai c-1) = Ai0-1*Ai0

   Ai0-1*Ai1

   ...

   Ai0-1*Ai c-1

   (Here the ·^{c/m} notation means the A_i0^-1 vector is to be repeated over c columns, because c may be less than m.) By definition, the effect of applying A_i0^-1 to form the vector product is the rearrangement of the rows of levels within the i^th row of vectors. This transformation is a permutation of rows, which results in an orthogonal array with the same parameters -- l, m, c, and r.

2. Consider the orthogonal array search criterion with k=0 and k'=1. For all distinct i and i', A_i0 * A_i'0^-1 =/= A_i1 * A_i'1^-1

   For an array with 0.₊ as its 0^th column,

   0₊ = 0₊ * 0₊^-1 =/= A_i1 * A_i'1^-1

   so

   A_i'1 =/= A_i1

   Thus the m vectors in the 1^st column are all different and must include all plus vectors from the set under consideration. Now it is possible to rearrange of the rows of vectors so that the 1^st column contains the i₊ vectors in ascending order. This transformation is a permutation of rows, which results in an orthogonal array with the same parameters.

3. To make the 0^th row of vectors consist of 0₊ vectors, apply to each column of vectors the inverse of the vector in the 0^th row of vectors repeated m times. Each column k of vectors is transformed as follows. A_0k * A_0k^-1
   A_1k * A_0k^-1
   :
   A_{m-1 k} * A_0k^-1

   By definition, the effect of taking the vector product of each plus vector in the column with A_0k^-1 is a remapping of levels within the k^th column. Specifically, the level h of each column vector element is mapped to the level of the element of A_0k^-1 with position h. Consequently, this transformation is a permutation of levels of a column, which results in an orthogonal array with the same parameters.

4. Consider the orthogonal array search criterion with i'=0 and i=1. For all distinct k and k', A_1k * A_0k^-1 =/= A_1k' * A_0k'^-1

   For an array with 0·₊ as its 0^th row of vectors,

   A_1k * 0₊^-1 =/= A_1k' * 0₊^-1

   so

   A_1k =/= A_1k'

   Thus the c vectors in the 1^st row are all different. Now it is possible to rearrange the columns so that the 1^st row of vectors contains the plus vectors in ascending order. This transformation is a permutation of columns, which results in an orthogonal array with the same parameters.

   When c=m, the orthogonal array of plus vectors can be expressed as an m-by-m array to which the plus operator is applied. If the orthogonal array is in standard form, the m-by-m array can be interpreted as a multiplication table. Its 0^th row and 0^th column consist of the element 0, indicating all multiplication products of 0 equal 0. Its 1^st row and 1^st column consist of the m elements in ascending order, indicating 1 is the multiplicative identity element. For example, when l=2 and c=m=5, the orthogonal array of plus vectors is

   A = (

   0 0 0 0 0

   0 1 2 3 4

   0 2 4 1 3

   0 3 1 4 2

   0 4 3 2 1

   )+

   The corresponding multiplication table is contained in the parentheses. In this example, the table represents multiplication modulo 5.

   When m=p is a prime, or m=p^a is a prime power, then c=m. In these cases corresponding addition and multiplication tables may define rings or fields for the elements h=0, 1, ..., m-1. Similarly the tables may define isomorphic rings or fields for the plus vectors h₊=0₊, 1₊, ..., (m-1)₊ . Here the addition operation is the composite vector operation, and the multiplication operation is given by the multiplication table.

1. For example, see Chapter 1 of Orthogonal Arrays Theory and Applications by A. S. Hedayat, N. J. A. Sloane, and John Stufken, 1999 Springer-Verlag.

Diagonal Form

To narrow its scope and improve its speed further, the orthogonal array search will look for arrays in diagonal form. A strength l=2 orthogonal array of plus vectors B is in diagonal form when it can be written as a vector product of a template array T and a first column vector f_uv as follows.

in which T is an m-by-c array, and f_uv is a vector with m rows. (The u and v vectors are used to label the first column vectors as described in a later section.) For m>1, the template array elements are defined as follows.

The f_uv vector contains a permutation of the m levels with 0 and 1 in the 0^th and 1^st positions respectively. For example, for m=5 and c=5, the template array is

and a first column vector is

Their product is

(Note the first column of this array is f₀₀, which leads to the name first column vector for an orthogonal array in diagonal form.) Finally, the application of the plus operator gives the full array:

Because an orthogonal array in diagonal form has 0₊ vectors in its 0^th row of vectors and in its 0^th column, it already satisfies conditions 1 and 3 for standard form (above). Thus, only transformations of type 2 and 4 are needed to change the orthogonal array from diagonal form to standard form. It is convenient to express the array in standard form in terms of the first column vector, as follows.

In this example

The entire orthogonal array in standard form is

In general the mapping from orthogonal arrays of plus vectors in diagonal form to those in standard form is not injective. This is because there can be multiple diagonal form arrays mapped to the same standard form array. In particular, for m=5 and c=5, the first column vector

maps to the same standard form array as f₀₀ does.

Generally the mapping from an orthogonal array of plus vectors in diagonal form to one in standard form is not surjective either, because there are orthogonal arrays of vectors in standard form¹ which do not have corresponding diagonal forms. (They are not found in a search for arrays in diagonal form.)

Requiring the orthogonal array search to find arrays of plus vectors in diagonal form is neither necessary nor sufficient. It is not a necessary condition because there are other orthogonal arrays which are not found by the search for arrays in diagonal form. Search results include orthogonal arrays based on Galois fields however. Finding an array in diagonal form is not sufficient because there are diagonal arrays of plus vectors which do not satisfy the orthogonal array search criterion. For example, for m=5 and c=5, the identity vector

yields a nonorthogonal array, though its product with the template array is diagonal. Thus 0₊ is not a first column vector in this example.

The advantage of searching for orthogonal arrays in diagonal form is the reduction in the scope of the search, leading to shorter execution times for large m. The search is reduced to finding first column vectors, for which there may be (m-2)! permutations of levels. In practice, the number of cases to test is less than (m-2)! because the first column vector can be built incrementally. After level 0 is assigned to the 0^th row and column, and after 1 is assigned to the first diagonal position, each candidate level can be checked in a partial array to see if it meets the orthogonal array search criterion. If it does, a candidate level is chosen for the next diagonal. If it does not, the search considers the next candidate level for the current diagonal, without consideration of additional diagonals containing this nonorthogonal, partial permutation.

1. For m=9 and c=9, a search for orthogonal arrays of plus vectors in standard form yields 17 arrays. Three of these are obtained from a corresponding search for orthogonal arrays of plus vectors in diagonal form, followed by the mapping to standard form (as described below). Two of the 17 are based on noncommutative rings with identity, because the multiplication tables are not symmetric. However each can be described in terms of the following template array (with four diagonal subarrays) and one of two first column vectors.

   	0	0 0 0 0	0 0 0 0			0		0
   T =	0 0 0 0	1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3	5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5		with f =	1 3 2 6	or	1 3 2 6
   	0 0 0 0	5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5	3 4 1 2 4 1 2 3 1 2 3 4 2 3 4 1			4 7 8 5		8 7 4 5

   The remaining 12 orthogonal arrays from the search yield multiplication tables which are not associative.

Products, Powers, and Primitive Elements

Products of Elements

The interpretation of the standard form orthogonal array of plus vectors as a multiplication table, and its expression in terms of the first column vector, lead to formulas for products of the levels. The multiplication products expressed in terms of the first column vectors are as follows:

Powers of Elements

In particular, for m>1 the powers of h are given by

In the m=5 example,

# Primitive Elements

The powers of h formula for h>1 implies which positions in a first column vector can contain primitive elements. (The powers of a primitive element generate all m-1 nonzero levels.) If q is a totitive of m-1, then f_uv(q+1) is a primitive element. (q is a totitive of m-1 if it is a relative prime of m-1 and less than m-1.)

When h=f_uv(q+1),

If q equals a totitive of m-1,

To see this, divide aq by m-1 as follows,

in which y and z are integers. aq_{mod m-1} = z, the remainder. A similar expression for a different power is:

Now consider when z'=z.

so

Since the right side of the equation is a multiple of m-1, and since q and m-1 are relative primes, a'-a must be a multiple of m-1. Since the values of a=1, 2, ..., m-1 differ by less than m-1, aq_{mod m-1} = z takes on all m-1 values 0, 1, ..., m-2 without repeating. Now in

the argument of f_uv must take on all values 1, 2, ..., m-1, so h^a generates all nonzero levels.

In the m=5 example, q=1 or 3 (relative primes of 4), so the first column vectors can have primitive elements only with positions 2 or 4. The primitive elements are 2 and 3.

Note that for any m>2, q may be 1 or m-2. Therefore the first column vector positions 2 and m-1 must contain primitive elements.

# Orders of Elements

Generally the powers of h formula implies which positions in a first column vector contain elements of a particular order. For an element h>1 with order a,

Application of f_uv^-1 and subtraction yield

so

for some integer y. Solving for h yields

in which 0<y<a, so the position of f_uv is greater than 1 and less than m. Also, a must divide y(m-1) so that the position of f_uv is an integer. Now y must be a totitive of a (i.e. y/a must be irreducible). To see this, suppose there is a reduced fraction

in which y'<y and a'<a. Replacement of y/a with y'/a' gives

Then the powers of h formula indicates a' is the order of h:

which contradicts the statement that a is the order of h. Thus, since y is a totitive of a, a cannot divide y, and a must divide m-1.

The order of the first column vector element in each position greater than 1 is determined as follows.

1. Find the allowed orders from the set of integers a>1 which divide m-1.
2. For each order a, find the totitives, which are the allowed values of y.
3. Compute the position y(m-1)/a + 1 for each pair of a,y.

For example, for m=16, the orders and corresponding positions are as follows.