The enumeration of Costas arrays of order 28 and its consequences

Previous Article
Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order
AMC Home
This Issue
Next Article
Cryptanalysis of a 2-party key establishment based on a semigroup action problem

February 2011, 5(1): 69-86. doi: 10.3934/amc.2011.5.69

The enumeration of Costas arrays of order 28 and its consequences

Konstantinos Drakakis ^1, , Francesco Iorio ^2, and Scott Rickard ^1,

1.	School of Electrical, Electronic & Mechanical Engineering, University College Dublin, Belﬁeld, Dublin 4
2.	Autodesk Research, 210 King Street East, Toronto, Ontario M5A 1J7, Canada

Received July 2010 Published February 2011

Abstract
Related Papers

The results of the enumeration of Costas arrays of order 28 are presented: all arrays found are accounted for by the Golomb and Welch construction methods, making 28 the first order (larger than 5) for which no sporadic Costas arrays exist. The enumeration was performed on several computer clusters and required the equivalent of 70 years of single CPU time. Furthermore, a classification of Costas arrays in four classes is proposed, and it is conjectured, based on the results of the enumeration combined with further evidence, that two of them eventually become extinct.

Keywords: order 28, enumeration, Costas arrays, Golomb method, Welch method..

Mathematics Subject Classification: Primary: 05A15, 05B10; Secondary: 05A05, 11B5.

Citation: 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

References:

[1]	L. Barker, K. Drakakis and S. Rickard, On the complexity of the verification of the Costas property,, Proc. IEEE, 97 (2009), 586. doi: 10.1109/JPROC.2008.2011947. Google Scholar
[2]	J. K. Beard, Private communication,, May 2008., (2008). Google Scholar
[3]	J. K. Beard, J. C. Russo, K. G. Erickson, M. C. Monteleone and M. T. Wright, Costas arrays generation and search methodology,, IEEE Trans. Aerospace Electr. Systems, 43 (2007), 522. doi: 10.1109/TAES.2007.4285351. Google Scholar
[4]	C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays,, in, (1993). doi: 10.1109/ISIT.1993.748721. Google Scholar
[5]	S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays,, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45. doi: 10.1007/BF01810854. Google Scholar
[6]	J. P. Costas, Medium constraints on SONAR design and performance,, in, (1975). Google Scholar
[7]	J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties,, Proc. IEEE, 72 (1984), 996. doi: 10.1109/PROC.1984.12967. Google Scholar
[8]	K. Drakakis, A review of Costas arrays,, J. Appl. Math., 2006 (). Google Scholar
[9]	K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays,, Discrete Math., 309 (2009), 2559. doi: 10.1016/j.disc.2008.04.058. Google Scholar
[10]	K. Drakakis, S. Rickard, J. Beard, R. Caballero, F. Iorio, G. O'Brien and J. Walsh, Results of the enumeration of Costas arrays of order 27,, IEEE Trans. Inform. Theory, 54 (2008), 4684. doi: 10.1109/TIT.2008.928979. Google Scholar
[11]	S. W. Golomb, Algebraic constructions for Costas arrays,, J. Combin. Theory Ser. A, 37 (1984), 13. doi: 10.1016/0097-3165(84)90015-3. Google Scholar
[12]	S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays,, IEEE Trans. Inform. Theory, 38 (1992), 1404. doi: 10.1109/18.144726. Google Scholar
[13]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays,, Proc. IEEE, 72 (1984), 1143. doi: 10.1109/PROC.1984.12994. Google Scholar
[14]	K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition,, Springer, (1990). Google Scholar
[15]	S. Rickard, Searching for Costas arrays using periodicity properties,, in, (2004). Google Scholar
[16]	S. Rickard, Open problems in Costas arrays,, in, (2006). Google Scholar
[17]	S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26,, in, (2006). doi: 10.1109/CISS.2006.286579. Google Scholar
[18]	J. Silverman, V. Vickers and J. Mooney, On the number of Costas arrays as a function of array size,, Proc. IEEE, 76 (1988), 851. doi: 10.1109/5.7156. Google Scholar
[19]	K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays,, in, (2008). Google Scholar

show all references

References:

[1]	L. Barker, K. Drakakis and S. Rickard, On the complexity of the verification of the Costas property,, Proc. IEEE, 97 (2009), 586. doi: 10.1109/JPROC.2008.2011947. Google Scholar
[2]	J. K. Beard, Private communication,, May 2008., (2008). Google Scholar
[3]	J. K. Beard, J. C. Russo, K. G. Erickson, M. C. Monteleone and M. T. Wright, Costas arrays generation and search methodology,, IEEE Trans. Aerospace Electr. Systems, 43 (2007), 522. doi: 10.1109/TAES.2007.4285351. Google Scholar
[4]	C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays,, in, (1993). doi: 10.1109/ISIT.1993.748721. Google Scholar
[5]	S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays,, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45. doi: 10.1007/BF01810854. Google Scholar
[6]	J. P. Costas, Medium constraints on SONAR design and performance,, in, (1975). Google Scholar
[7]	J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties,, Proc. IEEE, 72 (1984), 996. doi: 10.1109/PROC.1984.12967. Google Scholar
[8]	K. Drakakis, A review of Costas arrays,, J. Appl. Math., 2006 (). Google Scholar
[9]	K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays,, Discrete Math., 309 (2009), 2559. doi: 10.1016/j.disc.2008.04.058. Google Scholar
[10]	K. Drakakis, S. Rickard, J. Beard, R. Caballero, F. Iorio, G. O'Brien and J. Walsh, Results of the enumeration of Costas arrays of order 27,, IEEE Trans. Inform. Theory, 54 (2008), 4684. doi: 10.1109/TIT.2008.928979. Google Scholar
[11]	S. W. Golomb, Algebraic constructions for Costas arrays,, J. Combin. Theory Ser. A, 37 (1984), 13. doi: 10.1016/0097-3165(84)90015-3. Google Scholar
[12]	S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays,, IEEE Trans. Inform. Theory, 38 (1992), 1404. doi: 10.1109/18.144726. Google Scholar
[13]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays,, Proc. IEEE, 72 (1984), 1143. doi: 10.1109/PROC.1984.12994. Google Scholar
[14]	K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition,, Springer, (1990). Google Scholar
[15]	S. Rickard, Searching for Costas arrays using periodicity properties,, in, (2004). Google Scholar
[16]	S. Rickard, Open problems in Costas arrays,, in, (2006). Google Scholar
[17]	S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26,, in, (2006). doi: 10.1109/CISS.2006.286579. Google Scholar
[18]	J. Silverman, V. Vickers and J. Mooney, On the number of Costas arrays as a function of array size,, Proc. IEEE, 76 (1988), 851. doi: 10.1109/5.7156. Google Scholar
[19]	K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays,, in, (2008). Google Scholar

[1]	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
[2]	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
[3]	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
[4]	Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321
[5]	Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic & Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417
[6]	Min Tang. Second order all speed method for the isentropic Euler equations. Kinetic & Related Models, 2012, 5 (1) : 155-184. doi: 10.3934/krm.2012.5.155
[7]	Yong Li, Catalin Trenchea. Partitioned second order method for magnetohydrodynamics in Elsässer variables. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2803-2823. doi: 10.3934/dcdsb.2018106
[8]	Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068
[9]	Lijun Yi, Zhongqing Wang. Legendre spectral collocation method for second-order nonlinear ordinary/partial differential equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 299-322. doi: 10.3934/dcdsb.2014.19.299
[10]	Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems & Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025
[11]	Kazuyuki Yagasaki. Higher-order Melnikov method and chaos for two-degree-of-freedom Hamiltonian systems with saddle-centers. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 387-402. doi: 10.3934/dcds.2011.29.387
[12]	Klemens Fellner, Wolfang Prager, Bao Q. Tang. The entropy method for reaction-diffusion systems without detailed balance: First order chemical reaction networks. Kinetic & Related Models, 2017, 10 (4) : 1055-1087. doi: 10.3934/krm.2017042
[13]	Xiao-Yu Zhang, Qing Fang. A sixth order numerical method for a class of nonlinear two-point boundary value problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 31-43. doi: 10.3934/naco.2012.2.31
[14]	Ben-Yu Guo, Zhong-Qing Wang. A spectral collocation method for solving initial value problems of first order ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 1029-1054. doi: 10.3934/dcdsb.2010.14.1029
[15]	Netra Khanal, Ramjee Sharma, Jiahong Wu, Juan-Ming Yuan. A dual-Petrov-Galerkin method for extended fifth-order Korteweg-de Vries type equations. Conference Publications, 2009, 2009 (Special) : 442-450. doi: 10.3934/proc.2009.2009.442
[16]	M. A. Christou, C. I. Christov. Fourier-Galerkin method for localized solutions of the Sixth-Order Generalized Boussinesq Equation. Conference Publications, 2001, 2001 (Special) : 121-130. doi: 10.3934/proc.2001.2001.121
[17]	Juan-Ming Yuan, Jiahong Wu. A dual-Petrov-Galerkin method for two integrable fifth-order KdV type equations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (4) : 1525-1536. doi: 10.3934/dcds.2010.26.1525
[18]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[19]	Andrea L. Bertozzi, Ning Ju, Hsiang-Wei Lu. A biharmonic-modified forward time stepping method for fourth order nonlinear diffusion equations. Discrete & Continuous Dynamical Systems - A, 2011, 29 (4) : 1367-1391. doi: 10.3934/dcds.2011.29.1367
[20]	Honglei Xu, Peng Sui, Guanglu Zhou, Louis Caccetta. Dampening bullwhip effect of order-up-to inventory strategies via an optimal control method. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 655-664. doi: 10.3934/naco.2013.3.655

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences