Content deleted Content added
→Numerical representation: beautify |
almost entirely cs2, standardize on that |
||
| (5 intermediate revisions by 5 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==
Line 131 ⟶ 133:
{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 164 ⟶ 166:
== 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|
== See also ==
Line 190 ⟶ 192:
| 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
Line 201 ⟶ 204:
| doi = 10.1109/ciss.2006.286635
| publisher = IEEE
| title = 2006 40th Annual Conference on Information Sciences and Systems
}}.
*{{citation
| last = Beard | first = James K.
Line 208 ⟶ 212:
| doi = 10.1109/ciss.2008.4558709
| publisher = IEEE
| title = 2008 42nd Annual Conference on Information Sciences and Systems
}}.
*{{citation
| last = Beard | first = James K.
Line 233 ⟶ 238:
| 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
Line 250 ⟶ 256:
| pages = 522–538
| title = Costas array generation and search methodology
| volume = 43
| url = https://zenodo.org/record/893374
}}.
*{{citation
| last = Costas | first = J. P. | author-link = John P. Costas (engineer)
Line 269 ⟶ 277:
| 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
Line 310 ⟶ 319:
| title = Results of the enumeration of Costas arrays of order 29
| volume = 5| doi-access = free
| hdl = 2262/59260
| hdl-access = free
}}.
*{{citation
Line 319 ⟶ 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
Line 351 ⟶ 362:
| 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
Line 383 ⟶ 394:
| 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 ==
| |||