AFTD Auto-Formalizing Theoretical Domains

good_slopes_rook_strong_neighbors_rectangle

theoremverified

A nonempty set of at most seven cells in a four-by-six grid is a complete two-by-three rectangle if each selected cell has at least two other selected cells in its row and at least one other selected cell in its column.

Statement

theorem good_slopes_rook_strong_neighbors_rectangle (B : Finset (Fin 4 × Fin 6)) (hnonempty : B.Nonempty) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 2 ≤ (B.filter fun q => q ≠ p ∧ q.1 = p.1).card ∧ 1 ≤ (B.filter fun q => q ≠ p ∧ q.2 = p.2).card) : ∃ (rows : Finset (Fin 4)) (cols : Finset (Fin 6)), rows.card = 2 ∧ cols.card = 3 ∧ B = rows.product cols
Source
The rook-neighbor reduction for good_slopes_fiber35_colored_gap; compare the finite shape search in experiment 22260.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Lean source view module on GitHub

open Finset

theorem good_slopes_rook_strong_neighbors_rectangle (B : Finset (Fin 4 × Fin 6)) (hnonempty : B.Nonempty) (hsize : B.card ≤ 7) (hneighbors : ∀ p ∈ B, 2 ≤ (B.filter fun q => q ≠ p ∧ q.1 = p.1).card ∧ 1 ≤ (B.filter fun q => q ≠ p ∧ q.2 = p.2).card) : ∃ (rows : Finset (Fin 4)) (cols : Finset (Fin 6)), rows.card = 2 ∧ cols.card = 3 ∧ B = rows.product cols := by
  classical
  let rows := B.image Prod.fst
  let cols := B.image Prod.snd
  have hrow : ∀ r ∈ rows, 3 ≤ (B.filter fun q => q.1 = r).card := by
    intro r hr
    obtain ⟨p,hp,hpr⟩ := Finset.mem_image.mp hr
    let N := B.filter fun q => q ≠ p ∧ q.1 = p.1
    have hpN : p ∉ N := by simp [N]
    have hsub : insert p N ⊆ B.filter fun q => q.1 = r := by
      intro q hq
      rcases Finset.mem_insert.mp hq with rfl | hq
      · exact Finset.mem_filter.mpr ⟨hp,hpr⟩
      · have hq' := Finset.mem_filter.mp hq
        exact Finset.mem_filter.mpr ⟨hq'.1,hq'.2.2.trans hpr⟩
    have hbound : N.card + 1 ≤ (B.filter fun q => q.1 = r).card := by
      rw [← Finset.card_insert_of_notMem hpN]
      exact Finset.card_le_card hsub
    have hN : 2 ≤ N.card := (hneighbors p hp).1
    omega
  have hcol : ∀ c ∈ cols, 2 ≤ (B.filter fun q => q.2 = c).card := by
    intro c hc
    obtain ⟨p,hp,hpc⟩ := Finset.mem_image.mp hc
    let N := B.filter fun q => q ≠ p ∧ q.2 = p.2
    have hpN : p ∉ N := by simp [N]
    have hsub : insert p N ⊆ B.filter fun q => q.2 = c := by
      intro q hq
      rcases Finset.mem_insert.mp hq with rfl | hq
      · exact Finset.mem_filter.mpr ⟨hp,hpc⟩
      · have hq' := Finset.mem_filter.mp hq
        exact Finset.mem_filter.mpr ⟨hq'.1,hq'.2.2.trans hpc⟩
    have hbound : N.card + 1 ≤ (B.filter fun q => q.2 = c).card := by
      rw [← Finset.card_insert_of_notMem hpN]
      exact Finset.card_le_card hsub
    have hN : 1 ≤ N.card := (hneighbors p hp).2
    omega
  have hsumrow : 3 * rows.card ≤ B.card := by
    rw [Finset.card_eq_sum_card_image Prod.fst B]
    calc
      3 * rows.card = ∑ r ∈ rows, 3 := by simp [Nat.mul_comm]
      _ ≤ ∑ r ∈ rows, (B.filter fun q => q.1 = r).card := by
        exact Finset.sum_le_sum fun r hr => hrow r hr
  have hsumcol : 2 * cols.card ≤ B.card := by
    rw [Finset.card_eq_sum_card_image Prod.snd B]
    calc
      2 * cols.card = ∑ c ∈ cols, 2 := by simp [Nat.mul_comm]
      _ ≤ ∑ c ∈ cols, (B.filter fun q => q.2 = c).card := by
        exact Finset.sum_le_sum fun c hc => hcol c hc
  obtain ⟨p,hp⟩ := hnonempty
  have hpr : p.1 ∈ rows := Finset.mem_image.mpr ⟨p,hp,rfl⟩
  have hpc : p.2 ∈ cols := Finset.mem_image.mpr ⟨p,hp,rfl⟩
  let col := B.filter fun q => q.2 = p.2
  have hinjcol : Set.InjOn (fun q : Fin 4 × Fin 6 => q.1) col := by
    intro x hx y hy heq
    apply Prod.ext heq
    exact (Finset.mem_filter.mp hx).2.trans (Finset.mem_filter.mp hy).2.symm
  have hrows : 2 ≤ rows.card := by
    calc
      2 ≤ col.card := hcol p.2 hpc
      _ = (col.image Prod.fst).card := (Finset.card_image_of_injOn hinjcol).symm
      _ ≤ rows.card := Finset.card_le_card (Finset.image_subset_image (Finset.filter_subset _ _))
  let row := B.filter fun q => q.1 = p.1
  have hinjrow : Set.InjOn (fun q : Fin 4 × Fin 6 => q.2) row := by
    intro x hx y hy heq
    apply Prod.ext
    · exact (Finset.mem_filter.mp hx).2.trans (Finset.mem_filter.mp hy).2.symm
    · exact heq
  have hcols : 3 ≤ cols.card := by
    calc
      3 ≤ row.card := hrow p.1 hpr
      _ = (row.image Prod.snd).card := (Finset.card_image_of_injOn hinjrow).symm
      _ ≤ cols.card := Finset.card_le_card (Finset.image_subset_image (Finset.filter_subset _ _))
  have hr : rows.card = 2 := by omega
  have hc : cols.card = 3 := by omega
  have hsub : B ⊆ rows.product cols := by
    intro q hq
    exact Finset.mem_product.mpr ⟨Finset.mem_image.mpr ⟨q,hq,rfl⟩,
      Finset.mem_image.mpr ⟨q,hq,rfl⟩⟩
  have hproduct : (rows.product cols).card = 6 := by simp [hr,hc]
  have hBupper := Finset.card_le_card hsub
  have hB : B.card = 6 := by omega
  exact ⟨rows,cols,hr,hc,Finset.eq_of_subset_of_card_le hsub (by omega)⟩
See it in the graphDiscuss this resultChallenge it