The circulant Hadamard conjecture and the possible orders of Hadamard matrices with one circulant core

This record states the open questions left by Orozco López's preprint on Schur rings over elementary abelian $2$-groups and circulant $S$-sets invariant under decimation: (i) Conjecture 1, the circulant Hadamard conjecture originating with Ryser — no circulant Hadamard matrix of order greater than $4$ exists — and (ii) Conjecture 2 — Hadamard matrices with one circulant core exist only at the four classical families of core orders ($p \equiv 3 \pmod 4$ prime, twin-prime products $q(q+2)$, $2^t-1$, and primes $4x^2+27$). Both are equivalent to classification questions for cyclic difference sets: nonexistence of parameters $(4u^2, 2u^2-u, u^2-u)$ for $u>1$, and confinement of the possible orders of cyclic difference sets with parameters $(4m-1, 2m-1, m-1)$ to the orders of the four classical families (quadratic-residue, twin-prime, Singer, and Hall). The two conjectures are unattributed restatements in the preprint of Ryser's 1963 conjecture and the Golomb–Song 1997 conjecture, respectively. Both problems remain open: the strongest general results are Leung–Schmidt's nonexistence theorems and Borwein–Mossinghoff's computations; several claimed proofs (Hurley–Hurley–Hurley 2012 — refuted by Craigen–Jedwab; Oh-Hashi 2016; Orozco López 2019; Morris 2023; Gallardo 2024) are refuted or unaccepted, and recent literature uniformly treats both conjectures as open.

Background

A Hadamard matrix is a square matrix $H$ with entries in $\{\pm 1\}$ whose rows are pairwise orthogonal, so that $HH^{T} = nI$ where $n$ is its order; such matrices can exist only when $n$ equals $1$, $2$, or a multiple of $4$. The famous Hadamard conjecture asserts existence for every multiple of $4$; it is listed among the open problems of the source paper but is a separate question, not the subject of this record. A circulant matrix is a matrix whose rows are successive cyclic shifts of a single row $(a_0, \ldots, a_{n-1})$, so it is determined by one binary sequence. The only known circulant Hadamard matrices have orders $1$ and $4$, and the conjecture — stated as Conjecture 1 of the source paper and originating in Ryser's 1963 monograph — is that no circulant Hadamard matrix of larger order exists.

The question has classical equivalent forms. For a circulant matrix, row orthogonality says that the periodic autocorrelation $\sum_{i} a_i a_{i+j}$ (the inner product of the sequence with its shift by $j$ positions, indices taken cyclically) vanishes for every $j \not\equiv 0$. Writing $D$ for the set of indices with $a_i = -1$, this is exactly the condition that $D$ is a difference set in the cyclic group $\mathbb{Z}_n$ of integers modulo $n$: a $k$-element subset such that every nonzero element of the group is representable as a difference of two elements of $D$ in exactly $\lambda$ ways. Comparing parameters forces $k = (n \pm \sqrt{n})/2$, so a circulant Hadamard matrix of order $n > 2$ must have $n = 4u^2$; the conjecture is therefore equivalent to the nonexistence of cyclic difference sets with parameters $(4u^2, 2u^2-u, u^2-u)$ for $u > 1$, and to the nonexistence of perfect binary sequences — binary sequences with zero periodic autocorrelation at every nonzero shift — of length greater than $4$. The problem is classically studied together with the Barker sequence problem, where a Barker sequence is a binary sequence whose aperiodic autocorrelations $\sum_{i=0}^{n-k-1} a_i a_{i+k}$ are all at most $1$ in absolute value: it is known that no Barker sequence has odd length greater than $13$ and that every Barker sequence of length $n > 13$ must have $n = 4u^2$, so the two nonexistence problems share the same critical orders.

A Hadamard matrix with one circulant core is a bordered variant of order $p+1$, $H = \begin{pmatrix} 1 & e \\ e^{T} & C \end{pmatrix},$ where $e$ is the all-ones vector and $C$ is a circulant $\pm 1$ matrix of order $p$ (studied systematically by Kotsireas, Koukouvinos and Seberry through the ideal structure of the defining equations). Orthogonality against the border forces each row of $C$ to sum to $-1$ and forces $p \equiv 3 \pmod 4$, and the set of $+1$ positions in the first row of $C$ is then a cyclic difference set with parameters $(p, (p-1)/2, (p-3)/4)$ — a cyclic Hadamard difference set. Four infinite families of such difference sets are classical: quadratic-residue difference sets (built from the nonzero squares modulo $p$) of prime order $p \equiv 3 \pmod 4$; twin-prime difference sets of order $q(q+2)$ where $q$ and $q+2$ are both prime; Singer difference sets, arising from the cyclic symmetry group of the point set of a projective geometry over the two-element field, of Mersenne orders $2^t-1$; and Hall sextic-residue difference sets, built from sixth-power residue classes, of prime orders $p = 4x^2+27$. Further cyclic difference sets carrying the same parameters as Singer's but inequivalent to it — notably the Gordon–Mills–Welch difference sets at Mersenne orders — are also known, which is why the order-classification conjectures below constrain possible orders and not equivalence classes of difference sets. Conjecture 2 of the source paper — which coincides with a conjecture of Golomb and Song from 1997 — asserts that these four families exhaust the possible orders of a one-circulant-core Hadamard matrix.

The source paper (Orozco López, arXiv:1802.05788) approaches both questions through Schur rings over the elementary abelian $2$-groups $\mathbb{Z}_2^n$. A Schur ring is a subring of the integral group ring spanned by a partition of the group into blocks, called basic sets or $S$-sets, that is closed under inversion; the paper studies which of these sets are invariant under the decimation operator (dilation of indices by a unit) and proves that circulant and one-core Hadamard matrices cannot exist when their defining sequences carry certain block-partitioned or sign-alternated structure; among these exclusions, its Corollary 11 recovers the odd-order case of Brualdi's 1965 corollary that no Hadamard matrix of order greater than $4$ is a symmetric circulant. These exclusions cover only structured proper subsets of the possibilities, and the paper states both conjectures as open.

Independent of this source, the strongest general restrictions on the circulant question are due to Leung and Schmidt: their field descent method and its refinements, which constrain how the group-ring equation behind a circulant Hadamard matrix can factor in rings of cyclotomic integers (integer rings of number fields generated by roots of unity), exclude most prime-factorization patterns of $u$ but leave genuinely open cases. On the computational side, Borwein and Mossinghoff verified the absence of Barker sequences up to an enormous bound and reported updated negative computations on open cases of the circulant Hadamard matrix problem; for the one-core side, Baumert and Gordon extended verified tables of cyclic difference sets to $k \le 300$, leaving open Paley-type parameter cases.

Problem Statement

Two linked questions, stated as Conjectures 1 and 2 of the source paper, jointly asking for a classification of the Hadamard matrices that are, or are built from, a single cyclic $\pm 1$ block — equivalently, of the cyclic difference sets whose parameters are forced by Hadamard orthogonality.

(1) Ryser's circulant Hadamard conjecture (Conjecture 1 of the source): no circulant Hadamard matrix of order greater than $4$ exists. Equivalently: there is no cyclic difference set with parameters $(4u^2, 2u^2-u, u^2-u)$ for any integer $u > 1$, and no perfect binary sequence (binary sequence with zero periodic autocorrelation at every nonzero shift) of length greater than $4$.

(2) One-circulant-core order classification (Conjecture 2 of the source; the Golomb–Song conjecture): a Hadamard matrix of order $p+1$ of the bordered form with a circulant core of order $p$ exists only when $p$ belongs to the four classical families — $p \equiv 3 \pmod 4$ prime, $p = q(q+2)$ with $q$ and $q+2$ both prime, $p = 2^t-1$ for a positive integer $t$, and $p = 4x^2+27$ prime for a positive integer $x$. Equivalently: cyclic difference sets with parameters $(4m-1, 2m-1, m-1)$ exist only at orders belonging to the four classical families; the conjecture constrains the possible orders, not the equivalence classes of the difference sets at those orders.

Both questions are posed in full generality, with no structural restriction — no symmetry, partition type, eigenvalue, or congruence hypothesis — imposed on the matrices beyond the stated circulant or bordered-circulant form. A resolution of either question at this full generality, and a fortiori of both, is a complete answer; conditional or template-restricted exclusions, such as those proved in the source paper and the prior literature, do not resolve either question.

References

1. Ronald Orozco López, Schur Ring over Group $\mathbb{Z}_2^n$, Circulant $S$-Sets Invariant by Decimation and Hadamard Matrices, arXiv:1802.05788 (2018), https://arxiv.org/abs/1802.05788 (source paper of the recorded open questions).
2. Herbert John Ryser, Combinatorial Mathematics, The Carus Mathematical Monographs No. 14, Mathematical Association of America, distributed by John Wiley and Sons (1963), Zbl 0112.24806, https://zbmath.org/?q=an%3A0112.24806.
3. Richard J. Turyn, Character sums and difference sets, Pacific Journal of Mathematics 15 (1965) 319-346, DOI 10.2140/pjm.1965.15.319, https://doi.org/10.2140/pjm.1965.15.319.
4. Richard A. Brualdi, A note on multipliers of difference sets, Journal of Research of the National Bureau of Standards, Section B 69 (1965) 87-89, DOI 10.6028/jres.069B.008, https://doi.org/10.6028/jres.069B.008 (Zbl 0132.25302).
5. Hong-Yeop Song, Solomon W. Golomb, On the existence of cyclic Hadamard difference sets, IEEE Transactions on Information Theory 40 (1994) 1266-1268, DOI 10.1109/18.335939, https://doi.org/10.1109/18.335939.
6. Solomon W. Golomb, Hong-Yeop Song, A conjecture on the existence of cyclic Hadamard difference sets, Journal of Statistical Planning and Inference 62 (1997) 39-41, DOI 10.1016/S0378-3758(96)00165-6, https://doi.org/10.1016/S0378-3758(96)00165-6.
7. B. Gordon, W. H. Mills, L. R. Welch, Some new difference sets, Canadian Journal of Mathematics 14 (1962) 614-625, DOI 10.4153/CJM-1962-052-2, https://doi.org/10.4153/CJM-1962-052-2 (Zbl 0111.24201; Gordon–Mills–Welch difference sets with Singer parameters, inequivalent to Singer's).
8. Leonard D. Baumert, Daniel M. Gordon, On the existence of cyclic difference sets with small parameters, in: High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of H. C. Williams, Fields Institute Communications 41, American Mathematical Society (2004) 61-68, arXiv:math/0304502, https://arxiv.org/abs/math/0304502 (Zbl 1065.05022).
9. Ilias S. Kotsireas, Christos Koukouvinos, Jennifer Seberry, Hadamard ideals and Hadamard matrices with circulant core, Journal of Combinatorial Mathematics and Combinatorial Computing 57 (2006) 47-63, Zbl 1117.05017, https://zbmath.org/?q=an%3A1117.05017.
10. Teodor Banica, Ion Nechita, Jean-Marc Schlenker, Analytic aspects of the circulant Hadamard conjecture, Annales Mathématiques Blaise Pascal 21 (2014) 25-59, DOI 10.5802/ambp.334, https://doi.org/10.5802/ambp.334.
11. 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.
12. Ka Hin Leung, Bernhard Schmidt, The anti-field-descent method, Journal of Combinatorial Theory, Series A 139 (2016) 87-131, DOI 10.1016/j.jcta.2015.11.005, https://doi.org/10.1016/j.jcta.2015.11.005.
13. Peter Borwein, Michael J. Mossinghoff, Wieferich pairs and Barker sequences II, LMS Journal of Computation and Mathematics 17 (2014) 24-32, DOI 10.1112/s1461157013000223, https://doi.org/10.1112/s1461157013000223.
14. Barry Hurley, Paul Hurley, Ted Hurley, The Hadamard circulant conjecture, Bulletin of the London Mathematical Society 44 (2012), DOI 10.1112/blms/bdq112, https://doi.org/10.1112/blms/bdq112.
15. Robert Craigen, Jonathan Jedwab, Comment on revised version of 'The Hadamard circulant conjecture', arXiv:1111.3437 (2011), https://arxiv.org/abs/1111.3437.
16. Yoshimasa Oh-Hashi, A Proof of Turyn's Conjecture: Nonexistence of Circulant Hadamard Matrices for Order Greater than Four, IEICE Transactions on Communications E99-B (2016) 1395-1407, DOI 10.1587/transcom.2015ebp3506, https://doi.org/10.1587/transcom.2015ebp3506.
17. Ronald Orozco López, Proof of the circulant Hadamard conjecture, arXiv:1907.12683 (2019), https://arxiv.org/abs/1907.12683.
18. Joshua Morris, A proof of Ryser's circulant Hadamard conjecture, arXiv:2302.08346 (2023), https://arxiv.org/abs/2302.08346.
19. Luis H. Gallardo, Ryser's Conjecture and Stochastic matrices, arXiv:2405.13033 (2024), https://arxiv.org/abs/2405.13033.
20. Luis H. Gallardo, Olivier Rahavandrainy, Reinhardt Euler, Combinatorial properties of Circulant Hadamard matrices, arXiv:2406.10748 (2024), https://arxiv.org/abs/2406.10748.
21. Luis H. Gallardo, Under a mild condition, Ryser's conjecture holds for every $n := 4h^2$ with $h > 1$ odd and non square-free, Mathematical Communications 26 (2021) 1-8, https://hrcak.srce.hr/252594.
22. Stefan Steinerberger, A Note on Approximate Hadamard Matrices, arXiv:2402.13202 (2024), https://arxiv.org/abs/2402.13202.
23. Jürgen Willms, A note on Barker sequences of even length, arXiv:2104.00502 (2021), https://arxiv.org/abs/2104.00502.