mondrian_partition_row_width_sum
At every integer row y below n in an admissible n-square partition, the widths of the tiles crossing that row sum to n.
Statement
theorem mondrian_partition_row_width_sum (n y : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hy : y < n) : ((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map mondrian_rect_width).sum = n
- Source
- Helper for OP-280. Cross-section identity underlying HAL:hal-05729522v2, Lemma 2.3; also follows from the horizontal moment.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
The proof, explained
The proof specializes the general horizontal moment identity ∑_{r ∈ P} width(r) · (f(r.y₂) - f(r.y₁)) = n(f(n) - f(0)) to the step function f(t) = 1 if t > y else 0. For this choice of f, the difference f(r.y₂) - f(r.y₁) equals 1 precisely when tile r crosses row y (r.y₁ ≤ y < r.y₂) and 0 otherwise, while the boundary term simplifies to n(1 - 0) = n because 0 ≤ y < n. Equating the two expressions and casting from ℤ back to ℕ shows that the widths of all tiles crossing row y sum to n.
Summing a conditionally zeroed integer function over a list equals summing the function over the sublist satisfying the condition (`mondrian_partition_row_width_sum_sum_map_ite`). automation
We prove this auxiliary lemma by structural induction on the list l. In the base case where l is nil, both sides reduce to 0. In the inductive step for a :: t, we case-split on whether p(a) holds. In both branches, unfolding the list definitions and applying the induction hypothesis simplifies both sides to identical sums.
induction l with | nil => simp | cons a t ih => by_cases h : p a · simp [h, ih] · simp [h, ih]
The sum of integer-cast rectangle widths over a list equals the cast to ℤ of their natural sum (`mondrian_partition_row_width_sum_cast_sum`).
The pointwise integer cast of rectangle widths is rewritten as the composition of the cast from ℕ to ℤ with `mondrian_rect_width`. Rewriting with `List.map_map` decomposes this into two consecutive mappings, and `Nat.cast_list_sum` then pulls the integer cast outside the summation.
uses
List.map_map,Nat.cast_list_sumchange ((List.map (Nat.cast ∘ mondrian_rect_width) l).sum) = _ rw [← List.map_map, ← Nat.cast_list_sum]
Apply the horizontal moment identity to the indicator test function f(t) = 1 for t > y (and 0 otherwise).
We define f : ℕ → ℤ to be 1 when y < t and 0 otherwise. Applying the general partition identity `mondrian_partition_horizontal_moment` to f equates the sum over all rectangles r ∈ P of width(r) * (f(r.y₂) - f(r.y₁)) to n * (f(n) - f(0)).
uses
mondrian_partition_horizontal_momentlet f : ℕ → ℤ := fun t => if y < t then 1 else 0 have hm := mondrian_partition_horizontal_moment n P hP f
For every tile r in the partition, width(r) * (f(r.y₂) - f(r.y₁)) equals width(r) if the tile crosses row y (r.y₁ ≤ y < r.y₂), and 0 otherwise. automation
For any rectangle r ∈ P, the partition validity hypothesis ensures r.y₁ < r.y₂. Unfolding f, we perform a case split on whether y < r.y₂: if y < r.y₂, we further split on whether y < r.y₁. If y < r.y₁, then f(r.y₂) - f(r.y₁) = 1 - 1 = 0. If ¬(y < r.y₁), then r.y₁ ≤ y < r.y₂ holds, giving f(r.y₂) - f(r.y₁) = 1 - 0 = 1, which yields width(r). In the outer negative case ¬(y < r.y₂), since r.y₁ < r.y₂ linear arithmetic gives ¬(y < r.y₁), so f(r.y₂) - f(r.y₁) = 0 - 0 = 0.
have hstep : ∀ r ∈ P, (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1) = (if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0) := by intro r hr have hbt := (hP.2.1 r hr).2 simp only [f] by_cases htop : y < r.2.2.2 · by_cases hbot : y < r.2.2.1 · simp [htop, hbot] · have hc : (r.2.2.1 ≤ y ∧ y < r.2.2.2) := ⟨by omega, htop⟩ simp [htop, hbot, hc] · have hbot : ¬ y < r.2.2.1 := by omega simp [htop, hbot]
The left-hand side of the moment sum equals the integer cast of the sum of widths of tiles crossing row y.
We apply `List.map_congr_left` with the pointwise equality from the previous step to replace the summand with the conditional expression (`hmap`). Using the auxiliary lemma `mondrian_partition_row_width_sum_sum_map_ite`, this conditional sum is rewritten as the sum of integer widths over the filtered list of tiles satisfying r.y₁ ≤ y < r.y₂ (`hfilter`). Finally, `mondrian_partition_row_width_sum_cast_sum` relates this to the integer cast of the natural sum of widths (`hnat`).
uses
List.map_congr_left,mondrian_partition_row_width_sum_sum_map_ite,mondrian_partition_row_width_sum_cast_sumhave hmap : P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)) = P.map (fun r => if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0) := List.map_congr_left hstep have hfilter : (P.map (fun r => if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0)).sum = ((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map (fun r => (mondrian_rect_width r : ℤ))).sum := mondrian_partition_row_width_sum_sum_map_ite P _ _ have hnat := mondrian_partition_row_width_sum_cast_sum (P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2)))
The boundary factor f(n) - f(0) evaluates to 1.
Unfolding f, because y < n by hypothesis, `if_pos` gives f(n) = 1. Since y is a natural number, y < 0 is impossible, so `if_neg` gives f(0) = 0. Numerical evaluation then simplifies 1 - 0 to 1.
uses
if_pos,if_neghave hfn : f n - f 0 = 1 := by simp only [f] rw [if_pos hy] have h0 : ¬ (y < 0) := by omega rw [if_neg h0] norm_num
The sum of widths of tiles crossing row y equals n.
Substituting the equivalences `hnat`, `hfilter`, and `hmap` into the horizontal moment identity, together with the boundary value f(n) - f(0) = 1 and `mul_one`, establishes that the sum of widths of tiles crossing row y, cast to ℤ, equals n : ℤ (`h2`). The tactic `exact_mod_cast` then casts this equality back to ℕ, completing the proof.
uses
mul_onehave h2 : ((((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map mondrian_rect_width).sum : ℕ) : ℤ) = (n : ℤ) := by rw [← hnat, ← hfilter, ← hmap, hm, hfn, mul_one] exact_mod_cast h2
List.map_map- Mapping a function f over a list and then mapping g over the result is equal to mapping the composite g ∘ f over the original list.
Nat.cast_list_sum- The sum of a list of natural numbers, cast to an additive structure with one (such as ℤ), equals the sum of the individually cast elements.
mondrian_partition_horizontal_moment- For any partition P of an n × n square into rectangles and any function f : ℕ → ℤ, the sum of width(r) * (f(r.y₂) - f(r.y₁)) over all tiles r ∈ P equals n * (f(n) - f(0)).
List.map_congr_left- If two functions f and g agree on all elements of a list l, then mapping f over l equals mapping g over l.
mondrian_partition_row_width_sum_sum_map_ite- Summing a conditional expression that takes value g(x) when p(x) holds and 0 otherwise over a list l equals summing g(x) over the sublist filtered by p.
mondrian_partition_row_width_sum_cast_sum- The sum of integer-cast rectangle widths over a list equals the cast to ℤ of the sum of their natural widths.
if_pos- An if-then-else expression `if c then t else e` evaluates to t when the condition c holds.
if_neg- An if-then-else expression `if c then t else e` evaluates to e when the condition c does not hold.
mul_one- Multiplying any element by 1 on the right leaves it unchanged.
- The general identity `mondrian_partition_horizontal_moment` is formulated over ℤ rather than ℕ to permit signed differences `f(y₂) - f(y₁)`. As a result, the proof requires explicit type casting between ℕ and ℤ (handled by `mondrian_partition_row_width_sum_cast_sum` and `exact_mod_cast`).
- The step analysis for each tile relies on the linear arithmetic decision procedure `omega` to handle trichotomy cases on the integer row coordinates.
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.
/-- A sum of `if p then g else 0` over a list equals the sum of `g` over the filtered list. -/private lemma mondrian_partition_row_width_sum_sum_map_ite {α : Type} (l : List α) (p : α → Prop) [DecidablePred p] (g : α → ℤ) : (l.map (fun r => if p r then g r else 0)).sum = ((l.filter (fun r => decide (p r))).map g).sum := by induction l with | nil => simp | cons a t ih => by_cases h : p a · simp [h, ih] · simp [h, ih]/-- Casting a list sum of widths to integers equals the list sum of the cast widths. -/private lemma mondrian_partition_row_width_sum_cast_sum (l : List (ℕ × ℕ × ℕ × ℕ)) : ((l.map (fun r => (mondrian_rect_width r : ℤ))).sum) = (((l.map mondrian_rect_width).sum : ℕ) : ℤ) := by change ((List.map (Nat.cast ∘ mondrian_rect_width) l).sum) = _ rw [← List.map_map, ← Nat.cast_list_sum]theorem mondrian_partition_row_width_sum (n y : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hy : y < n) : ((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map mondrian_rect_width).sum = n := by let f : ℕ → ℤ := fun t => if y < t then 1 else 0 have hm := mondrian_partition_horizontal_moment n P hP f have hstep : ∀ r ∈ P, (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1) = (if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0) := by intro r hr have hbt := (hP.2.1 r hr).2 simp only [f] by_cases htop : y < r.2.2.2 · by_cases hbot : y < r.2.2.1 · simp [htop, hbot] · have hc : (r.2.2.1 ≤ y ∧ y < r.2.2.2) := ⟨by omega, htop⟩ simp [htop, hbot, hc] · have hbot : ¬ y < r.2.2.1 := by omega simp [htop, hbot] have hmap : P.map (fun r => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)) = P.map (fun r => if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0) := List.map_congr_left hstep have hfilter : (P.map (fun r => if (r.2.2.1 ≤ y ∧ y < r.2.2.2) then (mondrian_rect_width r : ℤ) else 0)).sum = ((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map (fun r => (mondrian_rect_width r : ℤ))).sum := mondrian_partition_row_width_sum_sum_map_ite P _ _ have hnat := mondrian_partition_row_width_sum_cast_sum (P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))) have hfn : f n - f 0 = 1 := by simp only [f] rw [if_pos hy] have h0 : ¬ (y < 0) := by omega rw [if_neg h0] norm_num have h2 : ((((P.filter (fun r => decide (r.2.2.1 ≤ y ∧ y < r.2.2.2))).map mondrian_rect_width).sum : ℕ) : ℤ) = (n : ℤ) := by rw [← hnat, ← hfilter, ← hmap, hm, hfn, mul_one] exact_mod_cast h2