# P2634: Exact value of CAN(3,15,3)

- ID: `P2634`
- Reference: `covering-array-3-15-3`
- Page: https://theoremdb.org/statements/P2634
- Record maturity: Reviewed problem with recorded work

## 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.

### Remarks

- **Remark.** Rows may repeat, although repeats never help a minimum array.
- **Remark.** Column permutations and independent symbol permutations preserve the covering property.

### What 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.

## Status

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. [3](#reference-3) [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

Both witness arrays and nonisomorphic partial-array exclusions are compact, independently verifiable records.

- Original intake status: The NIST page supplies an 80-row construction for k=15. It is a construction table and does not certify a matching lower bound. A current CATables audit is still required before asserting the best-known interval.
- Normalize the first few columns under row, column, and symbol permutations. For lower bounds, record every nonisomorphic partial array used in a juxtaposition or SAT proof.
- Trap: the 80-row repository entry is an incumbent, not an exact value. A zero row may be normalized in one column only after the relevant symbol symmetry is proved.

- Recorded example: NIST lists an 80-row construction. A separate simple randomized greedy run reached 82 rows under seed 120315.

### Other known results

- **Computation 1** (reproduced): Exhaustive enumeration verifies all 12,285 interaction requirements in an explicit completion of NIST's IPOG-F array. [4](#reference-4)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python decodes the explicit array and verifies every ternary interaction in every triple of columns. [4](#reference-4)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `covering-array-3-15-3`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 construction table checked 2026-07-24 https://math.nist.gov/coveringarrays/ipof/tables/table.3.3.html
   - Also cited at 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-25
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>Kianoosh Shokri and Lucia Moura, “New Families of Strength‐3 Covering Arrays Using Linear Feedback Shift Register Sequences”. Journal of Combinatorial Designs 33(4) (2025), 156-171. DOI 10.1002/jcd.21963. 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 https://doi.org/10.1002/jcd.21963
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>Himer Avila-George, Jose Torres-Jimenez, and Vicente Hernández, “New Bounds for Ternary Covering Arrays Using a Parallel Simulated Annealing”. Mathematical Problems in Engineering 2012(1) (2012), 897027. DOI 10.1155/2012/897027. 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 https://doi.org/10.1155/2012/897027
   - Also cited at Table 2(a), t=3, k=15, best-known and cooperative-search sizes both 57
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - 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.
4. <a id="reference-4"></a>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 https://math.nist.gov/coveringarrays/ipof/cas/t%3D3/v%3D3/ca.3.3%5E15.txt.zip
   - 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
   - dataset; primary source; web version checked 2026-07-25; checked 2026-08-01
   - Source use: original_summary
   - 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.