Algebraic constructions for Costas arrays (Q798660)

The following is equivalent to a problem posed by \textit{J. P. Costas} [Medium constraints on sonar design and performance. EASCON Convention Record, 68A-68L (1975)], who encountered it in the context of attempting to construct sonar signal patterns. Problem. For each positive integer n, construct an \(n\times n\) permutation matrix with the property that the \(\left( \begin{matrix} n\\ 2\end{matrix} \right)\) vectors connecting two 1's of the matrix are all distinct as vectors. (That is, no two vectors are equal in both magnitude and slope.) This paper contains the first published proofs of the validity of the Welch and Lempel constructions, as well as a major new construction. As a consequence of all these constructions, \(n\times n\) Costas Arrays are now known to exist for the following positive values of \(n\): (i) \(n=p-1\), \(p\) prime, (ii) \(n=q-2\), \(q=p^ k\) (any prime power), (iii)\(^*\) \(n=q-3\), \(q=p^ k\) (any prime power), (iv)\(^*\) \(n=2^k-4\), \(k\geq 3\). Cases (iii) and (iv) depend on the conjecture that the field of \(q\) elements, \(q>2\), contains primitive roots \(\alpha\) and \(\beta\) (not necessarily distinct) for which \(\alpha +\beta =1.\)