A Costas array is a permutation array for which no two line segments joining a pair of distinct ‘1’ entries have the same length and slope. This property can be used to control the frequencies of a sequence of sonar pulses, so that both the distance and velocity of a target can be correctly determined even in the presence of noise. Despite an extensive literature and massive computer searches, the only known constructions of Costas arrays are infinite families due to Welch (1982) and Golomb (1984), and minor variations. All 18,223 inequivalent Costas arrays of order at most 29 are known from exhaustive search, but only about 3% of those are explained by known constructions.

In 2014, Jane Wodlinger and I discovered numerically that the histogram of deficiency values for all Costas arrays of a given order appears to isolate three classes of Costas arrays, only two of which belong to known constructions; we suggested that the third class might arise from an algebraic construction that has yet to be identified. We also used combinatorial and probabilistic arguments to prove exact and asymptotic results for when a Costas array can contain an all-zero square corner region, proving a 2010 conjecture due to Russo, Erickson and Beard.

A symmetric Costas array of order 18 with anomalously small deficiency.