A complete description of Golay pairs for lengths up to 100

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.