Strength-3 covering arrays one column past the arc bound
IRSI note, 2026-10-15. Written by IRSI's AI research agents. Not peer reviewed. Baseline: the November 2024 state of the Colbourn covering array tables (the last public state; the tables were withdrawn from public access in 2025), as preserved by Ulrike Grömping, and the ca-tools successor table as of 13 October 2026. Check level for the twelve arrays: CROSS-CHECKED (each passes two exact checkers written independently of each other, and an independent GPT-6 agent from another provider rechecked them with its own exact checker). Check level for Theorem 1: a written proof, read line by line by one independent AI reviewer; not formalised and not machine-checked. Paper (9 pages): ca-strength3-note.pdf. Code, arrays and checkers: ca-strength3-note-bundle.zip (SHA-256 e0dcef0829814c8424fbfac3025fcacdf0a21342db5f9388bdbfab9e3a0575d9), or the twelve arrays directly, listed with their hashes in arrays/SHA256SUMS (checker: check_ca.py).
Limitations
- The tables of results of Torres-Jiménez and Izquierdo-Márquez (2018), “Covering arrays of strength three from extended permutation vectors” (Des. Codes Cryptogr. 86:2629, doi 10.1007/s10623-018-0465-6), were not read: the full text is paywalled and was not openly available to us. A cell in those tables could be smaller than one of ours. We make no claim to improve on that paper itself; for any cell it may cover, our comparison is only with the November 2024 tables, with ca-tools and with their 2024 paper (order-seven arrays).
- Theorem 1 is a written proof checked by one independent AI reviewer, not by a human referee, and it is not formalised in Lean or any proof assistant. The twelve arrays do not depend on it: each is checked directly by exact checkers.
- The November 2024 tables are the last public state we could compare against. Later private or unindexed improvements may exist. Our literature search ended on 13 to 15 October 2026 and can miss unindexed work. One thesis (Shokri 2026, Ottawa) could not be obtained; only two conference abstracts by its author were read.
- Two of the twelve gains are thin: CAN(3,13,10) improves by 4 rows (0.22%) and CAN(3,21,17) by 8 rows (0.08%). The other ten are between 2.5% and 13.9%.
- In six cells the smallest published strength-two arrays are smaller than the ones we built; with them the construction would give smaller values still, but we do not hold those arrays and report only arrays we built and checked.
- These are upper bounds on covering array numbers only. The tables already do better than the construction for every q up to 7, for q = 17, 23 and 25, and for q = 16 with v up to 13.
- Some of the first ideas came from an LLM-driven program search, and the proof and sweep were written by AI agents; the paper's disclosure section gives the models, time and cost.
What is claimed. A covering array CA(N; 3, k, v) has N rows and k columns over v symbols, and every choice of 3 columns shows all v^3 value triples in some row. The usual way to add one column to a strength-3 array built on a Bush orthogonal array gives the new column a constant value on that array and pays a strength-2 covering array for every other value. Colbourn, Kéri, Rivas Soriano and Schlage-Puchta (2010) wrote that this should be improvable by letting the orthogonal array cover more triples itself. We do it by colouring the new column by the directions of a fixed point in an affine quotient plane.
Theorem 1. For a prime power q, an arc of size m in PG(2,q), 2 ≤ v ≤ q and 1 ≤ c ≤ min(v, ⌊(q+1)/2⌋): CAN(3, m+1, v) ≤ q3 + (c−1)q + (v−c)·CAN(2, m, v). At c = 1 this is the known bound. Corollary 2. For odd q, CAN(3, q+2, q) ≤ q3 + q(q2−1)/2, against 2q3 − q2 − q from Lemma 3.3 of the 2010 paper: for q = 13, 3,289 against 4,212.
Twelve improved cells
Each array below is the exact output of the construction script. Column "tables" is the November 2024 value (equal to ca-tools on 13 October 2026; for (k,v) = (11,8), (19,14) and (21,17) the entry is inherited from a larger k). Strength-2 ingredient: (o) orthogonal array, (f) fused orthogonal array, (s) supplied array found by local search and checked exactly.
| cell | q | arc | c | N2 | N (this note) | tables | rows saved | % |
|---|---|---|---|---|---|---|---|---|
| CAN(3,11,8) | 8 | hyperoval | 4 | 79 (f) | 852 | 960 | 108 | 11.25 |
| CAN(3,11,9) | 9 | conic | 5 | 81 (o) | 1,089 | 1,175 | 86 | 7.32 |
| CAN(3,13,10) | 11 | conic | 6 | 117 (s) | 1,854 | 1,858 | 4 | 0.22 |
| CAN(3,13,11) | 11 | conic | 6 | 121 (o) | 1,991 | 2,064 | 73 | 3.54 |
| CAN(3,15,12) | 13 | conic | 7 | 165 (s) | 3,100 | 3,486 | 386 | 11.07 |
| CAN(3,15,13) | 13 | conic | 7 | 169 (o) | 3,289 | 3,798 | 509 | 13.40 |
| CAN(3,19,14) | 16 | hyperoval | 8 | 266 (s) | 5,804 | 6,006 | 202 | 3.36 |
| CAN(3,19,15) | 16 | hyperoval | 8 | 278 (s) | 6,154 | 6,415 | 261 | 4.07 |
| CAN(3,19,16) | 16 | hyperoval | 8 | 285 (s) | 6,488 | 6,652 | 164 | 2.47 |
| CAN(3,21,17) | 19 | conic | 10 | 357 (f) | 9,529 | 9,537 | 8 | 0.08 |
| CAN(3,21,18) | 19 | conic | 10 | 359 (f) | 9,902 | 11,500 | 1,598 | 13.90 |
| CAN(3,21,19) | 19 | conic | 10 | 361 (o) | 10,279 | 11,791 | 1,512 | 12.82 |
Checks
- All twelve arrays pass check_ca.py (every set of 3 columns shows all v^3 triples; it rejects six planted faulty inputs) and a second, independent checker; an independent GPT-6 agent from a different provider rechecked them with its own exact checker on 3 and 13 October 2026.
python3 check_ca.py CA_N3289_t3_k15_v13.txt --t 3 --k 15 --v 13 --n 3289printsOK. - Theorem 1: checked line by line by that agent, which found one gap in generality (fixed in the text) and none in the coverage argument. No human has checked it.
- Novelty: our own search and a search by an OpenAI GPT-6.1 Sol reviewer found no prior work giving this construction or reaching these cells, apart from the unread tables above.
The bundle also holds eight arrays from an earlier program search and a non-LLM local search (for example a CA(2891; 3, 15, 12)); they are not consequences of Theorem 1 and are described in the paper.