AFTD Auto-Formalizing Theoretical Domains

op_1423_three_band_closure_iff

theoremverified

For 1 ≤ m, 3m ≤ F < 4m and finite sets A ⊆ [m,2m), B ⊆ [2m,3m), C ⊆ [3m,F), the union A ∪ B ∪ C is closed under sums at most F if and only if F is in neither A+A nor A+B, every element of (A+A) in [2m,3m) is in B, and every element of ((A+A) ∪ (A+B)) in [3m,F) is in C.

Statement

theorem op_1423_three_band_closure_iff (F m : ℕ) (hm : 1 ≤ m) (hlow : 3*m ≤ F) (hhigh : F < 4*m)
    (A B C : Finset ℕ)
    (hA : A ⊆ Finset.Ico m (2*m))
    (hB : B ⊆ Finset.Ico (2*m) (3*m))
    (hC : C ⊆ Finset.Ico (3*m) F) :
    (∀ x ∈ A ∪ B ∪ C, ∀ y ∈ A ∪ B ∪ C, x+y ≤ F → x+y ∈ A ∪ B ∪ C) ↔
    let AA := Finset.image₂ (fun a b : ℕ => a+b) A A
    let AB := Finset.image₂ (fun a b : ℕ => a+b) A B
    let P := (AA ∪ AB).filter (fun x => 3*m ≤ x ∧ x < F)
    F ∉ AA ∧ F ∉ AB ∧ AA ∩ Finset.Ico (2*m) (3*m) ⊆ B ∧ P ⊆ C
Source
Structural closure step for op_1423_two_band_binomial_count, following the band decomposition in OP-1423.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem characterizes when three bands of integers A ⊆ [m, 2m), B ⊆ [2m, 3m), and C ⊆ [3m, F) have their union closed under sums bounded by F, where 3m ≤ F < 4m. In the forward direction, every element of the union is strictly less than F, which immediately prevents F from being in A+A or A+B, and forces any sum lying in [2m, 3m) or [3m, F) into B or C respectively by interval disjointness. In the reverse direction, any pair involving C or two elements from B sums to at least 4m > F, so only pairs from A × A, A × B, and B × A can have sums bounded by F, and the assumed conditions route them into B or C.

  1. Every element of A, B, and C satisfies the bounds of its ambient interval: m ≤ x < 2m for x ∈ A, 2m ≤ x < 3m for x ∈ B, and 3m ≤ x < F for x ∈ C.

    Unpack the subset assumptions A ⊆ [m, 2m), B ⊆ [2m, 3m), and C ⊆ [3m, F) using the characterisation of membership in half-open intervals (`Finset.mem_Ico.mp`).

    lines 11–16

    uses Finset.mem_Ico.mp

      have a_bounds : ∀ x ∈ A, m ≤ x ∧ x < 2*m := by
        intro x hx; exact Finset.mem_Ico.mp (hA hx)
      have b_bounds : ∀ x ∈ B, 2*m ≤ x ∧ x < 3*m := by
        intro x hx; exact Finset.mem_Ico.mp (hB hx)
      have c_bounds : ∀ x ∈ C, 3*m ≤ x ∧ x < F := by
        intro x hx; exact Finset.mem_Ico.mp (hC hx)
  2. Every element x ∈ A ∪ B ∪ C satisfies m ≤ x < F.

    Split into cases depending on whether x ∈ A, x ∈ B, or x ∈ C; in each case, the individual interval bounds together with 1 ≤ m and 3m ≤ F imply m ≤ x < F via linear arithmetic.

    lines 17–23

    uses Finset.mem_union

      have xin : ∀ x, x ∈ A ∪ B ∪ C → m ≤ x ∧ x < F := by
        intro x hx
        simp only [Finset.mem_union] at hx
        rcases hx with (ha | hb) | hc
        · have := a_bounds x ha; omega
        · have := b_bounds x hb; omega
        · have := c_bounds x hc; omega
  3. The goal reduces to proving the forward and reverse implications of the equivalence separately.

    Simplify the local let-bindings and split the iff goal into forward and backward directions.

    lines 24–25

      simp only
      constructor
  4. Assuming closure under bounded sums, F does not belong to A ∪ B ∪ C.

    Assume for contradiction that F ∈ A ∪ B ∪ C. By the bounds on elements of the union, this implies F < F, an immediate arithmetic contradiction.

    lines 26–30

      · intro h
        have hnof : F ∉ A ∪ B ∪ C := by
          intro hf
          have := xin F hf
          omega
  5. Neither A+A nor A+B contains F.

    If F ∈ A+A, then F = a + b with a, b ∈ A; since a + b ≤ F, closure would place F in A ∪ B ∪ C, contradicting F ∉ A ∪ B ∪ C. The exact same argument applies to F ∈ A+B with a ∈ A and b ∈ B.

    lines 31–42

    uses Finset.mem_image₂.mp

        have hnoaa : F ∉ Finset.image₂ (fun a b : ℕ => a+b) A A := by
          intro hf
          obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp hf
          have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)
          apply hnof
          simpa only [hab] using hh
        have hnoab : F ∉ Finset.image₂ (fun a b : ℕ => a+b) A B := by
          intro hf
          obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp hf
          have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)
          apply hnof
          simpa only [hab] using hh
  6. Every element of A+A lying in [2m, 3m) belongs to B.

    Let z ∈ (A+A) ∩ [2m, 3m), so z = a + b for some a, b ∈ A. Since z < 3m ≤ F, the sum is bounded by F, so z ∈ A ∪ B ∪ C by closure. But 2m ≤ z < 3m is incompatible with z ∈ A (which requires z < 2m) and z ∈ C (which requires z ≥ 3m), leaving z ∈ B as the only possibility.

    lines 43–55

    uses Finset.mem_inter.mp, Finset.mem_image₂.mp, Finset.mem_Ico.mp, Finset.mem_union

        refine ⟨hnoaa,hnoab,?_,?_⟩
        · intro z hz
          obtain ⟨haa,hband⟩ := Finset.mem_inter.mp hz
          obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp haa
          have hband' := Finset.mem_Ico.mp hband
          have hz' : z ∈ A ∪ B ∪ C := by
            have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)
            simpa only [hab] using hh
          simp only [Finset.mem_union] at hz'
          rcases hz' with (ha' | hb') | hc'
          · have := a_bounds z ha'; omega
          · exact hb'
          · have := c_bounds z hc'; omega
  7. Every element of (A+A) ∪ (A+B) lying in [3m, F) belongs to C.

    Let z ∈ P, so z ∈ (A+A) ∪ (A+B) with 3m ≤ z < F. In either case, z is the sum of two elements of A ∪ B with sum strictly less than F, so z ∈ A ∪ B ∪ C by closure. Since z ≥ 3m, z cannot belong to A (which is below 2m) or B (which is below 3m), so z ∈ C.

    lines 56–71

    uses Finset.mem_filter.mp, Finset.mem_union.mp, Finset.mem_image₂.mp, Finset.mem_union

        · intro z hz
          obtain ⟨hs,hrange⟩ := Finset.mem_filter.mp hz
          obtain ⟨hlo,hhi⟩ := hrange
          have hz' : z ∈ A ∪ B ∪ C := by
            rcases Finset.mem_union.mp hs with haa | hab
            · obtain ⟨a,ha,b,hb,heq⟩ := Finset.mem_image₂.mp haa
              have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)
              simpa only [heq] using hh
            · obtain ⟨a,ha,b,hb,heq⟩ := Finset.mem_image₂.mp hab
              have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)
              simpa only [heq] using hh
          simp only [Finset.mem_union] at hz'
          rcases hz' with (ha' | hb') | hc'
          · have := a_bounds z ha'; omega
          · have := b_bounds z hb'; omega
          · exact hc'
  8. In the reverse direction, it suffices to check closure on all nine combinations of membership for x and y in A, B, and C.

    Assume the four conditions: F ∉ A+A, F ∉ A+B, (A+A) ∩ [2m, 3m) ⊆ B, and P ⊆ C. Given x, y ∈ A ∪ B ∪ C with x + y ≤ F, case split on which of A, B, C contains x and which contains y.

    lines 72–74

    uses Finset.mem_union

      · rintro ⟨hnoaa,hnoab,hforce,hP⟩ x hx y hy hxy
        simp only [Finset.mem_union] at hx hy ⊢
        rcases hx with (ha | hb) | hc <;> rcases hy with (ha' | hb') | hc'
  9. If x, y ∈ A with x + y ≤ F, then x + y ∈ B ∪ C.

    Here x + y ∈ A+A. Because F ∉ A+A, x + y cannot equal F, so x + y < F. If x + y < 3m, then since x, y ≥ m we have 2m ≤ x + y < 3m, placing x + y in (A+A) ∩ [2m, 3m) ⊆ B. If instead x + y ≥ 3m, then 3m ≤ x + y < F, placing x + y in P ⊆ C.

    lines 75–89

    uses Finset.mem_image₂.mpr, Finset.mem_inter.mpr, Finset.mem_Ico.mpr, Finset.mem_filter.mpr, Finset.mem_union.mpr, Or.inl

        · have hax := a_bounds x ha
          have hay := a_bounds y ha'
          have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A A := Finset.mem_image₂.mpr ⟨x,ha,y,ha',rfl⟩
          have hne : x+y ≠ F := by
            intro heq
            exact hnoaa (by simpa only [heq] using hsum)
          have hlt : x+y < F := by omega
          by_cases hband : x+y < 3*m
          · left; right
            apply hforce
            exact Finset.mem_inter.mpr ⟨hsum, Finset.mem_Ico.mpr (by omega)⟩
          · right
            apply hP
            apply Finset.mem_filter.mpr
            exact ⟨Finset.mem_union.mpr (Or.inl hsum), by omega⟩
  10. If x ∈ A, y ∈ B with x + y ≤ F, then x + y ∈ C.

    Here x + y ∈ A+B. Since F ∉ A+B and x + y ≤ F, we have x + y < F. Furthermore, x ≥ m and y ≥ 2m give x + y ≥ 3m. Thus x + y ∈ P ⊆ C.

    lines 90–98

    uses Finset.mem_image₂.mpr, Finset.mem_filter.mpr, Finset.mem_union.mpr, Or.inr

        · have hax := a_bounds x ha
          have hby := b_bounds y hb'
          have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := Finset.mem_image₂.mpr ⟨x,ha,y,hb',rfl⟩
          have hne : x+y ≠ F := by
            intro heq
            exact hnoab (by simpa only [heq] using hsum)
          have hlt : x+y < F := by omega
          right; apply hP; apply Finset.mem_filter.mpr
          exact ⟨Finset.mem_union.mpr (Or.inr hsum), by omega⟩
  11. The case x ∈ A, y ∈ C cannot occur when x + y ≤ F.

    Since x ≥ m and y ≥ 3m, their sum is at least 4m, contradicting x + y ≤ F < 4m.

    line 99

        · have := a_bounds x ha; have := c_bounds y hc'; omega
  12. If x ∈ B, y ∈ A with x + y ≤ F, then x + y ∈ C.

    By commutativity of addition (`Nat.add_comm`), x + y = y + x ∈ A+B. As in the A × B case, x + y ≠ F implies x + y < F, and x + y ≥ 3m, so x + y ∈ P ⊆ C.

    lines 100–110

    uses Finset.mem_image₂.mpr, Nat.add_comm, Finset.mem_filter.mpr, Finset.mem_union.mpr, Or.inr

        · have hbx := b_bounds x hb
          have hay := a_bounds y ha'
          have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := by
            have h : y+x ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := Finset.mem_image₂.mpr ⟨y,ha',x,hb,rfl⟩
            simpa only [Nat.add_comm] using h
          have hne : x+y ≠ F := by
            intro heq
            exact hnoab (by simpa only [heq] using hsum)
          have hlt : x+y < F := by omega
          right; apply hP; apply Finset.mem_filter.mpr
          exact ⟨Finset.mem_union.mpr (Or.inr hsum), by omega⟩
  13. All remaining combinations (B × B, B × C, C × A, C × B, C × C) exceed F and are impossible.

    In each of these five cases, the interval lower bounds imply x + y ≥ 4m, contradicting x + y ≤ F < 4m.

    lines 111–115

        · have := b_bounds x hb; have := b_bounds y hb'; omega
        · have := b_bounds x hb; have := c_bounds y hc'; omega
        · have := c_bounds x hc; have := a_bounds y ha'; omega
        · have := c_bounds x hc; have := b_bounds y hb'; omega
        · have := c_bounds x hc; have := c_bounds y hc'; omega
Finset.mem_Ico.mp
An element belongs to the half-open interval [a, b) only if a ≤ x and x < b.
Finset.mem_Ico.mpr
If a ≤ x and x < b, then x belongs to the half-open interval [a, b).
Finset.mem_union
An element is in the union s ∪ t if and only if it is in s or in t.
Finset.mem_union.mp
If an element is in s ∪ t, then it is in s or in t.
Finset.mem_union.mpr
If an element is in s or in t, then it is in s ∪ t.
Finset.mem_image₂.mp
If c is in the pairwise image {f(a, b) | a ∈ s, b ∈ t}, then there exist a ∈ s and b ∈ t with f(a, b) = c.
Finset.mem_image₂.mpr
If there exist a ∈ s and b ∈ t such that f(a, b) = c, then c belongs to {f(a, b) | a ∈ s, b ∈ t}.
Finset.mem_inter.mp
If an element belongs to the intersection s ∩ t, then it belongs to both s and t.
Finset.mem_inter.mpr
If an element belongs to both s and t, then it belongs to the intersection s ∩ t.
Finset.mem_filter.mp
If an element is in the filtered finset {x ∈ s | p(x)}, then it is in s and satisfies p.
Finset.mem_filter.mpr
If an element belongs to s and satisfies p, then it belongs to {x ∈ s | p(x)}.
Or.inl
From a proof of P, conclude the disjunction P ∨ Q.
Or.inr
From a proof of Q, conclude the disjunction P ∨ Q.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem op_1423_three_band_closure_iff (F m : ℕ) (hm : 1 ≤ m) (hlow : 3*m ≤ F) (hhigh : F < 4*m)    (A B C : Finset ℕ)    (hA : A ⊆ Finset.Ico m (2*m))    (hB : B ⊆ Finset.Ico (2*m) (3*m))    (hC : C ⊆ Finset.Ico (3*m) F) :    (∀ x ∈ A ∪ B ∪ C, ∀ y ∈ A ∪ B ∪ C, x+y ≤ F → x+y ∈ A ∪ B ∪ C) ↔    let AA := Finset.image₂ (fun a b : ℕ => a+b) A A    let AB := Finset.image₂ (fun a b : ℕ => a+b) A B    let P := (AA ∪ AB).filter (fun x => 3*m ≤ x ∧ x < F)    F ∉ AA ∧ F ∉ AB ∧ AA ∩ Finset.Ico (2*m) (3*m) ⊆ B ∧ P ⊆ C := by  have a_bounds : ∀ x ∈ A, m ≤ x ∧ x < 2*m := by    intro x hx; exact Finset.mem_Ico.mp (hA hx)  have b_bounds : ∀ x ∈ B, 2*m ≤ x ∧ x < 3*m := by    intro x hx; exact Finset.mem_Ico.mp (hB hx)  have c_bounds : ∀ x ∈ C, 3*m ≤ x ∧ x < F := by    intro x hx; exact Finset.mem_Ico.mp (hC hx)  have xin : ∀ x, x ∈ A ∪ B ∪ C → m ≤ x ∧ x < F := by    intro x hx    simp only [Finset.mem_union] at hx    rcases hx with (ha | hb) | hc    · have := a_bounds x ha; omega    · have := b_bounds x hb; omega    · have := c_bounds x hc; omega  simp only  constructor  · intro h    have hnof : F ∉ A ∪ B ∪ C := by      intro hf      have := xin F hf      omega    have hnoaa : F ∉ Finset.image₂ (fun a b : ℕ => a+b) A A := by      intro hf      obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp hf      have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)      apply hnof      simpa only [hab] using hh    have hnoab : F ∉ Finset.image₂ (fun a b : ℕ => a+b) A B := by      intro hf      obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp hf      have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)      apply hnof      simpa only [hab] using hh    refine ⟨hnoaa,hnoab,?_,?_⟩    · intro z hz      obtain ⟨haa,hband⟩ := Finset.mem_inter.mp hz      obtain ⟨a,ha,b,hb,hab⟩ := Finset.mem_image₂.mp haa      have hband' := Finset.mem_Ico.mp hband      have hz' : z ∈ A ∪ B ∪ C := by        have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)        simpa only [hab] using hh      simp only [Finset.mem_union] at hz'      rcases hz' with (ha' | hb') | hc'      · have := a_bounds z ha'; omega      · exact hb'      · have := c_bounds z hc'; omega    · intro z hz      obtain ⟨hs,hrange⟩ := Finset.mem_filter.mp hz      obtain ⟨hlo,hhi⟩ := hrange      have hz' : z ∈ A ∪ B ∪ C := by        rcases Finset.mem_union.mp hs with haa | hab        · obtain ⟨a,ha,b,hb,heq⟩ := Finset.mem_image₂.mp haa          have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)          simpa only [heq] using hh        · obtain ⟨a,ha,b,hb,heq⟩ := Finset.mem_image₂.mp hab          have hh := h a (by simp [ha]) b (by simp [hb]) (by omega)          simpa only [heq] using hh      simp only [Finset.mem_union] at hz'      rcases hz' with (ha' | hb') | hc'      · have := a_bounds z ha'; omega      · have := b_bounds z hb'; omega      · exact hc'  · rintro ⟨hnoaa,hnoab,hforce,hP⟩ x hx y hy hxy    simp only [Finset.mem_union] at hx hy ⊢    rcases hx with (ha | hb) | hc <;> rcases hy with (ha' | hb') | hc'    · have hax := a_bounds x ha      have hay := a_bounds y ha'      have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A A := Finset.mem_image₂.mpr ⟨x,ha,y,ha',rfl⟩      have hne : x+y ≠ F := by        intro heq        exact hnoaa (by simpa only [heq] using hsum)      have hlt : x+y < F := by omega      by_cases hband : x+y < 3*m      · left; right        apply hforce        exact Finset.mem_inter.mpr ⟨hsum, Finset.mem_Ico.mpr (by omega)⟩      · right        apply hP        apply Finset.mem_filter.mpr        exact ⟨Finset.mem_union.mpr (Or.inl hsum), by omega⟩    · have hax := a_bounds x ha      have hby := b_bounds y hb'      have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := Finset.mem_image₂.mpr ⟨x,ha,y,hb',rfl⟩      have hne : x+y ≠ F := by        intro heq        exact hnoab (by simpa only [heq] using hsum)      have hlt : x+y < F := by omega      right; apply hP; apply Finset.mem_filter.mpr      exact ⟨Finset.mem_union.mpr (Or.inr hsum), by omega⟩    · have := a_bounds x ha; have := c_bounds y hc'; omega    · have hbx := b_bounds x hb      have hay := a_bounds y ha'      have hsum : x+y ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := by        have h : y+x ∈ Finset.image₂ (fun a b : ℕ => a+b) A B := Finset.mem_image₂.mpr ⟨y,ha',x,hb,rfl⟩        simpa only [Nat.add_comm] using h      have hne : x+y ≠ F := by        intro heq        exact hnoab (by simpa only [heq] using hsum)      have hlt : x+y < F := by omega      right; apply hP; apply Finset.mem_filter.mpr      exact ⟨Finset.mem_union.mpr (Or.inr hsum), by omega⟩    · have := b_bounds x hb; have := b_bounds y hb'; omega    · have := b_bounds x hb; have := c_bounds y hc'; omega    · have := c_bounds x hc; have := a_bounds y ha'; omega    · have := c_bounds x hc; have := b_bounds y hb'; omega    · have := c_bounds x hc; have := c_bounds y hc'; omega
See it in the graphDiscuss this resultChallenge it