A neutral schematic of the objects and relations in the statement.
Problem. Determine the minimum number \(N=\operatorname{CAN}(3,15,3)\) of rows in a ternary 15-column array such that every choice of three columns contains all 27 ordered ternary triples.
1Context
Both witness arrays and nonisomorphic partial-array exclusions are compact, independently verifiable records.
2Remarks
Remark 1. Rows may repeat, although repeats never help a minimum array.
Remark 2. Column permutations and independent symbol permutations preserve the covering property.
3What counts as a solution
Give a ternary covering array with N rows and a complete proof that N-1 rows cannot cover all three-column interactions.
1Status
Current status (The checked published interval is 27 through 57). The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.[1][2][3]
1Packet records
3 records
Record
Kind
Assessment
Result
Supported
claim · Claim 1
The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.[1][2][3]
Relevance to this problem
For Exact value of CAN(3,15,3), record ca3153-claim-published-interval (“The checked published interval is 27 through 57”) records a bound, answer, status fact, or structural consequence. The record states: The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Record state
reported
Scope
the homogeneous ternary covering-array number CAN(3,15,3)
A strength-three ternary covering array with 15 columns must display all \(3^3=27\) ordered triples in every choice of three columns. One row supplies one triple for a fixed column choice, so every such array has at least 27 rows.
Avila-George, Torres-Jimenez, Hernandez, and Gonzalez-Hernandez report 57 rows for \(k=15\) in Table 2(a) of their 2012 primary paper. Their table labels this value as the best-known solution before their cooperative simulated-annealing experiment and reproduces 57 in the experiment. This gives the sourced upper bound
\[
27\le \operatorname{CAN}(3,15,3)\le57.
\]
The paper says its arrays were deposited in the Cinvestav Covering Array Repository and verified with a separate tool. The repository now requires access, and the audit recovered no public 57-row payload or nonexistence certificate for 56 rows. The exact value should therefore remain open in TheoremDB.
Result
Reproduced
claim · Computation 1
Exhaustive enumeration verifies all 12,285 interaction requirements in an explicit completion of NIST's IPOG-F array.[4]
Relevance to this problem
For Exact value of CAN(3,15,3), record ca3153-claim-nist-80-row-array (“The completed NIST 80-row array covers every interaction”) records a bound, answer, status fact, or structural consequence. The record states: Exhaustive enumeration verifies all 12,285 interaction requirements in an explicit completion of NIST's IPOG-F array.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
established
Scope
all 455 triples of columns and all 27 ternary interactions in each triple for the completed NIST 80 by 15 array
NIST publishes an 80-row IPOG-F array for these parameters. Its file contains 65 don't-care cells marked with hyphens. Replacing every don't-care cell by zero gives an ordinary array over \(\{0,1,2\}\). This completion preserves every interaction already witnessed by a specified cell and supplies a compact explicit certificate.
The executable record checks the shape and alphabet, then enumerates all \(\binom{15}{3}=455\) column triples. Each of their 27 ordered ternary interactions occurs at least once. Across the 12,285 requirements, the minimum multiplicity is one and the maximum is eleven. The canonical completed array has SHA-256 digest `ed0f7e38bdb4c43d87b6cba972fe940ba0c3123f3a2c31f95cf3c4cd66bb100b`.
This proves the independently reproduced bound \(\operatorname{CAN}(3,15,3)\le80\). The sharper 57-row bound in the interval record rests on the cited primary report because its deposited witness was unavailable during this audit.
Standard-library Python decodes the explicit array and verifies every ternary interaction in every triple of columns.[4]
Relevance to this problem
For Exact value of CAN(3,15,3), record ca3153-artifact-coverage-verifier (“Exhaustive verifier for the NIST array”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python decodes the explicit array and verifies every ternary interaction in every triple of columns.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
the complete 80-row ternary array and every strength-three coverage requirement on its 15 columns
The compressed payload contains 80 lines of 15 ternary digits, with one row per line and a final newline. The program binds the payload to its digest, checks every entry, and enumerates the full coverage condition. It also verifies the complete multiplicity distribution and the incidence identity \(80\binom{15}{3}=36400\).
The four-line standard output has SHA-256 digest `821bdc633a47f7300160b992df72caad902c15d2dc87723219e55ec3bbe1280a`.
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion materialContext, examples, and computations
Original intake status. UNKNOWN as of 2026-07-25. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed. The checked sources do not settle the full acceptance condition.
The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. NIST lists an 80-row construction. A separate simple randomized greedy run reached 82 rows under seed 120315.
Computational notes
Any fixed three columns require all 27 triples, so 27 rows are necessary. An independent greedy program produced an 82-row array and reconstructed its coverage exactly. The NIST construction supplies the current checked upper endpoint, giving the conservative certified interval 27<=CAN(3,15,3)<=80. No stronger lower endpoint is claimed without the pending table audit.
How the 3 records connectTyped relations and evidence flowHow the records connect to the problem
TheoremDB contributors, “Exact value of CAN(3,15,3),” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/covering-array-3-15-3
The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.
1References
Packet source. J. Avila-George, J. Torres-Jimenez, V. Hernandez, and N. Gonzalez-Hernandez, New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing, Mathematical Problems in Engineering 2012, Article 897027, Table 2(a), row t=3 and k=15; repository and verification statement in Section 6. J. Avila-George, J. Torres-Jimenez, V. Hernandez, and N. Gonzalez-Hernandez, New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing, Mathematical Problems in Engineering 2012, Article 897027, Table 2(a), row t=3 and k=15; repository and verification statement in Section 6; Table 2(a), t=3, k=15, best-known and cooperative-search sizes both 57. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The checked published interval is 27 through 57. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.Also cited at Table 2(a), t=3, k=15, best-known and cooperative-search sizes both 57.For Exact value of CAN(3,15,3): The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.Source named by the research packet.
J. Avila-George, J. Torres-Jimenez, V. Hernandez, and N. Gonzalez-Hernandez, New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing, Mathematical Problems in Engineering 2012, Article 897027, Table 2(a), row t=3 and k=15; repository and verification statement in Section 6. NIST IPOG-F table and downloadable 80-row array for t=3, v=3, k=15. ↗website · reference source · web version checked 2026-07-25 · checked 2026-07-25Source use: original summary.The checked published interval is 27 through 57. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.Also cited at NIST IPOG-F construction table checked 2026-07-24.Source used to formulate or check the problem record.For Exact value of CAN(3,15,3): The checked published interval is 27 through 57. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.
J. Avila-George, J. Torres-Jimenez, V. Hernandez, and N. Gonzalez-Hernandez, New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing, Mathematical Problems in Engineering 2012, Article 897027, Table 2(a), row t=3 and k=15; repository and verification statement in Section 6. K. Shokri, L. Moura, and B. Stevens, New Families of Strength-3 Covering Arrays Using Linear Feedback Shift Register Sequences, description of the maintained Colbourn tables and Table 6 improvements; no k=15 ternary improvement is listed. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The checked published interval is 27 through 57. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.For Exact value of CAN(3,15,3): The checked published interval is 27 through 57. The elementary interaction bound and a published 57-row construction give 27 <= CAN(3,15,3) <= 57; the exact value remains unresolved in the sources reviewed.
NIST Covering Array Tables, file ca.3.3^15.txt; 65 don't-care cells completed with zero and replayed in ca3153-artifact-coverage-verifier. math.nist.gov checked 2026-08-01. NIST Covering Array Tables, file ca.3.3^15.txt; 65 don't-care cells completed with zero and replayed in ca3153-artifact-coverage-verifier; Inline CPython standard-library replay of the zero-completed NIST array, executed 2026-07-25. ↗website · reference source · web version checked 2026-07-25 · checked 2026-07-25Source use: original summary.The completed NIST 80-row array covers every interaction. Exhaustive enumeration verifies all 12,285 interaction requirements in an explicit completion of NIST's IPOG-F array. Exhaustive verifier for the NIST array. Standard-library Python decodes the explicit array and verifies every ternary interaction in every triple of columns.Also cited at NIST Covering Array Tables, file ca.3.3^15.txt; 65 don't-care cells completed with zero and replayed in ca3153-artifact-coverage-verifier.Also cited at Inline CPython standard-library replay of the zero-completed NIST array, executed 2026-07-25.For Exact value of CAN(3,15,3): The completed NIST 80-row array covers every interaction. Exhaustive enumeration verifies all 12,285 interaction requirements in an explicit completion of NIST's IPOG-F array. Exhaustive verifier for the NIST array. Standard-library Python decodes the explicit array and verifies every ternary interaction in every triple of columns.
CC0 finite covering-array target with a repository upper bound and an independent baseline.