mondrian_partition_horizontal_moment
For every integer-valued function f on row levels, the sum over an admissible n-square partition of width times the increment of f across each tile is n times (f(n)-f(0)).
Statement
theorem mondrian_partition_horizontal_moment (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition n P) (f : ℕ → ℤ) : (P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1))).sum = (n : ℤ) * (f n - f 0)
- 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 6
- mondrian_cells_union_sumSumming any integer-valued cell weight over a union of pairwise disjoint rectangle cell sets equals the sum of its sums over the rectangles.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- 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_horizontal_momentThe 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…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- Used by 7
- mondrian_perfect_min_width_layer_countFor a perfect admissible n-square partition and prime p dividing n, suppose b is the minimum p-adic exponent of tile widths. Then b is at…
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- mondrian_partition_floor_momentFor every natural q, the sum of width times the difference of the quotient y coordinates across each tile in an admissible n-square…
- mondrian_partition_isolated_row_functionLet d divide the square side. If an integer row-level function has increment one on a selected tile and has zero increment on every other…
- mondrian_partition_isolated_height_residueLet d divide the square side. If every tile except r either has width divisible by d or height divisible by m, and r has height…
- mondrian_partition_row_width_sumAt every integer row y below n in an admissible n-square partition, the widths of the tiles crossing that row sum to n.
- mondrian_common_width_divides_sideEvery common divisor of the tile widths in an admissible n-square partition divides n.
The proof, explained
The proof reinterprets the sum over partition tiles as a double sum over the entire n × n grid. Each term width(r) · (f(y₂) - f(y₁)) is first shown to equal the sum of cell increments f(y + 1) - f(y) over the cells of rectangle r. Because the tiles partition the square [0, n) × [0, n), summing over all tiles is equivalent to summing f(y + 1) - f(y) over every cell (x, y) in the grid. The sum over y telescopes along each column to f(n) - f(0), and summing this constant over all n columns gives n · (f(n) - f(0)).
The sum of the cell increments f(y + 1) - f(y) over the union of all tiles in P equals the sum over tiles of the sum of increments within each tile.
Because the rectangles in partition P are pairwise disjoint (from hypothesis hp.2.2.1), mondrian_cells_union_sum decomposes the sum of f(c.2 + 1) - f(c.2) over the union of all cells into the sum of the individual rectangle cell sums.
uses
mondrian_cells_union_sumhave hu := mondrian_cells_union_sum P (hp.2.2.1.imp fun h => h.1) (fun c => f (c.2 + 1) - f c.2)
For each tile r in P, the cell sum equals width(r) · (f(y₂) - f(y₁)), so mapping this cell sum over P is equal to mapping width(r) · (f(y₂) - f(y₁)).
Using List.map_congr_left, it suffices to prove the equality tile by tile. For any r ∈ P, the partition conditions ensure y₁ < y₂, so y₁ ≤ y₂ by Nat.le_of_lt. Lemma mondrian_rect_horizontal_moment then evaluates the sum of f(y + 1) - f(y) over the cells of r to width(r) · (f(y₂) - f(y₁)).
uses
List.map_congr_left,Nat.le_of_lt,mondrian_rect_horizontal_momenthave hm : P.map (fun r => ∑ c ∈ mondrian_rect_cells r, (f (c.2 + 1) - f c.2)) = P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)) := by apply List.map_congr_left intro r hr exact mondrian_rect_horizontal_moment r (Nat.le_of_lt (hp.2.1 r hr).2) f
The partition sum is re-expressed as the sum of cell increments f(y + 1) - f(y) over the entire n × n grid [0, n) × [0, n).
Rewriting the partition cell sum identity hu using the list equality hm and the fact that the union of all tile cells is the full square [0, n) × [0, n) (hp.2.2.2), we substitute hu backwards to turn the goal into a sum of f(c.2 + 1) - f(c.2) over all c ∈ [0, n) × [0, n).
rw [hm, hp.2.2.2] at hu rw [← hu]
The grid sum splits into an iterated sum over x and y from 0 to n - 1.
By Finset.sum_product, the summation over the product set [0, n) × [0, n) splits into an outer sum over x ∈ [0, n) and an inner sum over y ∈ [0, n).
uses
Finset.sum_productsimp only [Finset.sum_product]The inner sum over y telescopes to f(n) - f(0).
By Finset.sum_range_sub, the sum of differences f(y + 1) - f(y) for y from 0 to n - 1 telescopes directly to f(n) - f(0).
uses
Finset.sum_range_subhave hsum : ∑ y ∈ Finset.range n, (f (y + 1) - f y) = f n - f 0 := Finset.sum_range_sub f nSumming the constant f(n) - f(0) over the n values of x yields n · (f(n) - f(0)).
Substituting the telescoped inner sum leaves a constant f(n) - f(0) for each of the n values of x in [0, n). Simplifying using Finset.sum_const, Finset.card_range, and nsmul_eq_mul completes the proof.
uses
Finset.sum_const,Finset.card_range,nsmul_eq_mulsimp only [hsum, Finset.sum_const, Finset.card_range, nsmul_eq_mul]
mondrian_cells_union_sum- the sum of a function over the union of pairwise disjoint cell sets of rectangles equals the sum of the sums over the individual rectangles
List.map_congr_left- two lists obtained by mapping functions f and g over a list l are equal if f and g agree on every element of l
Nat.le_of_lt- a strictly smaller natural number is also less than or equal
mondrian_rect_horizontal_moment- for a rectangle [x₁, x₂) × [y₁, y₂] with y₁ ≤ y₂, summing f(y + 1) - f(y) over its cells yields width × (f(y₂) - f(y₁))
Finset.sum_product- a sum over a Cartesian product of two finite sets equals the iterated double sum over each set
Finset.sum_range_sub- the sum of consecutive differences f(i + 1) - f(i) from i = 0 to n - 1 telescopes to f(n) - f(0)
Finset.sum_const- summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by that constant
Finset.card_range- the number of elements in the range of natural numbers from 0 to n - 1 is n
nsmul_eq_mul- scalar multiplication of a ring element by a natural number equals ordinary multiplication by that natural number
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_partition_horizontal_moment (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition n P) (f : ℕ → ℤ) : (P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1))).sum = (n : ℤ) * (f n - f 0) := by have hu := mondrian_cells_union_sum P (hp.2.2.1.imp fun h => h.1) (fun c => f (c.2 + 1) - f c.2) have hm : P.map (fun r => ∑ c ∈ mondrian_rect_cells r, (f (c.2 + 1) - f c.2)) = P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)) := by apply List.map_congr_left intro r hr exact mondrian_rect_horizontal_moment r (Nat.le_of_lt (hp.2.1 r hr).2) f rw [hm, hp.2.2.2] at hu rw [← hu] simp only [Finset.sum_product] have hsum : ∑ y ∈ Finset.range n, (f (y + 1) - f y) = f n - f 0 := Finset.sum_range_sub f n simp only [hsum, Finset.sum_const, Finset.card_range, nsmul_eq_mul]