AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_horizontal_moment

theoremverified

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

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

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

    lines 7–8

    uses mondrian_cells_union_sum

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

    lines 9–15

    uses List.map_congr_left, Nat.le_of_lt, mondrian_rect_horizontal_moment

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

    lines 16–17

      rw [hm, hp.2.2.2] at hu
      rw [← hu]
  4. 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).

    line 18

    uses Finset.sum_product

      simp only [Finset.sum_product]
  5. 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).

    lines 19–20

    uses Finset.sum_range_sub

      have hsum : ∑ y ∈ Finset.range n, (f (y + 1) - f y) = f n - f 0 :=
        Finset.sum_range_sub f n
  6. Summing 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.

    line 21

    uses Finset.sum_const, Finset.card_range, nsmul_eq_mul

      simp 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

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