A complete description of Golay pairs for lengths up to 100

Authors:
P. B. Borwein and R. A. Ferguson

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

Published electronically:
July 1, 2003

MathSciNet review:
2031419

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In his 1961 paper, Marcel Golay showed how the search for pairs of binary sequences of length with complementary autocorrelation is at worst a problem. Andres, in his 1977 master's thesis, developed an algorithm which reduced this to a search and investigated lengths up to 58 for existence of pairs. In this paper, we describe refinements to this algorithm, enabling a 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 generated by a primitive pair of length . 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.

**1.**T.H. Andres,*Some combinatorial properties of complementary sequences*, M.Sc. Thesis, University of Manitoba, Winnipeg, 1977.**2.**T.H. Andres, R.G. Stanton,*Golay Sequences*, Lecture Notes in Mathematics,**622**, 44-54, 1977. MR**57:5380****3.**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.**4.**Dragomir Djokovic,*Equivalence classes and representatives of Golay sequences*, Discrete Math.**189**, 79-92, 1998. MR**99j:94031****5.**S. Eliahou, M. Kervaire, B. Saffari,*A new restriction on the lengths of Golay complementary sequences*, J. Comb. Theory (A)**55**: 49-59, 1990. MR**91i:11020****6.**S. Eliahou, M. Kervaire, B. Saffari,*On Golay polynomial pairs*, Adv. in Appl. Math.**12**, No. 3: 235-292, 1991. MR**93b:68066****7.**M.J.E. Golay,*Complementary Series*, IRE Trans. Inform. Theory,**IT-7**: 82-87, 1961. MR**23:A3096****8.**M.J.E. Golay,*Note on complementary series*, Proc. IRE: 84, Jan. 1962.**9.**M. James,*Golay sequences*, Honours Thesis, University of Sydney, 1987.**10.**Stephen Jauregui, Jr.,*Complementary series of length 26*, IRE Trans. Inform. Theory,**IT-7**: 323, 1962.**11.**R.J. Turyn,*Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings*. J. Combinatorial Theory Ser. (A)**16**: 313-333, 1974. MR**49:10577**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11B83,
05B20,
94A11,
68R05

Retrieve articles in all journals with MSC (2000): 11B83, 05B20, 94A11, 68R05

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

DOI:
https://doi.org/10.1090/S0025-5718-03-01576-X

Keywords:
Complementary pairs,
composition of sequences

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

Article copyright:
© Copyright 2003
Copyright retained by the authors