Why a perfectly orthogonal cyclic sign pattern would stop at length four

← All digests

Family 179 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Take a row of plus and minus signs, then place all its cyclic shifts beneath it. Can every pair of distinct rows be orthogonal? At length four the answer is yes: the pattern $(1,1,1,-1)$ and its shifts work. The circulant Hadamard conjecture says there are no larger examples.

This question combines a strong symmetry requirement with exact cancellation. Cyclic shifting makes the entire matrix depend on one row, but orthogonality imposes a different equation for every nonzero shift.

The manuscript claims that only orders one and four are possible. It also deduces a complete classification of Barker-sequence lengths, another classical problem about sign patterns whose shifted overlaps are as small as possible. The connection depends on distinguishing periodic overlaps, which wrap around, from aperiodic overlaps, which do not.

2. Background and essential definitions

A real Hadamard matrix of order $n$ is an $n$-by-$n$ matrix $H$ with entries $\pm1$ satisfying

$$HH^T=nI_n.$$

Each row has squared length $n$, and distinct rows have inner product zero. The matrix is circulant when every row is a cyclic shift of the first. With indices starting at zero,

$$H_{ij}=h_{j-i\bmod n}.$$

For the first row $h$, define its periodic autocorrelation at shift $t$ by

$$P_h(t)=\sum_{j=0}^{n-1}h_jh_{j+t\bmod n}.$$

The zero-shift value is $n$. The circulant matrix is Hadamard exactly when all other values are zero. These sums count agreements minus disagreements between the row and its shifted version.

For a finite sign sequence $a$, the aperiodic autocorrelation instead uses only the overlapping positions:

$$C_a(t)=\sum_{j=0}^{n-t-1}a_ja_{j+t} \qquad(1\leq t<n).$$

A Barker sequence satisfies $|C_a(t)|\leq1$ for every nontrivial shift. For example, $(1,1,1,-1)$ has aperiodic correlations $1,0,-1$, so it is a Barker sequence.

These are idealized signal patterns: the zero-shift overlap is large, while shifted overlaps are small or vanish. The mathematical theorem concerns exact sign sequences; it does not classify approximate designs, arbitrary real amplitudes or complex phases.

3. Development history and previous partial results

The circulant Hadamard conjecture is traditionally attributed to Ryser. Its close relation to cyclic difference sets brought algebraic number theory into the problem.

Let $D$ be the positions of the negative signs in a cyclic row, and write $k=|D|$. If $N_D(t)$ counts ordered pairs of elements of $D$ whose difference is $t$ modulo $n$, then

$$P_h(t)=n-4k+4N_D(t).$$

Thus zero correlations require every nonzero difference to occur equally often. Such a subset is called a cyclic difference set.

Turyn’s 1965 work studied these structures through character sums, the Fourier coefficients of functions on cyclic groups. It showed that any order larger than four must have the form $4u^2$, where $u$ is odd and is not a prime power. This eliminated broad classes of possibilities, but not all products of several odd primes.

Schmidt’s field-descent method and later work with Leung imposed further arithmetic restrictions. Their 2012 manuscript is one primary source for these exclusions. Logan and Mossinghoff’s 2017 computation excluded all but 4,489 candidate orders between four and $4\cdot10^{30}$. Those remaining numbers were candidates under the tests, not constructed matrices.

For Barker sequences, Turyn and Storer established the odd-length nonexistence result above thirteen. Schmidt and Willms later gave a proof yielding the exact odd-length list. The major remaining length question was even: a Barker sequence of even length greater than two produces a circulant Hadamard matrix.

The present manuscript cites earlier claimed complete proofs as well as these established partial results. Its own contribution is an arithmetic argument intended to exclude every remaining circulant order, thereby resolving the even Barker case through the classical implication.

4. What the new manuscripts claim

The main theorem states that a real circulant Hadamard matrix of positive order $n$ exists if and only if

$$n\in\{1,4\}.$$

At order one, either sign is an example. At order four, the cyclic shifts of $(1,1,1,-1)$ provide one. The nonexistence statement covers all larger orders, rather than extending a finite numerical search range.

As a consequence, the manuscript states that a Barker sequence of length $n>1$ exists exactly when

$$n\in\{2,3,4,5,7,11,13\}.$$

If length one is admitted, it also works because there are no nontrivial shifts to test. The paper records explicit examples for all seven listed lengths.

The deduction for even lengths uses

$$P_a(t)=C_a(t)+C_a(n-t).$$

For an even Barker sequence of length greater than two, parity and congruences modulo four force every nontrivial periodic correlation to vanish. Its cyclic shifts therefore form a circulant Hadamard matrix. The new main theorem forces the length to be four. Length two is handled separately, while the odd lengths come from the earlier classification.

Equivalently, the main claim excludes cyclic difference sets with parameters

$$(v,k,\lambda)=(4u^2,\,2u^2-u,\,u^2-u)$$

for every $u>1$. Here $v$ is the cyclic group order, $k$ is the subset size, and $\lambda$ is the common multiplicity of every nonzero difference.

5. Why the advance matters

Importance: 4/5. The claim closes two longstanding classification problems connecting combinatorial design, harmonic analysis and arithmetic. It replaces an extensive collection of necessary conditions and computational exclusions with a complete nonexistence theorem.

The exactness is especially striking. Many sign matrices can have approximately orthogonal rows, and recent work constructs sign circulants whose singular values are all within constant factors of $\sqrt n$ at every order. Requiring every singular value to equal $\sqrt n$ exactly is vastly more rigid.

The Barker consequence also links two different measures of shifted overlap. Aperiodic smallness seems weaker than periodic zero correlation, yet the parity constraints of even binary sequences bridge the gap. The rating reflects the importance of these classical problems while recognizing their focused setting of cyclic real sign patterns.

6. The main idea

Package all correlations into one equation

Write the row as a formal polynomial

$$h(X)=\sum_{j=0}^{n-1}h_jX^j$$

with the relation $X^n=1$. Multiplication then follows cyclic convolution. Replace $X$ by $X^{-1}$ to obtain $h^*$. The orthogonality equations become the single identity

$$hh^*=n.$$

Evaluating at roots of unity gives the discrete Fourier coefficients. A root of unity is a complex number whose positive integer power is one. Every character value of $h$ has absolute value $\sqrt n$, but the values also come from one common array of integer signs. The proof exploits that shared origin, rather than treating the Fourier magnitudes independently.

Compare several prime directions at once

After recovering the classical restriction $n=4u^2$ with $u$ odd, suppose $u>1$. The cyclic group splits into a factor of order four and an odd factor of order $u^2$.

Evaluating the order-four factor at $1$, $-1$ and $i$, where $i^2=-1$, gives three normalized expressions. Their coefficients lie in the Gaussian integers $\mathbb Z[i]$, and each has the same norm identity on the odd cyclic factor.

For each prime dividing $u$, the argument compares a trivial character with a selected nontrivial character on that prime component. It assembles these values into an alternating product indexed by subsets of the prime divisors, much like an inclusion–exclusion product.

A descent argument controls the ratios at the relevant primes. The manuscript concludes that the alternating products are algebraic integers whose conjugates all have absolute value one. Kronecker’s criterion then makes them roots of unity. Further local information forces their orders to be odd.

Use the binary signs at the prime two

The three normalized expressions are linked because they came from the same four blocks of signs. Reducing their ratios in an arithmetic setting of characteristic two supplies additional congruences.

An odd-order root of unity with the required residue is forced to equal one. Expanding the resulting exact product identities yields cancellation relations for their first-order terms.

The original sign coefficients supply a conflicting relation. The sum over the odd cyclic group vanishes under every nontrivial character, while its trivial character value is the odd number $u^2$. Thus the alternating sum has a single surviving nonzero term where the product identities require zero. This is the contradiction described by the manuscript.

The exceptional order four corresponds to $u=1$, with no odd prime direction available. The argument’s odd-order step is then absent, consistent with the known example.

7. Scope, limitations, and open questions

The theorem is specifically about real circulant Hadamard matrices. General Hadamard matrices need not have cyclically shifted rows, and many larger examples exist. The general Hadamard existence conjecture is a different question and is not settled here.

Complex circulant matrices with unit-modulus entries also lie outside the claim. Their phases are not restricted to $\pm1$, removing the binary arithmetic used in the contradiction. Approximate orthogonality and small but nonzero periodic correlations remain separate design problems.

The Barker classification concerns binary sequences with every nontrivial aperiodic correlation bounded by one. Relaxing that bound or changing the alphabet produces other families and other optimization questions.

The result supplies a nonexistence conclusion, not a recipe for the best approximate sequence at a chosen larger length. Such approximation problems remain relevant even if the exact classification is complete. Likewise, the argument’s character comparisons use the cyclic structure; they should not be transferred automatically to arbitrary difference-set parameters or noncyclic groups.

8. Sources and further reading

The manuscript states both classifications, develops the cyclic group-ring argument, and ends with the even-length Barker deduction and examples.

Primary historical sources include Turyn’s character-sum paper, Leung–Schmidt’s arithmetic restrictions, Logan–Mossinghoff’s finite-range exclusions, and Schmidt–Willms on odd Barker lengths. They explain why the new circulant nonexistence claim would complete the remaining even-length classification.

Source manuscripts

• M1. OpenAI, The circulant Hadamard conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.