Constructing New Families of Covering Arrays Using Finite Geometry and Finite Fields

Abstract

Covering arrays are well-studied objects in combinatorial design theory. A strength-$t$ \emph{covering array}, denoted by CA$(N; t, k, v)$, is an $N \times k$ array over an alphabet with $v$ symbols such that in any $t$-set of columns, each $t$-tuple over the alphabet occurs in at least one row. Finite fields and finite geometry have been widely employed in the construction of covering arrays. Let $q$ be a prime power. One of the significant geometric objects arising from $\PG(2,q)$ that has been used to construct strength-$3$ covering arrays is a pair of \emph{orthogoval} projective planes. Two projective (affine) planes with the same point sets are orthogoval if the intersection of any two lines, one from each plane, has size at most two. The existence of such pairs of orthogoval projective planes has been independently proven and published multiple times. In this thesis, we extend the concept of a pair of orthogoval projective planes to a key property involving M{\"o}bius planes in $\PG(3,q)$. We say that $m$ (truncated) M{\"o}bius planes are \emph{anti-cocircular} if the common intersection of any choice of $m$ circles, one from each of the planes, has size at most three. We prove the existence of three anti-cocircular truncated M{\"o}bius planes for any odd prime power $q$. This new geometric object has significant properties that enable the construction of strength-$4$ covering arrays. The covering arrays obtained through this method significantly improve the upper bounds on the size of the best-known arrays. Moreover, these covering arrays have a rich structure, which can be beneficial to their use as ingredients in recursive constructions. Our results suggest the existence of analogous properties in higher-dimensional projective geometries, with potential applications in the construction of higher strength covering arrays. Another contribution of this thesis involves strength-$3$ covering arrays. Strength-$3$ covering arrays obtained from a pair of orthogoval projective planes have a significant property that makes them suitable for recursive constructions. Each such array is obtained by the vertical concatenation of two strength-$2$ orthogonal arrays that together form a strength-$3$ covering array. Taking advantage of this structure, we construct new families of strength-$3$ covering arrays by first horizontally concatenating multiple copies of this strength-$3$ array. The coverage is then completed by adding key ingredient arrays, which together are used as part of a general recursive construction. In certain cases, the ingredient arrays are carefully selected to introduce systematic redundancy among rows, allowing redundant rows to be removed to optimize the size of the covering arrays. These new families reduce the size of some of the best-known covering arrays. Such improvements were enabled by exploiting the diverse properties inherited from finite fields and finite geometry.