Covering arrays from line-polychromatic colourings of affine planes

For a prime power q, Reed-Solomon codes give orthogonal arrays OA(q^t; t, q+1, q) of index one, so CAN(t,k,q) = q^t for t <= k <= q+1. With one column more, no array of index one is known apart from a few cases, and the best known covering arrays had considerably more than q^t rows. We add the (q+2)-nd column as a colouring of the affine plane AG(2,q) composed with evaluation of the message polynomial at an element of Fq^2 \ F_q. The rows of the orthogonal array that agree on t-1 old columns are mapped by this evaluation bijectively onto a line of AG(2,q), so a colouring in which every line sees all c colours makes c symbols of the new column free. This gives CAN(t,q+2,q) <= q^t + (q-c) q^(t-1) for every prime power q and 2 <= t <= q+1, a statement formalised in Lean 4. By the Jamison-Brouwer-Schrijver bound on affine blocking sets c <= floor(q/2); colourings attaining this were found for twelve values of q. Allowing the colour classes to overlap leads to a cost model whose optimum for odd q is an explicit cover by pairs of lines through a point, giving CAN(t,q+2,v) <= q^t + (v-(q+1)/2) q^(t-1) + ((q-1)/2) q^(t-2) for all odd q and (q+1)/2 <= v <= q. Two new columns (k = q+3), the hyperoval array for even q, and a partial symbol fusion of the base rows for v < q (saving 2(q-v) further rows) are also treated. In total 64 arrays improve the current covering array table for 3 <= t <= 6; 49 of them are explicit arrays that were checked exhaustively and 15 rest on certificates for the theorems. This record is the preprint (PDF). The arrays, certificates, verification programs and Lean 4 sources it refers to are in the data record (doi:10.5281/zenodo.23787055); the companion preprint B is doi:10.5281/zenodo.23787053.