mondrian_partition_floor_moment_div_width
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
- mondrian_perfect_min_width_layer_countFor a perfect admissible n-square partition and prime p dividing n, suppose b is the minimum p-adic exponent of tile widths. Then b is at…
- 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…
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.
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.
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 : ℕ) : ℤ))
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).
uses
List.map_congr_left,Nat.mul_div_cancel',mul_assochave 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]
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.
uses
Nat.mul_div_cancel',mondrian_common_width_divides_sidehave hn : (d : ℤ) * ((n / d : ℕ) : ℤ) = (n : ℤ) := by exact_mod_cast Nat.mul_div_cancel' (mondrian_common_width_divides_side n d P hP hd)
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.
uses
mul_left_cancel₀,Nat.ne_of_gtchange (P.map F).sum = _ apply mul_left_cancel₀ (by exact_mod_cast (Nat.ne_of_gt hdpos) : (d : ℤ) ≠ 0)
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.
uses
List.sum_map_mul_left,mondrian_partition_floor_momentcalc (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
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_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