Name:Enumeration of Costas Arrays of order 27, 28, 29 (and beyond)
Description:Parallel code is run to discover all Costas arrays of a certain order
Abstract:Costas arrays are square arrays of 1s/dots and 0s/blanks, such that there is exactly one dot per row and column, and such that any two linear segments connecting pairs of dots have either different length or different slope. The latter can be rephrased into the following three conditions: a) no four non-collinear dots form a parallelogram; b) no four collinear dots form two equidistant pairs; and c) no three collinear dots are equidistant. Though they originated as time-frequency waveform descriptions in SONAR systems, they soon became objects of mathematical study, due to the many and interesting problems they give rise to in combinatorics, algebra, and number theory.
It is currently unknown whether nxn Costas arrays exist for all orders n. The smallest n for which no Costas array is known are n=32 and 33. There exist some algebraic constructions for Costas arrays, which successfully work for infinitely many n, but not all n. Even where they work, however, they normally fail to recover all existing Costas arrays there.
As of today, the only method guaranteed to produce all Costas arrays in a certain order is brute force enumeration, whereby each of the n! permutation arrays of order n is tested for the Costas property. So far, this task has been accomplished up to n=28, while enumeration of n=29 is currently in progress. The major milestone ahead is the enumeration of n=32, as it is possible that no Costas array will be found there, thus disproving the existence of nxn Costas arrays for all n.
Created:2010-11-08
Last updated:2010-11-08
Software Appliances
Applications Database
