New results on periodic Golay pairs

Lumsden, Tyler; Kotsireas, Ilias; Bright, Curtis

doi:10.1090/mcom/4096

New results on periodic Golay pairs
HTML articles powered by AMS MathViewer

by Tyler Lumsden, Ilias Kotsireas and Curtis Bright;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4096

Published electronically: April 15, 2025

PDF | Request permission

Abstract:

In this paper, we provide algorithmic methods for conducting exhaustive searches for periodic Golay pairs. Our methods enumerate several lengths beyond the currently known state-of-the-art available searches: we conducted exhaustive searches for periodic Golay pairs of all lengths $v \leq 72$ using our methods, while only lengths $v \leq 34$ had previously been exhaustively enumerated. Our methods are applicable to periodic complementary sequences in general. We utilize sequence compression, a method of sequence generation derived in 2013 by Ðoković and Kotsireas. We also introduce and implement a new method of “multi-level” compression, where sequences are uncompressed in several steps. This method allowed us to exhaustively search all lengths $v \leq 72$ using less than 10 compute years. For cases of complementary sequences where uncompression is not possible, we introduce some new methods of sequence generation inspired by the isomorph-free exhaustive generation algorithm of orderly generation. Finally, we pose a conjecture regarding the structure of periodic Golay pairs and prove it holds in many lengths, including all lengths $v<100$. We demonstrate the usefulness of our algorithms by providing the first ever examples of periodic Golay pairs of length $v = 90$. The smallest length for which the existence of periodic Golay pairs is undecided is now $106$.

References

Omar A. AbuGhneim, On nonabelian McFarland difference sets, Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing, 2004, pp. 159–175. MR 2122050
J. Alexander, R. Balasubramanian, J. Martin, K. Monahan, H. Pollatsek, and A. Sen, Ruling out $(160,54,18)$ difference sets in some nonabelian groups, J. Combin. Des. 8 (2000), no. 4, 221–231. MR 1760973, DOI 10.1002/1520-6610(2000)8:4<221::AID-JCD1>3.3.CO;2-Y
S. Baldwin, Compute Canada: advancing computational research, J. Phys. Conf. Ser. 341 (2012), DOI 10.1088/1742-6596/341/1/012001.
N. Balonin and D. Ž. Ðoković, Symmetry of two-circulant Hadamard matrices and periodic Golay pairs (Russian), Inf. Control Sys. (2015), no. 3, 2–16.
P. B. Borwein and R. A. Ferguson, A complete description of Golay pairs for lengths up to 100, Math. Comp. 73 (2004), no. 246, 967–985. MR 2031419, DOI 10.1090/S0025-5718-03-01576-X
Curtis Bright, Ilias Kotsireas, and Vijay Ganesh, Applying computer algebra systems with SAT solvers to the Williamson conjecture, J. Symbolic Comput. 100 (2020), 187–209. MR 4079047, DOI 10.1016/j.jsc.2019.07.024
Curtis Bright, Ilias Kotsireas, Albert Heinle, and Vijay Ganesh, Complex Golay pairs up to length 28: a search via computer algebra and programmatic SAT, J. Symbolic Comput. 102 (2021), 153–172. MR 4131454, DOI 10.1016/j.jsc.2019.10.013
R. Craigen, W. Holzmann, and H. Kharaghani, Complex Golay sequences: structure and applications, Discrete Math. 252 (2002), no. 1-3, 73–89. MR 1907747, DOI 10.1016/S0012-365X(01)00162-5
Dean Crnković, Doris Dumičić Danilović, Ronan Egan, and Andrea Švob, Periodic Golay pairs and pairwise balanced designs, J. Algebraic Combin. 55 (2022), no. 1, 245–257. MR 4382636, DOI 10.1007/s10801-021-01084-0
I. A. Faradžev, Constructive enumeration of combinatorial objects, Problèmes combinatoires et théorie des graphes, 1978, pp. 131–135.
Frank Fiedler and Jonathan Jedwab, How do more Golay sequences arise?, IEEE Trans. Inform. Theory 52 (2006), no. 9, 4261–4266. MR 2298554, DOI 10.1109/TIT.2006.880024
Frank Fiedler, Jonathan Jedwab, and Matthew G. Parker, A framework for the construction of Golay sequences, IEEE Trans. Inform. Theory 54 (2008), no. 7, 3114–3129. MR 2450821, DOI 10.1109/TIT.2008.924667
Frank Fiedler, Jonathan Jedwab, and Matthew G. Parker, A multi-dimensional approach to the construction and enumeration of Golay complementary sequences, J. Combin. Theory Ser. A 115 (2008), no. 5, 753–776. MR 2417020, DOI 10.1016/j.jcta.2007.10.001
Roderick J. Fletcher, Marc Gysin, and Jennifer Seberry, Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices, Australas. J. Combin. 23 (2001), 75–86. MR 1814602
M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE 93 (2005), no. 2, 216–231, DOI 10.1109/jproc.2004.840301.
M. J. E. Golay, Multi-slit spectrometry, J. Opt. Soc. Amer. 39 (1949), no. 6, 437, DOI 10.1364/JOSA.39.000437.
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 6th ed., Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silverman; With a foreword by Andrew Wiles. MR 2445243
Joel E. Iiams, Lander’s tables are complete!, Difference sets, sequences and their correlation properties (Bad Windsheim, 1998) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 542, Kluwer Acad. Publ., Dordrecht, 1999, pp. 239–257. MR 1735400
Jonathan Jedwab, Generalized perfect arrays and Menon difference sets, Des. Codes Cryptogr. 2 (1992), no. 1, 19–68. MR 1157478, DOI 10.1007/BF00124209
I. S. Kotsireas, C. Koukouvinos, P. M. Pardalos, and O. V. Shylo, Periodic complementary binary sequences and combinatorial optimization algorithms, J. Comb. Optim. 20 (2010), no. 1, 63–75. MR 2670202, DOI 10.1007/s10878-008-9194-5
Ilias Kotsireas and Christoph Koutschan, Legendre pairs of lengths $\ell \equiv 0\pmod 3$, J. Combin. Des. 29 (2021), no. 12, 870–887. MR 4373597, DOI 10.1002/jcd.21806
Ilias S. Kotsireas, Christos Koukouvinos, and Jennifer Seberry, Weighing matrices and string sorting, Ann. Comb. 13 (2009), no. 3, 305–313. MR 2557041, DOI 10.1007/s00026-009-0027-8
Siu Lun Ma and Bernhard Schmidt, The structure of the abelian groups containing McFarland difference sets, J. Combin. Theory Ser. A 70 (1995), no. 2, 313–322. MR 1329395, DOI 10.1016/0097-3165(95)90096-9
Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI 10.1006/jagm.1997.0898
Ronald C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math. 2 (1978), 107–120. MR 491273
Ken W. Smith, In search of a $(495, 39, 3)$ difference set, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), 1990, pp. 73–88. MR 1041839
R. J. Turyn, Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings, J. Combinatorial Theory Ser. A 16 (1974), 313–333. MR 345847, DOI 10.1016/0097-3165(74)90056-9
Dragomir Ž. Đoković, Equivalence classes and representatives of Golay sequences, Discrete Math. 189 (1998), no. 1-3, 79–93. MR 1637705, DOI 10.1016/S0012-365X(98)00034-X
Dragomir Ž. Đoković and Ilias S. Kotsireas, Some new periodic Golay pairs, Numer. Algorithms 69 (2015), no. 3, 523–530. MR 3360476, DOI 10.1007/s11075-014-9910-4
Dragomir Ž. Đoković and Ilias S. Kotsireas, Compression of periodic complementary sequences and applications, Des. Codes Cryptogr. 74 (2015), no. 2, 365–377. MR 3302662, DOI 10.1007/s10623-013-9862-z
Dragomir Ž. Đoković and Ilias S. Kotsireas, Periodic Golay pairs of length 72, Algebraic design theory and Hadamard matrices, Springer Proc. Math. Stat., vol. 133, Springer, Cham, 2015, pp. 83–92. MR 3440529, DOI 10.1007/978-3-319-17729-8_{7}

AMS Website Down

Mathematics of Computation

New results on periodic Golay pairs
HTML articles powered by AMS MathViewer

Abstract: