# P2612: Existence of a Costas array of order 32

- ID: `P2612`
- Reference: `costas-array-order-32`
- Page: https://theoremdb.org/statements/P2612
- Record maturity: Reviewed problem with recorded work

## Problem

Does there exist a permutation \(\pi\) of \(\{0,\ldots,31\}\) such that all displacement vectors \((j-i,\pi(j)-\pi(i))\), for \(0\le i<j<32\), are distinct?

### Remarks

- **Remark.** Such a permutation is a Costas array of order 32.
- **Remark.** For a fixed horizontal displacement d, the values pi(i+d)-pi(i) must be pairwise distinct.

### What counts as a solution

- Give and directly verify a 32-entry Costas permutation, or exhaust all canonical permutations with a machine-checkable decomposition and no omitted symmetry class.

## Status

No verified order-32 Costas permutation or exhaustive nonexistence certificate was found in the audited primary literature. [1](#reference-1) [3](#reference-3) [4](#reference-4) [5](#reference-5)

## Work

### Evidence for the current status

**Claim 1 (Existence at order 32 remains open).** No verified order-32 Costas permutation or exhaustive nonexistence certificate was found in the audited primary literature.

The candidate remains unresolved. Vulakh and Finkel describe order 32 as unsolved in their 2022 peer-reviewed paper. Their search produced near solutions rather than a Costas permutation. The 2022 paper `The Density of Costas Arrays Decays Exponentially` likewise states that existence at order 32 remains unknown.

A fresh 2026 paper by Gulec and Abolghasemi reports that exhaustive enumeration reaches order 29 and bases its higher-order experiments on Beard's public collection of known arrays. Beard's database page says that its generated collection reaches order 1030, while exhaustive-search additions stop at orders 28 and 29. These records provide a current cross-check against a published witness. Database absence cannot establish nonexistence.

The acceptance condition therefore remains unchanged. A positive resolution needs a 32-entry permutation whose 496 displacement vectors pass an exact duplicate check. A negative resolution needs an exhaustive search certificate that covers every symmetry class.

### Background and intake notes

The search is finite, route-concentrated, and expensive enough that certified subtree exclusions would prevent substantial repeated work.

- Original intake status: Vulakh and Finkel reported in 2022 that order 32 remained the smallest unresolved order. Status after that paper remains unverified.
- Canonicalize complete arrays under the eight symmetries of the square before splitting the tree. Store used vertical differences separately for each horizontal displacement.
- Trap: the square symmetries map corners to corners, so fixing pi(0)=0 restricts the search to arrays with a corner dot. Prefix counts under that restriction do not cover every symmetry class.

- Recorded example: At order 6, [2,0,5,1,4,3] is a Costas permutation under zero-based indexing.

### Other known results

- **Claim 2** (supported): After more than 10,000 CPU-days, mDRACO reported an order-32 permutation with 17 Costas-property violations. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): The principal Welch and Golomb parameter routes miss order 32, and the current known-array records contain no order-32 witness. [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks the permutation condition and every unordered pair of dots.

### Computational notes

- A fresh exact depth-first search in the corner-dot subclass fixed pi(0)=0 and enforced the Costas difference condition. The numbers of valid prefixes of lengths 2, 3, 4, 5, and 6 were 31, 915, 25655, 667122, and 16035001. These counts certify only that subclass.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `costas-array-order-32`, 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>David Vulakh and Raphael Finkel, Parallel m-dimensional relative ant colony optimization (mDRACO) for the Costas-array problem, Soft Computing 26(12) (2022), 5765-5772. David Vulakh and Raphael Finkel, Parallel m-dimensional relative ant colony optimization (mDRACO) for the Costas-array problem, Soft Computing 26 (2022), 5765-5772, Conclusion and Appendix https://doi.org/10.1007/s00500-022-06969-1
   - Also cited at Vulakh and Finkel 2022, Conclusion and Appendix
   - Also cited at Vulakh and Finkel 2022, Section 4, page 5771, and Appendix: Arrays discovered
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Reports an order-32 heuristic search whose best permutation still has 17 Costas violations.
   - Source named by the research packet.
2. <a id="reference-2"></a>Ken Taylor, Scott Rickard, and Konstantinos Drakakis, Costas Arrays: Survey, Standardization, and MATLAB Toolbox, ACM Transactions on Mathematical Software 37(4) (2011), Article 41, 31 pp. Survey definitions, construction taxonomy, and status tables https://doi.org/10.1145/1916461.1916465
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - Fixes the Costas-array definitions and construction taxonomy used to assess the order-32 status.
3. <a id="reference-3"></a>Lutz Warnke, Bill Correll Jr., and Christopher N. Swanson, The Density of Costas Arrays Decays Exponentially, IEEE Transactions on Information Theory 69(1) (2023), 575-581. Introduction, Theorem 1, and Table I https://mathweb.ucsd.edu/~lwarnke/CostasArrayExponentialDecay.pdf
   - journal_article; primary source; author-hosted version of record checked 2026-07-26; checked 2026-07-25
   - Source use: citation_only
   - Proves exponential decay of Costas-array density and supplies the enumeration context for the order-32 search.
4. <a id="reference-4"></a>Fatih Gulec and Vahid Abolghasemi, Universal Costas Matrices: Towards a General Framework for Costas Array Construction, arXiv:2602.03407v1 (2026). Fatih Gulec and Vahid Abolghasemi, Universal Costas Matrices: Towards a General Framework for Costas Array Construction, 2026, Introduction and Table I https://arxiv.org/abs/2602.03407
   - preprint; reference source; arXiv:2602.03407v1; checked 2026-07-25
   - Source use: citation_only
   - Surveys standard Costas constructions and records the continuing gap at order 32.
5. <a id="reference-5"></a>James K. Beard, Costas Arrays and Enumeration to Order 1030, IEEE DataPort (2017). IEEE DataPort database description, download index, and CC BY 4.0 notice https://jameskbeard.com/Files.html
   - dataset; dataset source; dataset snapshot checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - Provides the maintained Costas enumeration files checked for an order-32 witness and states their CC BY 4.0 terms.