Low autocorrelation binary sequences beyond length 66

Find a sequence of $\pm 1$ values whose shifted copies are as uncorrelated with it as possible. Optimal sequences are known only up to length 66, and the problem appears under several names: radar and sonar pulse design, flat Littlewood polynomials, and the ground states of the Bernasconi spin model.

Problem

For a sequence $S = (s_1, \dots, s_N)$ with $s_i \in \{-1, +1\}$ , the aperiodic autocorrelations are

C_k(S) = \sum_{i=1}^{N-k} s_i\, s_{i+k}, \qquad k = 1, \dots, N-1,

and the energy is $E(S) = \sum_{k=1}^{N-1} C_k(S)^2$ . The low autocorrelation binary sequence (LABS) problem asks, for each length $N$ , for a sequence of minimum energy, or equivalently of maximum merit factor $F(S) = N^2 / (2E(S))$ . The open tasks are to find the minimum energy for lengths $N \ge 67$ and to find sequences with lower energy than the best known for longer $N$ . The asymptotic behaviour of the best merit factor $F_N$ as $N \to \infty$ is a separate question, discussed below but not asked here.

Background

The merit factor goes back to Golay, who argued heuristically that $F_N$ cannot asymptotically exceed about $12.3248$ (Golay, 1982). LABS entered CSPLib as problem 5, proposed by Toby Walsh, because its search landscape defeats both exhaustive and local search: optimal sequences are isolated and the best merit factors found by heuristics drop for long sequences. CSPLib collects several related sequence and ruler problems, among them Golomb rulers (prob006), which are catalogued separately.

What is known

Packebusch and Mertens (2016) found all optimal sequences for $N \le 66$ with a branch-and-bound algorithm running in time $\Theta(N \cdot 1.73^N)$ ; for $N = 66$ the minimum energy is 257 ( $F = 8.475$ ). They also found all optimal skew-symmetric sequences, a restricted class, up to $N = 119$ .
Skew-symmetric optima give good values for many odd lengths beyond 66; for $N = 67$ the best energy they report is 241 ( $F \approx 9.313$ ), and no one has proved it optimal.
Asymptotics: the best asymptotic merit factor proved for an explicit family, as reported by Packebusch and Mertens, is $6.342061\ldots$ , achieved by appended rotated Legendre sequences (Jedwab, Katz and Schmidt, 2013). In September and October 2026 OpenAI released preprints, with a Lean formalization, showing that some sign sequences of every large length have polynomials that are asymptotically flat on the unit circle, so that $F_N\to\infty$ , against Golay's heuristic [5]. The construction is existential, with no algorithm or rate, so it gives no sequences for the finite lengths asked about here.
Heuristic records keep improving for long sequences: in 2026 Pšeničnik, Bošković, Popić and Brest reported better sequences for 35 lengths between 450 and 527 and for $N = 573$ , including the longest known sequence with $F > 8$ ( $N = 451$ , $F = 8.0555$ ).

What would count as progress

A sequence of some length $N$ with lower energy than the best published value. Computing $E$ takes $O(N^2)$ operations, so a script checks a claim in milliseconds.
A proof that the minimum energy for $N = 67$ (or a larger length) equals a given value, for example by an exhaustive branch-and-bound search whose code and logs can be rerun. This is a separate, much harder kind of progress than a better sequence.
New optimal skew-symmetric sequences beyond $N = 119$ , the limit of [1]; skew-symmetric optima give the best known sequences at many odd lengths.

References

T. Packebusch and S. Mertens (2016). Low autocorrelation binary sequences. Journal of Physics A 49, 165001. https://doi.org/10.1088/1751-8113/49/16/165001 (arXiv:1512.02475)
M. J. E. Golay (1982). The merit factor of long low autocorrelation binary sequences. IEEE Transactions on Information Theory 28, 543–549. https://doi.org/10.1109/TIT.1982.1056505
J. Jedwab, D. J. Katz and K.-U. Schmidt (2013). Advances in the merit factor problem for binary sequences. Journal of Combinatorial Theory, Series A 120, 882–906. https://doi.org/10.1016/j.jcta.2013.01.010
B. Pšeničnik, B. Bošković, J. Popić and J. Brest (2026). Prioritizing search space regions in the low autocorrelation binary sequences problem. arXiv:2607.09688. https://arxiv.org/abs/2607.09688
OpenAI (2026). Real ultraflat Littlewood polynomials and unbounded binary merit factors, result 076 of the OpenAI mathematics release, with its Lean scope. https://github.com/openai/math/blob/main/lean/docs/076.md

Source

Imported from CSPLib prob005, curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.