The Hadamard conjecture: a Hadamard matrix of every order divisible by 4
Difficulty 70.5: 130 years old with no general construction; each open order has needed its own method, and the reported August 2026 matrices (orders up to 2000, unpublished) would fill finitely many gaps without touching the general case. It sits just below sunflowers (71) and Lehmer (72), above the finite R(5,5) question (67). Application value 14: Hadamard matrices are used in codes, designs and signal processing, but the orders used in practice are already known, so a full proof changes little; above the other combinatorics problems (3–12.5) and below RH (30). Leverage 28: equivalent to existence statements for Hadamard designs and related codes.
The problem
Is there a square grid of +1 and −1 with perfectly 'orthogonal' rows for every size divisible by 4?
- 1Grid of +1 and −1
- 2Rows must be perfectly balanced pairs
- 3Recipes cover most sizes
- 4Size 668 reported found in 2026
Definition. A Hadamard matrix of order is an matrix with entries and . Equivalently (Hadamard's inequality is attained). For , .
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- The Hadamard conjecture: a Hadamard matrix of every order divisible by 4The problem
State of the art
Constructions cover most orders: Sylvester's doubling gives all powers of 2, and Paley's constructions give orders and for prime powers in the right residue classes; Williamson-type and other constructions fill many more. The previous smallest open order, 428, was settled in 2004 by Kharaghani and Tayfeh-Rezaie, leaving as the smallest order with no known Hadamard matrix. A 2025 paper by Eliahou () built a matrix of order 668 satisfying , raising the record modulus from 32 but not reaching a true Hadamard matrix. on 12 August 2026 Levent Alpöge (Anthropic) posted on X () data, in the form of a puzzle with a decoder, encoding Hadamard matrices of order 668 and of every other order up to 2000 for which none was known, crediting two collaborators and Claude. There is no paper or data file. The mathematician Ion Nechita reported checking the order-668 matrix ( entries and ) with a short script but did not publish the check (); Epoch AI lists the order as solved, provisionally crediting AI (); and the Formal Conjectures corpus still labels the order-668 statement open (commit e754a78, 17 October 2026). This entry records the report as a claim under review (see the claims file). Even if confirmed, the conjecture for all orders remains open.
Realistic applications
Hadamard matrices underlie error-correcting codes (Reed–Muller and Hadamard codes), spread-spectrum and CDMA sequences, optimal experimental designs, and Hadamard transforms in signal processing and quantum information. Having a matrix at every order would let designers choose sizes freely, but existing constructions already cover the sizes used in practice.
What counts as solved
A Lean proof of HadamardConjecture for all ; the realistic partial milestones are Lean-checked Hadamard matrices at specific open orders (a matrix is its own certificate).
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: Hadamard.HadamardConjecture in formal-conjectures (quoted above). The same file states the first open order as its own open declaration, HadamardConjecture.variants.«167» : ∃ M, IsHadamard (n := 4 * 167) M, and the solved range HadamardConjecture.variants.first_cases for . It also defines the equivalent IsHadamard' via ; the equivalence is proved in one direction only (the other is ), so check which form a proof uses. Mathlib supplies , and real powers, so no new definitions are needed. Verifying a specific order is a finite computation: for an explicit matrix of order 668, check , about integer operations, heavy for plain but feasible with certified computation in Lean; the corpus's own shows the pattern at order 12. A full proof must cover every . Judge with Comparator; for specific orders also publish the matrix so others can re-check it independently.
Claims under verification
+ add a claimWhere the work is
Existence at each remaining order is settled by clever constructions plus search; a general proof for every multiple of 4 needs a new idea.
Bottlenecks
ranked by votes- #1TheoryNo general construction
Sylvester, Paley and Williamson-type constructions cover a thin set of orders; each gap order needs a bespoke method.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Aug 12, 2026Matrices of order 668 and other open orders below 2000 reportedsource
Levent Alpöge posts data encoding the matrices on X, crediting two collaborators and Claude; no paper or data file yet, and no published independent check.
- Sep 24, 202564-modular matrix of order 668source
Eliahou's paper (received 24 September 2025) raises the modulus record to 64 without producing a true Hadamard matrix.
- Jan 1, 2004Order 428 settledsource
Kharaghani and Tayfeh-Rezaie construct a Hadamard matrix of order 428, per Epoch AI (year only known).