AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_floor_moment

theoremverified

For every natural q, the sum of width times the difference of the quotient y coordinates across each tile in an admissible n-square partition is n times floor(n/q), with integer-valued differences.

Statement

theorem mondrian_partition_floor_moment (n q : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition n P) :
    (P.map (fun r => (mondrian_rect_width r : ℤ) *
      (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))).sum =
      (n : ℤ) * (n / q : ℕ)
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 3
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • 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_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
Used by 3

The proof, explained

The theorem is proved by specializing the general horizontal moment identity, `mondrian_partition_horizontal_moment`, to the floor division function $f(y) = \lfloor y / q \rfloor$. The general formula evaluates the partition's weighted sum to $n \cdot (f(n) - f(0))$. Because $f(0) = \lfloor 0 / q \rfloor = 0$, the boundary term at zero vanishes, directly yielding $n \cdot \lfloor n / q \rfloor$.

  1. The sum over all rectangles in the partition of $\operatorname{width}(r) \cdot (\lfloor y_2/q \rfloor - \lfloor y_1/q \rfloor)$ equals $n \lfloor n/q \rfloor$.

    We instantiate the general horizontal moment identity, `mondrian_partition_horizontal_moment`, with the test function $f(y) = \lfloor y / q \rfloor$ (cast to $\mathbb{Z}$). The theorem asserts that the weighted sum of vertical differences equals $n \cdot (f(n) - f(0))$. Since $f(0) = \lfloor 0 / q \rfloor = 0$, the right-hand side simplifies to $n \cdot \lfloor n / q \rfloor$, which `simpa` evaluates to complete the proof.

    lines 8–9

    uses mondrian_partition_horizontal_moment

      have hh := mondrian_partition_horizontal_moment n P hp (fun y => ((y / q : ℕ) : ℤ))
      simpa using hh
mondrian_partition_horizontal_moment
For any partition $P$ of an $n \times n$ square and any function $f : \mathbb{N} \to \mathbb{Z}$, the sum over all rectangles $r \in P$ of $\operatorname{width}(r) \cdot (f(y_2) - f(y_1))$ equals $n \cdot (f(n) - f(0))$, where $y_1$ and $y_2$ are the lower and upper vertical coordinates of $r$.

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_floor_moment (n q : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition n P) :    (P.map (fun r => (mondrian_rect_width r : ℤ) *      (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))).sum =      (n : ℤ) * (n / q : ℕ) := by  have hh := mondrian_partition_horizontal_moment n P hp (fun y => ((y / q : ℕ) : ℤ))  simpa using hh
See it in the graphDiscuss this resultChallenge it