Circulant Hadamard matrices and Barker sequences

Source and verification

This article explains family 179 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Sign matrices and periodic correlation

A real Hadamard matrix of order $n$ has entries $\pm 1$ and satisfies $H{H}^{\mathsf{T}}=nI$. Its rows are pairwise orthogonal. A circulant matrix is determined by one row $h_0,\dots ,h_{n-1}$, with every other row obtained by a cyclic shift.

Define the periodic autocorrelation

$$P_h(t)=\sum _{j=0}^{n-1}{h}_j{h}_{j+t\mathrm{mod}n}.$$

The circulant Hadamard condition is exactly $P_h(0)=n$ and $P_h(t)=0$ for $1\le t<n$. It asks for cancellation at every nonzero cyclic shift.

Manuscript claim

A real circulant Hadamard matrix of positive order $n$ exists exactly for $n=1$ and $n=4$. (OpenAI, 2026)

This concerns real signs and circulant structure. It does not classify general Hadamard matrices or matrices with arbitrary complex unit entries.

For $n=4$, the row $(1,1,1,-1)$ has zero correlation at shifts one, two, and three. Its cyclic shifts therefore give an explicit example. Order one is immediate.

🏷️ Elementary necessary conditions

Summing all periodic correlations gives

$$\sum _{t=0}^{n-1}{P}_h(t)={\left(\sum _{j=0}^{n-1}{h}_j\right)}^2.$$

Under orthogonality this equals $n$, so $n$ must be a square. The usual Hadamard parity argument further makes every nontrivial order greater than two divisible by four. These elementary conditions leave orders $n=4u^2$, far more than the claimed final list.

Let $D$ be the set of negative positions and let $k=|D|$. If $N_D(t)$ counts ordered pairs of negative positions with difference $t$ modulo $n$, expanding $h_j=1-21_D(j)$ gives

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

After changing every sign if needed, the row sum is $2u$. Hence $k=2u^2-u$, and every nonzero cyclic difference must occur exactly $u^2-u$ times among ordered pairs from $D$. This translates exact orthogonality into an exact counting design.

In Fourier language, all discrete Fourier values of the sign row have modulus $\sqrt{n}$. Approximate flatness is much less restrictive: keeping those moduli within fixed multiples of $\sqrt{n}$ does not force equality and does not imply the theorem.

🏷️ Comparing values from one coefficient array

The proof first obtains the classical reduction to $n=4u^2$ with $u$ odd. Its remaining task is to exclude $u>1$.

The manuscript uses arithmetic evaluations at roots of unity. These encode the same cyclic coefficient array at several frequencies. The point of the method is compatibility among those values, not separate estimates for each frequency.

For each prime dividing $u$, choose either a specified nontrivial prime-order frequency or the trivial frequency. Index the resulting evaluations by subsets $S$ of the prime divisors, writing them as $x_S$. Orthogonality gives $|x_S|=u$. Consider the alternating product

$$\Delta (x)=\prod _S{x}_S^{(-1{)}^{|S|}}.$$

None of its factors vanishes. The source proves that adjacent ratios in each prime direction have prescribed local divisibility and residue properties. Combining all directions makes $\Delta (x)$ an algebraic integer with all its conjugates on the unit circle. A standard root-of-unity criterion then makes it a root of unity, and the local conditions restrict its order to be odd.

These divisibility statements are the specialized arithmetic input. The post records their role without developing the excluded group-ring and algebraic-number-theory machinery. Equal absolute values alone would not justify either integrality or the residue restrictions.

🏷️ The sign constraint supplies the contradiction

The cyclic factor of order four gives three normalized partial evaluations of the original row, at $1$, $-1$, and $i$. Call the resulting arrays $c,d,g$. Their coefficients come from the same signs, and each has the same norm $u^2$.

The alternating ratios $\Delta (d)/\Delta (c)$ and $\Delta (g)/\Delta (c)$ therefore have odd order. A separate calculation at the prime two uses the binary coefficients to show that these ratios have residue one, forcing them to equal one exactly in the setting of the argument.

Taking first-order terms of these exact products gives a vanishing alternating sum. But the original coefficient identity expresses that sum through the all-ones cyclic array. Every nontrivial frequency annihilates this array, while the trivial frequency gives the odd nonzero value $u^2$. Exactly one term survives, contradicting vanishing.

The two kinds of information are both essential: prime-by-prime norm comparisons restrict alternating products, while the common sign array creates the final incompatible residue identity.

🏷️ Barker sequences

The aperiodic correlation of a sign sequence is

$$C_h(t)=\sum _{j=0}^{n-t-1}{h}_j{h}_{j+t}.$$

A Barker sequence has $|C_h(t)|\le 1$ for every nonzero shift. Unlike periodic correlation, it does not wrap around the end. The relation $P_h(t)=C_h(t)+C_h(n-t)$ connects the two conventions.

The manuscript combines the even-length implication from Barker correlations to circulant orthogonality with the known odd-length classification, obtaining lengths $2,3,4,5,7,11,13$ for $n>1$. The selected formalization scope additionally covers only the even Barker conclusion, namely lengths two and four; its odd-length part should not be inferred from that scope entry.

🏷️ Key steps and proof outlines

The final contradiction compares three evaluations of the same signs

After the order reduction, suppose $n=4u^2$ with odd $u>1$. Index the row by a four-coordinate cyclic direction and an odd cyclic direction, and write its four sign arrays as $H_0,H_1,H_2,H_3$. The normalized evaluations at the fourth roots $1,-1,i$ are

$$\begin{array}{rl}c& =(H_0+H_1+H_2+H_3)/2,\\ d& =(H_0-H_1+H_2-H_3)/2,\\ g& =(H_0-H_2)/2+i(H_1-H_3)/2.\end{array}$$

Their coefficients are integral, with Gaussian integers allowed for $g$, because every original coefficient is odd. Orthogonality gives the same norm identity $x{x}^{\ast }=u^2$ for all three arrays. Here $\ast$ conjugates coefficients and reverses the cyclic index. (OpenAI, 2026)

The “Alternating products” theorem is the specialized arithmetic input: for evaluations $x_S$ indexed by subsets of the prime divisors of $u$, it proves that $\Delta (x)={\prod }_S{x}_S^{(-1{)}^{|S|}}$ is a root of unity of odd order. In particular, the ratios $R=\Delta (d)/\Delta (c)$ and $W=\Delta (g)/\Delta (c)$ have odd order. Their individual factors need not be roots of unity, and equal absolute values alone would not establish this conclusion.

Reduce both first-order comparisons in one residue field

Work in the source’s local coefficient domain $O$ at a prime above two, with maximal ideal $\mathfrak{n}$ and residue field $k=O/\mathfrak{n}$. All $c_S,d_S,g_S$ are units because their norm is the odd integer $u^2$. In $k$, one has $i=1$, since $(i-1{)}^2=0$ in characteristic two and a field has no nonzero nilpotents.

Let $b=(H_1+H_3)/2$ and let $J$ be the all-ones array. The common binary coefficients yield the exact identity

$$H_2+i{H}_3=(1+i)J+2U$$

for an integral array $U$: every coefficient $\alpha +i\beta$, with $\alpha ,\beta \in \{\pm 1\}$, differs from $1+i$ by a multiple of two. Consequently, for $r_S=d_S/c_S$ and $w_S=g_S/c_S$,

$$\begin{array}{rl}{L}_{r,S}:=\frac{r_S-1}{2}& =-\frac{b_S}{c_S},\\ L_{w,S}:=\frac{w_S-1}{1+i}& =i\frac{b_S}{c_S}-\frac{J_S}{c_S}-(1-i)\frac{U_S}{c_S}.\end{array}$$

Both quotients are integral in $O$. Adding and reducing in the same field cancels the $b_S$ term and gives $L_{r,S}+L_{w,S}\equiv J_S/c_S$.

Exact products become additive identities

For any nonzero $t\in \mathfrak{n}$, the map

$$1+tL⟼L\mathrm{mod}\mathfrak{n}$$

turns multiplication into addition. Indeed, the product’s first-order coefficient is $L+M+tLM$, and the last term vanishes modulo $\mathfrak{n}$; inversion gives coefficient $-L/(1+tL)$, reducing to $-L$.

Each $r_S$ and $w_S$ has residue one, so $R$ and $W$ do too. An odd-order root of unity with residue one must equal one: if its order is $m$ and it is not one, factoring $z^m-1$ forces $1+z+\cdots +z^{m-1}=0$, whereas its residue is the nonzero odd integer $m$ modulo two. Hence $R=W=1$ exactly.

Apply the first-order map separately with $t=2$ and $t=1+i$, both landing in $k$. The alternating products then give two vanishing sums. Adding them yields

$$\sum _S(-1{)}^{|S|}\frac{J_S}{c_S}\equiv 0(\mathrm{mod}\mathfrak{n}).$$

Every nontrivial frequency annihilates $J$, while the trivial frequency gives $J_{\varnothing }=u^2$. Thus the sum is the unit $u^2/c_{\varnothing }$, whose residue cannot vanish. This is the contradiction. At order four the prime index set is empty and the example has $W=i$ of even order, so the odd-torsion step is unavailable, as it must be.

The even Barker consequence uses only parity afterward

For even Barker length $n>2$, $C(2)$ and $C(n-2)$ are even and have magnitude at most one, so both vanish. On the other hand, the product of the signs in any periodic correlation is one; its number of negative terms is even, giving $P(t)\equiv n(\mathrm{mod}4)$. Since $P(2)=0$, one gets $4\mid n$. For every other shift, $|P(t)|\le 2$ and $P(t)\equiv 0(\mathrm{mod}4)$, forcing $P(t)=0$. The cyclic shifts form a circulant Hadamard matrix, hence $n=4$. The odd Barker classification uses the separate classical input identified above.

See Also

• Littlewood polynomials concerns sign-coefficient Fourier flatness, with exact and approximate conclusions carefully separated.
• Boolean Fourier degree studies a different restriction on Fourier coefficients of sign-valued functions.

🏷️ Manuscripts and verification scope

• The circulant Hadamard conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the exact circulant orders and the even Barker classification. The odd Barker lengths in the manuscript are outside the selected additional statement. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The circulant Hadamard conjecture.