AFTD Auto-Formalizing Theoretical Domains

mondrian_rect_floor_contribution

theoremverified

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
Used by 3

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.

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

    line 9

      obtain ⟨d, hd⟩ := hd
  2. The 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`).

    lines 10–12

      have hy1 : r.2.2.2 = r.2.2.1 + q * d := by
        dsimp [mondrian_rect_height] at hd
        omega
  3. 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`.

    lines 13–16

    uses Nat.mul_div_cancel

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

    lines 17–19

    uses Nat.add_mul_div_left

      rw [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$.

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