Namespaces
Variants
Actions

Difference between revisions of "Costas array"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
''of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104402.png" />''
+
<!--
 +
c1104402.png
 +
$#A+1 = 92 n = 2
 +
$#C+1 = 92 : ~/encyclopedia/old_files/data/C110/C.1100440 Costas array
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104403.png" /> permutation matrix in which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104404.png" /> line segments connecting pairs of ones in the matrix are distinct as vectors, i.e., no two agree in both magnitude and slope. Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104405.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104406.png" /> in the matrix, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104407.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104408.png" />, and at least three of these four ordered pairs are distinct, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c1104409.png" /> equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044010.png" />, then
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044011.png" /></td> </tr></table>
+
''of order  $  n $''
  
All known (1996) general constructions for Costas arrays (see [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]]) involve primitive roots in finite fields (cf. [[Field|Field]]). The Welch construction, for every prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044012.png" />, gives a Costas array of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044013.png" /> by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044014.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044016.png" /> is a [[Primitive root|primitive root]] modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044017.png" />. Removing row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044018.png" /> and column <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044019.png" /> from this construction leaves a Costas array of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044020.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044021.png" /> is used as the primitive root modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044022.png" />, the array can be further reduced to order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044023.png" />.
+
An  $  ( n \times n ) $
 +
permutation matrix in which the  $  { {n ( n - 1 ) } / 2 } $
 +
line segments connecting pairs of ones in the matrix are distinct as vectors, i.e., no two agree in both magnitude and slope. Thus, if  $  a _ {ij }  = a _ {kl }  = 1 $
 +
and  $  a _ {mn }  = a _ {pq }  = 1 $
 +
in the matrix, with  $  ( i,j ) \neq ( k,l ) $,
 +
$  ( m,n ) \neq ( p,q ) $,
 +
and at least three of these four ordered pairs are distinct, and if  $  | {( a _ {ij }  ,a _ {kl }  ) } | ^ {2} = ( k - i )  ^ {2} + ( l - j )  ^ {2} $
 +
equals  $  | {( a _ {mn }  ,a _ {pq }  ) } |  ^ {2} = ( p - m )  ^ {2} + ( q - n )  ^ {2} $,  
 +
then
  
In Golomb's construction, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044025.png" /> are any two primitive elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044026.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044027.png" />, a Costas array of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044028.png" /> is obtained by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044029.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044030.png" />. (The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044031.png" /> had been discovered by A. Lempel.) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044032.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044033.png" />, so that by removing the first row and first column, a Costas array or order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044034.png" /> is obtained. As shown in [[#References|[a6]]], for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044035.png" /> one can find primitive roots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044037.png" /> (not necessarily distinct) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044038.png" />.
+
$$
 +
\left | { {
 +
\frac{( l - j ) }{( k - i ) }
 +
} } \right | \neq \left | { {
 +
\frac{( q - n ) }{( p - m ) }
 +
} } \right | .
 +
$$
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044039.png" />, or any prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044040.png" />, and for no other finite fields, there is a primitive root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044041.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044042.png" />. Thus, in the Lempel construction, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044043.png" />, so that if the first two rows and first two columns are removed, a (symmetric) Costas array or order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044044.png" /> results. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044045.png" />, or any prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044046.png" />, there are primitive roots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044048.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044050.png" />. In this case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044053.png" />. By successive removal of rows and columns Costas arrays of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044056.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044057.png" /> are obtained for these values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044058.png" />.
+
All known (1996) general constructions for Costas arrays (see [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]]) involve primitive roots in finite fields (cf. [[Field|Field]]). The Welch construction, for every prime  $  p > 2 $,  
 +
gives a Costas array of order $  p - 1 $
 +
by setting  $  a _ {ij }  = 1 $
 +
when  $  j = g  ^ {i} ( { \mathop{\rm mod} } p ) $,  
 +
where  $  g $
 +
is a [[Primitive root|primitive root]] modulo  $  p $.  
 +
Removing row  $  p - 1 $
 +
and column  $  1 $
 +
from this construction leaves a Costas array of order  $  p - 2 $.  
 +
When  $  g = 2 $
 +
is used as the primitive root modulo  $  p $,  
 +
the array can be further reduced to order  $  p - 3 $.
  
In some cases a Costas array of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044059.png" /> can be obtained from one of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044060.png" /> by adjoining a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044061.png" /> in an exterior corner, i.e., in one of the positions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044064.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044065.png" />. Several prime-order examples were obtained in this way from a Welch example of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044066.png" />.
+
In Golomb's construction, if  $  \alpha $
 +
and  $  \beta $
 +
are any two primitive elements in  $  { \mathop{\rm GF} } ( q ) $,
 +
for  $  q > 2 $,
 +
a Costas array of order $  q - 2 $
 +
is obtained by setting  $  a _ {ij }  = 1 $
 +
whenever  $  \alpha  ^ {i} + \beta  ^ {j} = 1 $.
 +
(The case  $  \alpha = \beta $
 +
had been discovered by A. Lempel.) If  $  \alpha + \beta = 1 $,  
 +
then  $  a _ {11 }  = 1 $,  
 +
so that by removing the first row and first column, a Costas array or order  $  q - 3 $
 +
is obtained. As shown in [[#References|[a6]]], for every  $  q > 2 $
 +
one can find primitive roots  $  \alpha $
 +
and  $  \beta $(
 +
not necessarily distinct) with  $  \alpha + \beta = 1 $.
  
The total number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044067.png" /> of Costas arrays of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044068.png" /> is known (1996) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044069.png" /> (see the table), with a local maximum at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044070.png" />.''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044071.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044072.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044073.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044074.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">2</td> <td colname="2" style="background-color:white;" colspan="1">2</td> <td colname="3" style="background-color:white;" colspan="1">13</td> <td colname="4" style="background-color:white;" colspan="1">12828</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">3</td> <td colname="2" style="background-color:white;" colspan="1">4</td> <td colname="3" style="background-color:white;" colspan="1">14</td> <td colname="4" style="background-color:white;" colspan="1">17252</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">4</td> <td colname="2" style="background-color:white;" colspan="1">12</td> <td colname="3" style="background-color:white;" colspan="1">15</td> <td colname="4" style="background-color:white;" colspan="1">19612</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">5</td> <td colname="2" style="background-color:white;" colspan="1">40</td> <td colname="3" style="background-color:white;" colspan="1">16</td> <td colname="4" style="background-color:white;" colspan="1">21104</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">6</td> <td colname="2" style="background-color:white;" colspan="1">116</td> <td colname="3" style="background-color:white;" colspan="1">17</td> <td colname="4" style="background-color:white;" colspan="1">18276</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">7</td> <td colname="2" style="background-color:white;" colspan="1">200</td> <td colname="3" style="background-color:white;" colspan="1">18</td> <td colname="4" style="background-color:white;" colspan="1">15096</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">8</td> <td colname="2" style="background-color:white;" colspan="1">444</td> <td colname="3" style="background-color:white;" colspan="1">19</td> <td colname="4" style="background-color:white;" colspan="1">10240</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">9</td> <td colname="2" style="background-color:white;" colspan="1">760</td> <td colname="3" style="background-color:white;" colspan="1">20</td> <td colname="4" style="background-color:white;" colspan="1">6464</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">10</td> <td colname="2" style="background-color:white;" colspan="1">2160</td> <td colname="3" style="background-color:white;" colspan="1">21</td> <td colname="4" style="background-color:white;" colspan="1">3536</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">11</td> <td colname="2" style="background-color:white;" colspan="1">4368</td> <td colname="3" style="background-color:white;" colspan="1">22</td> <td colname="4" style="background-color:white;" colspan="1">2052</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">12</td> <td colname="2" style="background-color:white;" colspan="1">7852</td> <td colname="3" style="background-color:white;" colspan="1">23</td> <td colname="4" style="background-color:white;" colspan="1">872</td> </tr> </tbody> </table>
+
For  $  q = 4,5,9 $,
 +
or any prime  $  p \equiv \pm  1 ( { \mathop{\rm mod} } 10 ) $,
 +
and for no other finite fields, there is a primitive root  $  \alpha $
 +
with  $  \alpha + \alpha  ^ {2} = 1 $.
 +
Thus, in the Lempel construction,  $  a _ {12 }  = a _ {21 }  = 1 $,
 +
so that if the first two rows and first two columns are removed, a (symmetric) Costas array or order  $  q - 4 $
 +
results. For  $  q = 4,5,9 $,
 +
or any prime  $  p \equiv 1,9 ( { \mathop{\rm mod} } 20 ) $,
 +
there are primitive roots  $  \alpha $
 +
and  $  \beta $
 +
with  $  \alpha + \beta = 1 $
 +
and  $  \alpha  ^ {2} + \beta ^ {- 1 } = 1 $.  
 +
In this case,  $  a _ {11 }  = 1 $,
 +
$  a _ {2,q - 2 }  = 1 $
 +
and  $  a _ {q - 2,2 }  = 1 $.  
 +
By successive removal of rows and columns Costas arrays of orders  $  q - 2 $,
 +
$  q - 3 $,
 +
$  q - 4 $,
 +
and  $  q - 5 $
 +
are obtained for these values of  $  q $.
 +
 
 +
In some cases a Costas array of order $  n + 1 $
 +
can be obtained from one of order  $  n $
 +
by adjoining a  $  1 $
 +
in an exterior corner, i.e., in one of the positions  $  a _ {00 }  $,
 +
$  a _ {0,n + 1 }  $,
 +
$  a _ {n + 1,0 }  $,
 +
or  $  a _ {n + 1,n + 1 }  $.  
 +
Several prime-order examples were obtained in this way from a Welch example of order  $  p - 1 $.
 +
 
 +
The total number  $  C ( n ) $
 +
of Costas arrays of order  $  n $
 +
is known (1996) for $  n \leq  23 $(
 +
see the table), with a local maximum at $  n = 16 $.
 +
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  n $
 +
</td> <td colname="2" style="background-color:white;" colspan="1"> $  C ( n ) $
 +
</td> <td colname="3" style="background-color:white;" colspan="1"> $  n $
 +
</td> <td colname="4" style="background-color:white;" colspan="1"> $  C ( n ) $
 +
</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">2</td> <td colname="2" style="background-color:white;" colspan="1">2</td> <td colname="3" style="background-color:white;" colspan="1">13</td> <td colname="4" style="background-color:white;" colspan="1">12828</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">3</td> <td colname="2" style="background-color:white;" colspan="1">4</td> <td colname="3" style="background-color:white;" colspan="1">14</td> <td colname="4" style="background-color:white;" colspan="1">17252</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">4</td> <td colname="2" style="background-color:white;" colspan="1">12</td> <td colname="3" style="background-color:white;" colspan="1">15</td> <td colname="4" style="background-color:white;" colspan="1">19612</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">5</td> <td colname="2" style="background-color:white;" colspan="1">40</td> <td colname="3" style="background-color:white;" colspan="1">16</td> <td colname="4" style="background-color:white;" colspan="1">21104</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">6</td> <td colname="2" style="background-color:white;" colspan="1">116</td> <td colname="3" style="background-color:white;" colspan="1">17</td> <td colname="4" style="background-color:white;" colspan="1">18276</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">7</td> <td colname="2" style="background-color:white;" colspan="1">200</td> <td colname="3" style="background-color:white;" colspan="1">18</td> <td colname="4" style="background-color:white;" colspan="1">15096</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">8</td> <td colname="2" style="background-color:white;" colspan="1">444</td> <td colname="3" style="background-color:white;" colspan="1">19</td> <td colname="4" style="background-color:white;" colspan="1">10240</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">9</td> <td colname="2" style="background-color:white;" colspan="1">760</td> <td colname="3" style="background-color:white;" colspan="1">20</td> <td colname="4" style="background-color:white;" colspan="1">6464</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">10</td> <td colname="2" style="background-color:white;" colspan="1">2160</td> <td colname="3" style="background-color:white;" colspan="1">21</td> <td colname="4" style="background-color:white;" colspan="1">3536</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">11</td> <td colname="2" style="background-color:white;" colspan="1">4368</td> <td colname="3" style="background-color:white;" colspan="1">22</td> <td colname="4" style="background-color:white;" colspan="1">2052</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">12</td> <td colname="2" style="background-color:white;" colspan="1">7852</td> <td colname="3" style="background-color:white;" colspan="1">23</td> <td colname="4" style="background-color:white;" colspan="1">872</td> </tr> </tbody> </table>
  
 
</td></tr> </table>
 
</td></tr> </table>
  
For a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044075.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044076.png" /> primitive roots, each of which leads to a different Costas array of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044077.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044078.png" /> can be arbitrarily large, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044079.png" />. It has been conjectured, but not proved, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044080.png" />. This would require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044081.png" /> infinitely often. No case of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044082.png" /> is yet known, but no examples of Costas arrays of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044083.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044084.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044085.png" /> have yet been found. (Many larger orders also lack examples.)
+
For a prime number $  p $
 +
there are $  \phi ( p - 1 ) $
 +
primitive roots, each of which leads to a different Costas array of order $  p - 1 $.  
 +
Since $  \phi ( p - 1 ) $
 +
can be arbitrarily large, $  {\lim\limits  \sup } _ {n \rightarrow \infty }  C ( n ) = \infty $.  
 +
It has been conjectured, but not proved, that $  {\lim\limits  \inf } _ {n \rightarrow \infty }  C ( n ) = 0 $.  
 +
This would require $  C ( n ) = 0 $
 +
infinitely often. No case of $  C ( n ) = 0 $
 +
is yet known, but no examples of Costas arrays of orders $  32 $,  
 +
$  33 $,  
 +
or $  43 $
 +
have yet been found. (Many larger orders also lack examples.)
  
J.P. Costas [[#References|[a1]]] first proposed these arrays for an application to frequency hopping sonar signals. Let the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044086.png" /> rows represent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044087.png" /> equally spaced frequencies, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044088.png" /> columns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044089.png" /> equal duration time intervals. Then the Costas array specifies a permuted order for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044090.png" /> frequencies to be transmitted in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044091.png" /> consecutive time intervals. As a sonar (or radar) signal this design has an ideal  "thumb-tack"  ambiguity function (the two-dimensional auto-correlation function in time and frequency). The horizontal (time) shift measures range (the distance to the target) and the vertical (frequency) shift measures the Doppler (the velocity of the target relative to the observer). For any non-zero shift parallel to the coordinate axes a Costas array has at most one  "hit"  (coincidence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044092.png" /> with a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044093.png" />), and thus gives the least ambiguous reading of the correct range and Doppler in the presence of noise.
+
J.P. Costas [[#References|[a1]]] first proposed these arrays for an application to frequency hopping sonar signals. Let the $  n $
 +
rows represent $  n $
 +
equally spaced frequencies, and the $  n $
 +
columns $  n $
 +
equal duration time intervals. Then the Costas array specifies a permuted order for the $  n $
 +
frequencies to be transmitted in $  n $
 +
consecutive time intervals. As a sonar (or radar) signal this design has an ideal  "thumb-tack"  ambiguity function (the two-dimensional auto-correlation function in time and frequency). The horizontal (time) shift measures range (the distance to the target) and the vertical (frequency) shift measures the Doppler (the velocity of the target relative to the observer). For any non-zero shift parallel to the coordinate axes a Costas array has at most one  "hit"  (coincidence of a $  1 $
 +
with a $  1 $),  
 +
and thus gives the least ambiguous reading of the correct range and Doppler in the presence of noise.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Costas,  "Project medior. A medium-oriented approach to sonar signal processing" , ''HMED Tech. Publ. R66EMH12'' , General Electric  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S.W. Golomb,  H. Taylor,  "Two-dimensional synchronization patterns with minimum ambiguity"  ''IEEE Trans. Inform. Theory'' , '''28'''  (1982)  pp. 600–604</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S.W. Golomb,  H. Taylor,  "Constructions and properties of Costas arrays"  ''Proc. IEEE'' , '''72'''  (1984)  pp. 1143–1163</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S.W. Golomb,  "Algebraic constructions for Costas arrays"  ''J. Combin. Th. A'' , '''37'''  (1984)  pp. 13–21</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  S.W. Golomb,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044095.png" /> constructions for Costas arrays"  ''IEEE Trans. Inform. Th.'' , '''38'''  (1992)  pp. 1404–1406</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  O. Moreno,  J. Sotero,  "Computational approach to conjecture A of Golomb"  ''Congressus Numerantium'' , '''70'''  (1990)  pp. 7–16</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.P. Costas,  "A study of a class of detection waveforms having nearly ideal range-doppler ambiguity properties"  ''Proc. IEEE'' , '''72'''  (1984)  pp. 996–1009</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Costas,  "Project medior. A medium-oriented approach to sonar signal processing" , ''HMED Tech. Publ. R66EMH12'' , General Electric  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S.W. Golomb,  H. Taylor,  "Two-dimensional synchronization patterns with minimum ambiguity"  ''IEEE Trans. Inform. Theory'' , '''28'''  (1982)  pp. 600–604</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S.W. Golomb,  H. Taylor,  "Constructions and properties of Costas arrays"  ''Proc. IEEE'' , '''72'''  (1984)  pp. 1143–1163</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S.W. Golomb,  "Algebraic constructions for Costas arrays"  ''J. Combin. Th. A'' , '''37'''  (1984)  pp. 13–21</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  S.W. Golomb,  "The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110440/c11044095.png" /> constructions for Costas arrays"  ''IEEE Trans. Inform. Th.'' , '''38'''  (1992)  pp. 1404–1406</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  O. Moreno,  J. Sotero,  "Computational approach to conjecture A of Golomb"  ''Congressus Numerantium'' , '''70'''  (1990)  pp. 7–16</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.P. Costas,  "A study of a class of detection waveforms having nearly ideal range-doppler ambiguity properties"  ''Proc. IEEE'' , '''72'''  (1984)  pp. 996–1009</TD></TR></table>

Revision as of 17:31, 5 June 2020


of order $ n $

An $ ( n \times n ) $ permutation matrix in which the $ { {n ( n - 1 ) } / 2 } $ line segments connecting pairs of ones in the matrix are distinct as vectors, i.e., no two agree in both magnitude and slope. Thus, if $ a _ {ij } = a _ {kl } = 1 $ and $ a _ {mn } = a _ {pq } = 1 $ in the matrix, with $ ( i,j ) \neq ( k,l ) $, $ ( m,n ) \neq ( p,q ) $, and at least three of these four ordered pairs are distinct, and if $ | {( a _ {ij } ,a _ {kl } ) } | ^ {2} = ( k - i ) ^ {2} + ( l - j ) ^ {2} $ equals $ | {( a _ {mn } ,a _ {pq } ) } | ^ {2} = ( p - m ) ^ {2} + ( q - n ) ^ {2} $, then

$$ \left | { { \frac{( l - j ) }{( k - i ) } } } \right | \neq \left | { { \frac{( q - n ) }{( p - m ) } } } \right | . $$

All known (1996) general constructions for Costas arrays (see [a3], [a4], [a5]) involve primitive roots in finite fields (cf. Field). The Welch construction, for every prime $ p > 2 $, gives a Costas array of order $ p - 1 $ by setting $ a _ {ij } = 1 $ when $ j = g ^ {i} ( { \mathop{\rm mod} } p ) $, where $ g $ is a primitive root modulo $ p $. Removing row $ p - 1 $ and column $ 1 $ from this construction leaves a Costas array of order $ p - 2 $. When $ g = 2 $ is used as the primitive root modulo $ p $, the array can be further reduced to order $ p - 3 $.

In Golomb's construction, if $ \alpha $ and $ \beta $ are any two primitive elements in $ { \mathop{\rm GF} } ( q ) $, for $ q > 2 $, a Costas array of order $ q - 2 $ is obtained by setting $ a _ {ij } = 1 $ whenever $ \alpha ^ {i} + \beta ^ {j} = 1 $. (The case $ \alpha = \beta $ had been discovered by A. Lempel.) If $ \alpha + \beta = 1 $, then $ a _ {11 } = 1 $, so that by removing the first row and first column, a Costas array or order $ q - 3 $ is obtained. As shown in [a6], for every $ q > 2 $ one can find primitive roots $ \alpha $ and $ \beta $( not necessarily distinct) with $ \alpha + \beta = 1 $.

For $ q = 4,5,9 $, or any prime $ p \equiv \pm 1 ( { \mathop{\rm mod} } 10 ) $, and for no other finite fields, there is a primitive root $ \alpha $ with $ \alpha + \alpha ^ {2} = 1 $. Thus, in the Lempel construction, $ a _ {12 } = a _ {21 } = 1 $, so that if the first two rows and first two columns are removed, a (symmetric) Costas array or order $ q - 4 $ results. For $ q = 4,5,9 $, or any prime $ p \equiv 1,9 ( { \mathop{\rm mod} } 20 ) $, there are primitive roots $ \alpha $ and $ \beta $ with $ \alpha + \beta = 1 $ and $ \alpha ^ {2} + \beta ^ {- 1 } = 1 $. In this case, $ a _ {11 } = 1 $, $ a _ {2,q - 2 } = 1 $ and $ a _ {q - 2,2 } = 1 $. By successive removal of rows and columns Costas arrays of orders $ q - 2 $, $ q - 3 $, $ q - 4 $, and $ q - 5 $ are obtained for these values of $ q $.

In some cases a Costas array of order $ n + 1 $ can be obtained from one of order $ n $ by adjoining a $ 1 $ in an exterior corner, i.e., in one of the positions $ a _ {00 } $, $ a _ {0,n + 1 } $, $ a _ {n + 1,0 } $, or $ a _ {n + 1,n + 1 } $. Several prime-order examples were obtained in this way from a Welch example of order $ p - 1 $.

The total number $ C ( n ) $ of Costas arrays of order $ n $ is known (1996) for $ n \leq 23 $( see the table), with a local maximum at $ n = 16 $.

<tbody> </tbody>
$ n $ $ C ( n ) $ $ n $ $ C ( n ) $
2 2 13 12828
3 4 14 17252
4 12 15 19612
5 40 16 21104
6 116 17 18276
7 200 18 15096
8 444 19 10240
9 760 20 6464
10 2160 21 3536
11 4368 22 2052
12 7852 23 872

For a prime number $ p $ there are $ \phi ( p - 1 ) $ primitive roots, each of which leads to a different Costas array of order $ p - 1 $. Since $ \phi ( p - 1 ) $ can be arbitrarily large, $ {\lim\limits \sup } _ {n \rightarrow \infty } C ( n ) = \infty $. It has been conjectured, but not proved, that $ {\lim\limits \inf } _ {n \rightarrow \infty } C ( n ) = 0 $. This would require $ C ( n ) = 0 $ infinitely often. No case of $ C ( n ) = 0 $ is yet known, but no examples of Costas arrays of orders $ 32 $, $ 33 $, or $ 43 $ have yet been found. (Many larger orders also lack examples.)

J.P. Costas [a1] first proposed these arrays for an application to frequency hopping sonar signals. Let the $ n $ rows represent $ n $ equally spaced frequencies, and the $ n $ columns $ n $ equal duration time intervals. Then the Costas array specifies a permuted order for the $ n $ frequencies to be transmitted in $ n $ consecutive time intervals. As a sonar (or radar) signal this design has an ideal "thumb-tack" ambiguity function (the two-dimensional auto-correlation function in time and frequency). The horizontal (time) shift measures range (the distance to the target) and the vertical (frequency) shift measures the Doppler (the velocity of the target relative to the observer). For any non-zero shift parallel to the coordinate axes a Costas array has at most one "hit" (coincidence of a $ 1 $ with a $ 1 $), and thus gives the least ambiguous reading of the correct range and Doppler in the presence of noise.

References

[a1] J.P. Costas, "Project medior. A medium-oriented approach to sonar signal processing" , HMED Tech. Publ. R66EMH12 , General Electric (1966)
[a2] S.W. Golomb, H. Taylor, "Two-dimensional synchronization patterns with minimum ambiguity" IEEE Trans. Inform. Theory , 28 (1982) pp. 600–604
[a3] S.W. Golomb, H. Taylor, "Constructions and properties of Costas arrays" Proc. IEEE , 72 (1984) pp. 1143–1163
[a4] S.W. Golomb, "Algebraic constructions for Costas arrays" J. Combin. Th. A , 37 (1984) pp. 13–21
[a5] S.W. Golomb, "The and constructions for Costas arrays" IEEE Trans. Inform. Th. , 38 (1992) pp. 1404–1406
[a6] O. Moreno, J. Sotero, "Computational approach to conjecture A of Golomb" Congressus Numerantium , 70 (1990) pp. 7–16
[a7] J.P. Costas, "A study of a class of detection waveforms having nearly ideal range-doppler ambiguity properties" Proc. IEEE , 72 (1984) pp. 996–1009
How to Cite This Entry:
Costas array. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Costas_array&oldid=46534
This article was adapted from an original article by S.W. Golomb (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article