Smallest orders for periodic multidimensional Costas arrays
Write $[a] = \{1, \dots, a\}$. Let $m \ge 2$ and $k$ be integers with $1 \le m - k \le k$, and let $n_1, \dots, n_m \ge 2$ be integers with $$n = \prod_{i=1}^{k} n_i = \prod_{i=k+1}^{m} n_i.$$ For a bijection $\varphi \colon \prod_{i=1}^{k} [n_i] \to \prod_{i=k+1}^{m} [n_i]$ let $S = \{(x, \varphi(x))\} \subset \mathbb{Z}^m$ be its graph and $$\widetilde S = S + (n_1\mathbb{Z} \times \cdots \times n_m\mathbb{Z})$$ its periodic extension. Call $\varphi$ periodic Costas if, for every $t \in \mathbb{Z}^m$, the difference vectors $y - y'$ between distinct points $y, y'$ of $\widetilde S \cap \bigl(t + \prod_{i=1}^{m} [n_i]\bigr)$ are pairwise distinct; the differences are vectors in $\mathbb{Z}^m$, not reduced modulo the side lengths. For $m = 2$ this asks for an $n \times n$ Costas array with a Costas array in every $n \times n$ window of its doubly periodic extension, and Taylor proved that then $n = 2$. Torres and Rubio proved that $n = 2^k$ when $m = 3$ and that $n$ cannot be odd for any $m$, and excluded further shapes with $k = m - 1$; periodic Costas bijections of size $2 \times 2 \times 4$ exist.
Problem. If $\varphi$ is periodic Costas, must $n = 2^k$, that is, $n_1 = \cdots = n_k = 2$?
Source: Torres and Rubio (2023), Conjecture 1, a higher-dimensional analogue of Taylor's theorem (1984) for m = 2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT
- Keywords
- AIM Open Applied Problems, Costas arrays, permutation arrays
References
@article{torres2023,
author = {Torres, Jaziel and Rubio, Ivelisse},
title = {Multidimensional {C}ostas arrays and their periodicity},
journal = {IEEE Trans. Inform. Theory},
volume = {69},
number = {8},
year = {2023},
pages = {5032--5040},
doi = {10.1109/TIT.2023.3264951},
eprint = {2208.02378},
archivePrefix = {arXiv},
}
@techreport{taylor1984,
author = {Taylor, Herbert},
title = {Non-attacking rooks with distinct differences},
institution = {Communication Sciences Institute, University of Southern California},
number = {CSI-84-03-02},
year = {1984},
}
@misc{aim-periodic-costas,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Smallest orders for periodic multidimensional Costas arrays}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/627-periodic-costas.md},
note = {Entry 627 at commit a153f46, 2026-10-13},
}
Resolution claims
We give a bijection from $[2]\times[3]$ onto itself whose graph, extended periodically in four coordinates, has distinct nonzero ordered ordinary difference vectors in every $2\times3\times2\times3$ window. Its order is $6$, whereas the proposed minimum-order restriction of Rubio and Torres would require $4$. A short proof keeps the signs of the two binary-coordinate differences and reduces the other two differences modulo …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-17 | Open → Solution claimed | The registry's curators | A four-dimensional periodic Costas array of order six v1 recorded from AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00367, "Smallest orders for periodic multidimensional Costas arrays", clopen.solutions.