/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtil
public import FormalConjectures.Wikipedia.HadamardThe circulant Hadamard conjecture
A circulant matrix is generated by cyclically shifting one row. The circulant Hadamard conjecture, also attributed to Ryser, says that no circulant Hadamard matrix has order greater than $4$.
References:
S. Steinerberger, A note on approximate Hadamard matrices
[OAI26a] OpenAI, The circulant Hadamard conjecture. OpenAI Math Release preprint (2026). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-circulant-Hadamard-conjecture-September-23-2026/paper.pdf
@[expose] public sectionnamespace CirculantHadamardA generator for a circulant Hadamard matrix of order four.
def orderFourGenerator : Fin 4 → ℝ :=
![1, 1, 1, -1]The order-four generator gives a circulant Hadamard matrix.
@[category test, AMS 15]
theorem orderFourGenerator_isHadamard :
Hadamard.IsHadamard' (Matrix.circulant orderFourGenerator) := ⊢ Hadamard.IsHadamard' (Matrix.circulant orderFourGenerator)
⊢ ∀ (i j : Fin 4), Matrix.circulant orderFourGenerator i j ∈ {1, -1}⊢ (Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator = ↑4
⊢ ∀ (i j : Fin 4), Matrix.circulant orderFourGenerator i j ∈ {1, -1} i:Fin 4j:Fin 4⊢ Matrix.circulant orderFourGenerator i j ∈ {1, -1}
j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) j ∈ {1, -1} j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) j ∈ {1, -1}j:Fin 4⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) j ∈ {1, -1} ⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ∈ {1, -1} ⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩) ∈ {1, -1}⊢ Matrix.circulant orderFourGenerator ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ∈ {1, -1}
All goals completed! 🐙
⊢ (Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator = ↑4 i:Fin 4j:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) i j = ↑4 i j
j:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) j j:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) jj:Fin 4⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩) j =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) j ⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨0, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨1, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨2, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨3, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩) ⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩)
((fun i ↦ i) ⟨0, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩)
((fun i ↦ i) ⟨1, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩)
((fun i ↦ i) ⟨2, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨0, ⋯⟩)
((fun i ↦ i) ⟨3, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨0, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩)
((fun i ↦ i) ⟨0, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩)
((fun i ↦ i) ⟨1, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩)
((fun i ↦ i) ⟨2, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨1, ⋯⟩)
((fun i ↦ i) ⟨3, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨1, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩)
((fun i ↦ i) ⟨0, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩)
((fun i ↦ i) ⟨1, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩)
((fun i ↦ i) ⟨2, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨2, ⋯⟩)
((fun i ↦ i) ⟨3, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨2, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨0, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨0, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨1, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨1, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨2, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨2, ⋯⟩)⊢ ((Matrix.circulant orderFourGenerator).transpose * Matrix.circulant orderFourGenerator) ((fun i ↦ i) ⟨3, ⋯⟩)
((fun i ↦ i) ⟨3, ⋯⟩) =
↑4 ((fun i ↦ i) ⟨3, ⋯⟩) ((fun i ↦ i) ⟨3, ⋯⟩)
All goals completed! 🐙Every circulant Hadamard matrix has order at most four.
This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof, which shows that a real circulant Hadamard matrix of positive order $n$ exists exactly when $n = 1$ or $n = 4$.
@[category research solved, AMS 15, formal_proof using lean4 at
"https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/LinearAlgebra/CirculantHadamard/Main.lean#L21"]
theorem circulant_hadamard_conjecture {n : ℕ} (v : Fin n → ℝ)
(hv : Hadamard.IsHadamard' (Matrix.circulant v)) : n ≤ 4 := n:ℕv:Fin n → ℝhv:Hadamard.IsHadamard' (Matrix.circulant v)⊢ n ≤ 4
All goals completed! 🐙end CirculantHadamard