Legendre pairs of length 115 and the other open lengths below 200

A Legendre pair is two $\pm 1$ sequences whose periodic autocorrelations cancel almost perfectly, and each pair yields a Hadamard matrix. They are conjectured to exist for every odd length, but for ten odd lengths below 200, starting with 115, nobody has found one.

Problem

Let $\ell$ be odd and $m = (\ell - 1)/2$. For $A = (a_0, \dots, a_{\ell-1}) \in \{-1, +1\}^\ell$, define the periodic autocorrelation

$$\mathrm{PAF}_A(s) = \sum_{i=0}^{\ell-1} a_i\, a_{(i+s) \bmod \ell}.$$

A Legendre pair of length $\ell$ is a pair $A, B \in \{-1, +1\}^\ell$ with

$$\mathrm{PAF}_A(s) + \mathrm{PAF}_B(s) = -2 \quad (s = 1, \dots, m), \qquad \sum_i a_i = \sum_i b_i = 1.$$

Because $\mathrm{PAF}(s) = \mathrm{PAF}(\ell - s)$, this covers every nonzero shift. Find a Legendre pair for one of the open lengths

$$\ell \in \{115, 145, 159, 161, 169, 175, 177, 185, 187, 195\},$$

or prove that none exists for one of them.

Background

A Legendre pair of length $\ell$ gives, through a two-circulant-core construction, a Hadamard matrix of order $2\ell + 2$, so the conjecture that Legendre pairs exist for every odd $\ell$ is a structured route towards the Hadamard conjecture. The problem is problem 84 of CSPLib, proposed by Ilias Kotsireas, as a constraint satisfaction problem with $2\ell$ variables, $m$ quadratic constraints and two linear ones. Searches combine compression (summing entries over cosets), power spectral density tests and decimation symmetries, and have settled lengths one by one. The formal-conjectures project has a Lean statement of the Hadamard conjecture itself: https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/Hadamard.lean

What is known

• Kotsireas and Koutschan (2021) found pairs of lengths 117, 129, 133 and 147, and Kotsireas, Koutschan, Bulutoglu, Arquette, Turner and Ryan (2023) found lengths 85 and 87. That reduced the open lengths below 200 to the ten listed above.
• Kotsireas, Koutschan and Winterhof (2025) confirm that 115 is still the smallest unsettled length.
• At $\ell = 115$, two partial searches restricted by a multiplier symmetry have found nothing; the first was stopped after covering almost 4% of its search space, which took about 4,359 CPU days.
• Hadamard matrices of order $2\ell + 2$ are already known for these lengths by other constructions, so the question is specifically about Legendre pairs.

What would count as progress

• A pair $(A, B)$ for one of the open lengths, given as two lists of $\pm 1$. A script checks all $m$ autocorrelation conditions and both sums in $O(\ell^2)$ time, a few milliseconds.
• A proof that no Legendre pair exists for some odd length, which would refute the conjecture; this would need a certificate or exhaustive search that others can reproduce, and is a separate and much harder kind of progress.

References

1. I. Kotsireas and C. Koutschan (2021). Legendre pairs of lengths ℓ ≡ 0 (mod 3). Journal of Combinatorial Designs 29, 870–887. https://doi.org/10.1002/jcd.21806
2. I. Kotsireas, C. Koutschan, D. Bulutoglu, D. Arquette, J. Turner and K. Ryan (2023). Legendre pairs of lengths ℓ ≡ 0 (mod 5). Special Matrices 11, 20230105. https://doi.org/10.1515/spma-2023-0105
3. I. S. Kotsireas, C. Koutschan and A. Winterhof (2025). Quaternary Legendre pairs II. Discrete Mathematics 348, 114501. https://doi.org/10.1016/j.disc.2025.114501
4. CSPLib problem 84, 2cc Hadamard matrix Legendre pairs, with the CSP instances for odd ℓ up to 99. https://www.csplib.org/Problems/prob084/

Source

Imported from CSPLib prob084, 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.