Content deleted Content added
Motorfingers (talk | contribs) →Known arrays: Added reference to IEEE DataPort database to order 1030 |
almost entirely cs2, standardize on that |
||
| (29 intermediate revisions by 20 users not shown) | |||
Line 1:
{{Short description|Set of marks on a 2d square grid such that no two pairs of marks are the same distance apart}}
{{CS1 config|mode=cs2}}
In mathematics, a '''Costas array''' can be regarded [[geometry|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 (vector)|displacement]] [[Euclidean vector|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.
Costas arrays are named after [[John P. Costas (engineer)|John P. Costas]], who first wrote about them in a 1965 technical report. 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.<ref>{{harvtxt|Costas|1965}}; {{harvtxt|Gilbert|1965}}; [http://nanoexplanations.wordpress.com/2011/10/09/an-independent-discovery-of-costas-arrays/ An independent discovery of Costas arrays], Aaron Sterling, October 9, 2011.</ref>
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.
==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 [[
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:
:<math>\begin{array}{|c|c|c|c|}\hline0&0&0&1\\\hline0&0&1&0\\\hline1&0&0&0\\\hline0&1&0&0\\\hline\end{array}</math> or simply <math>\begin{array}{|c|c|c|c|}\hline&&&\bullet\\\hline&&\bullet&\\\hline\bullet&&&\\\hline&\bullet&&\\\hline\end{array}</math>
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 defines a permutation. This makes it easy to communicate the arrays for a given order of ''N''.
==Known arrays==
Costas array counts are known for orders 1 through 29<ref>{{harvtxt|Beard|2006}}; {{harvtxt|Drakakis|Rickard|Beard|Caballero|2008}}; {{harvtxt|Drakakis|Iorio|Rickard|2011}}; {{harvtxt|Drakakis|Iorio|Rickard|Walsh|2011}}</ref> {{OEIS|A008404}}:
{| border="1" cellpadding="2"
Line 132 ⟶ 113:
|----
|}
Here are some known arrays:
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}
Enumeration of known Costas arrays to order 200,{{sfnp|Beard|2006}} order 500{{sfnp|Beard|2008}} and to order 1030<ref>{{harvtxt|Beard|2017}}; {{citation|url=http://jameskbeard.com/jameskbeard/Files.html#CostasArrays|title=Files for Download: Costas Arrays|first=James K.|last=Beard|accessdate=2020-04-20}} </ref> are available. Although these lists and databases of these Costas arrays are likely near complete, other Costas arrays with orders above 29 that are not in these lists may exist. In general, the currently best known upper bound on the number <math>C(n)</math> of Costas Arrays of order <math>n</math> is of asymptotic form <math>C(n)/n! \le e^{-\Theta(n)}</math>.{{sfnp|Warnke|Correll|Swanson|2023}}
==Constructions==
Line 144 ⟶ 145:
3 is a primitive element modulo 5.
:3<sup>1</sup> = 3 ≡ 3 (mod 5)
:3<sup>2</sup> = 9
:3<sup>3</sup> = 27
:3<sup>4</sup> = 81
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.
Line 157 ⟶ 158:
===Extensions by Taylor, Lempel, and Golomb===
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
More sophisticated methods of generating new Costas arrays by deleting rows and columns of existing Costas arrays that were generated by the Welch, Lempel or Golomb generators were published in 1992.
===Other methods===
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
== Variants ==
Costas arrays on a [[hexagonal lattice]] are known as ''honeycomb arrays''. 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.<ref>{{Cite journal|last1=Blackburn|first1=Simon R.|last2=Panoui|first2=Anastasia|last3=Paterson|first3=Maura B.|last4=Stinson|first4=Douglas R.|date=2010-12-10|title=Honeycomb Arrays|url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r172|journal=The Electronic Journal of Combinatorics|volume=17 |language=en|pages=R172|doi=10.37236/444|issn=1077-8926|doi-access=free}}</ref>
== See also ==
Line 174 ⟶ 178:
==References==
*{{citation
| last1 = Barker
| first1 = L. | last2 = Drakakis
| first2 = K. | last3 = Rickard
| first3 = S. | doi = 10.1109/JPROC.2008.2011947
| issue = 3
Line 184 ⟶ 191:
| url = http://eeme.ucd.ie/~kdrakaka/work/publications/020.On_The_Complexity_Of_The_Verification_Of_The_Costas_Property.pdf
| volume = 97
| year = 2009
| s2cid = 29776660
| access-date = 2011-10-10
| archive-url = https://web.archive.org/web/20120425053202/http://eeme.ucd.ie/~kdrakaka/work/publications/020.On_The_Complexity_Of_The_Verification_Of_The_Costas_Property.pdf
| archive-date = 2012-04-25
| url-status = dead
}}.
*{{citation
|
| contribution = Generating Costas Arrays to Order 200
|
| doi = 10.1109/ciss.2006.286635
| publisher = IEEE
| title = 2006 40th Annual Conference on Information Sciences and Systems| s2cid = 2241386
}}.
*{{citation
| last = Beard | first = James K.
| contribution = Costas array generator polynomials in finite fields
| date = March 2008
| doi = 10.1109/ciss.2008.4558709
| publisher = IEEE
| title = 2008 42nd Annual Conference on Information Sciences and Systems| s2cid = 614347
}}.
*{{citation
| last = Beard | first = James K.
| doi = 10.21227/H21P42
| publisher = IEEE Dataport
| title = Costas arrays and enumeration to order 1030
| url = https://ieee-dataport.org/open-access/costas-arrays-and-enumeration-order-1030
| year = 2017}}.
*{{citation
| last1 = Beard
| first1 = J.
| last2 = Russo
| first2 = J.
| last3 = Erickson
| first3 = K.
| last4 = Monteleone
| first4 = M.
| last5 = Wright
| first5 = M.
| contribution = Combinatoric collaboration on Costas arrays and radar applications
| doi = 10.1109/NRC.2004.1316432
Line 196 ⟶ 237:
| title = IEEE Radar Conference, Philadelphia, Pennsylvania
| url = http://www.costasarrays.org/costasrefs/beard04combinatoric.pdf
| year = 2004
| s2cid = 7733481
| access-date = 2011-10-10
| archive-url = https://web.archive.org/web/20120425053202/http://www.costasarrays.org/costasrefs/beard04combinatoric.pdf
| archive-date = 2012-04-25
| url-status = dead
}}.
*{{citation
| last1 = Beard | first1 = James
| last2 = Russo | first2 = Jon
| last3 = Erickson | first3 = Keith
| last4 = Monteleone | first4 = Michael
| last5 = Wright | first5 = Michael
| date = April 2007
| doi = 10.1109/taes.2007.4285351
| issue = 2
| journal = IEEE Transactions on Aerospace and Electronic Systems
| pages = 522–538
| title = Costas array generation and search methodology
| volume = 43| s2cid = 32271456
| url = https://zenodo.org/record/893374
}}.
*{{citation
| last = Costas | first = J. P. | author-link = John P. Costas (engineer)
Line 204 ⟶ 266:
| year = 1965}}
*{{citation
| last = Costas
| first = J. P. | author-link = John P. Costas (engineer) | doi = 10.1109/PROC.1984.12967
| issue = 8
Line 212 ⟶ 276:
| url = http://costasarrays.org/costasrefs/costas84study.pdf
| volume = 72
| year = 1984
| s2cid = 2742217
| access-date = 2011-10-10
| archive-url = https://web.archive.org/web/20110930054819/http://www.costasarrays.org/costasrefs/costas84study.pdf
| archive-date = 2011-09-30
| url-status = dead
}}.
*{{citation
| last1 = Drakakis | first1 = Konstantinos
| last2 = Rickard | first2 = Scott
| last3 = Beard | first3 = James K.
| last4 = Caballero | first4 = Rodrigo
| last5 = Iorio | first5 = Francesco
| last6 = O'Brien | first6 = Gareth
| last7 = Walsh | first7 = John
| date = October 2008
| doi = 10.1109/tit.2008.928979
| issue = 10
| journal = IEEE Transactions on Information Theory
| pages = 4684–4687
| title = Results of the Enumeration of Costas Arrays of Order 27
| volume = 54| hdl = 2262/59260
| hdl-access = free
}}.
*{{citation
| last1 = Drakakis | first1 = Konstantinos
| last2 = Iorio | first2 = Francesco
| last3 = Rickard | first3 = Scott
| title = The enumeration of Costas arrays of order 28 and its consequences
| journal = Advances in Mathematics of Communications
| year = 2011}}
*{{citation
| last1 = Drakakis | first1 = Konstantinos
| last2 = Iorio | first2 = Francesco
| last3 = Rickard | first3 = Scott
| last4 = Walsh | first4 = John
| date = August 2011
| doi = 10.3934/amc.2011.5.547
| issue = 3
| journal = Advances in Mathematics of Communications
| pages = 547–553
| title = Results of the enumeration of Costas arrays of order 29
| volume = 5| doi-access = free
| hdl = 2262/59260
| hdl-access = free
}}.
*{{citation
| last = Gilbert | first = E. N. | authorlink = Edgar Gilbert
Line 221 ⟶ 330:
| title = Latin squares which contain no repeated digrams
| volume = 7
| year = 1965| issue = 2 }}.
*{{citation
| last = Golomb | first = Solomon W. | authorlink = Solomon W. Golomb
| doi = 10.1016/0097-3165(84)90015-3
| issue = 1
| journal = Journal of Combinatorial Theory | series = Series A
| mr = 749508
| pages = 13–21
| title = Algebraic constructions for Costas arrays
| volume = 37
| year = 1984}}.
*{{citation
| last = Golomb | first = Solomon W. | authorlink = Solomon W. Golomb
| doi = 10.1109/18.144726
| issue = 4
| journal = IEEE Transactions on Information Theory
| mr = 1168761
| pages = 1404–1406
| title = The <math>T_4</math> and <math>G_4</math> constructions for Costas arrays
| volume = 38
| year = 1992}}
*{{citation
| last1 = Golomb | first1 = S. W. | author1-link = Solomon W. Golomb
Line 232 ⟶ 361:
| url = http://www.costasarrays.org/costasrefs/golomb84constructions.pdf
| volume = 72
| year = 1984
| s2cid = 39718506 | access-date = 2011-10-10
| archive-url = https://web.archive.org/web/20110930054835/http://www.costasarrays.org/costasrefs/golomb84constructions.pdf
| archive-date = 2011-09-30
| url-status = dead
}}.
*{{citation
| last = Guy | first = Richard K. | author-link = Richard K. Guy
Line 255 ⟶ 389:
| volume = 542
| year = 1999}}.
*{{citation
| last = Rickard | first = Scott
| contribution = Searching for Costas Arrays using Periodicity Properties
| title = IMA International Conference on Mathematics in Signal Processing
| year = 2004}}.
*{{citation
| last1 = Warnke | first1 = Lutz
| last2 = Correll| first2 = Bill
| last3 = Swanson | first3 = Christopher
| doi = 10.1109/TIT.2022.3202507
| issue = 1
| journal = IEEE Transactions on Information Theory
| mr = 4544975
| pages = 575-581
| title = The density of Costas arrays decays exponentially
| volume = 69
| year = 2023}}.
== External links ==
Line 261 ⟶ 412:
**A008404: [[OEIS:A008404|Number of Costas arrays of order ''n'', counting rotations and flips as distinct.]]
**A001441: [[OEIS:A001441|Number of inequivalent Costas arrays of order ''n'' under dihedral group.]]
* {{
[[Category:Permutations]]
| |||