In mathematics, a Costas array can be regarded geometrically

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

 as a set of n points lying on the square

Square (geometry)

In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...

s of a n×n checkerboard

Checkerboard

A checkerboard or chequerboard is a board of chequered pattern on which English draughts is played. It is an 8×8 board and the 64 squares are of alternating dark and light color, often red and black....

, such that each row or column contains only one point, and that all of the n(n − 1)/2 displacement

Displacement (vector)

A displacement is the shortest distance from the initial to the final position of a point P. Thus, it is the length of an imaginary straight path, typically distinct from the path actually travelled by P...

 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

Sonar

Sonar is a technique that uses sound propagation to navigate, communicate with or detect other vessels...

 and radar

Radar

Radar is an object-detection system which uses radio waves to determine the range, altitude, direction, or speed of objects. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, weather formations, and terrain. The radar dish or antenna transmits pulses of radio...

. Costas arrays can be regarded as two-dimensional cousins of the one-dimensional Golomb ruler

Golomb ruler

In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length...

 construction, and, as well as being of mathematical interest, have similar applications in experimental design and phased array

Phased array

In wave theory, a phased array is an array of antennas in which the relative phases of the respective signals feeding the antennas are varied in such a way that the effective radiation pattern of the array is reinforced in a desired direction and suppressed in undesired directions.An antenna array...

 radar engineering.

Costas arrays are named after John P. Costas, who first wrote about them in a 1965 technical report. Independently, Edgar Gilbert

Edgar Gilbert

Edgar Nelson Gilbert was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model for random...

 also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays.

Numerical representation

A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as binary matrices, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also permutation matrices

Permutation matrix

In mathematics, in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere...

. 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:

0	0	0	1
0	0	1	0
1	0	0	0
0	1	0	0

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 position in the set would then be the x-coordinate. Observe: {2,1,3,4} would describe the aforementioned array. This makes it easy to communicate the arrays for a given order of N.

Known arrays

All Costas arrays of size up to and including 27×27 are known http://www.costasarrays.org/Enumeration27TalkWeb.pdf. Costas arrays are known for infinitely many sizes because there exist two methods of generating them, both of which work near primes (of which there are infinitely many) and powers of primes. These are known as the Welch and Lempel-Golomb generation methods, and come from a branch of mathematics known as finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 theory.

The following table describes all possible Costas arrays of size up to six 6×6:

N = 1

{1}

N = 2

{1,2}
{2,1}

N = 3

{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}

N = 4

{1,2,4,3}
{1,3,4,2}
{1,4,2,3}
{2,1,3,4}
{2,3,1,4}
{2,4,3,1}
{3,1,2,4}
{3,2,4,1}
{3,4,2,1}
{4,1,3,2}
{4,2,1,3}
{4,3,1,2}

N = 5

{1,3,4,2,5}
{1,4,2,3,5}
{1,4,3,5,2}
{1,4,5,3,2}
{1,5,3,2,4}
{1,5,4,2,3}
{2,1,4,5,3}
{2,1,5,3,4}
{2,3,1,5,4}
{2,3,5,1,4}
{2,3,5,4,1}
{2,4,1,5,3}
{2,4,3,1,5}
{2,5,1,3,4}
{2,5,3,4,1}
{2,5,4,1,3}
{3,1,2,5,4}
{3,1,4,5,2}
{3,1,5,2,4}
{3,2,4,5,1}
{3,4,2,1,5}
{3,5,1,4,2}
{3,5,2,1,4}
{3,5,4,1,2}
{4,1,2,5,3}
{4,1,3,2,5}
{4,1,5,3,2}
{4,2,3,5,1}
{4,2,5,1,3}
{4,3,1,2,5}
{4,3,1,5,2}
{4,3,5,1,2}
{4,5,1,3,2}
{4,5,2,1,3}
{5,1,2,4,3}
{5,1,3,4,2}
{5,2,1,3,4}
{5,2,3,1,4}
{5,2,4,3,1}
{5,3,2,4,1}

N = 6

{1,2,5,4,6,3}
{1,2,6,4,3,5}
{1,3,2,5,6,4}
{1,3,2,6,4,5}
{1,3,6,4,5,2}
{1,4,3,5,6,2}
{1,4,5,3,2,6}
{1,4,6,5,2,3}
{1,5,3,4,6,2}
{1,5,3,6,2,4}
{1,5,4,2,3,6}
{1,5,4,6,2,3}
{1,5,6,2,4,3}
{1,5,6,3,2,4}
{1,6,2,4,5,3}
{1,6,3,2,4,5}
{1,6,3,4,2,5}
{1,6,3,5,4,2}
{1,6,4,3,5,2}
{2,3,1,5,4,6}
{2,3,5,4,1,6}
{2,3,6,1,5,4}
{2,4,1,6,5,3}
{2,4,3,1,5,6}
{2,4,3,6,1,5}
{2,4,5,1,6,3}
{2,4,5,3,6,1}
{2,5,1,6,3,4}
{2,5,1,6,4,3}
{2,5,3,4,1,6}
{2,5,3,4,6,1}
{2,5,4,6,3,1}
{2,6,1,4,3,5}
{2,6,4,3,5,1}
{2,6,4,5,1,3}
{2,6,5,3,4,1}
{3,1,2,5,4,6}
{3,1,5,4,6,2}
{3,1,5,6,2,4}
{3,1,6,2,5,4}
{3,1,6,5,2,4}
{3,2,5,1,6,4}
{3,2,5,6,4,1}
{3,2,6,1,4,5}
{3,2,6,4,5,1}
{3,4,1,6,2,5}
{3,4,2,6,5,1}
{3,4,6,1,5,2}
{3,5,1,2,6,4}
{3,5,1,4,2,6}
{3,5,2,1,6,4}
{3,5,4,1,2,6}
{3,5,4,2,6,1}
{3,5,6,1,4,2}
{3,5,6,2,1,4}
{3,6,1,5,4,2}
{3,6,4,5,2,1}
{3,6,5,1,2,4}
{4,1,2,6,5,3}
{4,1,3,2,5,6}
{4,1,6,2,3,5}
{4,2,1,5,6,3}
{4,2,1,6,3,5}
{4,2,3,5,1,6}
{4,2,3,6,5,1}
{4,2,5,6,1,3}
{4,2,6,3,5,1}
{4,2,6,5,1,3}
{4,3,1,6,2,5}
{4,3,5,1,2,6}
{4,3,6,1,5,2}
{4,5,1,3,2,6}
{4,5,1,6,3,2}
{4,5,2,1,3,6}
{4,5,2,6,1,3}
{4,6,1,2,5,3}
{4,6,1,5,2,3}
{4,6,2,1,5,3}
{4,6,2,3,1,5}
{4,6,5,2,3,1}
{5,1,2,4,3,6}
{5,1,3,2,6,4}
{5,1,3,4,2,6}
{5,1,6,3,4,2}
{5,2,3,1,4,6}
{5,2,4,3,1,6}
{5,2,4,3,6,1}
{5,2,6,1,3,4}
{5,2,6,1,4,3}
{5,3,2,4,1,6}
{5,3,2,6,1,4}
{5,3,4,1,6,2}
{5,3,4,6,2,1}
{5,3,6,1,2,4}
{5,4,1,6,2,3}
{5,4,2,3,6,1}
{5,4,6,2,3,1}
{6,1,3,4,2,5}
{6,1,4,2,3,5}
{6,1,4,3,5,2}
{6,1,4,5,3,2}
{6,1,5,3,2,4}
{6,2,1,4,5,3}
{6,2,1,5,3,4}
{6,2,3,1,5,4}
{6,2,3,5,4,1}
{6,2,4,1,5,3}
{6,2,4,3,1,5}
{6,3,1,2,5,4}
{6,3,2,4,5,1}
{6,3,4,2,1,5}
{6,4,1,3,2,5}
{6,4,5,1,3,2}
{6,4,5,2,1,3}
{6,5,1,3,4,2}
{6,5,2,3,1,4}

A full database of the arrays for all sizes which have been exhaustively checked is available http://osl-vps-4.ucd.ie/downloader
It is not known whether Costas arrays exist for all sizes. Currently, the smallest sizes for which no arrays are known are 32×32 and 33×33.

Welch

A Welch–Costas array, or just Welch array, is a Costas array generated using the following method, first discovered by Edgar Gilbert

Edgar Gilbert

Edgar Nelson Gilbert was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model for random...

 in 1965 and rediscovered in 1982 by Lloyd R. Welch

Lloyd R. Welch

Lloyd Richard Welch is a noted American information theorist, and co-inventor of the Baum–Welch algorithm.Welch received his B.S. in mathematics from the University of Illinois, 1951, and Ph.D. in mathematics from the California Institute of Technology, 1958, under advisor Frederic Bohnenblust...

.
The Welch–Costas array is constructed by taking a primitive root

Primitive root modulo n

In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...

 g of a prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 p and defining the array A by if , otherwise 0. The result is a Costas array of size p − 1.

Example:

3 is a primitive element of 5.

3^1 = 3

3^2 = 9 = 4 (mod 5)

3^3 = 27 = 2 (mod 5)

3^4 = 81 = 1 (mod 5)

Therefore [3 4 2 1] is a Costas permutation. More specifically, this is an exponential Welch array. The transposition of the array is a logarithmic Welch array.

The number of Welch–Costas arrays which exist for a given size depends on the totient function

Euler's totient function

In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...

.

Lempel–Golomb

The Lempel–Golomb construction takes α and β to be primitive elements of the finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 GF(q) and similarly defines if , otherwise 0. The result is a Costas array of size q − 2. If α + β = 1 then the first row and column may be deleted to form another Costas array of size q − 3: it is not known whether there is such a pair of primitive elements for every prime power q.

External links

• Information clearinghouse concerning Costas arrays and their study.
• MacTech
  MacTech
  MacTech is the journal of Apple technology, a monthly magazine for software developers, system administrators, and other technical users of the Apple Macintosh line of computers....
  
   1999 Programmer's challenge: Costas arrays
• On-Line Encyclopedia of Integer Sequences
  On-Line Encyclopedia of Integer Sequences
  The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
  
  :
  • A008404: Number of Costas arrays of order n, counting rotations and flips as distinct.
  • A001441: Number of inequivalent Costas arrays of order n under dihedral group.