Existence of periodic compatible binary sequences and circulant-core Hadamard matrices: the six conjectures of Orozco López (2018)

A 2018 paper of R. Orozco López introduces periodic compatible binary sequences — families of $\{\pm1\}$-sequences of common period $n$ whose periodic autocorrelations sum to one constant $d$ at every nonzero shift, written $PComS(n,k,d)$ — as a common generalization of Hadamard matrices, periodic complementary sequences, and two-level autocorrelation sequences, and poses six interrelated existence conjectures: (1) no circulant Hadamard matrix of order greater than $4$ exists (the circulant Hadamard conjecture, attributed to Ryser); (2) a Hadamard matrix of order $p+1$ with one circulant core exists only for the four classical families of cyclic Hadamard difference sets; (3) a Hadamard matrix of order $2n+2$ with two circulant cores exists for every odd $n$ (the Legendre-pair existence conjecture); (4) a Goethals–Seidel Hadamard matrix exists for every order divisible by $4$; (5) no perfect binary sequence with constant off-peak autocorrelation $d=1$ has period $2u^{2}+2u+1$ with $u\ge3$; (6) no perfect binary sequence with $d=2$ has period greater than $6$. All six remain open, each with substantial partial results: circulant Hadamard matrices are excluded for every order $4<n<548{,}964{,}900$, $d=1$ perfect sequences below period $20{,}605$, $d=2$ perfect sequences below period $33{,}895{,}686$, and Legendre pairs are known for all but ten odd lengths below $200$. The problem is to determine, by proof or explicit counterexample, the truth of each conjecture.

Background

An $n\times n$ matrix $H$ with all entries in $\{\pm1\}$ is a Hadamard matrix when its rows are pairwise orthogonal, equivalently $HH^{t}=nI_{n}$, where $H^{t}$ is the transpose and $I_{n}$ the identity matrix. Such matrices can exist only in orders $1$, $2$, or multiples of $4$; the Hadamard conjecture asserts that they exist in every such order and is itself open (the smallest order not yet settled is $668$ as of 2026). This record concerns a family of circulant-structured Hadamard matrices and of binary sequences with near-ideal autocorrelation posed as six interrelated conjectures by Orozco López (2018).

A circulant matrix is a square matrix whose rows are successive cyclic shifts of its first row. A circulant Hadamard matrix of order $n$ is equivalent to a $\{\pm1\}$-sequence $s=(s_{0},\dots,s_{n-1})$ of period $n$ whose periodic autocorrelation $C(t)=\sum_{i}s_{i}s_{i+t}$ (indices modulo $n$) vanishes at every nonzero shift: the cyclic shifts of $s$ then form the orthogonal rows. More generally, a binary sequence has two-level autocorrelation when $C(t)=d$ is constant for all $t\not\equiv0\pmod n$; such sequences are equivalent to cyclic difference sets — subsets $D\subseteq\mathbb{Z}_{n}$ with $|D|=k$ such that every nonzero element of $\mathbb{Z}_{n}$ has exactly $\lambda$ representations as a difference of two elements of $D$ — via $d=n-4(k-\lambda)$. A perfect binary sequence is one whose constant off-peak value $d$ has the smallest absolute value permitted by $n\bmod 4$: $d=0$ for $n\equiv0\pmod4$, $d=1$ for $n\equiv1\pmod4$, $d=\pm2$ for $n\equiv2\pmod4$, $d=-1$ for $n\equiv3\pmod4$. The identity $\sum_{t}C(t)=(\sum_{i}s_{i})^{2}$ forces arithmetic structure on the periods: for $d=0$ the period is a square $4m^{2}$ (with $m$ odd; classical theorem of Turyn, see Gallardo–Rahavandrainy–Euler 2024, ref. 3), and for $d=1$ the period has the form $(w^{2}+1)/2=2u^{2}+2u+1$ with $w=2u+1$ odd.

The source paper unifies these objects as periodic compatible binary sequences: a family $PComS(n,k,d)$ consists of $k$ binary sequences of common period $n$ whose autocorrelations sum to the same constant $d$ at every nonzero shift. The case $k=1$ is a two-level (in particular perfect) binary sequence; $k=2$ with $d=-2$ and row sums $\pm1$ is exactly a Legendre pair; two-sequence families with $d=0$ are the periodic Golay pairs studied in the communications literature. The paper bounds the sizes of these families using the run structure of the sequences (their maximal blocks of consecutive equal symbols) and Schur rings (subrings of integer group rings spanned by orbits of subgroups, a tool from algebraic combinatorics), and then poses six conjectures connecting to four classical problem families.

First, the circulant Hadamard conjecture, attributed to Ryser and standard in the literature (see Gallardo–Rahavandrainy–Euler 2024 for the attribution): no circulant Hadamard matrix of order greater than $4$ exists — equivalently, no $d=0$ perfect binary sequence of period greater than $4$ exists. Several purported proofs have been circulated, but none is accepted: the argument of Hurley–Hurley–Hurley (ref. 4) was refuted by Craigen–Jedwab (ref. 5), and the later proofs claimed by Orozco López (refs. 6–7) and Morris (ref. 8) remain unrefereed. Second, Hadamard matrices with one circulant core: a bordered matrix of order $p+1$ whose core is a circulant $\{\pm1\}$ matrix of order $p$ is equivalent to a cyclic Hadamard difference set with parameters $(4t-1,2t-1,t-1)$ on the group $\mathbb{Z}_{p}$; only four families of these are known — quadratic-residue (Paley) sets for primes $p\equiv3\pmod4$, twin-prime sets for $p=q(q+2)$ with $q,q+2$ prime, Singer sets for Mersenne numbers $p=2^{t}-1$, and Hall sextic-residue sets for primes $p=4x^{2}+27$. Third, Hadamard matrices with two circulant cores: matrices of order $2n+2$ built from two circulant $\{\pm1\}$ matrices $A,B$ of order $n$ satisfying

$$AA^{t}+BB^{t}=(2n+2)I_{n}-2J_{n}$$

with $J_{n}$ the all-ones matrix; these are equivalent to Legendre pairs of odd length $n$ (two $\{\pm1\}$-sequences with row sums $\pm1$ whose periodic autocorrelations sum to $-2$ at every nonzero shift), and constructions are known when $n$ is prime, $2n+1$ is a prime power, $n=2^{k}-1$, $n=p(p+2)$, for all odd $n\le63$, and for $n=143$ (Kotsireas–Koukouvinos–Seberry 2006). Fourth, Goethals–Seidel arrays: Hadamard matrices of order $n$ divisible by $4$ assembled from four circulant $\{\pm1\}$-matrices $A,B,C,D$ of order $n/4$ satisfying the core equation $AA^{t}+BB^{t}+CC^{t}+DD^{t}=nI_{n/4}$, pairwise amicable (each pair $A,B$ satisfies $AB^{t}=BA^{t}$), with row sums $a,b,c,d$ obeying $a^{2}+b^{2}+c^{2}+d^{2}=n$; this Williamson-type assembly is responsible for many known Hadamard matrices. Finally, perfect binary sequences with $d=1$ (only periods $5$ and $13$ known) and with $d=2$ (only period $6$ known). The paper's conclusion states that the six conjectures are all related and jointly frame one research program.

Problem Statement

Determine the truth of each of the following six conjectures of Orozco López (2018), which together ask for the existence/nonexistence classification of the periodic compatible binary sequence families underlying circulant-structured Hadamard matrices and perfect binary sequences. Refutation of a nonexistence conjecture requires an explicit object in the conjectured-empty range, and refutation of an existence conjecture requires a proof of nonexistence at some admissible parameter, while a proof of the general statement settles a conjecture affirmatively.

1. (Conjecture 1; the circulant Hadamard conjecture, attributed to Ryser) No circulant Hadamard matrix of order larger than $4$ exists; equivalently, there is no binary sequence of period $n>4$ whose periodic autocorrelation vanishes at every nonzero shift.

2. (Conjecture 2) If a Hadamard matrix with one circulant core of order $p+1$ exists, then $p\equiv3\pmod4$ is prime, or $p=q(q+2)$ with $q$ and $q+2$ both prime, or $p=2^{t}-1$ for a positive integer $t$, or $p=4x^{2}+27$ is prime; equivalently, the only cyclic Hadamard difference sets are the Paley/quadratic-residue, twin-prime, Singer/Mersenne, and Hall families.

3. (Conjecture 3) For every odd $n$ there exists a Hadamard matrix of order $2n+2$ with two circulant cores; equivalently, a Legendre pair of length $n$ exists for every odd $n$.

4. (Conjecture 4) If $n$ is a multiple of $4$, then a Goethals–Seidel Hadamard matrix of order $n$ exists.

5. (Conjecture 5) There is no $PComS(2u^{2}+2u+1,1,1)$ with $u\ge3$; since every binary sequence with constant off-peak autocorrelation $d=1$ has period $2u^{2}+2u+1$, this is equivalent to: no perfect binary sequence with $d=1$ exists of period greater than $13$.

6. (Conjecture 6) There is no $PComS(n,1,2)$ with $n>6$; equivalently, no binary sequence with constant off-peak autocorrelation $d=2$ exists of period greater than $6$.

The conjectures are linked by the source's framework: conjectures 1, 2, 5 and 6 are nonexistence and classification statements about single two-level autocorrelation sequences (cyclic difference sets with $d=0$, the $d=-1$ Hadamard families, and $d=1$, $d=2$), while conjectures 3 and 4 assert existence of complementary families ($d=-2$ pairs and four-matrix Goethals–Seidel assemblies) for all admissible parameters. The common objective is a complete existence decision for each of these families; the completion boundary is that all six conjectures are settled, each by a proof or a definitive counterexample.

References

1. Ronald Orozco López, Schur Ring, Run Structure and Periodic Compatible Binary Sequences, arXiv:1807.10849 (2018), DOI 10.48550/arXiv.1807.10849, https://arxiv.org/abs/1807.10849
2. Ka Hin Leung, Bernhard Schmidt, New restrictions on possible orders of circulant Hadamard matrices, Designs, Codes and Cryptography 64 (2012) 143–151, DOI 10.1007/s10623-011-9493-1, https://doi.org/10.1007/s10623-011-9493-1
3. Luis H. Gallardo, Olivier Rahavandrainy, Reinhardt Euler, Combinatorial properties of Circulant Hadamard matrices, arXiv:2406.10748 (2024), DOI 10.48550/arXiv.2406.10748, https://arxiv.org/abs/2406.10748
4. Barry Hurley, Paul Hurley, Ted Hurley, The Hadamard circulant conjecture, arXiv:1109.0748 (2011); published in Bulletin of the London Mathematical Society 44 (2012) 206, DOI 10.1112/blms/bdq112, https://doi.org/10.1112/blms/bdq112
5. Robert Craigen, Jonathan Jedwab, Comment on revised version of 'The Hadamard circulant conjecture', arXiv:1111.3437 (2011), DOI 10.48550/arXiv.1111.3437, https://arxiv.org/abs/1111.3437
6. Ronald Orozco López, An Approximation to Proof of the Circulant Hadamard Conjecture, arXiv:1804.05007 (2018), DOI 10.48550/arXiv.1804.05007, https://arxiv.org/abs/1804.05007
7. Ronald Orozco López, Proof of the circulant Hadamard conjecture, arXiv:1907.12683 (2019), DOI 10.48550/arXiv.1907.12683, https://arxiv.org/abs/1907.12683
8. Joshua Morris, A proof of Ryser's circulant Hadamard conjecture, arXiv:2302.08346 (2023), DOI 10.48550/arXiv.2302.08346, https://arxiv.org/abs/2302.08346
9. Leonard D. Baumert, Daniel M. Gordon, On the existence of cyclic difference sets with small parameters, arXiv:math/0304502 (2003), DOI 10.48550/arXiv.math/0304502, https://arxiv.org/abs/math/0304502
10. X. Niu, H. Cao, K. Feng, Non-existence of perfect binary sequences, arXiv:1804.03808 (2018); published as Binary periodic sequences with 2-level autocorrelation values, Discrete Mathematics 343 (2020) 111723, DOI 10.1016/j.disc.2019.111723, https://doi.org/10.1016/j.disc.2019.111723
11. Kai-Uwe Schmidt, Sequences with small correlation, Designs, Codes and Cryptography 78 (2016) 237–267, DOI 10.1007/s10623-015-0154-7, https://doi.org/10.1007/s10623-015-0154-7
12. Dieter Jungnickel, Alexander Pott, Perfect and almost perfect sequences, Discrete Applied Mathematics 95 (1999) 331–359, DOI 10.1016/S0166-218X(99)00085-2, https://doi.org/10.1016/S0166-218X(99)00085-2
13. Ilias Kotsireas, Christoph Koutschan, Legendre pairs of lengths ℓ ≡ 0 (mod 3), Journal of Combinatorial Designs 29(12) (2021) 870–887, DOI 10.1002/jcd.21806, arXiv:2101.03116, https://doi.org/10.1002/jcd.21806
14. Ilias Kotsireas, Christoph Koutschan, Dursun Bulutoglu, David Arquette, Jonathan Turner, Kenneth Ryan, Legendre pairs of lengths ℓ ≡ 0 (mod 5), Special Matrices 11 (2023) 20230105, DOI 10.1515/spma-2023-0105, arXiv:2111.02105, https://doi.org/10.1515/spma-2023-0105
15. N. A. Balonin, D. Ž. Đoković, Three new lengths for cyclic Legendre pairs, Information and Control Systems 2021(1) (2021) 2–7, DOI 10.31799/1684-8853-2021-1-2-7, arXiv:2010.02829, https://doi.org/10.31799/1684-8853-2021-1-2-7
16. Jonathan Turner, Ilias Kotsireas, Dursun Bulutoglu, Andrew Geyer, Legendre pair of length 77 using complementary binary matrices with fixed marginals, arXiv:2101.10918 (2021), DOI 10.48550/arXiv.2101.10918, https://arxiv.org/abs/2101.10918
17. Arthur F. Ramos, David B. Hulak, Ruy J. G. B. de Queiroz, Multiplier obstructions for Legendre pairs of length 333, arXiv:2607.20765 (2026), DOI 10.48550/arXiv.2607.20765, https://arxiv.org/abs/2607.20765
18. Ilias S. Kotsireas, Christos Koukouvinos, Jennifer Seberry, Hadamard ideals and Hadamard matrices with two circulant cores, European Journal of Combinatorics 27 (2006) 658–668, DOI 10.1016/j.ejc.2005.03.004, https://doi.org/10.1016/j.ejc.2005.03.004
19. Curtis Bright, Ilias Kotsireas, Vijay Ganesh, Applying Computer Algebra Systems with SAT Solvers to the Williamson Conjecture, arXiv:1804.01172 (2018); published as Applying computer algebra systems with SAT solvers to the Williamson conjecture, Journal of Symbolic Computation 100 (2020) 187–209, DOI 10.1016/j.jsc.2019.07.024, https://doi.org/10.1016/j.jsc.2019.07.024
20. Tyler Lumsden, Ilias Kotsireas, Curtis Bright, New Results on Periodic Golay Pairs, arXiv:2408.15611 (2024); published in Mathematics of Computation 95(359) (2025) 1517–1539, DOI 10.1090/mcom/4096, https://doi.org/10.1090/mcom/4096
21. Dragomir Z. Djokovic, Ilias S. Kotsireas, Goethals-Seidel difference families with symmetric or skew base blocks, arXiv:1802.00556 (2018); published in Mathematics in Computer Science 12 (2018) 373–388, DOI 10.1007/s11786-018-0381-1, https://doi.org/10.1007/s11786-018-0381-1
22. Dragomir Z. Djokovic, Ilias S. Kotsireas, Compression of Periodic Complementary Sequences and Applications, arXiv:1302.0571 (2013); published in Designs, Codes and Cryptography 74 (2015) 365–377, DOI 10.1007/s10623-013-9862-z, https://doi.org/10.1007/s10623-013-9862-z