A construction for strength-3 covering arrays from linear feedback shift register sequences

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252–260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial \(f\) of degree \(m\) over \(\mathbb F _q\) , by taking all unique subintervals of length \(\frac{q^m-1}{q-1}\) from the LFSR generated by \(f\) , we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For \(m=3\) , by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over \(q^2+q+1\) factors, each with \(q\) levels that has size only \(2q^3-1\) , i.e. a \(\text {CA}(2q^3-1; 3, q^2+q+1, q)\) whenever \(q\) is a prime power. When \(q\) is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all \(2 \le q \le 25\) . Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all \(q\) except \(q = 2,3,6\) . By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.