C(24,14,4)≥ 20

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

C(24,14,4) ≥ 20

Theorem 1.1

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

C(25,15,5) ≥ 34

Corollary 5.2

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.

Corollary A.4 · Degree and codegree lower bounds

Step 1
theorem triple_cover_23_13_ge_eleven (F : Family 23)
    (hrows : ∀ R, R ∈ F → ValidBlock 13 R) (hcover : IsCovering 3 F) : 11≤F.length

Covering/PairCover/Floors.lean:37Checked by Lean

theorem pair_floor_six (T : Family 24)
    (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T)
    (p q : Fin 24) (hpq : p≠q) : 6≤pairDegree T p q

Covering/PairCover/Floors.lean:56Checked by Lean

theorem point_floor_eleven (T : Family 24)
    (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T)
    (p : Fin 24) : 11 ≤ degree T p

Covering/Components/Floors.lean:18Checked by Lean

Lemma A.6

Step 4
theorem no_two_low_in_pair_cover (F : Family 21)
    (hrows : ∀ R, R ∈ F → ValidBlock 11 R) (hcover : IsCovering 2 F)
    (hlen : F.length=6) (p q : Fin 21) (hpq : p≠q)
    (hp : degree F p=2) (hq : degree F q=2) : False

Covering/PairCover/Matching.lean:37Checked by Lean

theorem codegree_two_matching (F : Family 22)
    (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F)
    (u v w : Fin 22) (huv : u≠v) (huw : u≠w)
    (hu : degree F u=6) (hv : pairDegree F u v=2) (hw : pairDegree F u w=2) : v=w

Covering/PairCover/Matching.lean:103Checked by Lean

Theorem 2.1 · Eleven-block rigidity

Step 4
theorem eleven_block_regular (F : Family 22)
    (hr : ∀ R, R ∈ F → ValidBlock 12 R) (hc : IsCovering 3 F)
    (hlen : F.length = 11) : ∀ p, degree F p = 6

Covering/Rigidity/Regularity.lean:33Checked by Lean

theorem eleven_block_rigidity (F : Family 22)
    (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F)
    (hlen : F.length=11) :
    ∃ σ : Fin 22 → Fin 22,
      (∀ p, σ p≠p) ∧ (∀ p, σ (σ p)=p) ∧
      (∀ p q, pairDegree F p q=if p=q ∨ q=σ p then 6 else 3) ∧
      (∀ p R, R ∈ F → (p ∈ R ↔ σ p ∈ R))

Covering/Rigidity/Twins.lean:38Checked by Lean

theorem eleven_block_intersections (F : Family 22)
    (hrows : ∀ R, R ∈ F → ValidBlock 12 R) (hcover : IsCovering 3 F)
    (hlen : F.length = 11) (i j : Fin F.length) (hij : i ≠ j) :
    ((incidence F).transpose * incidence F) i j = 6

Covering/Rigidity/Twins.lean:82Checked by Lean

Equations (5)–(6)

Step 4
theorem incidence_excess_variance (F : Family 22)
    (hrows : ∀ R, R ∈ F → ValidBlock 12 R)
    (hregular : ∀ p, degree F p=6) (hlen : F.length=11) :
    (∑ p, energy (coverWeights F) p) = 198 +
      ∑ i : Fin F.length, ∑ j : Fin F.length,
        (if i=j then 0 else ((incidence F).transpose * incidence F) i j - 6)^2

Covering/Rigidity/Energy.lean:70Checked by Lean

theorem incidence_deficit_identity (F : Family 22)
    (hrows : ∀ R, R ∈ F → ValidBlock 12 R)
    (hregular : ∀ p, degree F p = 6) (hlen : F.length = 11) :
    (∑ p, (9 - energy (coverWeights F) p)) +
      (∑ i : Fin F.length, ∑ j : Fin F.length,
        (if i = j then 0 else ((incidence F).transpose * incidence F) i j - 6)^2) = 0

Covering/Rigidity/Energy.lean:140Checked by Lean

Lemma 3.1 · The incidence relation space

Step 3
lemma card_sub_rank_le_balanced_components (hd : S.d ≠ 0) (c : ℝ) (hc : 0 ≤ c) :
    Fintype.card V - (S.gram c).rank ≤ Nat.card {a // S.BalancedBipartite a}

Covering/Kernel/Gram.lean:77Checked by Lean

lemma at_least_three_components (T : Family 24)
    (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T) (hlen : T.length = 19) :
    3 ≤ Nat.card {c // (lowSystem T hrows hcover).BalancedBipartite c}

Covering/Components/RelationSpace.lean:57Checked by Lean

Equations (10)–(12)

Step 3
lemma component_slot_balance_with_edges (T : Family 24)
    (hrows : ∀ R, R ∈ T → ValidBlock 14 R) (hcover : IsCovering 4 T)
    (c : (lowSystem T hrows hcover).graph.ConnectedComponent)
    (hc : (lowSystem T hrows hcover).BalancedBipartite c) :
    ∃ s t : Finset (LowPoint T),
      s.Nonempty ∧ t.Nonempty ∧ _root_.Disjoint s t ∧ s.card = t.card ∧
      (∀ p, (lowSystem T hrows hcover).graph.connectedComponentMk p = c ↔ p ∈ s ∨ p ∈ t) ∧
      (∀ j : Fin T.length,
        (s.filter fun p => p.val ∈ T.get j).card =
        (t.filter fun p => p.val ∈ T.get j).card) ∧
      (∀ p q, (lowSystem T hrows hcover).graph.connectedComponentMk p = c →
        (lowSystem T hrows hcover).graph.Adj p q →
        (p ∈ s ∧ q ∈ t) ∨ (p ∈ t ∧ q ∈ s))

Covering/Components/Balance.lean:19Checked by Lean

Section 4.3 · A neighborhood cannot fit in an omission class

Step 6
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

Section 5.1 · A two-point component and two larger components

Step 7
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.