Barker Sequence Conjecture: How the OpenAI Proof Rules Out Lengths Beyond 13

Thirteen signs can meet a strict cancellation rule. According to OpenAI’s September 23, 2026 manuscript, fourteen signs, fourteen trillion signs, and every other length above thirteen cannot. Its proof of the Barker sequence conjecture closes the outstanding even-length case through a theorem about cyclically shifted matrices.

The answer is precise: Barker sequences longer than one exist exactly at lengths 2, 3, 4, 5, 7, 11, and 13. The new ingredient is the circulant Hadamard theorem. The odd-length classification comes from classical work, rather than being rediscovered here. This OpenAI Barker sequence conjecture proof is presented in a preprint, with separately documented Lean scope. Its argument makes a shared array of binary coefficients contradict itself.

1. What Did the OpenAI Proof Establish About the Barker Sequence Conjecture?

Theorem 1.1 of The Circulant Hadamard Conjecture states that real circulant Hadamard matrices exist only at orders one and four. “Order” means the number of rows and columns.

Its Barker consequence is Corollary 1.2. Every even Barker sequence longer than two generates one of these matrices. Restricting the matrix order therefore restricts the sequence length.

1.1. Barker Sequence Conjecture: Key Facts

OpenAI’s release announcement attributes the collection to an internal frontier model. That establishes provenance, not independent acceptance. As in our AI mathematical proofs coverage, the important questions concern the theorem’s assumptions, argument, and verification evidence.

2. What Is a Barker Sequence? The Autocorrelation Formula Explained

A Barker sequence is an ordered list $a=(a_0,\ldots,a_{n-1})$, with each entry either positive or negative one. For a shift $t$, its aperiodic autocorrelation is

Only overlapping positions contribute. Matching signs add one, opposite signs subtract one. The Barker condition requires $|C_a(t)|\le1$ at every nonzero shift, so matches and mismatches must almost perfectly balance.

Take $a=(1,1,1,-1)$. At shift one, the overlapping lists are $(1,1,1)$ and $(1,1,-1)$. Their complete comparison gives

At shift two, the products are positive one and negative one, giving zero. Shift three leaves one product, giving negative one. All shifts pass.

Barker sequence autocorrelation is an exact finite condition. Unlike the long-run sign cancellation studied in the two-point Chowla conjecture, no averaging limit softens the requirement. Every allowed shift must pass.

3. Why Was Length 13 the Barrier for So Long?

Examples exist at the seven listed lengths. A Barker sequence of length 13 is $(+,+,+,+,+,-,-,+,+,-,+,-,+)$, where the signs denote positive and negative one. Length one also works if admitted, because it has no nonzero shifts to test.

Turyn and Storer proved odd-length nonexistence above thirteen in 1961. The manuscript uses Schmidt and Willms’s later proof for the exact odd list: 3, 5, 7, 11, and 13.

The remaining uncertainty was even length. Arithmetic restrictions made a hypothetical long even sequence extremely special, but special is not impossible. A length outside every completed search could still escape.

“Thirteen” therefore describes the largest surviving example, not a single boundary that all earlier techniques approached uniformly. Odd and even lengths followed different mathematical routes. The new paper closes the even route by proving that its associated matrix cannot exist.

4. How Even Barker Sequences Lead to Circulant Hadamard Matrices

Periodic autocorrelation wraps the sequence around instead of discarding positions beyond the end. Splitting its sum into ordinary and wrapped overlaps gives

Here $1\le t<n$. For even $n>2$, the two aperiodic correlations at shift two and its complementary shift have even numbers of summands. Their parity and Barker bounds force both to be zero.

Meanwhile, the product of all summands in any periodic correlation is one: every sequence entry appears twice. Consequently the number of negative summands is even, and $P_a(t)\equiv n\pmod4$. The zero at shift two forces four to divide $n$.

At every other shift, the Barker bound gives $|P_a(t)|\le2$. But that integer is divisible by four, so it must be zero. Thus distinct cyclic shifts have zero inner product. Putting those shifts into rows produces the required orthogonal sign matrix.

5. The Circulant Hadamard Conjecture: From Orthogonal Rows to Cyclic Difference Sets

For a sign matrix $H$, orthogonality means

The superscript denotes transpose and $I_n$ is the identity matrix. Diagonal entries record each row’s squared length. Off-diagonal entries record correlations between different rows.

Encode the first row as $h=\sum_{j=0}^{n-1}h_jX^j$ in the integer group ring of the cyclic group $C_n$. Multiplication uses cyclic index addition. The operation star reverses group elements and conjugates coefficients, turning orthogonality into $hh^*=n$. Our group-ring explainer introduces this coefficient bookkeeping in another setting.

There is also a combinatorial translation. Let $D$ contain the positions carrying negative signs. If $N_D(t)$ counts ordered pairs in $D$ with difference $t$, then $P_h(t)=n-4|D|+4N_D(t)$.

For order $4u^2$, reverse every sign if necessary so the row sum is $2u$. Then $D$ has $2u^2-u$ elements, and every nonzero cyclic difference occurs $u^2-u$ times. These are the difference-set parameters $(4u^2,2u^2-u,u^2-u)$. The translation is exact in both directions.

6. Why Earlier Number-Theoretic Restrictions Were Not Enough

Turyn’s restrictions required any order beyond four to have the form $4u^2$, with $u$ odd and not a prime power. Field descent and later refinements imposed additional restrictions on the cyclotomic numbers obtained from candidate rows.

Cyclotomic numbers involve roots of unity, complex numbers whose positive integer powers eventually equal one. Evaluating a row at these roots translates combinatorial requirements into arithmetic constraints.

Logan and Mossinghoff’s 2017 computation, as summarized in the manuscript, left 4,489 candidate orders within the range above four and at most $4\cdot10^{30}$. These were survivors of necessary tests, not constructed matrices.

Excluding almost every candidate in an enormous interval still leaves a logical gap. No finite cutoff addresses all larger integers. The new circulant Hadamard conjecture proof instead derives an obstruction for every hypothetical odd $u>1$. Its force comes from uniformity, not a larger search budget.

7. The First Proof Step: Why the Matrix Order Must Be 4u²

First, send every group element in $hh^*=n$ to one. This gives $h(1)^2=n$, so the order is a square. Two orthogonal sign rows also force an even order. Write $n=2^{2s}u^2$, with $s\ge1$ and $u$ odd.

Lemma 2.1 supplies the divisibility tool. After localizing an appropriate cyclotomic integer ring at a prime, powers of that prime dividing an evaluation force corresponding divisibility of its coefficients in a cyclotomic basis. Localization permits denominators outside the chosen prime ideal.

The basis condition matters. Divisibility of one polynomial value normally tells us little about its separate coefficients. Here the remainder modulo the relevant cyclotomic polynomial has a unique basis expansion. That uniqueness transfers divisibility back to specific differences of coefficients, making the descent possible.

Proposition 2.2 applies this at two. Project the row onto its cyclic component of order $2^{2s}$. Its coefficients remain odd because each sums an odd number of signs. Assuming $s\ge2$, cyclotomic divisibility makes opposite coefficients congruent modulo four.

Project again and divide by two. The new coefficients stay odd, while the scalar norm loses a factor of four. After $s-1$ repetitions, there are $2^{s+1}$ odd coefficients whose squares sum to $4u^2$.

Every odd square is one modulo eight. The left side is therefore zero modulo eight, while the right side is four. Contradiction. Hence $s=1$, giving $n=4u^2$ with odd $u$.

8. The Key Construction: Alternating Products of Character Values

Now assume $u>1$. Put $P=C_{u^2}$, and let $I$ be the nonempty set of primes dividing $u$. A character is a multiplicative map from group elements to roots of unity, the algebraic viewpoint behind Fourier evaluation.

For each prime $p$ in $I$, choose a primitive $p$-th root $\rho_p$. Each subset $S\subseteq I$ specifies a character: use that root on the corresponding primary generator when $p\in S$, and one otherwise. Write $x_S$ for the resulting evaluation of $x$.

If $xx^*=u^2$, every evaluation has absolute value $u$ and is nonzero. Define

Even-sized subsets contribute numerator factors, odd-sized subsets denominator factors. For two primes $p,q$, this becomes $\frac{x_{\varnothing}x_{\{p,q\}}}{x_{\{p\}}x_{\{q\}}}$.

The useful feature is flexibility: the same fraction pairs character values along either prime direction. Each pairing exposes local arithmetic at a different prime without changing the global quantity being studied.

This resembles a multiplicative inclusion-exclusion calculation. Information attached to separate prime choices cancels, leaving their joint compatibility under examination. No single character sees that compatibility alone. The construction forces several otherwise separate arithmetic tests to constrain one algebraic number.

9. How Local Units and Kronecker’s Theorem Force Odd-Order Roots of Unity

Lemma 3.1 compares evaluations with a chosen prime component switched on and off. It requires the component order $p^e$ to match the prime valuation $e$ of the scalar norm. Repeated projection and division preserve the comparison ratios while reducing both exponents together.

The outcome is a local unit with residue one. A unit is invertible in the localized ring. Its residue is its image after reduction modulo the maximal ideal, where arithmetic takes place in a field of characteristic $p$.

Pairing factors in every prime direction proves that $\Delta(x)$ is integral in $B=\mathbb{Z}[i,\{\rho_p:p\in I\}]$, where $i^2=-1$. At other prime ideals, the norm identity supplies the necessary control.

Every algebraic conjugate of the product has absolute value one, because the alternating exponents sum to zero. Kronecker’s theorem now makes it a root of unity. Residue one above each $p$ forces its order to be a power of that prime. Proposition 3.4 therefore gives odd order.

Integrality is indispensable. Absolute value one in a single complex embedding would not imply finite order. The proof establishes the stronger package: an algebraic integer and absolute value one under every relevant embedding. Kronecker’s criterion converts these size constraints into a discrete arithmetic restriction.

Odd order does not always mean the product equals one. With one prime divisor, a nontrivial prime-order root can remain. The final step must handle that possibility.

10. The Binary Coefficient Identity: Where the Final Contradiction Appears

Split the cyclic group as $C_4\times P$. For its order-four generator $Z$, write $h=H_0+ZH_1+Z^2H_2+Z^3H_3$. Every coefficient of every $H_j$ remains a sign. Define the normalized partial evaluations

Their coefficients are integral: sums of four signs and differences of two signs are even. Each satisfies $xx^*=u^2$. Consequently $R=\frac{\Delta(d)}{\Delta(c)}$ and $W=\frac{\Delta(g)}{\Delta(c)}$ have odd order.

Work in one localization $O$ of $B$ at a maximal ideal above two, with maximal ideal $\mathfrak n$ and residue field $k=O/\mathfrak n$. All character values are units because their norms are odd. Here $i$ reduces to one.

Put $b=\frac{H_1+H_3}{2}$ and $J=\sum_{z\in P}z$. The sign coefficients force $H_2+iH_3=(1+i)J+2U$ for some integral group-ring element $U$. Define

Direct subtraction makes both expressions integral in $O$: the first is $-\frac{b_S}{c_S}$, and the second is $i\frac{b_S}{c_S}-\frac{J_S}{c_S}-(1-i)\frac{U_S}{c_S}$. Reducing their sum gives

Both ratio families have residue one. Their alternating products are $R$ and $W$, so these products also have residue one. Odd-order roots reducing to one in characteristic two must equal one exactly. Thus $R=W=1$.

Lemma 4.1 extracts first-order terms: the map $1+tL\mapsto L\bmod\mathfrak n$ turns products into sums, separately for $t=2$ and $t=1+i$. Applying it to those exact product identities, then adding, yields

Every nontrivial character annihilates $J$. Multiplying the group sum by a group element merely permutes its summands. A nontrivial character turns that invariance into multiplication by a value different from one, forcing its evaluated sum to vanish. The trivial character instead simply counts all group elements.

Only the trivial character remains, contributing $\frac{u^2}{c_{\varnothing}}$, a unit with nonzero residue. The same sum must therefore be zero and nonzero. That contradiction excludes $u>1$.

“First-order” here describes exact algebra, not an approximation. Multiplying two terms of the form $1+tL$ introduces a cross term divisible by $t^2$. After division by $t$ and reduction, that term vanishes. This explains why multiplicative identities yield additive identities in the same residue field.

Order four escapes for a precise reason. There $u=1$, so the prime set is empty and the odd-order conclusion is unavailable. In the explicit example, $W=i$, whose even order prevents the final argument from starting.

11. From the OpenAI Proof to the Complete Barker Sequence Classification

The even Barker sequence conjecture now reduces to lengths two and four. Combine that conclusion with the classical odd list, and the complete classification follows. The Barker sequence of length 13 remains the longest possible, without assuming that every older argument was newly proved.

11.1. What Each Verification Layer Establishes

The published Lean scope note describes formalizations of the exact circulant Hadamard theorem and the positive even-length Barker consequence. It explicitly excludes the odd classification from the selected additional statement. Comparator files specify target statements and should not be mistaken for completed certificates by themselves.

We have not independently rebuilt the formalization. Its documented scope, the manuscript’s proof, and community assessment remain distinct evidence, just as discovery and formalization differ in our Fermat proof coverage.

For researchers, the reusable idea is the link between prime-by-prime character comparisons and one coefficient identity. For developers, this is a nonexistence theorem, not a demonstrated faster algorithm. Follow Binary Verse AI for AI and mathematics research explainers that make the Barker sequence conjecture and its proof understandable without losing their mathematical boundaries.