Ryser's conjecture on circulant Hadamard matrices

The order-4 circulant Hadamard matrix. Each row is a cyclic shift of the preceding row, and $H{H}^{𝖳}=4I_4$.

In matrix theory and combinatorics, Ryser's conjecture on circulant Hadamard matrices, also called the circulant Hadamard matrix conjecture, states that no real circulant Hadamard matrix has order greater than 4. The conjecture is attributed to Herbert John Ryser, who recorded the problem in 1963.

A circulant Hadamard matrix of order $n$ is an $n\times n$ circulant matrix $H$ with entries in $\{-1,1\}$ such that $$H{H}^{𝖳}=n{I}_n.$$ The order-1 and order-4 examples are the only known real circulant Hadamard matrices. Elementary considerations show that any further example would have order $4u^2$. Richard Turyn proved that $u>1$ would have to be odd and could not be a prime power. Equivalently, the conjecture asserts that no nontrivial cyclic Menon–Hadamard difference set exists.

The problem has equivalent formulations in terms of periodic autocorrelation, discrete Fourier transforms, Littlewood polynomials, perfect binary sequences, and cyclic Menon–Hadamard difference sets. It is also closely connected with the open problem of whether a Barker sequence can have length greater than 13.

Definition and the order-4 example

Let $a=(a_0,a_1,\dots ,a_{n-1})$, where each $a_j\in \{-1,1\}$. The circulant matrix generated by $a$ is $$H=\mathrm{circ}(a_0,a_1,\dots ,a_{n-1}),H_{r,s}=a_{s-rmodn}.$$ It is Hadamard exactly when distinct cyclic shifts of $a$ are orthogonal. In the terminology of weighing matrices, it is a circulant weighing matrix of weight $n$.

For $n=4$, one example is $$\left(\begin{array}{cccc}1& 1& 1& -1\\ -1& 1& 1& 1\\ 1& -1& 1& 1\\ 1& 1& -1& 1\end{array}\right).$$ The four cyclic shifts of the generating row and their negatives give the eight order-4 circulant Hadamard matrices.

Necessary form of the order

The all-ones vector is an eigenvector of a circulant matrix, with eigenvalue $P(1)=\sum _j{a}_j$. If $H$ is Hadamard, then $$P(1{)}^2=n,$$ so $n$ is a square. Every real Hadamard matrix of order greater than 2 has order divisible by 4. It follows that every nontrivial circulant Hadamard matrix has order $$n=4u^2.$$ There is no order-2 circulant Hadamard matrix, since its row sum would have to be the non-integer $\pm \sqrt{2}$.

Turyn proved the substantially stronger restrictions that $u$ must be odd and cannot be a prime power. He also developed the self-conjugacy test, a character-sum divisibility criterion. One useful consequence is that, if $p^a$ is the exact power of an odd prime $p$ dividing $u$, then $$p^{3a}\le 2u^2.$$ Thus no single prime-power divisor of $u$ can be too large compared with the remaining factors.

Equivalent formulations

Periodic autocorrelation

The periodic autocorrelation of $a$ at shift $t$ is $$C_a(t)=\sum _{j=0}^{n-1}{a}_j{a}_{j+tmodn}.$$ The rows of $H$ are the cyclic shifts of $a$, so $$H{H}^{𝖳}=n{I}_n⟺C_a(0)=n\text{ and }{C}_a(t)=0(1\le t<n).$$ Thus a circulant Hadamard matrix is equivalent to a binary sequence with zero nontrivial periodic autocorrelations, often called a perfect binary sequence.

Fourier and polynomial formulation

Let $$P(z)=\sum _{j=0}^{n-1}{a}_j{z}^j$$ be the associated Littlewood polynomial, and let $\omega =e^{2\pi i/n}$. Circulant matrices are diagonalized by the discrete Fourier matrix, and the eigenvalues of $H$ are $P({\omega }^k)$, for $0\le k<n$. Consequently, $$H\text{ is Hadamard}⟺|P({\omega }^k)|=\sqrt{n}(0\le k<n).$$ In this language, the conjecture says that a polynomial with coefficients $\pm 1$ cannot be exactly flat on all $n$th roots of unity when $n>4$.

Cyclic Menon–Hadamard difference sets

Suppose $n=4u^2$ and, after negating the sequence if necessary, assume that $\sum _j{a}_j=2u$. Let $$D=\{j\in {\mathbb{Z}}_n:a_j=-1\}.$$ Then $|D|=2u^2-u$. The equations $C_a(t)=0$ for nonzero $t$ are equivalent to requiring every nonzero element of ${\mathbb{Z}}_{4u^2}$ to occur exactly $u^2-u$ times among the ordered differences $d_1-d_2$ with $d_1,d_2\in D$. Hence a circulant Hadamard matrix of order $4u^2$ is equivalent, up to complementing $D$, to a cyclic difference set with parameters $$(v,k,\lambda )=(4u^2,2u^2-u,u^2-u).$$

Difference sets with these parameters, and their complements, are called Menon difference sets, Menon–Hadamard difference sets, or Hadamard difference sets. They are named after P. Kesava Menon, who in 1962 studied difference sets satisfying $v=4(k-\lambda )$. Their translates form the blocks of a symmetric $2\text{-}(4u^2,2u^2-u,u^2-u)$ Menon design, and their sign functions give regular group-developed Hadamard matrices. Thus Ryser's conjecture is equivalently the assertion that no cyclic Menon–Hadamard difference set exists for $u>1$.

Many Menon–Hadamard difference sets are known in noncyclic groups. Broad constructions exist, for example, in groups formed from a group of order 4 and elementary abelian groups of odd-prime-power order. The exceptional requirement in the circulant Hadamard problem is therefore that the developing group be cyclic.

Difference-set context

Broader Ryser and Lander conjectures

Template:Further For a $(v,k,\lambda )$ difference set, the integer $N=k-\lambda$ is called the order of the difference set. A broader conjecture, also attributed to Ryser, states that a difference set in a cyclic group must satisfy $$gcd(v,N)=1.$$ For a Menon–Hadamard difference set, $v=4u^2$ and $N=u^2$, so the circulant Hadamard conjecture is a special case.

A stronger conjecture, proposed in 1983 by E. S. Lander, states that, if an abelian group of order $v$ contains a difference set of order $N$ and a prime $p$ divides both $v$ and $N$, then the Sylow $p$-subgroup cannot be cyclic. Lander's conjecture implies the broader cyclic difference-set conjecture and hence the circulant Hadamard conjecture. It has been proved when $N$ is a power of a prime greater than 3; for powers of 2 or 3, strong restrictions are known on any possible cyclic Sylow subgroup.

Bent functions and noncyclic analogues

The Fourier-flat formulation also places the problem in the theory of generalized bent functions. A map $f:{\mathbb{Z}}_n\to {\mathbb{Z}}_2$ is generalized bent when, for every $k$, $$|\sum _{j=0}^{n-1}(-1{)}^{f(j)}{e}^{-2\pi ikj/n}|=\sqrt{n}.$$ Thus a circulant Hadamard matrix is equivalent to a binary generalized bent function on the cyclic group ${\mathbb{Z}}_n$. More generally, generalized bent functions are linked by standard equivalences to group-invariant Butson-type Hadamard matrixs, perfect arrays, and, under suitable hypotheses, splitting relative difference sets.

Classical Boolean bent functions have domain $V={𝔽}_2^{2m}$. If $f:V\to {𝔽}_2$ is bent, then $$H_f={((-1{)}^{f(x+y)})}_{x,y\in V}$$ is a group-developed Hadamard matrix, and the support of $f$, or its complement, is a Menon–Hadamard difference set in $V$, with $u=2^{m-1}$. The group $V$ is noncyclic. For $m>1$, these therefore give higher-order noncyclic analogues rather than counterexamples to Ryser's conjecture. Replacing the binary alphabet by complex roots of unity similarly leads to perfect polyphase sequences and circulant Butson-type Hadamard matrices.

Number-theoretic methods

For a cyclic Menon–Hadamard difference set $D\subseteq {\mathbb{Z}}_{4u^2}$ and every nonprincipal character $\chi$, the difference-set equations imply $$\chi (D)\overline{\chi (D)}=u^2.$$ Thus $\chi (D)$ is a cyclotomic integer of prescribed absolute value. Number-theoretic approaches study the prime-ideal factorization, Galois symmetries, and possible fields of definition of these character sums. The classical background includes Gauss sums and Stickelberger's theorem, which gives explicit prime-ideal factorizations for powers of Gauss sums in cyclotomic fields.

Character sums, multipliers and self-conjugacy

Turyn's method combines character sums with multiplier theory, self-conjugacy, and magnitude bounds. A numerical multiplier is an automorphism of the cyclic group that sends a difference set to one of its translates. When a rational prime is self-conjugate, or semiprimitive, modulo the relevant conductor, complex conjugation fixes the prime ideals above it. Divisibility of $\chi (D)\overline{\chi (D)}$ then forces divisibility of $\chi (D)$ itself. Bounds on the coefficients of the character sum can contradict this forced divisibility.

Field descent

Schmidt's field descent method studies cyclotomic integers $X\in \mathbb{Z}[{\zeta }_m]$ satisfying $X\bar{X}=N$. Under explicit arithmetic conditions, multiplication by a root of unity moves $X$ into a much smaller cyclotomic subfield. Combining this descent with coefficient bounds gives restrictions on the exponent of groups containing difference sets and, in the cyclic case, rules out possible orders of circulant Hadamard matrices.

Leung and Schmidt refined the method by decomposing group-ring elements into a part supported on the descended subfield and a part lying in the kernel of the relevant homomorphism. In 2012, they combined field descent with Turyn's self-conjugacy test, a sub-difference-set projection theorem of R. L. McFarland, and a prime-conductor bound based on work of Chan, obtaining further exclusions of possible circulant Hadamard orders.

Anti-field descent

The anti-field-descent method, introduced by Leung and Schmidt in 2016, uses a complementary idea. A hypothetical circulant Hadamard matrix produces certain "twisted cyclotomic integers" that have small absolute value but cannot lie in a sufficiently small subfield. Lower bounds forced by this non-descent, including estimates for Cassels's $M$-function, contradict the small modulus in many cases.

Computational results

Computational searches apply arithmetic restrictions to possible values of $u$, rather than enumerating the $2^{4u^2}$ possible generating rows. An important ingredient is the search for Wieferich prime pairs: ordered pairs of primes $(q,p)$ satisfying $$q^{p-1}\equiv 1(\mathrm{mod}{p}^2).$$ Such congruences arise in the field-descent restrictions and strongly constrain the possible prime divisors of $u$. Passing the known arithmetic tests does not establish that a matrix exists.

In 2014, Borwein and Mossinghoff reported 1,371 values of $u\le 10^{13}$—equivalently, orders $4<n\le 4\times 10^{26}$—that were not eliminated by the tests they implemented. The five smallest were $$11715,82005,550605,3854235,3877665.$$

Leung and Schmidt's anti-field-descent test subsequently eliminated 423 of those 1,371 cases. In that computation, the smallest value not ruled out remained $$u=11715=3\cdot 5\cdot 11\cdot 71,$$ corresponding to order $4u^2=\mathrm{548,964,900}$.

Separately, in 2017, Brooke Logan and Mossinghoff extended the search to $u\le 10^{15}$. Their calculation left 4,489 orders $n=4u^2$ with $4<n\le 4\times 10^{30}$ not excluded by the tests used in the search. Its principal improvement was a separate search for double Wieferich pairs $\{p,q\}$, satisfying both $$p^{q-1}\equiv 1(\mathrm{mod}{q}^2)\text{and}{q}^{p-1}\equiv 1(\mathrm{mod}{p}^2).$$ The conjecture continued to be stated as an open problem in work published in 2024.

Relation to Barker sequences

A Barker sequence of length $\ell$ is a sequence $b_1,\dots ,b_{\ell }\in \{-1,1\}$ whose nontrivial aperiodic autocorrelations satisfy $$\left|\sum _{j=1}^{\ell -t}{b}_j{b}_{j+t}\right|\le 1(1\le t<\ell ).$$ Turyn and Storer proved that no Barker sequence of odd length greater than 13 exists. For $\ell >13$, the existence of a Barker sequence implies the existence of a circulant Hadamard matrix of the same order. Therefore Ryser's conjecture would imply that no Barker sequence has length greater than 13.

The arithmetic restrictions for Barker sequences are stronger than those for arbitrary circulant Hadamard matrices. In particular, if a Barker sequence of length $\ell =4u^2>13$ exists, then every prime divisor $p$ of $u$ satisfies $p\equiv 1(\mathrm{mod}4)$.

Borwein and Mossinghoff's 2014 search produced 237,807 candidate lengths below $10^{100}$ that survived the tests used in that search. In 2016, Leung and Schmidt ruled out 229,682 of those candidates and proved that no Barker sequence has length $$13<\ell \le 4\times 10^{33}.$$ These Barker-sequence candidate counts should not be confused with the separate list of candidate orders for general circulant Hadamard matrices.

Quantitative Ryser conjecture

In 2024, Stefan Steinerberger proposed the quantitative Ryser conjecture, a strengthened form of the circulant Hadamard conjecture. It asserts that there is an absolute constant ${\epsilon }_0>0$ such that, for every $n>4$ and every Littlewood polynomial $$P(z)=\sum _{k=0}^{n-1}{a}_k{z}^k,a_k\in \{-1,1\},$$ one has $$\underset{0\le j<n}{max}|\left|P\left(e^{2\pi ij/n}\right)\right|-\sqrt{n}|\ge {\epsilon }_0{n}^{1/4}.$$ Steinerberger called this formulation ultra-flat at roots of unity.

If $A=\mathrm{circ}(a_0,\dots ,a_{n-1})$, its singular values are the numbers $|P(e^{2\pi ij/n})|$. Thus the conjecture is equivalently the spectral-gap assertion $$\underset{1\le j\le n}{max}|{\sigma }_j(A)-\sqrt{n}|\ge {\epsilon }_0{n}^{1/4},$$ where ${\sigma }_1(A),\dots ,{\sigma }_n(A)$ are the singular values of $A$. The ordinary Ryser conjecture says only that the left-hand side is nonzero; the quantitative version predicts a universal gap of order $n^{1/4}$.

The exponent $1/4$ would be optimal up to logarithmic factors. When $n$ is prime, probabilistic modifications of the Legendre symbol give circulant sign matrices satisfying $$\underset{0\le j<n}{max}|\left|P\left(e^{2\pi ij/n}\right)\right|-\sqrt{n}|=O\left(n^{1/4}\sqrt{\log n}\right).$$ Consequently, the power of $n$ in the conjectured lower bound cannot in general be increased beyond $1/4$.

Analytic and approximate approaches

Banica, Nechita and Schlenker studied analytic reformulations of the conjecture, including variational characterizations in terms of the eigenvalue vector of a circulant matrix. Related work asks for circulant $\pm 1$ matrices that are only approximately Hadamard. Steinerberger proved that there are absolute constants $0<c<C$ such that, for every order $n$, some circulant $\pm 1$ matrix has all singular values between $c\sqrt{n}$ and $C\sqrt{n}$. Ryser's conjecture concerns the much stronger exact requirement that every singular value equal $\sqrt{n}$.

See also

• Hadamard conjecture
• Difference set
• Barker code
• Circulant matrix
• Littlewood polynomial
• Perfect sequence
• Weighing matrix