Constructions and properties of Costas arrays

A Costas array is an n × n array of dots and blanks with exactly one dot in each row and column, and with distinct vector differences between all pairs of dots. As a frequency-hop pattern for radar or sonar, a Costas array has an optimum ambiguity function, since any translation of the array parallel to the coordinate axes produces at most one out-of-phase coincidence. We conjecture that n × n Costas arrays exist for every positive integer n. Using various constructions due to L. Welch, A. Lempel, and the authors, Costas arrays are shown to exist when n = p - 1, n = q - 2, n = q - 3, and sometimes when n = q - 4 and n = q - 5, where p is a prime number, and q is any power of a prime number. All known Costas array constructions are listed for 271 values of n up to 360. The first eight gaps in this table occur at n = 32, 33, 43, 48, 49, 53, 54, 63. (The examples for n = 19 and n = 31 were obtained by augmenting Welch's construction.) Let C(n) denote the total number of n × n Costas arrays. Costas calculated C(n) for n ≤ 12. Recently, John Robbins found C(13) = 12828. We exhibit all the arrays for n ≤ 8. From Welch's construction, C(n) ≥ 2n for infinitely many n. Some Costas arrays can be sheared into "honeycomb arrays." All known honeycomb arrays are exhibited, corresponding to n = 1, 3, 7, 9, 15, 21, 27, 45. Ten unsolved problems are listed.