A complete description of Golay pairs for lengths up to 100
HTML articles powered by AMS MathViewer
- by P. B. Borwein and R. A. Ferguson PDF
- Math. Comp. 73 (2004), 967-985
Abstract:
In his 1961 paper, Marcel Golay showed how the search for pairs of binary sequences of length $n$ with complementary autocorrelation is at worst a $2^{\frac {3n}{2}-6}$ problem. Andres, in his 1977 master’s thesis, developed an algorithm which reduced this to a $2^{\frac {n}{2}-1}$ search and investigated lengths up to 58 for existence of pairs. In this paper, we describe refinements to this algorithm, enabling a $2^{\frac {n}{2}-5}$ search at length 82. We find no new pairs at the outstanding lengths 74 and 82. In extending the theory of composition, we are able to obtain a closed formula for the number of pairs of length $2^kn$ generated by a primitive pair of length $n$. Combining this with the results of searches at all allowable lengths up to 100, we identify five primitive pairs. All others pairs of lengths less than 100 may be derived using the methods outlined.References
- T.H. Andres, Some combinatorial properties of complementary sequences, M.Sc. Thesis, University of Manitoba, Winnipeg, 1977.
- T. H. Andres and R. G. Stanton, Golay sequences, Combinatorial mathematics, V (Proc. Fifth Austral. Conf., Roy. Melbourne Inst. Tech., Melbourne, 1976) Lecture Notes in Math., Vol. 622, Springer, Berlin, 1977, pp. 44–54. MR 0465481
- James A. Davis, Jonathan Jedwab, Peak-to mean power control in OFDM, Golay complementary sequences and Reed-Muller codes, IEEE Transactions on Information Theory 45: 2397-2417, 1999.
- 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
- Shalom Eliahou, Michel Kervaire, and Bahman Saffari, A new restriction on the lengths of Golay complementary sequences, J. Combin. Theory Ser. A 55 (1990), no. 1, 49–59. MR 1070014, DOI 10.1016/0097-3165(90)90046-Y
- Shalom Eliahou, Michel Kervaire, and Bahman Saffari, On Golay polynomial pairs, Adv. in Appl. Math. 12 (1991), no. 3, 235–292. MR 1117993, DOI 10.1016/0196-8858(91)90014-A
- Marcel J. E. Golay, Complementary series, IRE Trans. IT-7 (1961), 82–87. MR 0125799, DOI 10.1109/tit.1961.1057620
- M.J.E. Golay, Note on complementary series, Proc. IRE: 84, Jan. 1962.
- M. James, Golay sequences, Honours Thesis, University of Sydney, 1987.
- Stephen Jauregui, Jr., Complementary series of length 26, IRE Trans. Inform. Theory, IT-7: 323, 1962.
- 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
Additional Information
- P. B. Borwein
- Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia V5A 1S6 Canada
- Email: pborwein@cecm.sfu.ca
- R. A. Ferguson
- Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia V5A 1S6 Canada
- Email: rferguson@pims.math.ca
- Received by editor(s): December 10, 2001
- Received by editor(s) in revised form: November 28, 2002
- Published electronically: July 1, 2003
- Additional Notes: Research of the authors was supported in part by grants from NSERC of Canada and MITACS Symbolic Analysis Project
- © Copyright 2003 Copyright retained by the authors
- Journal: Math. Comp. 73 (2004), 967-985
- MSC (2000): Primary 11B83, 05B20; Secondary 94A11, 68R05
- DOI: https://doi.org/10.1090/S0025-5718-03-01576-X
- MathSciNet review: 2031419