mondrian_partition_normalized_prime_free_width_mod
In an admissible n-square partition with every width divisible by positive d and with constant normalized area C, the number of normalized widths indivisible by prime p, multiplied by the p-free part of C, is congruent modulo p to (n/d) times floor(n/p^v_p(C)).
Statement
theorem mondrian_partition_normalized_prime_free_width_mod (n p d C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hd : 0 < d) (hP : mondrian_is_partition n P) (hwidth : ∀ r ∈ P, d ∣ mondrian_rect_width r) (harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C) : Nat.ModEq p ((P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))) * (C / p ^ C.factorization p)) ((n / d) * (n / p ^ C.factorization p))
- Source
- Helper for OP-280 and mondrian_perfect_min_width_layer_count, from the normalized floor moment for arXiv:2610.19193, Section 1.
- 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_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…
- 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_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- 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_areaThe area |R| = width × height of a rectangle.
- Used by 1
- 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…
The proof, explained
We define an auxiliary functional for each rectangle r in the partition: f(r) = (w_r / d) * (floor(y_{2,r} / q) - floor(y_{1,r} / q)), where q = p^{v_p(C)} is the prime-power factor of the normalized area C. For rectangles whose normalized width w_r / d is divisible by p, f(r) is divisible by p; for those not divisible by p, coprimality forces q to divide the height, so f(r) simplifies exactly to C / q. Summing f(r) across the entire partition yields both the count times C / q modulo p and, via a global partition moment identity, the total (n/d) * floor(n/q), establishing the desired congruence.
Define the prime-power factor q = p^{v_p(C)}, the p-free part u = C/q, the per-rectangle weighted floor functional f, and the predicate selecting rectangles whose normalized width is not divisible by p, and note that q > 0.
We set q = p^{v_p(C)} and u = C / q. For each rectangle r with vertical span [y_1, y_2] and normalized width w_r / d, we define f(r) = (w_r / d) * (floor(y_2 / q) - floor(y_1 / q)). The predicate pred(r) tests whether p does not divide w_r / d. Since p is prime, p > 0, so q = p^{v_p(C)} > 0 by `pow_pos`.
uses
pow_poslet q := p ^ C.factorization p let u := C / q let f := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬ p ∣ mondrian_rect_width r / d) have hq : 0 < q := pow_pos hp.pos _
For any rectangle r ∈ P whose normalized width is divisible by p, the term f(r) is divisible by p, so f(r) ≡ 0 (mod p).
We begin establishing that p ∣ f(r) - if pred(r) then u else 0 for every rectangle r ∈ P. Splitting on whether p ∣ (w_r / d): if it does, pred(r) is false, so the target reduces to p ∣ f(r). Since f(r) has w_r / d as an integer factor, `dvd_mul_of_dvd_left` shows that p divides f(r).
uses
dvd_mul_of_dvd_lefthave 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 / d · have hwZ : (p : ℤ) ∣ ((mondrian_rect_width r / d : ℕ) : ℤ) := 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 : ℕ) : ℤ)))
For any rectangle r ∈ P whose normalized width is not divisible by p, f(r) = u, completing the proof that f(r) ≡ if pred(r) then u else 0 (mod p) for all r ∈ P.
When p does not divide w_r / d, q = p^{v_p(C)} is coprime to w_r / d. Since (w_r / d) * h_r = C and q ∣ C by `Nat.ordProj_dvd`, coprimality implies q ∣ h_r. Applying `mondrian_rect_floor_contribution` to an auxiliary rectangle of width w_r / d and height h_r (using y_1 ≤ y_2 from `hP` via `Nat.le_of_lt`), the weighted floor difference evaluates exactly to ((w_r / d) * h_r) / q = C / q = u. Since pred(r) is true, f(r) - u = u - u = 0, which is divisible by p.
uses
Nat.ordProj_dvd,mondrian_rect_floor_contribution,Nat.le_of_lt· have hcop : q.Coprime (mondrian_rect_width r / d) := (hp.coprime_iff_not_dvd.mpr hw).pow_left _ have hqh : q ∣ mondrian_rect_height r := by apply hcop.dvd_mul_left.mp rw [harea r hr] exact Nat.ordProj_dvd C p let v : ℕ × ℕ × ℕ × ℕ := (0, mondrian_rect_width r / d, r.2.2.1, r.2.2.2) have he := mondrian_rect_floor_contribution v (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh change ((mondrian_rect_width r / d : ℕ) : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) = (((mondrian_rect_width r / d) * mondrian_rect_height r / q : ℕ) : ℤ) at he rw [harea r hr] at he simp only [f, pred, hw, not_false_eq_true, decide_true, if_true] change (p : ℤ) ∣ _ - (C / q : ℕ) rw [he] simp
Summing over the partition, ∑_{r ∈ P} f(r) is congruent modulo p to u times the count of rectangles with normalized width indivisible by p.
Applying `mondrian_list_sum_count_mod` to the list P and the term-by-term divisibility condition establishes that p divides ∑_{r ∈ P} f(r) - (count of rectangles satisfying pred) * u.
uses
mondrian_list_sum_count_modhave hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred htermThe sum ∑_{r ∈ P} f(r) equals (n/d) * floor(n/q), so p ∣ (n/d) * floor(n/q) - (count) * u.
By `mondrian_partition_floor_moment_div_width`, the sum of (w_r / d) * (floor(y_2 / q) - floor(y_1 / q)) over the partition of an n × n square evaluates globally to (n/d) * floor(n/q). Rewriting this identity into the previous divisibility relation replaces the sum with (n/d) * floor(n/q).
uses
mondrian_partition_floor_moment_div_widthhave hmoment := mondrian_partition_floor_moment_div_width n q d P hd hP hwidth change (P.map f).sum = ((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ) at hmoment rw [hmoment] at hsum
The count of rectangles with normalized width indivisible by p, multiplied by C / p^{v_p(C)}, is congruent modulo p to (n/d) * floor(n / p^{v_p(C)}).
Using `Nat.modEq_iff_dvd.mpr`, the integer divisibility relation p ∣ (n/d) * floor(n/q) - (count) * u is converted into the congruence (count) * u ≡ (n/d) * floor(n/q) (mod p) over natural numbers.
uses
Nat.modEq_iff_dvd.mprexact Nat.modEq_iff_dvd.mpr (by exact_mod_cast hsum)
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 factor p^(v_p(n)) divides n for any natural numbers n and p.
mondrian_rect_floor_contribution- When the height of a rectangle is a multiple of q > 0, its width times the floor difference of its vertical endpoints divided by q equals its area divided by q.
Nat.le_of_lt- A strict inequality a < b between natural numbers implies a ≤ b.
mondrian_list_sum_count_mod- If every element of a list satisfies f(r) ≡ u [MOD p] when a boolean predicate holds and f(r) ≡ 0 [MOD p] otherwise, then the sum of f(r) over the list is congruent modulo p to u times the count of elements satisfying the predicate.
mondrian_partition_floor_moment_div_width- In an admissible partition of an n-square whose rectangle widths are all divisible by d, the sum of (w_r / d) * (floor(y_{2,r}/q) - floor(y_{1,r}/q)) over all rectangles equals (n/d) * floor(n/q).
Nat.modEq_iff_dvd.mpr- An integer divisibility relation n ∣ b - a implies the modular congruence a ≡ b [MOD n] on natural numbers.
- The rectangle floor contribution lemma `mondrian_rect_floor_contribution` is applied to an auxiliary rectangle `v` whose width is normalized to `mondrian_rect_width r / d` and whose vertical span matches `r`.
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.
theorem mondrian_partition_normalized_prime_free_width_mod (n p d C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hd : 0 < d) (hP : mondrian_is_partition n P) (hwidth : ∀ r ∈ P, d ∣ mondrian_rect_width r) (harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C) : Nat.ModEq p ((P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))) * (C / p ^ C.factorization p)) ((n / d) * (n / p ^ C.factorization p)) := by let q := p ^ C.factorization p let u := C / q let f := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬ p ∣ mondrian_rect_width r / d) 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 / d · have hwZ : (p : ℤ) ∣ ((mondrian_rect_width r / d : ℕ) : ℤ) := 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 / d) := (hp.coprime_iff_not_dvd.mpr hw).pow_left _ have hqh : q ∣ mondrian_rect_height r := by apply hcop.dvd_mul_left.mp rw [harea r hr] exact Nat.ordProj_dvd C p let v : ℕ × ℕ × ℕ × ℕ := (0, mondrian_rect_width r / d, r.2.2.1, r.2.2.2) have he := mondrian_rect_floor_contribution v (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh change ((mondrian_rect_width r / d : ℕ) : ℤ) * (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) = (((mondrian_rect_width r / d) * mondrian_rect_height r / q : ℕ) : ℤ) at he rw [harea r hr] at he simp only [f, pred, hw, not_false_eq_true, decide_true, if_true] change (p : ℤ) ∣ _ - (C / q : ℕ) rw [he] simp have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm have hmoment := mondrian_partition_floor_moment_div_width n q d P hd hP hwidth change (P.map f).sum = ((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ) at hmoment rw [hmoment] at hsum exact Nat.modEq_iff_dvd.mpr (by exact_mod_cast hsum)