mondrian_rect_floor_contribution
When positive q divides a rectangle height, its width times the integer difference of quotient y coordinates is its area divided by q.
Statement
theorem mondrian_rect_floor_contribution (r : ℕ × ℕ × ℕ × ℕ)
(hy : r.2.2.1 ≤ r.2.2.2) (q : ℕ) (hq : 0 < q)
(hd : q ∣ mondrian_rect_height r) :
(mondrian_rect_width r : ℤ) *
(((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) =
((mondrian_rect_area r / 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
Quot.soundpropext- Built on 3
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- Used by 3
- mondrian_partition_normalized_prime_free_width_modIn an admissible n-square partition with every width divisible by positive d and with constant normalized area C, the number of normalized…
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- mondrian_partition_prime_free_width_countFor an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of…
The proof, explained
Because $q$ divides the rectangle height $y_2 - y_1$, the height can be factored as $q \cdot d$ for some natural number $d$, so that $y_2 = y_1 + q \cdot d$. This factorization allows the area divided by $q$ to simplify directly to $\operatorname{width}(r) \cdot d$. Similarly, natural number division distributes over the sum as $\lfloor y_2 / q \rfloor = \lfloor y_1 / q \rfloor + d$, reducing the difference of quotients to simply $d$. Multiplying by the width immediately matches the area quotient.
There is a natural number $d$ such that $\operatorname{mondrian\_rect\_height}(r) = q \cdot d$.
Unpacking the divisibility hypothesis $q \mid \operatorname{mondrian\_rect\_height}(r)$ yields a quotient $d$ satisfying $\operatorname{mondrian\_rect\_height}(r) = q \cdot d$.
obtain ⟨d, hd⟩ := hdThe upper $y$-coordinate satisfies $r.2.2.2 = r.2.2.1 + q \cdot d$.
Unfolding the definition of height as $r.2.2.2 - r.2.2.1$, the relation $r.2.2.2 - r.2.2.1 = q \cdot d$ together with $r.2.2.1 \le r.2.2.2$ implies $r.2.2.2 = r.2.2.1 + q \cdot d$ by linear natural arithmetic (`omega`).
have hy1 : r.2.2.2 = r.2.2.1 + q * d := by dsimp [mondrian_rect_height] at hd omega
The quotient $\operatorname{mondrian\_rect\_area}(r) / q$ equals $\operatorname{mondrian\_rect\_width}(r) \cdot d$.
Unfolding the definition of area as width times height and substituting $\operatorname{height} = q \cdot d$, the product rearranges to $(\operatorname{width} \cdot d) \cdot q$. Since $q > 0$, dividing by $q$ cancels the factor of $q$ using `Nat.mul_div_cancel`.
uses
Nat.mul_div_cancelhave hdiv : mondrian_rect_area r / q = mondrian_rect_width r * d := by rw [mondrian_rect_area, hd, show mondrian_rect_width r * (q * d) = (mondrian_rect_width r * d) * q by ring, Nat.mul_div_cancel _ hq]
The equality holds in the integers.
Substitute $\operatorname{mondrian\_rect\_area}(r) / q = \operatorname{width} \cdot d$ and replace $r.2.2.2$ with $r.2.2.1 + q \cdot d$. By `Nat.add_mul_div_left`, $(r.2.2.1 + q \cdot d) / q$ simplifies to $r.2.2.1 / q + d$. Pushing integer casts across the operations reduces the equality to $\operatorname{width} \cdot ((y_1 / q + d) - y_1 / q) = \operatorname{width} \cdot d$, which holds by basic ring algebra.
uses
Nat.add_mul_div_leftrw [hdiv, hy1, Nat.add_mul_div_left _ _ hq] push_cast ring
Nat.mul_div_cancel- For natural numbers $m$ and $n$ with $n > 0$, $(m \cdot n) / n = m$.
Nat.add_mul_div_left- For natural numbers $x, y, z$ with $y > 0$, $(x + y \cdot z) / y = x / y + z$.
- The rectangle $r$ is represented as a nested 4-tuple $(x_1, x_2, y_1, y_2)$, where $r.2.2.1$ is $y_1$ and $r.2.2.2$ is $y_2$.
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.
open scoped BigOperatorstheorem mondrian_rect_floor_contribution (r : ℕ × ℕ × ℕ × ℕ) (hy : r.2.2.1 ≤ r.2.2.2) (q : ℕ) (hq : 0 < q) (hd : q ∣ mondrian_rect_height r) : (mondrian_rect_width r : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) = ((mondrian_rect_area r / q : ℕ) : ℤ) := by obtain ⟨d, hd⟩ := hd have hy1 : r.2.2.2 = r.2.2.1 + q * d := by dsimp [mondrian_rect_height] at hd omega have hdiv : mondrian_rect_area r / q = mondrian_rect_width r * d := by rw [mondrian_rect_area, hd, show mondrian_rect_width r * (q * d) = (mondrian_rect_width r * d) * q by ring, Nat.mul_div_cancel _ hq] rw [hdiv, hy1, Nat.add_mul_div_left _ _ hq] push_cast ring