AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_row_width_sum

theoremverified

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.

  1. 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.

    lines 5–10

      induction l with
      | nil => simp
      | cons a t ih =>
        by_cases h : p a
        · simp [h, ih]
        · simp [h, ih]
  2. 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.

    lines 16–17

    uses List.map_map, Nat.cast_list_sum

      change ((List.map (Nat.cast ∘ mondrian_rect_width) l).sum) = _
      rw [← List.map_map, ← Nat.cast_list_sum]
  3. 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)).

    lines 22–23

    uses mondrian_partition_horizontal_moment

      let f : ℕ → ℤ := fun t => if y < t then 1 else 0
      have hm := mondrian_partition_horizontal_moment n P hP f
  4. 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.

    lines 24–35

      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]
  5. 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`).

    lines 36–43

    uses List.map_congr_left, mondrian_partition_row_width_sum_sum_map_ite, mondrian_partition_row_width_sum_cast_sum

      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)))
  6. 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.

    lines 44–49

    uses if_pos, if_neg

      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
  7. 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.

    lines 50–52

    uses mul_one

      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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it