×

Algebraic constructions for Costas arrays. (English) Zbl 0547.05020

The following is equivalent to a problem posed by 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.\)
Reviewer: J.Longyear

MSC:

05B30 Other designs, configurations
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Costas, J. P., Medium constraints on sonar design and performance, (EASCON Convention Record (1975)), 68A-68L
[2] Golomb, S. W.; Taylor, H., Two-dimensional synchronization patterns for minimum ambiguity, IEEE Trans. Inform. Theory, IT-28, No. 4 (1982)
[3] Golomb, S. W., Theory of transformation groups of polynomials over GF(2) with applications to shift register sequences, Inform. Sci., 1, No. 1, 87-109 (1968) · Zbl 0238.20060
[4] Golomb, S. W., Cyclotomic polynomials and factorization theorems, Amer. Math. Monthly, 85, No. 9, 734-737 (1978) · Zbl 0403.12002
[5] Golomb, S. W., Obtaining specified irreducible polynomials over finite fields, SIAM J. Algebra Discrete Math., 1, No. 4, 411-418 (1980) · Zbl 0498.12017
[6] Moreno, Oscar, On primitive elements of trace equal to 1 in \(GF (2^m )\), Discrete Math., 41, No. 1, 53-56 (1982) · Zbl 0485.12015
[7] Davenport, H., Bases for finite fields, J. London Math. Soc., 43, No. 169, 21-39 (1968), Part 1 · Zbl 0159.33901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.