mondrian_rect_horizontal_moment
The sum over a rectangle of the row increment f(y+1)-f(y) equals its width times the difference between f at its upper and lower y coordinates.
Statement
theorem mondrian_rect_horizontal_moment (r : ℕ × ℕ × ℕ × ℕ)
(hy : r.2.2.1 ≤ r.2.2.2) (f : ℕ → ℤ) :
∑ c ∈ mondrian_rect_cells r, (f (c.2 + 1) - f c.2) =
(mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)- 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 2
- 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…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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 sum over the rectangle's cells is split into an iterated sum over its horizontal and vertical ranges. The inner sum along the vertical coordinate telescopes, evaluating to f(r.2.2.2) - f(r.2.2.1). Because this result is independent of the horizontal coordinate, the outer sum simply multiplies this difference by the number of columns, which is the width of the rectangle.
The sum over all cells of r of f(c.2 + 1) - f(c.2) equals (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)
The single simplification step carries out the full computation: it unfolds the definition of `mondrian_rect_cells` into the Cartesian product [r.1, r.2.1) ×ˢ [r.2.2.1, r.2.2.2) and splits the sum into an iterated sum over x and y via `Finset.sum_product`. The inner sum over y telescopes to f(r.2.2.2) - f(r.2.2.1) by `Finset.sum_Ico_sub` using the hypothesis hy. The outer sum over x is then a sum of this constant term, which by `Finset.sum_const` equals the cardinality of [r.1, r.2.1) times the constant. By `Nat.card_Ico`, this cardinality is r.2.1 - r.1, which is the definition of `mondrian_rect_width`, and `nsmul_eq_mul` converts the scalar multiplication into integer multiplication.
uses
mondrian_rect_cells,Finset.sum_product,Finset.sum_Ico_sub,Finset.sum_const,Nat.card_Ico,nsmul_eq_mul,mondrian_rect_widthsimp only [mondrian_rect_cells, Finset.sum_product, Finset.sum_Ico_sub f hy, Finset.sum_const, Nat.card_Ico, nsmul_eq_mul, mondrian_rect_width]
mondrian_rect_cells- the set of grid cells in rectangle r is the Cartesian product of intervals [r.1, r.2.1) × [r.2.2.1, r.2.2.2)
Finset.sum_product- a sum over a Cartesian product s ×ˢ t equals the iterated sum ∑ x ∈ s, ∑ y ∈ t, f (x, y)
Finset.sum_Ico_sub- for m ≤ n, the telescoping sum ∑ i ∈ [m, n), (f (i + 1) - f i) equals f n - f m
Finset.sum_const- the sum of a constant value b over a finite set s equals the cardinality of s scalar-multiplied by b
Nat.card_Ico- the number of natural numbers in the half-open interval [a, b) is b - a
nsmul_eq_mul- scalar multiplication by a natural number n • a in a semiring equals the product (↑n) * a
mondrian_rect_width- the width of rectangle r is the difference between its horizontal coordinates, r.2.1 - r.1
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_rect_horizontal_moment (r : ℕ × ℕ × ℕ × ℕ) (hy : r.2.2.1 ≤ r.2.2.2) (f : ℕ → ℤ) : ∑ c ∈ mondrian_rect_cells r, (f (c.2 + 1) - f c.2) = (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1) := by simp only [mondrian_rect_cells, Finset.sum_product, Finset.sum_Ico_sub f hy, Finset.sum_const, Nat.card_Ico, nsmul_eq_mul, mondrian_rect_width]