August  2014, 8(3): 241-256. doi: 10.3934/amc.2014.8.241

Structural properties of Costas arrays

1. 

Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6

2. 

Department of Mathematics and Statistics, University of Victoria, 3800 Finnerty Road, Victoria BC V8P 5C2, Canada

Received  August 2012 Revised  March 2014 Published  August 2014

We apply combinatorial arguments to establish structural constraints on Costas arrays. We prove restrictions on when a Costas array can contain a large corner region whose entries are all 0. In particular, we prove a 2010 conjecture due to Russo, Erickson and Beard. We then constrain the vectors joining pairs of 1s in a Costas array by establishing a series of results on its number of "mirror pairs," namely pairs of these vectors having the same length but opposite slopes.
Citation: Jonathan Jedwab, Jane Wodlinger. Structural properties of Costas arrays. Advances in Mathematics of Communications, 2014, 8 (3) : 241-256. doi: 10.3934/amc.2014.8.241
References:
[1]

J. K. Beard, Orders three through 100, Database of Costas arrays, available from: http://jameskbeard.com/jameskbeard/Files.html#CostasArrays

[2]

S. R. Blackburn, T. Etzion, K. M. Martin and M. B. Paterson, Two-dimensional patterns with distinct differences - constructions, bounds, and maximal anticodes, IEEE Trans. Inform. Theory, 56 (2010), 1216-1229. doi: 10.1109/TIT.2009.2039046.

[3]

C. P. Brown, M. Cenkl, R. A. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in Proc. IEEE Int. Symp. Inform. Theory, Kobe, Japan, 1993. doi: 10.1109/ISIT.1993.748721.

[4]

J. P. Costas, A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009.

[5]

K. Drakakis, A review of Costas arrays, J. Appl. Math., (2006). doi: 10.1155/JAM/2006/26385.

[6]

K. Drakakis, Open problems in Costas arrays, preprint, arXiv:1102.5727

[7]

K. Drakakis, R. Gow, J. Healy and S. Rickard, Cross-correlation properties of Costas arrays and their images under horizontal and vertical flips, Math. Problems Engin., (2008). doi: 10.1155/2008/369321.

[8]

K. Drakakis, R. Gow and S. Rickard, Interlaced Costas arrays do not exist, Math. Problems Engin., (2008). doi: 10.1155/2008/456034.

[9]

K. Drakakis, R. Gow and S. Rickard, Common distance vectors between Costas arrays, Adv. Math. Commun., 3 (2009), 35-52. doi: 10.3934/amc.2009.3.35.

[10]

K. Drakakis, F. Iorio and S. Rickard, The enumeration of Costas arrays of order 28 and its consequences, Adv. Math. Commun., 5 (2011), 69-86. doi: 10.3934/amc.2011.5.69.

[11]

P. Erdős, R. Graham, I. Z. Ruzsa and H. Taylor, Bounds for arrays of dots with distinct slopes or lengths, Combinatorica, 12 (1992), 39-44. doi: 10.1007/BF01191203.

[12]

P. Erdős and P. Turán, On a problem of Sidon in additive number theory and on some related problems, J. London Math. Soc., 16 (1941), 212-215.

[13]

T. Etzion, Combinatorial designs derived from Costas arrays, in Sequences: Combinatorics, Compression, Security, and Transmission (ed. R.M. Capocelli), Springer-Verlag, 1990, 208-227.

[14]

T. Etzion, Sequence folding, lattice tiling, and multidimensional coding, IEEE Trans. Inform. Theory, 57 (2011), 4383-4400. doi: 10.1109/TIT.2011.2146010.

[15]

A. Freedman and N. Levanon, Any two $N \times N$ Costas arrays must have at least one common ambiguity sidelobe if $N>3$ - a proof, Proc. IEEE, 73 (1985), 1530-1531.

[16]

E. N. Gilbert, Latin squares which contain no repeated digrams, SIAM Review, 7 (1965), 189-198. doi: 10.1137/1007035.

[17]

S. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21. doi: 10.1016/0097-3165(84)90015-3.

[18]

S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163. doi: 10.1109/PROC.1984.12994.

[19]

S. Rickard, Database of Costas arrays, accessed 2012.

[20]

S. Rickard, Searching for Costas arrays using periodicity properties, in Proc. 2004 IMA Int. Conf. Math. Signal Proc., Cirencester, UK, 2004.

[21]

J. C. Russo, K. G. Erickson and J. K. Beard, Costas array search technique that maximizes backtrack and symmetry exploitation, in 44th Annual Conf. Inform. Sci. Systems, Princeton, USA, 2010. doi: 10.1109/CISS.2010.5464772.

[22]

H. Taylor, Non-attacking rooks with distinct differences, Technical Report CSI-84-03-02, Communication Sciences Institute, University of Southern California, 1984.

[23]

K. Taylor, S. Rickard and K. Drakakis, On Costas arrays with various types of symmetry, in 16th Int. Conf. Digital Signal Proc., IEEE, 2009. doi: 10.1109/ICDSP.2009.5201135.

[24]

J. L. Wodlinger, Costas Arrays, Golomb Rulers and Wavelength Isolation Sequence Pairs, Master's thesis, Department of Mathematics, Simon Fraser University, 2012. Available from: https://theses.lib.sfu.ca/thesis/etd7112

show all references

References:
[1]

J. K. Beard, Orders three through 100, Database of Costas arrays, available from: http://jameskbeard.com/jameskbeard/Files.html#CostasArrays

[2]

S. R. Blackburn, T. Etzion, K. M. Martin and M. B. Paterson, Two-dimensional patterns with distinct differences - constructions, bounds, and maximal anticodes, IEEE Trans. Inform. Theory, 56 (2010), 1216-1229. doi: 10.1109/TIT.2009.2039046.

[3]

C. P. Brown, M. Cenkl, R. A. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in Proc. IEEE Int. Symp. Inform. Theory, Kobe, Japan, 1993. doi: 10.1109/ISIT.1993.748721.

[4]

J. P. Costas, A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009.

[5]

K. Drakakis, A review of Costas arrays, J. Appl. Math., (2006). doi: 10.1155/JAM/2006/26385.

[6]

K. Drakakis, Open problems in Costas arrays, preprint, arXiv:1102.5727

[7]

K. Drakakis, R. Gow, J. Healy and S. Rickard, Cross-correlation properties of Costas arrays and their images under horizontal and vertical flips, Math. Problems Engin., (2008). doi: 10.1155/2008/369321.

[8]

K. Drakakis, R. Gow and S. Rickard, Interlaced Costas arrays do not exist, Math. Problems Engin., (2008). doi: 10.1155/2008/456034.

[9]

K. Drakakis, R. Gow and S. Rickard, Common distance vectors between Costas arrays, Adv. Math. Commun., 3 (2009), 35-52. doi: 10.3934/amc.2009.3.35.

[10]

K. Drakakis, F. Iorio and S. Rickard, The enumeration of Costas arrays of order 28 and its consequences, Adv. Math. Commun., 5 (2011), 69-86. doi: 10.3934/amc.2011.5.69.

[11]

P. Erdős, R. Graham, I. Z. Ruzsa and H. Taylor, Bounds for arrays of dots with distinct slopes or lengths, Combinatorica, 12 (1992), 39-44. doi: 10.1007/BF01191203.

[12]

P. Erdős and P. Turán, On a problem of Sidon in additive number theory and on some related problems, J. London Math. Soc., 16 (1941), 212-215.

[13]

T. Etzion, Combinatorial designs derived from Costas arrays, in Sequences: Combinatorics, Compression, Security, and Transmission (ed. R.M. Capocelli), Springer-Verlag, 1990, 208-227.

[14]

T. Etzion, Sequence folding, lattice tiling, and multidimensional coding, IEEE Trans. Inform. Theory, 57 (2011), 4383-4400. doi: 10.1109/TIT.2011.2146010.

[15]

A. Freedman and N. Levanon, Any two $N \times N$ Costas arrays must have at least one common ambiguity sidelobe if $N>3$ - a proof, Proc. IEEE, 73 (1985), 1530-1531.

[16]

E. N. Gilbert, Latin squares which contain no repeated digrams, SIAM Review, 7 (1965), 189-198. doi: 10.1137/1007035.

[17]

S. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21. doi: 10.1016/0097-3165(84)90015-3.

[18]

S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163. doi: 10.1109/PROC.1984.12994.

[19]

S. Rickard, Database of Costas arrays, accessed 2012.

[20]

S. Rickard, Searching for Costas arrays using periodicity properties, in Proc. 2004 IMA Int. Conf. Math. Signal Proc., Cirencester, UK, 2004.

[21]

J. C. Russo, K. G. Erickson and J. K. Beard, Costas array search technique that maximizes backtrack and symmetry exploitation, in 44th Annual Conf. Inform. Sci. Systems, Princeton, USA, 2010. doi: 10.1109/CISS.2010.5464772.

[22]

H. Taylor, Non-attacking rooks with distinct differences, Technical Report CSI-84-03-02, Communication Sciences Institute, University of Southern California, 1984.

[23]

K. Taylor, S. Rickard and K. Drakakis, On Costas arrays with various types of symmetry, in 16th Int. Conf. Digital Signal Proc., IEEE, 2009. doi: 10.1109/ICDSP.2009.5201135.

[24]

J. L. Wodlinger, Costas Arrays, Golomb Rulers and Wavelength Isolation Sequence Pairs, Master's thesis, Department of Mathematics, Simon Fraser University, 2012. Available from: https://theses.lib.sfu.ca/thesis/etd7112

[1]

Konstantinos Drakakis, Roderick Gow, Scott Rickard. Common distance vectors between Costas arrays. Advances in Mathematics of Communications, 2009, 3 (1) : 35-52. doi: 10.3934/amc.2009.3.35

[2]

Konstantinos Drakakis. On the degrees of freedom of Costas permutations and other constraints. Advances in Mathematics of Communications, 2011, 5 (3) : 435-448. doi: 10.3934/amc.2011.5.435

[3]

Qiu-Sheng Qiu. Optimality conditions for vector equilibrium problems with constraints. Journal of Industrial and Management Optimization, 2009, 5 (4) : 783-790. doi: 10.3934/jimo.2009.5.783

[4]

Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117

[5]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

[6]

Yongluo Cao, Stefano Luzzatto, Isabel Rios. Some non-hyperbolic systems with strictly non-zero Lyapunov exponents for all invariant measures: Horseshoes with internal tangencies. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 61-71. doi: 10.3934/dcds.2006.15.61

[7]

Ming Gao, Jonathan J. Wylie, Qiang Zhang. Inelastic Collapse in a Corner. Communications on Pure and Applied Analysis, 2009, 8 (1) : 275-293. doi: 10.3934/cpaa.2009.8.275

[8]

Jaume Llibre, Jesús S. Pérez del Río, J. Angel Rodríguez. Structural stability of planar semi-homogeneous polynomial vector fields applications to critical points and to infinity. Discrete and Continuous Dynamical Systems, 2000, 6 (4) : 809-828. doi: 10.3934/dcds.2000.6.809

[9]

Lev M. Lerman, Elena V. Gubina. Nonautonomous gradient-like vector fields on the circle: Classification, structural stability and autonomization. Discrete and Continuous Dynamical Systems - S, 2020, 13 (4) : 1341-1367. doi: 10.3934/dcdss.2020076

[10]

Mohammad Safdari. The regularity of some vector-valued variational inequalities with gradient constraints. Communications on Pure and Applied Analysis, 2018, 17 (2) : 413-428. doi: 10.3934/cpaa.2018023

[11]

Konstantinos Drakakis, Scott Rickard. On the generalization of the Costas property in the continuum. Advances in Mathematics of Communications, 2008, 2 (2) : 113-130. doi: 10.3934/amc.2008.2.113

[12]

Chang-Yeol Jung, Roger Temam. Interaction of boundary layers and corner singularities. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 315-339. doi: 10.3934/dcds.2009.23.315

[13]

Konstantinos Drakakis. On the generalization of the Costas property in higher dimensions. Advances in Mathematics of Communications, 2010, 4 (1) : 1-22. doi: 10.3934/amc.2010.4.1

[14]

Bingsheng Shen, Yang Yang, Ruibin Ren. Three constructions of Golay complementary array sets. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022019

[15]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010

[16]

N. D. Alikakos, P. W. Bates, J. W. Cahn, P. C. Fife, G. Fusco, G. B. Tanoglu. Analysis of a corner layer problem in anisotropic interfaces. Discrete and Continuous Dynamical Systems - B, 2006, 6 (2) : 237-255. doi: 10.3934/dcdsb.2006.6.237

[17]

Oǧul Esen, Serkan Sütlü. Matched pair analysis of the Vlasov plasma. Journal of Geometric Mechanics, 2021, 13 (2) : 209-246. doi: 10.3934/jgm.2021011

[18]

Konstantinos Drakakis, Francesco Iorio, Scott Rickard, John Walsh. Results of the enumeration of Costas arrays of order 29. Advances in Mathematics of Communications, 2011, 5 (3) : 547-553. doi: 10.3934/amc.2011.5.547

[19]

Konstantinos Drakakis, Francesco Iorio, Scott Rickard. The enumeration of Costas arrays of order 28 and its consequences. Advances in Mathematics of Communications, 2011, 5 (1) : 69-86. doi: 10.3934/amc.2011.5.69

[20]

Bo Wang, Jiguang Bao. Mirror symmetry for a Hessian over-determined problem and its generalization. Communications on Pure and Applied Analysis, 2014, 13 (6) : 2305-2316. doi: 10.3934/cpaa.2014.13.2305

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (130)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]