  Given a set $S$ of $v \ge 2$ symbols, and integers $k \ge t \ge 2$ and $N \ge
1$, an $N \times k$ array $A \in S^{N \times k}$ is an $(N; t, k, v)$-covering
array if all sequences in $S^t$ appear as rows in every $N \times t$ subarray
of $A$. These arrays have a wide variety of applications, driving the search
for small covering arrays. The covering array number, $\mathrm{CAN}(t,k,v)$, is
the smallest $N$ for which an $(N; t,k,v)$-covering array exists.
  In this paper, we combine probabilistic and linear algebraic constructions to
improve the upper bounds on $\mathrm{CAN}(t,k,v)$ by a factor of $\ln v$,
showing that for prime powers $v$, $\mathrm{CAN}(t,k,v) \le (1 + o(1)) \left(
(t-1) v^t / (2 \log_2 v - \log_2 (v+1)) \right)\log_2 k$, which also offers
improvements for large $v$ that are not prime powers. Our main tool, which may
be of independent interest, is a construction of an array with $v^t$ rows that
covers the maximum possible number of subsets of size $t$.
