AFTD Auto-Formalizing Theoretical Domains

mondrian_rect_horizontal_moment

theoremverified

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

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.

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

    lines 7–9

    uses mondrian_rect_cells, Finset.sum_product, Finset.sum_Ico_sub, Finset.sum_const, Nat.card_Ico, nsmul_eq_mul, mondrian_rect_width

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

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