Costas arrays at every order
A permutation $f$ of $\{1, \dots, n\}$ is a Costas permutation, and its permutation array a Costas array of order $n$, if for every $h \in \{1, \dots, n-1\}$ the integers $$f(i+h) - f(i), \qquad 1 \le i \le n - h,$$ are pairwise distinct; the differences are taken in $\mathbb{Z}$, not modulo $n$. Costas introduced these arrays as frequency-hopping patterns for sonar. Welch's construction gives Costas arrays of order $p - 1$ for every prime $p$, and the Lempel–Golomb construction gives order $q - 2$ for every prime power $q \ge 3$; variants of these constructions and computer searches give further orders.
Problem. Does a Costas array of order $n$ exist for every positive integer $n$? A negative answer requires a proof of nonexistence at some order; the failure of a search or of particular algebraic constructions does not suffice.
Source: Golomb and Taylor (1984); see Drakakis (2011), Problem 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT
- Keywords
- AIM Open Applied Problems, Costas arrays, permutation arrays
References
@article{golomb1984taylor,
author = {Golomb, Solomon W. and Taylor, Herbert},
title = {Constructions and properties of {C}ostas arrays},
journal = {Proc. IEEE},
volume = {72},
number = {9},
year = {1984},
pages = {1143--1163},
doi = {10.1109/PROC.1984.12994},
}
@misc{drakakis2011,
author = {Drakakis, Konstantinos},
title = {Open problems in {C}ostas arrays},
year = {2011},
eprint = {1102.5727},
archivePrefix = {arXiv},
}
@article{costas1984,
author = {Costas, John P.},
title = {A study of a class of detection waveforms having nearly ideal range--{D}oppler ambiguity properties},
journal = {Proc. IEEE},
volume = {72},
number = {8},
year = {1984},
pages = {996--1009},
doi = {10.1109/PROC.1984.12967},
}
@article{golomb1984,
author = {Golomb, Solomon W.},
title = {Algebraic constructions for {C}ostas arrays},
journal = {J. Combin. Theory Ser. A},
volume = {37},
number = {1},
year = {1984},
pages = {13--21},
doi = {10.1016/0097-3165(84)90015-3},
}
@misc{aim-costas-all-orders,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Costas arrays at every order}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/623-costas-all-orders.md},
note = {Entry 623 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00337, "Costas arrays at every order", clopen.solutions.