The Lean results
What the formal proof says
The proof is 69 Lean modules, about 6900 lines, organized to follow the paper. Below are its main theorems and, for each numbered result of the paper, the declarations that prove it, with their exact statements at commit 36ec6e6.
The main theorems
Every family of 14-point subsets of a 24-point set that covers every 4-point subset has at least 20 members.
theorem covering_24_14_4 (𝒯 : Finset (Finset (Fin 24)))
(hk : ∀ B ∈ 𝒯, B.card = 14)
(hcov : ∀ S : Finset (Fin 24), S.card = 4 → ∃ B ∈ 𝒯, S ⊆ B) :
20 ≤ 𝒯.card
Covering/Main.lean:44Checked by Lean
Derived from the first bound by counting the blocks through each point.
theorem covering_25_15_5 (𝒯 : Finset (Finset (Fin 25)))
(hk : ∀ B ∈ 𝒯, B.card = 15)
(hcov : ∀ S : Finset (Fin 25), S.card = 5 → ∃ B ∈ 𝒯, S ⊆ B) :
34 ≤ 𝒯.card
Covering/Main.lean:51Checked by Lean
The paper, result by result
This is the map in the repository’s README. The formal proof follows the paper’s argument, though not always its order or its exact intermediate statements.
theorem covering_24_14_4 (𝒯 : Finset (Finset (Fin 24)))
(hk : ∀ B ∈ 𝒯, B.card = 14)
(hcov : ∀ S : Finset (Fin 24), S.card = 4 → ∃ B ∈ 𝒯, S ⊆ B) :
20 ≤ 𝒯.card
Covering/Main.lean:44Checked by Lean
theorem covering_25_15_5 (𝒯 : Finset (Finset (Fin 25)))
(hk : ∀ B ∈ 𝒯, B.card = 15)
(hcov : ∀ S : Finset (Fin 25), S.card = 5 → ∃ B ∈ 𝒯, S ⊆ B) :
34 ≤ 𝒯.card
Covering/Main.lean:51Checked by Lean
theorem local_seven_vs_six {C : Type*} [DecidableEq C]
(N : Fin 20 → Finset (Fin 20))
(hn : ∀ x, x ∉ N x) (hs : ∀ x y, y ∈ N x ↔ x ∈ N y)
(hc : ∀ x, (N x).card=6) (a b : Fin 20) (color : Fin 20 → C)
(hedge : ∀ x y, x ≠ a → x ≠ b → y ≠ a → y ≠ b →
y ∈ N x → color x = color y)
(hcap : ∀ c, (univ.filter (fun x => x ≠ a ∧ x ≠ b ∧ color x=c)).card ≤ 6) :
False
Covering/Quadruple/SevenVsSix.lean:45Checked by Lean
theorem remaining_component_sizes {α : Type*} [DecidableEq α]
(s : Finset α) (f : α → ℕ) (hcard : 3 ≤ s.card)
(hmin : ∀ a ∈ s, 2 ≤ f a) (heven : ∀ a ∈ s, Even (f a))
(htotal : ∑ a ∈ s, f a ≤ 16)
(hfour : ¬ ∃ a ∈ s, f a = 4)
(htwo : ¬ ∃ a ∈ s, ∃ b ∈ s, a ≠ b ∧ f a = 2 ∧ f b = 2) :
∃ a ∈ s, ∃ b ∈ s, ∃ c ∈ s,
a ≠ b ∧ a ≠ c ∧ b ≠ c ∧ f a = 2 ∧ 6 ≤ f b ∧ 6 ≤ f c
Covering/Components/Sizes.lean:63Checked by Lean
All 69 modules
Grouped by folder, each in import order. Line counts include comments. The last group also lists the three files at the root: Challenge.lean, the statement Comparator checks; Solution.lean, which proves it; and Covering.lean, which imports the proof.
The covering model
Families, degrees, derivatives and counting
Section 3.1, for any weighted graph
Section 3 and Section 5.1
Theorem 1.1, Corollary 5.2, and the Palomar statements