AFTD Auto-Formalizing Theoretical Domains

good_slopes_grid_single_slice_rectangle

theoremverified

A nonempty set of at most seven cells whose nonempty first-coordinate slices have at least four cells, whose nonempty columns have at least two, and whose rows have either zero or three cells consists of one slice and a two-by-three rectangle.

Statement

theorem good_slopes_grid_single_slice_rectangle
    {R C K : Type*} [DecidableEq R] [DecidableEq C] [DecidableEq K]
    (M : Finset (R × (C × K))) (hne : M.Nonempty) (hcard : M.card ≤ 7)
    (hslice : ∀ r, (M.filter fun p => p.1 = r).card = 0 ∨
      4 ≤ (M.filter fun p => p.1 = r).card)
    (hcols : ∀ k, (M.filter fun p => p.2.2 = k).card = 0 ∨
      2 ≤ (M.filter fun p => p.2.2 = k).card)
    (hrows : ∀ r c, (M.filter fun p => p.1 = r ∧ p.2.1 = c).card = 0 ∨
      (M.filter fun p => p.1 = r ∧ p.2.1 = c).card = 3) :
    ∃ (r : R) (A : Finset C) (T : Finset K),
      A.card = 2 ∧ T.card = 3 ∧ M = {r} ×ˢ (A ×ˢ T)
Source
Counting assembly of the 15-, 21- and 35-point fiber bounds for OP-1027.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • good_slopes_grid_rectangleIf a nonempty finite collection of cells has at most seven cells, each row has either zero or three cells, and every nonempty column has…

Lean source view module on GitHub

theorem good_slopes_grid_single_slice_rectangle
    {R C K : Type*} [DecidableEq R] [DecidableEq C] [DecidableEq K]
    (M : Finset (R × (C × K))) (hne : M.Nonempty) (hcard : M.card ≤ 7)
    (hslice : ∀ r, (M.filter fun p => p.1 = r).card = 0 ∨
      4 ≤ (M.filter fun p => p.1 = r).card)
    (hcols : ∀ k, (M.filter fun p => p.2.2 = k).card = 0 ∨
      2 ≤ (M.filter fun p => p.2.2 = k).card)
    (hrows : ∀ r c, (M.filter fun p => p.1 = r ∧ p.2.1 = c).card = 0 ∨
      (M.filter fun p => p.1 = r ∧ p.2.1 = c).card = 3) :
    ∃ (r : R) (A : Finset C) (T : Finset K),
      A.card = 2 ∧ T.card = 3 ∧ M = {r} ×ˢ (A ×ˢ T) := by
  classical
  let Rset := M.image Prod.fst
  have hsum : M.card = ∑ r ∈ Rset, (M.filter fun p => p.1 = r).card := by
    exact Finset.card_eq_sum_card_image Prod.fst M
  have hlow : ∀ r ∈ Rset, 4 ≤ (M.filter fun p => p.1 = r).card := by
    intro r hr
    obtain ⟨p,hp,hpr⟩ := Finset.mem_image.mp hr
    have hpos : 0 < (M.filter fun p => p.1 = r).card :=
      Finset.card_pos.mpr ⟨p,Finset.mem_filter.mpr ⟨hp,hpr⟩⟩
    rcases hslice r with h | h
    · omega
    · exact h
  have hRlow : 4 * Rset.card ≤ M.card := by
    rw [hsum]
    calc
      4 * Rset.card = ∑ _r ∈ Rset, 4 := by simp [Nat.mul_comm]
      _ ≤ ∑ r ∈ Rset, (M.filter fun p => p.1 = r).card := Finset.sum_le_sum hlow
  have hRne : Rset.Nonempty := hne.image Prod.fst
  have hRcard : Rset.card = 1 := by
    have hpos := Finset.card_pos.mpr hRne
    omega
  obtain ⟨r,hr⟩ := Finset.card_eq_one.mp hRcard
  have hfirst : ∀ p ∈ M, p.1 = r := by
    intro p hp
    have hh : p.1 ∈ Rset := Finset.mem_image_of_mem _ hp
    rw [hr] at hh
    simpa using hh
  let B := M.image Prod.snd
  have hinj : Set.InjOn (fun p : R × (C × K) => p.2) M := by
    intro p hp q hq heq
    exact Prod.ext ((hfirst p hp).trans (hfirst q hq).symm) heq
  have hBC : B.card = M.card := Finset.card_image_of_injOn hinj
  have hBne : B.Nonempty := hne.image Prod.snd
  have hBcard : B.card ≤ 7 := by omega
  have hBcol (k : K) : (B.filter fun p => p.2 = k).card = 0 ∨
      2 ≤ (B.filter fun p => p.2 = k).card := by
    have heq : B.filter (fun p => p.2 = k) =
        (M.filter fun p => p.2.2 = k).image Prod.snd := by
      ext x
      simp only [B, Finset.mem_filter, Finset.mem_image]
      constructor
      · rintro ⟨⟨p,hp,rfl⟩,hx⟩
        exact ⟨p,⟨hp,hx⟩,rfl⟩
      · rintro ⟨p,⟨hp,hk⟩,rfl⟩
        exact ⟨⟨p,hp,rfl⟩,hk⟩
    rw [heq, Finset.card_image_of_injOn (hinj.mono (Finset.filter_subset _ _))]
    exact hcols k
  have hBrow (c : C) : (B.filter fun p => p.1 = c).card = 0 ∨
      (B.filter fun p => p.1 = c).card = 3 := by
    have heq : B.filter (fun p => p.1 = c) =
        (M.filter fun p => p.1 = r ∧ p.2.1 = c).image Prod.snd := by
      ext x
      simp only [B, Finset.mem_filter, Finset.mem_image]
      constructor
      · rintro ⟨⟨p,hp,rfl⟩,hx⟩
        exact ⟨p,⟨hp,⟨hfirst p hp,hx⟩⟩,rfl⟩
      · rintro ⟨p,⟨hp,_,hc⟩,rfl⟩
        exact ⟨⟨p,hp,rfl⟩,hc⟩
    rw [heq, Finset.card_image_of_injOn (hinj.mono (Finset.filter_subset _ _))]
    exact hrows r c
  obtain ⟨A,T,hA,hT,hrect⟩ := good_slopes_grid_rectangle B hBne hBcard hBrow hBcol
  refine ⟨r,A,T,hA,hT,?_⟩
  have hdecomp : M = {r} ×ˢ B := by
    ext p
    simp only [Finset.mem_product, Finset.mem_singleton]
    constructor
    · intro hp
      exact ⟨hfirst p hp,Finset.mem_image_of_mem _ hp⟩
    · rintro ⟨hpr,hh⟩
      obtain ⟨q,hq,hqp⟩ := Finset.mem_image.mp hh
      have hpq : p = q := Prod.ext (hpr.trans (hfirst q hq).symm) hqp.symm
      simpa [hpq] using hq
  simpa [hrect] using hdecomp
See it in the graphDiscuss this resultChallenge it