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 is an circulant matrix with entries in such that
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 . Richard Turyn proved that 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 , where each . The circulant matrix generated by is
It is Hadamard exactly when distinct cyclic shifts of are orthogonal. In the terminology of weighing matrices, it is a circulant weighing matrix of weight .
For , one example is
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 . If is Hadamard, then
so 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
There is no order-2 circulant Hadamard matrix, since its row sum would have to be the non-integer .
Turyn proved the substantially stronger restrictions that 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 is the exact power of an odd prime dividing , then
Thus no single prime-power divisor of can be too large compared with the remaining factors.
Equivalent formulations
Periodic autocorrelation The periodic autocorrelation of at shift is
The rows of are the cyclic shifts of , so
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
be the associated Littlewood polynomial, and let . Circulant matrices are diagonalized by the discrete Fourier matrix, and the eigenvalues of are , for . Consequently,
In this language, the conjecture says that a polynomial with coefficients cannot be exactly flat on all th roots of unity when .
Cyclic Menon–Hadamard difference sets Suppose and, after negating the sequence if necessary, assume that . Let
Then . The equations for nonzero are equivalent to requiring every nonzero element of to occur exactly times among the ordered differences with . Hence a circulant Hadamard matrix of order is equivalent, up to complementing , to a cyclic difference set with parameters
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 . Their translates form the blocks of a symmetric 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 .
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
For a difference set, the integer 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
For a Menon–Hadamard difference set, and , 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 contains a difference set of order and a prime divides both and , then the Sylow -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 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 is generalized bent when, for every ,
Thus a circulant Hadamard matrix is equivalent to a binary generalized bent function on the cyclic group . 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 . If is bent, then
is a group-developed Hadamard matrix, and the support of , or its complement, is a Menon–Hadamard difference set in , with . The group is noncyclic. For , 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 and every nonprincipal character , the difference-set equations imply
Thus 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 then forces divisibility of itself. Bounds on the coefficients of the character sum can contradict this forced divisibility.
Field descent Schmidt's field descent method studies cyclotomic integers satisfying . Under explicit arithmetic conditions, multiplication by a root of unity moves 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 -function, contradict the small modulus in many cases.
Computational results Computational searches apply arithmetic restrictions to possible values of , rather than enumerating the possible generating rows. An important ingredient is the search for Wieferich prime pairs: ordered pairs of primes satisfying
Such congruences arise in the field-descent restrictions and strongly constrain the possible prime divisors of . Passing the known arithmetic tests does not establish that a matrix exists.
In 2014, Borwein and Mossinghoff reported 1,371 values of —equivalently, orders —that were not eliminated by the tests they implemented. The five smallest were
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
corresponding to order .
Separately, in 2017, Brooke Logan and Mossinghoff extended the search to . Their calculation left 4,489 orders with not excluded by the tests used in the search. Its principal improvement was a separate search for double Wieferich pairs , satisfying both
The conjecture continued to be stated as an open problem in work published in 2024.
Relation to Barker sequences A Barker sequence of length is a sequence whose nontrivial aperiodic autocorrelations satisfy
Turyn and Storer proved that no Barker sequence of odd length greater than 13 exists. For , 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 exists, then every prime divisor of satisfies .
Borwein and Mossinghoff's 2014 search produced 237,807 candidate lengths below 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
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 such that, for every and every Littlewood polynomial
one has
Steinerberger called this formulation ultra-flat at roots of unity.
If , its singular values are the numbers . Thus the conjecture is equivalently the spectral-gap assertion
where are the singular values of . The ordinary Ryser conjecture says only that the left-hand side is nonzero; the quantitative version predicts a universal gap of order .
The exponent would be optimal up to logarithmic factors. When is prime, probabilistic modifications of the Legendre symbol give circulant sign matrices satisfying
Consequently, the power of in the conjectured lower bound cannot in general be increased beyond .
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 matrices that are only approximately Hadamard. Steinerberger proved that there are absolute constants such that, for every order , some circulant matrix has all singular values between and . Ryser's conjecture concerns the much stronger exact requirement that every singular value equal .
See also Hadamard conjecture Difference set Barker code Circulant matrix Littlewood polynomial Perfect sequence Weighing matrix
References