The Deficiency of Costas Arrays

A Costas array is a permutation array in which the vectors joining pairs of 1s are all distinct. The toroidal vectors of a permutation array are the vectors occurring when the array is written on a torus, and the deficiency of a permutation array of order n is the number of toroidal vectors, out of the (n-1)² possible, which are missing from the array. The smallest deficiency among all permutation arrays of order q-1, where q is a power of a prime other than 3, is known, and it is of interest to find examples of permutation arrays attaining this minimum value. The deficiency of Costas arrays is studied computationally and theoretically. It is shown that all Welch Costas arrays of a given order have the same deficiency. It is shown that the deficiency of Golomb-Rickard Costas arrays of order q-1 attains the minimum value over all permutation arrays when q is a power of a prime other than 3. Computational experiments show that the deficiency distribution of Costas arrays of a given order acts as a filter that highlights the Welch Costas arrays, isolates the Golomb-Rickard Costas arrays, and gives further insights into the structure of other Costas arrays. In particular, four Costas arrays with exceptionally small deficiency are recognised, and it is asked if they could be used to identify a new algebraic construction for Costas arrays.