mondrian_perfect_min_width_layer_count
For 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 most v_p(n), and the number of tiles in that minimum layer is congruent modulo p to the tile count if b=v_p(n), and to zero if b<v_p(n).
Statement
theorem mondrian_perfect_min_width_layer_count (n p b : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hmin : ∀ r ∈ P, p ^ b ∣ mondrian_rect_width r) (hex : ∃ r ∈ P, ¬ p ^ (b + 1) ∣ mondrian_rect_width r) : b ≤ n.factorization p ∧ Nat.ModEq p (P.countP (fun r => decide (¬p ^ (b + 1) ∣ mondrian_rect_width r))) (if b = n.factorization p then P.length else 0)
- Source
- Next step of the modular inventory route for OP-280, arXiv:2610.19193, Section 1. The minimum-layer strengthening is derived here on paper and tested in experiments 5295 and 5296; it is not yet Lean-proved.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- 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_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_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_common_width_divides_sideEvery common divisor of the tile widths in an admissible n-square partition divides n.
- 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_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- 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_boundsEvery rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.
- 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…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- 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…
The proof, explained
The proof scales the tile widths of the partition by the minimal power $d = p^b$, normalizing the partition so that the tiles in the minimal width layer are precisely those with scaled width coprime to $p$. The common divisor $d$ must divide the square side $n$, giving $b \le v_p(n)$. A normalized modular relation equates the count of these minimal tiles (scaled by the $p$-free tile area $u$) to $N \cdot (n/q) \pmod p$, where $N = n/p^b$. When $b = v_p(n)$, $N$ is coprime to $p$ and the total area product implies $N \cdot (n/q) = |P| \cdot u$, forcing the count to be congruent to $|P| \pmod p$; when $b < v_p(n)$, $p$ divides $N$, driving the right-hand side to $0 \pmod p$.
The partition $P$ contains at least one rectangle $z$.
Because $P$ is a valid partition of the $n$-square, its definition guarantees $|P| \ge 2$. Thus $P$ is non-empty, so there exists some rectangle $z \in P$.
obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by cases P with | nil => have := hP.1; simp at this | cons z P => exact ⟨z, by simp⟩
Define the scaling divisor $d = p^b$, the reference tile area $A$, the scaled area $C = A/d$, the scaled square size $N = n/d$, the maximal prime power $q = p^{v_p(C)}$ dividing $C$, the $p$-free part $u = C/q$, the tile count $k = |P|$, and the count $\text{cnt}$ of tiles whose scaled width is coprime to $p$.
These definitions set up the normalized parameters for applying modular reduction: dividing tile widths by $d$ standardizes the minimum $p$-adic layer to valuation zero, where divisibility by $p$ can be counted directly.
let d := p ^ b let A := mondrian_rect_area z let C := A / d let N := n / d let q := p ^ C.factorization p let u := C / q let k := P.length let cnt := P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))
The quantities $d, n, A, C$ are strictly positive, $d \mid n$, the bound $b \le v_p(n)$ holds, and the exact division identities $d \cdot C = A$ and $d \cdot N = n$ hold.
Since $p$ is prime, $d = p^b > 0$ by `pow_pos`. From the partition bounds on $z \in P$ (`mondrian_partition_bounds`), $n > 0$ and $A > 0$. Since $d$ divides the width of $z$, it divides $A$ (`dvd_mul_of_dvd_left`), making $C = A/d > 0$ by `Nat.div_pos`. Because $d$ divides the width of every tile in the partition, $d \mid n$ by `mondrian_common_width_divides_side`. Since $n \ne 0$, $p^b \mid n$ is equivalent to $b \le v_p(n)$. The product identities $d \cdot C = A$ and $d \cdot N = n$ follow from exact division (`Nat.mul_div_cancel'`).
uses
pow_pos,mondrian_partition_bounds,Nat.mul_pos,dvd_mul_of_dvd_left,Nat.div_pos,Nat.le_of_dvd,mondrian_common_width_divides_side,Nat.mul_div_cancel'have hd : 0 < d := pow_pos hp.pos b have hzb := mondrian_partition_bounds n P hP z hzP have hn : 0 < n := hzb.2.2.1.trans_le hzb.2.2.2.2.1 have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1 have hAd : d ∣ A := dvd_mul_of_dvd_left (hmin z hzP) _ have hC : 0 < C := Nat.div_pos (Nat.le_of_dvd hA hAd) hd have hdn : d ∣ n := mondrian_common_width_divides_side n d P hP hmin have hbd : b ≤ n.factorization p := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mp hdn have hdC : d * C = A := Nat.mul_div_cancel' hAd have hdN : d * N = n := Nat.mul_div_cancel' hdn
For every tile $r \in P$, the scaled width and unscaled height give area $(\text{width}(r)/d) \cdot \text{height}(r) = C$.
Multiplying the scaled area expression by $d$ recovers the unscaled area $\text{area}(r)$ by `Nat.mul_div_cancel'`. Since the partition has defect 0, all tiles have identical area, so $\text{area}(r) = A = d \cdot C$ by `mondrian_defect_zero_equal`. Cancelling the common factor $d > 0$ using `Nat.eq_of_mul_eq_mul_left` proves that every tile has scaled area $C$.
uses
Nat.eq_of_mul_eq_mul_left,Nat.mul_assoc,Nat.mul_div_cancel',mondrian_defect_zero_equalhave harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C := by intro r hr apply Nat.eq_of_mul_eq_mul_left hd calc d * ((mondrian_rect_width r / d) * mondrian_rect_height r) = mondrian_rect_area r := by rw [← Nat.mul_assoc, Nat.mul_div_cancel' (hmin r hr)] rfl _ = A := mondrian_defect_zero_equal P hz r z hr hzP _ = d * C := hdC.symm
The congruence $\text{cnt} \cdot u \equiv N \cdot (n/q) \pmod p$ holds, and $u$ is coprime to $p$.
Applying `mondrian_partition_normalized_prime_free_width_mod` to the normalized partition yields the modular relation $\text{cnt} \cdot u \equiv N \cdot (n/q) \pmod p$. Since $u = C / p^{v_p(C)}$ is the $p$-free part of $C \ne 0$, $p \nmid u$ by `Nat.not_dvd_ordCompl`, so $u$ is coprime to $p$.
uses
mondrian_partition_normalized_prime_free_width_mod,Nat.not_dvd_ordComplhave hmod := mondrian_partition_normalized_prime_free_width_mod n p d C P hp hd hP hmin harea change Nat.ModEq p (cnt * u) (N * (n / q)) at hmod have hunit : p.Coprime u := hp.coprime_iff_not_dvd.mpr (Nat.not_dvd_ordCompl hp (by omega : C ≠ 0))
The count $\text{cnt}$ equals the number of tiles in $P$ whose width is not divisible by $p^{b+1}$.
For any tile $r$, its width is a multiple of $d = p^b$. Hence $p \mid (\text{width}(r)/d)$ is equivalent via `Nat.mul_dvd_mul_iff_left` to $d \cdot p \mid \text{width}(r)$, which is $p^{b+1} \mid \text{width}(r)$ by `pow_succ`. Negating this equivalence and summing over $P$ with `List.countP_congr` identifies $\text{cnt}$ with the number of tiles having $p$-adic width exponent exactly $b$.
uses
List.countP_congr,decide_eq_true_eq,not_congr,Nat.mul_div_cancel',pow_succ,Nat.mul_dvd_mul_iff_lefthave hcount : cnt = P.countP (fun r => decide (¬ p ^ (b + 1) ∣ mondrian_rect_width r)) := by apply List.countP_congr intro r hr simp only [decide_eq_true_eq] apply not_congr have hw : d * (mondrian_rect_width r / d) = mondrian_rect_width r := Nat.mul_div_cancel' (hmin r hr) have he : p ^ (b + 1) = d * p := by rw [pow_succ] rw [he] conv_rhs => rw [← hw] exact (Nat.mul_dvd_mul_iff_left hd).symm
Discharge the inequality $b \le v_p(n)$ and rewrite the remaining goal in terms of $\text{cnt}$.
The first conjunct of the theorem, $b \le v_p(n)$, was already established as `hbd`. Replacing the filter in the second conjunct with `cnt` reduces the problem to evaluating $\text{cnt} \pmod p$.
refine ⟨hbd, ?_⟩ rw [← hcount]
If $b = v_p(n)$, then $\text{cnt} \equiv |P| \pmod p$.
When $b = v_p(n)$, $N = n / p^{v_p(n)}$ is not divisible by $p$ by `Nat.not_dvd_ordCompl`, so $q = p^{v_p(C)}$ is coprime to $N$. The total area identity $|P| \cdot A = n^2$ (`mondrian_perfect_area_product`) scales down to $k \cdot C = N \cdot n$. Since $q \mid C$, $q$ divides $N \cdot n$, and coprimality with $N$ implies $q \mid n$. Dividing $k \cdot C = N \cdot n$ by $q$ yields $k \cdot u = N \cdot (n/q)$. Substituting this into the normalized congruence gives $\text{cnt} \cdot u \equiv k \cdot u \pmod p$. Because $u$ is coprime to $p$, cancelling $u$ with `Nat.ModEq.cancel_right_of_coprime` concludes $\text{cnt} \equiv k \pmod p$.
uses
if_pos,Nat.not_dvd_ordCompl,Nat.eq_of_mul_eq_mul_left,mondrian_perfect_area_product,dvd_mul_of_dvd_right,Nat.ordProj_dvd,Nat.mul_div_cancel',pow_pos,congrArg,Nat.ModEq.cancel_right_of_coprimeby_cases hb : b = n.factorization p · rw [if_pos hb] have hNnot : ¬ p ∣ N := by simpa only [N, d, hb] using Nat.not_dvd_ordCompl hp (by omega : n ≠ 0) have hnorm : k * C = N * n := by apply Nat.eq_of_mul_eq_mul_left hd calc d * (k * C) = k * A := by rw [← hdC]; ring _ = n ^ 2 := mondrian_perfect_area_product n P hP hz z hzP _ = d * (N * n) := by rw [← hdN]; ring have hcop : q.Coprime N := (hp.coprime_iff_not_dvd.mpr hNnot).pow_left _ have hqn : q ∣ n := hcop.dvd_mul_left.mp (by rw [← hnorm] exact dvd_mul_of_dvd_right (Nat.ordProj_dvd C p) k) have hqC : q * u = C := Nat.mul_div_cancel' (Nat.ordProj_dvd C p) have hqN : q * (n / q) = n := Nat.mul_div_cancel' hqn have hprod : k * u = N * (n / q) := by apply Nat.eq_of_mul_eq_mul_left (pow_pos hp.pos (C.factorization p)) calc q * (k * u) = k * C := by rw [← hqC]; ring _ = N * n := hnorm _ = N * (q * (n / q)) := congrArg (fun v => N * v) hqN.symm _ = q * (N * (n / q)) := by ring rw [← hprod] at hmod exact Nat.ModEq.cancel_right_of_coprime hunit hmod
If $b < v_p(n)$, then $\text{cnt} \equiv 0 \pmod p$.
When $b < v_p(n)$, we have $b + 1 \le v_p(n)$, so $p^{b+1} \mid n$. Since $p^{b+1} = d \cdot p$ and $n = d \cdot N$, cancelling $d$ via `Nat.mul_dvd_mul_iff_left` gives $p \mid N$. It follows that $N \cdot (n/q)$ is divisible by $p$, so $N \cdot (n/q) \equiv 0 \cdot u \pmod p$ by `Nat.zero_mul`. The normalized congruence becomes $\text{cnt} \cdot u \equiv 0 \cdot u \pmod p$, and cancelling the coprime factor $u$ via `Nat.ModEq.cancel_right_of_coprime` gives $\text{cnt} \equiv 0 \pmod p$.
uses
if_neg,pow_succ,Nat.mul_dvd_mul_iff_left,Nat.zero_mul,dvd_mul_of_dvd_left,Nat.ModEq.cancel_right_of_coprime· rw [if_neg hb] have hba : b + 1 ≤ n.factorization p := by omega have hpow : p ^ (b + 1) ∣ n := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mpr hba have hN : p ∣ N := by have hh : d * p ∣ d * N := by rw [hdN] simpa only [d, pow_succ] using hpow exact (Nat.mul_dvd_mul_iff_left hd).mp hh have hzero : Nat.ModEq p (N * (n / q)) (0 * u) := by simpa only [Nat.zero_mul] using (dvd_mul_of_dvd_left hN (n / q)).modEq_zero_nat exact Nat.ModEq.cancel_right_of_coprime hunit (hmod.trans hzero)
congrArg- A function applied to equal inputs produces equal outputs: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
decide_eq_true_eq- The boolean expression `decide P` evaluates to `true` if and only if proposition $P$ holds.
dvd_mul_of_dvd_left- If $a$ divides $b$, then $a$ divides $b \cdot c$.
dvd_mul_of_dvd_right- If $a$ divides $b$, then $a$ divides $c \cdot b$.
if_neg- If condition $c$ is false, then `if c then t else e` equals $e$.
if_pos- If condition $c$ is true, then `if c then t else e` equals $t$.
List.countP_congr- If two predicates agree on all elements of a list, counting elements satisfying each predicate gives the same number.
mondrian_common_width_divides_side- If a divisor $d$ divides the width of every rectangle in a partition of an $n \times n$ square, then $d$ divides $n$.
mondrian_defect_zero_equal- In a partition with zero defect, all rectangles have the same area.
mondrian_partition_bounds- Every rectangle in an $n$-square partition has strictly positive dimensions bounded above by $n$.
mondrian_partition_normalized_prime_free_width_mod- For an $n$-square partition where all tile widths are multiples of $d$ and scaled tile area is $C$, the count of tiles whose scaled width is not divisible by $p$ multiplied by the $p$-free part of $C$ is congruent modulo $p$ to $(n/d) \cdot (n/p^{v_p(C)})$.
mondrian_perfect_area_product- In a defect-zero partition of an $n \times n$ square, the number of rectangles times the area of any single rectangle equals $n^2$.
Nat.div_pos- If $0 < b \le a$, then the integer quotient $a / b$ is strictly positive.
Nat.eq_of_mul_eq_mul_left- Multiplying both sides of an equality by a strictly positive natural number preserves equality.
Nat.le_of_dvd- If $m \mid n$ and $n > 0$, then $m \le n$.
Nat.ModEq.cancel_right_of_coprime- In modular arithmetic, a factor coprime to the modulus can be cancelled from both sides: $a \cdot c \equiv b \cdot c \pmod m$ implies $a \equiv b \pmod m$ when $\gcd(m, c) = 1$.
Nat.mul_assoc- Multiplication of natural numbers is associative: $(n \cdot m) \cdot k = n \cdot (m \cdot k)$.
Nat.mul_div_cancel'- If $n$ divides $m$, then $n \cdot (m / n) = m$.
Nat.mul_dvd_mul_iff_left- For $a > 0$, $a \cdot b \mid a \cdot c$ if and only if $b \mid c$.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Nat.not_dvd_ordCompl- For a prime $p$ and non-zero natural number $n$, $p$ does not divide the prime-free component $n / p^{v_p(n)}$.
Nat.ordProj_dvd- The prime power factor $p^{v_p(n)}$ divides $n$.
Nat.zero_mul- Zero multiplied by any natural number is zero.
not_congr- An equivalence of propositions $P \leftrightarrow Q$ implies an equivalence of their negations $\neg P \leftrightarrow \neg Q$.
pow_pos- A strictly positive natural number raised to any power is strictly positive.
pow_succ- For any base $a$ and natural exponent $n$, $a^{n+1} = a^n \cdot a$.
- Several arithmetic side conditions (such as $n \ne 0$ from strict positivity and $b + 1 \le v_p(n)$ from $b \le v_p(n)$ with $b \ne v_p(n)$) are discharged by `omega`, and polynomial rearrangements of products are closed by `ring`.
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_perfect_min_width_layer_count (n p b : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hmin : ∀ r ∈ P, p ^ b ∣ mondrian_rect_width r) (hex : ∃ r ∈ P, ¬ p ^ (b + 1) ∣ mondrian_rect_width r) : b ≤ n.factorization p ∧ Nat.ModEq p (P.countP (fun r => decide (¬p ^ (b + 1) ∣ mondrian_rect_width r))) (if b = n.factorization p then P.length else 0) := by obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by cases P with | nil => have := hP.1; simp at this | cons z P => exact ⟨z, by simp⟩ let d := p ^ b let A := mondrian_rect_area z let C := A / d let N := n / d let q := p ^ C.factorization p let u := C / q let k := P.length let cnt := P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d)) have hd : 0 < d := pow_pos hp.pos b have hzb := mondrian_partition_bounds n P hP z hzP have hn : 0 < n := hzb.2.2.1.trans_le hzb.2.2.2.2.1 have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1 have hAd : d ∣ A := dvd_mul_of_dvd_left (hmin z hzP) _ have hC : 0 < C := Nat.div_pos (Nat.le_of_dvd hA hAd) hd have hdn : d ∣ n := mondrian_common_width_divides_side n d P hP hmin have hbd : b ≤ n.factorization p := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mp hdn have hdC : d * C = A := Nat.mul_div_cancel' hAd have hdN : d * N = n := Nat.mul_div_cancel' hdn have harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C := by intro r hr apply Nat.eq_of_mul_eq_mul_left hd calc d * ((mondrian_rect_width r / d) * mondrian_rect_height r) = mondrian_rect_area r := by rw [← Nat.mul_assoc, Nat.mul_div_cancel' (hmin r hr)] rfl _ = A := mondrian_defect_zero_equal P hz r z hr hzP _ = d * C := hdC.symm have hmod := mondrian_partition_normalized_prime_free_width_mod n p d C P hp hd hP hmin harea change Nat.ModEq p (cnt * u) (N * (n / q)) at hmod have hunit : p.Coprime u := hp.coprime_iff_not_dvd.mpr (Nat.not_dvd_ordCompl hp (by omega : C ≠ 0)) have hcount : cnt = P.countP (fun r => decide (¬ p ^ (b + 1) ∣ mondrian_rect_width r)) := by apply List.countP_congr intro r hr simp only [decide_eq_true_eq] apply not_congr have hw : d * (mondrian_rect_width r / d) = mondrian_rect_width r := Nat.mul_div_cancel' (hmin r hr) have he : p ^ (b + 1) = d * p := by rw [pow_succ] rw [he] conv_rhs => rw [← hw] exact (Nat.mul_dvd_mul_iff_left hd).symm refine ⟨hbd, ?_⟩ rw [← hcount] by_cases hb : b = n.factorization p · rw [if_pos hb] have hNnot : ¬ p ∣ N := by simpa only [N, d, hb] using Nat.not_dvd_ordCompl hp (by omega : n ≠ 0) have hnorm : k * C = N * n := by apply Nat.eq_of_mul_eq_mul_left hd calc d * (k * C) = k * A := by rw [← hdC]; ring _ = n ^ 2 := mondrian_perfect_area_product n P hP hz z hzP _ = d * (N * n) := by rw [← hdN]; ring have hcop : q.Coprime N := (hp.coprime_iff_not_dvd.mpr hNnot).pow_left _ have hqn : q ∣ n := hcop.dvd_mul_left.mp (by rw [← hnorm] exact dvd_mul_of_dvd_right (Nat.ordProj_dvd C p) k) have hqC : q * u = C := Nat.mul_div_cancel' (Nat.ordProj_dvd C p) have hqN : q * (n / q) = n := Nat.mul_div_cancel' hqn have hprod : k * u = N * (n / q) := by apply Nat.eq_of_mul_eq_mul_left (pow_pos hp.pos (C.factorization p)) calc q * (k * u) = k * C := by rw [← hqC]; ring _ = N * n := hnorm _ = N * (q * (n / q)) := congrArg (fun v => N * v) hqN.symm _ = q * (N * (n / q)) := by ring rw [← hprod] at hmod exact Nat.ModEq.cancel_right_of_coprime hunit hmod · rw [if_neg hb] have hba : b + 1 ≤ n.factorization p := by omega have hpow : p ^ (b + 1) ∣ n := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mpr hba have hN : p ∣ N := by have hh : d * p ∣ d * N := by rw [hdN] simpa only [d, pow_succ] using hpow exact (Nat.mul_dvd_mul_iff_left hd).mp hh have hzero : Nat.ModEq p (N * (n / q)) (0 * u) := by simpa only [Nat.zero_mul] using (dvd_mul_of_dvd_left hN (n / q)).modEq_zero_nat exact Nat.ModEq.cancel_right_of_coprime hunit (hmod.trans hzero)