Seven covering arrays below the November 2024 tables

A covering array CA(N; t, k, v) is a table with N rows and k columns, filled with the symbols 0 to v-1, such that any t columns show every possible combination of t symbols in at least one row. Claude, working under my direction, found seven with fewer rows than the November 2024 snapshot of Charles Colbourn's covering array tables lists: six of strength 3 (over 5 and 7 symbols) and one of strength 4 (over 3 symbols). The arrays, the checkers, their logs and the constructions are in github.com/dzoba/covering-arrays-2026, and I sent the arrays to Colbourn so he can check them against the current tables.

What they are for

Say you ship software with 8 options, each with 5 possible values. Testing every combination is 5^8, about 390,000 runs. Combinatorial testing asks for less: every combination of values for any 3 options appears in at least one run. A CA(165; 3, 8, 5) is exactly that, in 165 runs. Rows are test runs, columns are options. NIST's IPOG-F tables list 257 runs for the same case. The same idea covers parameter sweeps and screening experiments. Colbourn's tables record the smallest N known for each (t, k, v), and test tools and catalogues draw on them.

The live tables at Arizona State have needed a login since February 2025 and I couldn't read them, so the right-hand column comes from the November 2024 snapshot that Ulrike Grömping mirrors. If a smaller value was reported after November 2024, I wouldn't see it. That is why the arrays went to Colbourn instead of my just announcing a record.

Symmetry for the 165 and the 129

The 165 isn't searched as 165 rows. The maps x -> mx + b (mod 5), with m nonzero, permute the symbols, and the array is built so that applying the same map in every column turns each row into another row of the array. It is 8 "starter" rows, all 20 images of each, and the 5 constant rows (a, a, ..., a). That is 5 + 8·20 = 165 rows, and the search only has to choose the 64 entries of the starters.

Checking gets short too. The 125 possible symbol triples fall into 7 orbits under these maps: the 5 constant triples, and 6 others of 20 triples each. The constant rows cover the first kind. The 20 images of a starter cover the whole orbit of whatever triple the starter shows on three given columns. So the array is a covering array exactly when, on each of the 56 column triples, the 8 starters between them land in all 6 non-constant orbits. A tabu search that Claude wrote hit that target in about 30 seconds. Delete any column and you have a CA(165; 3, 7, 5).

The 129 is the same trick at strength 4. Over 3 symbols there are 6 maps, so it is 3 constant rows plus 21 starters with 6 images each: 3 + 21·6 = 129. The search reached it in 8.6 seconds. Two 90-second runs with 20 starters (123 rows) didn't get there. An exact computation of whether 20 starters can work at 8 columns was still running when the repository went up, and nothing here depends on it.

The 218

The 218 builds on a smaller array of the same kind: 9 starters over 5 symbols and 10 columns, 5 + 9·20 = 185 rows. 185 is the table's own value at 10 columns, and Claude re-found an array of that size with this symmetry by a SAT search. Add an 11th column that is 0 on the constant rows and μ_r·m on the image mx + b of starter r, where μ_r is a nonzero scalar chosen per starter. With the right scalars, that column covers every new combination but one kind: a pair (a, b) with a different from b on two old columns, next to a 0 in the new column. The constant rows only show a = b, and every image row has a nonzero entry in the new column. So a 33-row block, found by simulated annealing and given 0 in the new column, supplies every such pair on every pair of old columns. That gives 185 + 33 = 218.

The conditions on the base, the scalars and the block are stated as a lemma with a short proof in the repository. It needs a suitable base array, and this is the only case we know of where it beats the table. The array doesn't depend on the lemma anyway: it passes the same checkers as the others.

The three arrays over 7 symbols

These came from tabu search, not from a construction, and all three descend from the table's own CA(479; 3, 10, 7), the 2010 array of Colbourn, Kéri, Rivas Soriano and Schlage-Puchta, as published in Aaron Dwyer's CA_Database. The search picks an uncovered combination, rewrites three cells in the row where that helps most, and when the array is complete it deletes the row that covers the fewest combinations on its own.

The 476 is a local repair of that 479, not a new construction: 253 of its rows are rows of the 479, and the other 223 differ from the nearest 479 row in 1 to 5 cells. The 479 has no redundant row, so this isn't the 479 with spare rows dropped. The 556 was seeded with the 479 plus a random 11th column and random extra rows, and the 633 the same way from the 556 with a 12th column.

How they were checked

Every strength-3 array passes three checkers written separately: two by the Claude sessions that ran the searches, and one by an agent that was given only the definition and some known arrays, not the search code. The 129 passes the two of them that handle strength 4. For every array, a copy with a row deleted and a copy with one cell changed fail every checker that applies, and a copy with an out-of-range symbol is rejected. The 165, 218 and 129 are also rebuilt from their constructions and the rows compared. All of it runs in about a minute with bash checkers/run_all.sh.

Codex wrote its own checkers from the definition and re-checked all seven arrays: the six strength-3 ones on October 19, and the 129 on October 20 with fresh C code that didn't reuse the search session's checkers. For the 129 it found all 5,670 pairs of (4 columns, symbol tuple) covered, all 129 single-row deletions failing, and the 6 maps preserving the row set. Separate Claude instances also refereed the six strength-3 arrays and checked public sources for earlier records. For the 129, Codex records novelty as unresolved, not refuted, since the ASU tables need a login and Torres-Jimenez's covering array repository couldn't be reached.

Claude ran the searches, worked out the constructions and proofs, and wrote most of the checkers. Codex did the re-checking above and the literature search for the 129. I directed the work.

What this doesn't show

These are upper bounds on the smallest possible N. Nothing here says 165 is the true minimum for CA(N; 3, 8, 5); the known lower bound, from the same 2010 paper, is 145. The searches did not improve the table values at k = 9, 10 and 12 for v = 5, at k = 9 and 13 to 16 for v = 7, or the strength-4 values at k = 7 and 9. The gains are uneven: the 633 and the 476 save under 1 percent each, while the 556 and the 165 save 13 and 11 percent. Whether the current tables already list smaller arrays is something I can't check from here, and Colbourn can.