op_1423_three_band_closure_iff
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.
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`).
uses
Finset.mem_Ico.mphave 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)
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.
uses
Finset.mem_unionhave 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
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.
simp only constructor
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.
· intro h have hnof : F ∉ A ∪ B ∪ C := by intro hf have := xin F hf omega
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.
uses
Finset.mem_image₂.mphave 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
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.
uses
Finset.mem_inter.mp,Finset.mem_image₂.mp,Finset.mem_Ico.mp,Finset.mem_unionrefine ⟨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
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.
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'
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.
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'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.
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⟩
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.
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⟩
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.
· have := a_bounds x ha; have := c_bounds y hc'; omega
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.
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⟩
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.
· 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.
- The arithmetic comparisons bounding sums and ruling out cases where sums exceed F are solved automatically by the Presburger arithmetic tactic `omega`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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