The circulant Hadamard and Barker-sequence conjectures

The explanation

Write down four signs: −, +, +, +. Make a square table from them. The first row is the four signs. Each next row is the row above, shifted one place right. The last sign wraps round to the front. Now compare any two different rows, position by position. They agree twice and disagree twice. So multiply matching entries and add, and you always get 0. A square table of plus and minus ones whose rows all cancel like this is called a Hadamard matrix. One built by shifting a single row is called circulant.

How big can a circulant Hadamard matrix be? A single + is a trivial example of size 1. The table above has size 4. Try size 16. There are 65,536 choices of first row, and a computer check shows none of them works. Herbert Ryser is traditionally credited with the conjecture that 1 and 4 are the only sizes.

The question is old and was cut down a lot. In 1965, Richard J. Turyn showed that any larger size must be 4 times the square of an odd number. That odd number cannot be a power of a single prime. Bernhard Schmidt, Ka Hin Leung and others later ruled out more sizes, using the arithmetic of roots of unity. In 2017, Brooke Logan and Michael Mossinghoff ran a computer search up to 4 followed by 30 zeros. They excluded all but 4,489 sizes in that range. Those 4,489 stayed open, and nothing covered the sizes beyond.

This paper proves that 1 and 4 are the only sizesSource 1. The difficulty was that each known test removed some sizes, but none removed all of them. The paper finds one quantity that ties all the odd prime factors of the size together. It evaluates the first row in several ways, using roots of unity. Then it multiplies those values with alternating powers +1 and −1. That product turns out to be a root of unity, a number some power of which equals 1Source 2. Looking at the same numbers modulo 2 then shows it must equal 1 exactlySource 3. Expanding it one step further gives a sum where all terms but one vanish. One nonzero term cannot add up to zero, and that is the contradictionSource 4.

There is a well-known consequence. A Barker sequence is a list of signs that barely matches shifted copies of itself. Slide the list along itself by any amount, multiply the overlapping signs and add. The total must be −1, 0 or 1. The list + + + + + − − + + − + − + of length 13 is one. Barker sequences exist at lengths 2, 3, 4, 5, 7, 11 and 13. Turyn and Storer had ruled out odd lengths above 13 in 1961. For even lengths above 2, a Barker sequence would give a circulant Hadamard matrix of the same sizeSource 5. So the new theorem leaves only 2 and 4 among even lengths, and the list of seven lengths is completeSource 6.

The theorem is exact, not a statement about large sizes only. It also says nothing about approximate versions. In 2024, Stefan Steinerberger showed that every size has a circulant sign table within fixed factors of the exact case. Exact cancellation is what fails.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It includes explicit examples of sizes 1 and 4. It has also checked the even-length Barker statement. The odd-length list, which relies on earlier work, is outside that check. Several earlier claimed proofs exist, and no specialist review of this one has been published.

What it doesn't show. This does not rule out circulant sign tables that only approximately cancel.