Covering arrays from cyclotomy
For a prime power q equivalent to 1 (mod nu), the q x q cyclotomic matrix, whose entries are the discrete logarithms modulo nu of the entries in the addition table of F(q), has been shown using character theoretic arguments to produce an epsilon-biased array, provided that q is large enough as a function of nu and epsilon. A suitable choice of epsilon ensures that the array is a covering array of strength t when q > t(2)nu(4t). On the other hand, when nu = 2, using a different character-theoretic argument the matrix has been shown to be a covering array of strength t when q > t(2)2(2t-2). The restrictions on epsilon-biased arrays are more severe than on covering arrays. This is exploited to prove that for all nu >= 2, the matrix is a covering array of strength t whenever q > t(2)nu(2t), again using character theory. A number of constructions of covering arrays arise by developing and extending the cyclotomic matrix. For each construction, extensive computations for various choices of t and nu are reported that determine the precise set of small primes for which the construction produces a covering array. As a consequence, many covering arrays are found when q is smaller than the bound t(2)nu(2t), and consequences for the existence of covering arrays reported.
covering array epsilon-biased array orthogonal array cyclotomic class