AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_floor_moment_div_width

theoremverified

If positive d divides every tile width in an admissible n-square partition, dividing all widths in the quotient-row moment by d gives (n/d) times floor(n/q).

Statement

theorem mondrian_partition_floor_moment_div_width (n q d : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hdpos : 0 < d)
    (hP : mondrian_is_partition n P)
    (hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) :
    (P.map (fun r => ((mondrian_rect_width r / d : ℕ) : ℤ) *
      (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))).sum =
      ((n / d : ℕ) : ℤ) * ((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 4
  • mondrian_common_width_divides_sideEvery common divisor of the tile widths in an admissible n-square partition divides n.
  • 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_floor_momentFor every natural q, the sum of width times the difference of the quotient y coordinates across each tile in an admissible n-square…
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
Used by 2

The proof, explained

The theorem is proved by scaling the entire sum by d and showing that the result matches d * (n / d) * floor(n / q), from which the factor d > 0 is cancelled. Multiplying each term by d restores the original rectangle width, transforming the expression into the known unscaled floor-moment sum, which evaluates to n * floor(n / q). Since d divides all rectangle widths, it divides the square's side length n, allowing n to be rewritten as d * (n / d) to complete the identity.

  1. Define shorthand functions F(r) and G(r) for the scaled and unscaled floor-moment terms of each rectangle r.

    We introduce F(r) = (width(r)/d) * (floor(r.y₂/q) - floor(r.y₁/q)) for the term appearing in the theorem's sum, and G(r) = width(r) * (floor(r.y₂/q) - floor(r.y₁/q)) for the corresponding unscaled term.

    lines 10–13

      let F := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) *
        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))
      let G := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) *
        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))
  2. Mapping r ↦ d * F(r) over the rectangle list P produces the same list as mapping G over P.

    By List.map_congr_left, it suffices to show d * F(r) = G(r) for each rectangle r ∈ P. Since d divides width(r) by assumption, Nat.mul_div_cancel' gives d * (width(r)/d) = width(r). Reassociating the multiplication (mul_assoc) shows that scaling F(r) by d recovers G(r).

    lines 14–24

    uses List.map_congr_left, Nat.mul_div_cancel', mul_assoc

      have hmap : P.map (fun r => (d : ℤ) * F r) = P.map G := by
        apply List.map_congr_left
        intro r hr
        have hw : (d : ℤ) * ((mondrian_rect_width r / d : ℕ) : ℤ) =
            (mondrian_rect_width r : ℤ) := by
          exact_mod_cast Nat.mul_div_cancel' (hd r hr)
        change (d : ℤ) * (((mondrian_rect_width r / d : ℕ) : ℤ) *
          (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))) =
          (mondrian_rect_width r : ℤ) *
            (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))
        rw [← mul_assoc, hw]
  3. d * (n / d) = n as integers.

    Because P is an admissible partition of the n-square and d divides the width of every rectangle, d divides the total side length n by mondrian_common_width_divides_side. Then Nat.mul_div_cancel' establishes d * (n / d) = n.

    lines 25–26

    uses Nat.mul_div_cancel', mondrian_common_width_divides_side

      have hn : (d : ℤ) * ((n / d : ℕ) : ℤ) = (n : ℤ) := by
        exact_mod_cast Nat.mul_div_cancel' (mondrian_common_width_divides_side n d P hP hd)
  4. To establish the equality of the sums, it suffices to prove d * sum_{r ∈ P} F(r) = d * ((n / d) * floor(n / q)).

    Since d > 0, d is nonzero as an integer (Nat.ne_of_gt). By left-cancellation of nonzero factors (mul_left_cancel₀), the original goal is equivalent to the equation obtained after multiplying both sides by d.

    lines 27–28

    uses mul_left_cancel₀, Nat.ne_of_gt

      change (P.map F).sum = _
      apply mul_left_cancel₀ (by exact_mod_cast (Nat.ne_of_gt hdpos) : (d : ℤ) ≠ 0)
  5. d * sum_{r ∈ P} F(r) = d * ((n / d) * floor(n / q)), completing the proof.

    Factoring d into the sum (List.sum_map_mul_left) and using the termwise equality gives d * sum_{r ∈ P} F(r) = sum_{r ∈ P} G(r). By mondrian_partition_floor_moment, this unscaled sum equals n * floor(n / q). Substituting n = d * (n / d) and regrouping factors yields the desired expression.

    lines 29–35

    uses List.sum_map_mul_left, mondrian_partition_floor_moment

      calc
        (d : ℤ) * (P.map F).sum = (P.map G).sum := by
          rw [← List.sum_map_mul_left, hmap]
        _ = (n : ℤ) * ((n / q : ℕ) : ℤ) := mondrian_partition_floor_moment n q P hP
        _ = (d : ℤ) * (((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ)) := by
          rw [← hn]
          ring
List.map_congr_left
If two functions produce equal values on all elements of a list, mapping either function over the list yields the same resulting list.
Nat.mul_div_cancel'
If a natural number n divides m, then n * (m / n) = m.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mondrian_common_width_divides_side
If a positive integer d divides the width of every rectangle in an admissible partition of an n-square, then d divides n.
mul_left_cancel₀
In a structure where nonzero multiplication cancels, a ≠ 0 and a * b = a * c imply b = c.
Nat.ne_of_gt
If b < a for natural numbers, then a ≠ b.
List.sum_map_mul_left
Multiplying the sum of a mapped list by a scalar from the left equals summing the list after scaling each mapped element by that scalar.
mondrian_partition_floor_moment
For an admissible partition of an n-square, the sum over all rectangles of width(r) * (floor(y₂/q) - floor(y₁/q)) equals n * floor(n/q).

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_div_width (n q d : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hdpos : 0 < d)    (hP : mondrian_is_partition n P)    (hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) :    (P.map (fun r => ((mondrian_rect_width r / d : ℕ) : ℤ) *      (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))).sum =      ((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ) := by  let F := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) *    (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))  let G := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) *    (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))  have hmap : P.map (fun r => (d : ℤ) * F r) = P.map G := by    apply List.map_congr_left    intro r hr    have hw : (d : ℤ) * ((mondrian_rect_width r / d : ℕ) : ℤ) =        (mondrian_rect_width r : ℤ) := by      exact_mod_cast Nat.mul_div_cancel' (hd r hr)    change (d : ℤ) * (((mondrian_rect_width r / d : ℕ) : ℤ) *      (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))) =      (mondrian_rect_width r : ℤ) *        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))    rw [← mul_assoc, hw]  have hn : (d : ℤ) * ((n / d : ℕ) : ℤ) = (n : ℤ) := by    exact_mod_cast Nat.mul_div_cancel' (mondrian_common_width_divides_side n d P hP hd)  change (P.map F).sum = _  apply mul_left_cancel₀ (by exact_mod_cast (Nat.ne_of_gt hdpos) : (d : ℤ) ≠ 0)  calc    (d : ℤ) * (P.map F).sum = (P.map G).sum := by      rw [← List.sum_map_mul_left, hmap]    _ = (n : ℤ) * ((n / q : ℕ) : ℤ) := mondrian_partition_floor_moment n q P hP    _ = (d : ℤ) * (((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ)) := by      rw [← hn]      ring
See it in the graphDiscuss this resultChallenge it