In mathematics, a Costas array can be regarded geometrically as a set of n points, each at the center of a square in an n×n square tiling such that each row or column contains only one point, and all of the n(n − 1)/2 displacement vectors between each pair of dots are distinct.
This results in an ideal "thumbtack" auto-ambiguity function, making the arrays useful in applications such as sonar and radar.
Costas arrays can be regarded as two-dimensional cousins of the one-dimensional Golomb ruler construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array radar engineering.
Independently, Edgar Gilbert also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays.
[1] The general enumeration of Costas arrays is an open problem in computer science and finding an algorithm that can solve it in polynomial time is an open research question.
Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n. Arrays are usually described as a series of indices specifying the column for any row.
Since it is given that any column has only one point, it is possible to represent an array one-dimensionally.
For instance, the following is a valid Costas array of order N = 4: There are dots at coordinates: (1,2), (2,1), (3,3), (4,4) Since the x-coordinate increases linearly, we can write this in shorthand as the set of all y-coordinates.
The number of Welch–Costas arrays which exist for a given size depends on the totient function.
The Lempel–Golomb construction takes α and β to be primitive elements of the finite field GF(q) and similarly defines
If α + β = 1 then the first row and column may be deleted to form another Costas array of size q − 3: such a pair of primitive elements exists for every prime power q>2.
Generation of new Costas arrays by adding or subtracting a row/column or two with a 1 or a pair of 1's in a corner were published in a paper focused on generation methods[7] and in Golomb and Taylor's landmark 1984 paper.
[9] There is no upper limit on the order for which these generators will produce Costas arrays.
Two methods that found Costas arrays up to order 52 using more complicated methods of adding or deleting rows and columns were published in 2004[10] and 2007.
It has been shown that there are only finitely many such arrays, which must have an odd number of elements, arranged in the shape of a hexagon.
Currently, 12 such arrays (up to symmetry) are known, which has been conjectured to be the total number.