mondrian_cells_union_sum
Summing any integer-valued cell weight over a union of pairwise disjoint rectangle cell sets equals the sum of its sums over the rectangles.
Statement
theorem mondrian_cells_union_sum (P : List (ℕ × ℕ × ℕ × ℕ)) (h : P.Pairwise (fun r s => Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s))) (f : ℕ × ℕ → ℤ) : ∑ c ∈ P.toFinset.biUnion mondrian_rect_cells, f c = (P.map (fun r => ∑ c ∈ mondrian_rect_cells r, f c)).sum
- Source
- Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
- Used by 1
- mondrian_partition_horizontal_momentFor every integer-valued function f on row levels, the sum over an admissible n-square partition of width times the increment of f across…
The proof, explained
The theorem is proved by induction on the list of rectangles P. The base case of an empty list holds because both the union and list sums are zero. In the inductive step for `r :: P`, the pairwise disjointness hypothesis ensures that the cell set of `r` is disjoint from the union of cell sets of `P`, allowing the sum over the union to split into the sum over `r` plus the sum over `P`. The proof is completed by applying the induction hypothesis to the tail sum and unfolding the list summation.
The sum equality holds when the list of rectangles is empty. automation
We induct on the list P. When P is empty, the union of cells is empty and the mapped list of sums is empty, so both sides evaluate to 0 by simplification.
induction P with | nil => simp
In the inductive step for r :: P, the head rectangle r is disjoint from every rectangle in P, and P is pairwise disjoint.
Applying `List.pairwise_cons.mp` to the assumption that `r :: P` is pairwise disjoint separates it into two hypotheses: `r` has cell sets disjoint from every rectangle in `P` (hr), and `P` itself is pairwise disjoint (hP).
uses
List.pairwise_cons.mp| cons r P ih => obtain ⟨hr, hP⟩ := List.pairwise_cons.mp hThe cells of rectangle r are disjoint from the union of cells of all rectangles in P.
By `Finset.disjoint_biUnion_right`, a set is disjoint from a union over a finite set if and only if it is disjoint from each constituent set. Rewriting the membership condition with `List.mem_toFinset` makes this match the hypothesis that `r` is disjoint from every rectangle in `P`.
uses
Finset.disjoint_biUnion_right,List.mem_toFinsethave hd : Disjoint (mondrian_rect_cells r) (P.toFinset.biUnion mondrian_rect_cells) := by rw [Finset.disjoint_biUnion_right] simpa only [List.mem_toFinset] using hr
The sum over the union of cells of r :: P equals the sum of the rectangle sums over r :: P.
The cell set of `r :: P` is rewritten as the union of the cells of `r` and the cell union of `P` using `List.toFinset_cons` and `Finset.biUnion_insert`. Since these two sets are disjoint, `Finset.sum_union` splits the summation into the sum over `r`'s cells plus the sum over `P`'s cells. Applying the induction hypothesis (`ih hP`) and expanding the list map and list sum with `List.map_cons` and `List.sum_cons` equates both sides.
uses
List.toFinset_cons,Finset.biUnion_insert,Finset.sum_union,List.map_cons,List.sum_consrw [List.toFinset_cons, Finset.biUnion_insert, Finset.sum_union hd, ih hP, List.map_cons, List.sum_cons]
List.pairwise_cons.mp- If a list `a :: l` is pairwise related under a relation R, then `a` is related to every element in `l` and `l` is itself pairwise related under R.
Finset.disjoint_biUnion_right- A finite set s is disjoint from a indexed union of finite sets over t if and only if s is disjoint from each member set.
List.mem_toFinset- An element belongs to the finite set of a list if and only if it belongs to the list.
List.toFinset_cons- The finite set associated with `a :: l` is obtained by inserting `a` into the finite set of `l`.
Finset.biUnion_insert- The union of a family of finite sets over `{a} ∪ s` equals `t a ∪ ⋃_{x ∈ s} t x`.
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum over the first set plus the sum over the second.
List.map_cons- Mapping a function over `a :: l` yields `f a` followed by the map over `l`.
List.sum_cons- The sum of a list `a :: l` is `a` plus the sum of `l`.
- The proof alternates between list representations (for induction and list summation) and finite sets (for unions and set summations), using `List.toFinset` to translate between them.
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.
open scoped BigOperatorstheorem mondrian_cells_union_sum (P : List (ℕ × ℕ × ℕ × ℕ)) (h : P.Pairwise (fun r s => Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s))) (f : ℕ × ℕ → ℤ) : ∑ c ∈ P.toFinset.biUnion mondrian_rect_cells, f c = (P.map (fun r => ∑ c ∈ mondrian_rect_cells r, f c)).sum := by induction P with | nil => simp | cons r P ih => obtain ⟨hr, hP⟩ := List.pairwise_cons.mp h have hd : Disjoint (mondrian_rect_cells r) (P.toFinset.biUnion mondrian_rect_cells) := by rw [Finset.disjoint_biUnion_right] simpa only [List.mem_toFinset] using hr rw [List.toFinset_cons, Finset.biUnion_insert, Finset.sum_union hd, ih hP, List.map_cons, List.sum_cons]