The enumeration of Costas arrays of order 28 and its consequences

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

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-593. doi: 10.1109/JPROC.2008.2011947.
[2]	J. K. Beard, Private communication, May 2008.
[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-538. doi: 10.1109/TAES.2007.4285351.
[4]	C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in "IEEE International Symposium on Information Theory,'' (1993), 405. doi: 10.1109/ISIT.1993.748721.
[5]	S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45-53. doi: 10.1007/BF01810854.
[6]	J. P. Costas, Medium constraints on SONAR design and performance, in "Technical Report Class 1 Rep. R65EMH33,'' GE Co., 1965; A synopsis of this report appeared in the EASCON Convention Record, (1975), 68A-68L.
[7]	J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009. doi: 10.1109/PROC.1984.12967.
[8]	K. Drakakis, A review of Costas arrays, J. Appl. Math., 2006, 32.
[9]	K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays, Discrete Math., 309 (2009), 2559-2563. doi: 10.1016/j.disc.2008.04.058.
[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-4687. doi: 10.1109/TIT.2008.928979.
[11]	S. W. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21. doi: 10.1016/0097-3165(84)90015-3.
[12]	S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays, IEEE Trans. Inform. Theory, 38 (1992), 1404-1406. doi: 10.1109/18.144726.
[13]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163. doi: 10.1109/PROC.1984.12994.
[14]	K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition, Springer, 1990.
[15]	S. Rickard, Searching for Costas arrays using periodicity properties, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2004.
[16]	S. Rickard, Open problems in Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2006.
[17]	S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26, in "Conference on Information Signals and Systems,'' Princeton University, USA, 2006. doi: 10.1109/CISS.2006.286579.
[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-853. doi: 10.1109/5.7156.
[19]	K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2008.

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-593. doi: 10.1109/JPROC.2008.2011947.
[2]	J. K. Beard, Private communication, May 2008.
[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-538. doi: 10.1109/TAES.2007.4285351.
[4]	C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in "IEEE International Symposium on Information Theory,'' (1993), 405. doi: 10.1109/ISIT.1993.748721.
[5]	S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45-53. doi: 10.1007/BF01810854.
[6]	J. P. Costas, Medium constraints on SONAR design and performance, in "Technical Report Class 1 Rep. R65EMH33,'' GE Co., 1965; A synopsis of this report appeared in the EASCON Convention Record, (1975), 68A-68L.
[7]	J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009. doi: 10.1109/PROC.1984.12967.
[8]	K. Drakakis, A review of Costas arrays, J. Appl. Math., 2006, 32.
[9]	K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays, Discrete Math., 309 (2009), 2559-2563. doi: 10.1016/j.disc.2008.04.058.
[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-4687. doi: 10.1109/TIT.2008.928979.
[11]	S. W. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21. doi: 10.1016/0097-3165(84)90015-3.
[12]	S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays, IEEE Trans. Inform. Theory, 38 (1992), 1404-1406. doi: 10.1109/18.144726.
[13]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163. doi: 10.1109/PROC.1984.12994.
[14]	K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition, Springer, 1990.
[15]	S. Rickard, Searching for Costas arrays using periodicity properties, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2004.
[16]	S. Rickard, Open problems in Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2006.
[17]	S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26, in "Conference on Information Signals and Systems,'' Princeton University, USA, 2006. doi: 10.1109/CISS.2006.286579.
[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-853. doi: 10.1109/5.7156.
[19]	K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2008.

[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]	Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[3]	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
[4]	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
[5]	Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[6]	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
[7]	Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic and Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417
[8]	Min Tang. Second order all speed method for the isentropic Euler equations. Kinetic and Related Models, 2012, 5 (1) : 155-184. doi: 10.3934/krm.2012.5.155
[9]	Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial and Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[10]	Yong Li, Catalin Trenchea. Partitioned second order method for magnetohydrodynamics in Elsässer variables. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2803-2823. doi: 10.3934/dcdsb.2018106
[11]	Giuseppe Floridia, Hiroshi Takase, Masahiro Yamamoto. A Carleman estimate and an energy method for a first-order symmetric hyperbolic system. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022016
[12]	Masaru Ikehata, Yavar Kian. The enclosure method for the detection of variable order in fractional diffusion equations. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022036
[13]	Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068
[14]	Jiantao Jiang, Jing An, Jianwei Zhou. A novel numerical method based on a high order polynomial approximation of the fourth order Steklov equation and its eigenvalue problems. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022066
[15]	Lijun Yi, Zhongqing Wang. Legendre spectral collocation method for second-order nonlinear ordinary/partial differential equations. Discrete and Continuous Dynamical Systems - B, 2014, 19 (1) : 299-322. doi: 10.3934/dcdsb.2014.19.299
[16]	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 and Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025
[17]	Kazuyuki Yagasaki. Higher-order Melnikov method and chaos for two-degree-of-freedom Hamiltonian systems with saddle-centers. Discrete and Continuous Dynamical Systems, 2011, 29 (1) : 387-402. doi: 10.3934/dcds.2011.29.387
[18]	Anis Theljani, Ke Chen. An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration. Inverse Problems and Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016
[19]	Klemens Fellner, Wolfang Prager, Bao Q. Tang. The entropy method for reaction-diffusion systems without detailed balance: First order chemical reaction networks. Kinetic and Related Models, 2017, 10 (4) : 1055-1087. doi: 10.3934/krm.2017042
[20]	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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Konstantinos Drakakis Francesco Iorio Scott Rickard
on Google Scholar
Konstantinos Drakakis Francesco Iorio Scott Rickard

[Back to Top]