mondrian_common_width_divides_side
Every common divisor of the tile widths in an admissible n-square partition divides n.
Statement
theorem mondrian_common_width_divides_side (n d : ℕ)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
(hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) : d ∣ n- 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_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_list_sum_count_modIf each integer list contribution is congruent modulo p to u when its predicate holds and to zero otherwise, their sum is congruent to u…
- 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 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_floor_moment_div_widthIf positive d divides every tile width in an admissible n-square partition, dividing all widths in the quotient-row moment by d gives…
The proof, explained
The theorem is trivial when $n = 0$ because every number divides $0$. When $n > 0$, the proof evaluates the partition against a step function $f$ that is $0$ at the origin and $1$ elsewhere. A horizontal moment identity shows that the weighted sum $\sum_{r \in P} \mathrm{width}(r)(f(y_2) - f(y_1))$ equals $n(f(n) - f(0)) = n$. Since $d$ divides the width of every tile, it divides each term of this sum, and therefore $d$ divides $n$.
The claim holds directly if $n = 0$.
If $n = 0$, the goal becomes $d \mid 0$, which holds trivially because every natural number divides $0$.
by_cases hn : n = 0 · simp [hn]
Define a step function $f$ and an associated rectangle functional $g$.
Assuming $n \neq 0$, let $f : \mathbb{N} \to \mathbb{Z}$ be defined by $f(0) = 0$ and $f(y) = 1$ for all $y > 0$. For each rectangle $r$ with width $w(r)$ and vertical coordinate interval $[y_1, y_2]$, define $g(r) = w(r) \cdot (f(y_2) - f(y_1))$.
let f : ℕ → ℤ := fun y => if y = 0 then 0 else 1 let g := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)
In the integers, $d$ divides the sum $\sum_{r \in P} g(r)$.
By assumption, $d$ divides the width of each rectangle $r \in P$, so by `dvd_mul_of_dvd_left`, $d$ divides $g(r) = w(r) \cdot (f(y_2) - f(y_1))$. Applying `mondrian_list_sum_count_mod` with offset $u = 0$ and a trivial predicate that is always false, $d$ divides the sum $\sum_{r \in P} g(r)$.
uses
mondrian_list_sum_count_mod,dvd_mul_of_dvd_lefthave hdiv : (d : ℤ) ∣ (P.map g).sum := by have hs := mondrian_list_sum_count_mod P (d : ℤ) 0 g (fun _ => false) (by intro r hr have hw : (d : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hd r hr simpa [g] using dvd_mul_of_dvd_left hw (f r.2.2.2 - f r.2.2.1)) simpa using hs
The sum $\sum_{r \in P} g(r)$ evaluates to $n$.
The identity `mondrian_partition_horizontal_moment` states that $\sum_{r \in P} w(r)(f(y_2) - f(y_1)) = n(f(n) - f(0))$. Since $n \neq 0$, $f(n) = 1$ and $f(0) = 0$, so $n(f(n) - f(0)) = n \cdot 1 = n$.
uses
mondrian_partition_horizontal_momenthave he : (P.map g).sum = (n : ℤ) := by simpa [g, f, hn] using mondrian_partition_horizontal_moment n P hP f
$d$ divides $n$ as a natural number.
Rewriting the sum as $n$ in the divisibility hypothesis gives $d \mid n$ in $\mathbb{Z}$. Casting this divisibility back from $\mathbb{Z}$ to $\mathbb{N}$ concludes that $d \mid n$.
rw [he] at hdiv exact_mod_cast hdiv
mondrian_list_sum_count_mod- if an integer $p$ divides $f(r) - (\text{if } \mathrm{pred}(r) \text{ then } u \text{ else } 0)$ for every element $r$ of a list $L$, then $p$ divides $\sum_{r \in L} f(r) - u \cdot (\text{count of elements satisfying } \mathrm{pred})$
dvd_mul_of_dvd_left- if $a$ divides $b$, then $a$ divides $b \cdot c$ for any $c$
mondrian_partition_horizontal_moment- for any admissible partition $P$ of an $n \times n$ square and any function $f : \mathbb{N} \to \mathbb{Z}$, the sum over rectangles $r \in P$ of $\mathrm{width}(r) \cdot (f(y_2) - f(y_1))$ equals $n \cdot (f(n) - f(0))$
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_common_width_divides_side (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) : d ∣ n := by by_cases hn : n = 0 · simp [hn] let f : ℕ → ℤ := fun y => if y = 0 then 0 else 1 let g := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1) have hdiv : (d : ℤ) ∣ (P.map g).sum := by have hs := mondrian_list_sum_count_mod P (d : ℤ) 0 g (fun _ => false) (by intro r hr have hw : (d : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hd r hr simpa [g] using dvd_mul_of_dvd_left hw (f r.2.2.2 - f r.2.2.1)) simpa using hs have he : (P.map g).sum = (n : ℤ) := by simpa [g, f, hn] using mondrian_partition_horizontal_moment n P hP f rw [he] at hdiv exact_mod_cast hdiv