The Merit Factor Problem

The merit factor is an important measure of the collective smallness of the aperiodic autocorrelations of a binary sequence (the other principal measure being the peak sidelobe level). The problem of determining the best value of the merit factor of long binary sequences has resisted decades of attack by mathematicians and communications engineers. In equivalent guise, the determination of the best asymptotic merit factor is an unsolved problem in complex analysis proposed by Littlewood in the 1960s, that was studied along largely independent lines for more than twenty years. The same problem is also studied in theoretical physics and theoretical chemistry as a notoriously difficult combinatorial optimisation problem. My 2005 survey paper traces the historical development of the merit factor problem, bringing together results from the various disciplines.

It has been known since 1988 that there are infinite families of binary sequences whose asymptotic merit factor is 6. Can a larger asymptotic merit factor value than 6 be attained by a family of binary sequences? Golay, who coined the term “merit factor”, speculated that even if it could, sequences attaining that value might never be found. In 1999, Kirilusha and Narayanaswamy offered the first numerical evidence that Golay's speculation might be incorrect. In 2004, Peter Borwein, Stephen Choi and I extended their work by constructing binary sequences whose merit factor appears to exceed 6.34, for sequence lengths up to several million. In 2013, Daniel Katz, Kai-Uwe Schmidt and I established the asymptotic merit factor properties of these sequences for the first time; the derived limiting value (an algebraic number greater than 6.34) is now the largest known asymptotic merit factor. We then gave a comprehensive treatment of the merit factor properties of Legendre sequences, m-sequences, and related binary sequence families, proving several conjectures and explaining numerical evidence of others.

Golay photo
M.J.E. Golay (1902-1989) coined the term “merit factor”.

Littlewood photo
J.E. Littlewood (1885-1977) studied the merit factor as a problem in complex analysis.