mondrian_partition_prime_free_width_count
For an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of tiles whose width is not divisible by p is divisible by p.
Statement
theorem mondrian_partition_prime_free_width_count (n p A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hApos : 0 < A) (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A) : p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r))
- 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 9
- 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_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_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_floor_contributionWhen positive q divides a rectangle height, its width times the integer difference of quotient y coordinates is its area divided by q.
- 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₁).
- mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
- mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- Used by 2
- mondrian_perfect_prime_free_side_countsIn any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not…
- mondrian_partition_prime_free_height_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
To prove that the number N of rectangles whose width is not divisible by p is a multiple of p, we assign each rectangle r a floor-weighted functional f(r) = width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋), where q = p^(v_p(A)) and u = A/q. Locally, f(r) ≡ u (mod p) when p ∤ width(r) (because q must then divide height(r), making f(r) = u exactly) and f(r) ≡ 0 (mod p) when p ∣ width(r). Summing over the partition shows that the total sum of f(r) is congruent to N * u modulo p. Globally, the sum of f(r) over the entire n × n partition evaluates to n ⌊n/q⌋, which is divisible by p since p ∣ n. Equating these modulo p yields p ∣ N * u; because u is coprime to p by construction, p must divide N.
Define the prime power q = p^(v_p(A)), the p-free part u = A/q, the floor functional f, and the predicate pred, and note that q > 0.
We extract the full p-adic factor of the common area A by letting q = p^(v_p(A)), so that u = A/q is coprime to p. For each rectangle r = [x₁, x₂) × [y₁, y₂), the functional f(r) = (x₂ - x₁)(⌊y₂/q⌋ - ⌊y₁/q⌋) tracks its weighted floor contribution, and pred(r) tests whether p does not divide the width of r. Since p is prime, p > 0, so q > 0 by pow_pos.
uses
pow_poslet q := p ^ A.factorization p let u := A / q let f := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬p ∣ mondrian_rect_width r) have hq : 0 < q := pow_pos hp.pos _
For every rectangle r in P, f(r) is congruent modulo p to u if p ∤ width(r) and to 0 if p ∣ width(r).
We split into cases based on whether p divides width(r): 1. If p ∣ width(r), then pred(r) is false (giving target 0). Since p divides the width, dvd_mul_of_dvd_left shows p divides f(r), so f(r) - 0 is divisible by p. 2. If p ∤ width(r), then pred(r) is true (giving target u). Since p does not divide the width, q = p^(v_p(A)) is coprime to width(r). Because q divides area(r) = A by Nat.ordProj_dvd, coprimality forces q to divide height(r). Using y₁ ≤ y₂ from Nat.le_of_lt, mondrian_rect_floor_contribution simplifies f(r) to exactly A / q = u. Hence f(r) - u = 0, which is divisible by p.
uses
dvd_mul_of_dvd_left,Nat.ordProj_dvd,mondrian_rect_floor_contribution,Nat.le_of_lthave hterm : ∀ r ∈ P, (p : ℤ) ∣ f r - if pred r then (u : ℤ) else 0 := by intro r hr by_cases hw : p ∣ mondrian_rect_width r · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw simpa only [f, pred, hw, not_true_eq_false, decide_false, Bool.false_eq_true, if_false, sub_zero] using dvd_mul_of_dvd_left hwZ ((((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))) · have hcop : q.Coprime (mondrian_rect_width r) := (hp.coprime_iff_not_dvd.mpr hw).pow_left _ have hqh : q ∣ mondrian_rect_height r := by apply hcop.dvd_mul_left.mp change q ∣ mondrian_rect_area r rw [hA r hr] exact Nat.ordProj_dvd A p have he := mondrian_rect_floor_contribution r (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh rw [hA r hr] at he simp only [f, pred, hw, not_false_eq_true, decide_true, if_true] change (p : ℤ) ∣ _ - (A / q : ℕ) rw [he] simp
The sum of f(r) over all rectangles in P is congruent modulo p to N * u, where N is the count of rectangles with width not divisible by p.
Applying mondrian_list_sum_count_mod to the list P aggregates the per-rectangle congruences, establishing that p divides ∑ f(r) - N * u.
uses
mondrian_list_sum_count_modhave hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred htermThe total sum ∑ f(r) over all rectangles in P is divisible by p.
By the global moment identity mondrian_partition_floor_moment, the sum of f(r) over the partition of the n × n square equals n ⌊n / q⌋. Since p ∣ n by hypothesis, p divides this product by dvd_mul_of_dvd_left.
uses
mondrian_partition_floor_moment,dvd_mul_of_dvd_lefthave hmoment := mondrian_partition_floor_moment n q P hP have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn have hsumdiv : (p : ℤ) ∣ (P.map f).sum := by rw [show (P.map f).sum = (n : ℤ) * (n / q : ℕ) from hmoment] exact dvd_mul_of_dvd_left hnZ _
The product N * u is divisible by p in the integers.
Since p divides the total sum and also divides the difference ∑ f(r) - N * u, dvd_sub shows that p divides their difference. Ring arithmetic simplifies ∑ f(r) - (∑ f(r) - N * u) to N * u.
uses
dvd_subhave hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by have hh := dvd_sub hsumdiv hsum have heq : (P.map f).sum - ((P.map f).sum - (P.countP pred : ℤ) * (u : ℤ)) = (P.countP pred : ℤ) * (u : ℤ) := by ring rwa [heq] at hh
The number of rectangles in P whose width is not divisible by p is divisible by p.
Casting the divisibility p ∣ N * u to natural numbers, the primality of p implies that p ∣ N or p ∣ u. But u = A / p^(v_p(A)) has all factors of p removed, so Nat.not_dvd_ordCompl (with A ≠ 0 from Nat.ne_of_gt) guarantees p does not divide u. Hence p must divide N.
uses
Nat.not_dvd_ordCompl,Nat.ne_of_gthave hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod rcases hp.dvd_mul.mp hprodN with hc | hu · exact hc · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim
pow_pos- A strictly positive element raised to any natural power is strictly positive.
dvd_mul_of_dvd_left- If a divides b, then a divides b * c for any c.
Nat.ordProj_dvd- The prime power p^(v_p(n)) divides n.
mondrian_rect_floor_contribution- If q > 0 divides the height of rectangle r, then width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋) = area(r) / q.
Nat.le_of_lt- Strict inequality between natural numbers implies non-strict inequality.
mondrian_list_sum_count_mod- If each element r of a list satisfies f(r) ≡ u (mod p) when pred(r) holds and f(r) ≡ 0 (mod p) otherwise, then the sum of f(r) over the list is congruent modulo p to the count of satisfying elements times u.
mondrian_partition_floor_moment- For an admissible partition P of an n × n square, the sum of width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋) over all rectangles r in P equals n ⌊n / q⌋.
dvd_sub- If a divides b and a divides c, then a divides b - c.
Nat.not_dvd_ordCompl- For a prime p and non-zero n, p does not divide the p-free part n / p^(v_p(n)).
Nat.ne_of_gt- If b < a, then a ≠ b.
- The proof works with integer casts (exact_mod_cast) because the floor difference functional is evaluated in ℤ to handle subtraction cleanly, before casting back to ℕ for prime divisibility.
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_prime_free_width_count (n p A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hApos : 0 < A) (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A) : p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r)) := by let q := p ^ A.factorization p let u := A / q let f := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬p ∣ mondrian_rect_width r) have hq : 0 < q := pow_pos hp.pos _ have hterm : ∀ r ∈ P, (p : ℤ) ∣ f r - if pred r then (u : ℤ) else 0 := by intro r hr by_cases hw : p ∣ mondrian_rect_width r · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw simpa only [f, pred, hw, not_true_eq_false, decide_false, Bool.false_eq_true, if_false, sub_zero] using dvd_mul_of_dvd_left hwZ ((((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))) · have hcop : q.Coprime (mondrian_rect_width r) := (hp.coprime_iff_not_dvd.mpr hw).pow_left _ have hqh : q ∣ mondrian_rect_height r := by apply hcop.dvd_mul_left.mp change q ∣ mondrian_rect_area r rw [hA r hr] exact Nat.ordProj_dvd A p have he := mondrian_rect_floor_contribution r (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh rw [hA r hr] at he simp only [f, pred, hw, not_false_eq_true, decide_true, if_true] change (p : ℤ) ∣ _ - (A / q : ℕ) rw [he] simp have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm have hmoment := mondrian_partition_floor_moment n q P hP have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn have hsumdiv : (p : ℤ) ∣ (P.map f).sum := by rw [show (P.map f).sum = (n : ℤ) * (n / q : ℕ) from hmoment] exact dvd_mul_of_dvd_left hnZ _ have hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by have hh := dvd_sub hsumdiv hsum have heq : (P.map f).sum - ((P.map f).sum - (P.countP pred : ℤ) * (u : ℤ)) = (P.countP pred : ℤ) * (u : ℤ) := by ring rwa [heq] at hh have hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod rcases hp.dvd_mul.mp hprodN with hc | hu · exact hc · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim