mondrian_partition_width_dvd_of_height_prime_chain
Suppose d divides the square side and all tiles whose widths are indivisible by d have heights C times powers of a fixed prime p, with positive C. In a perfect admissible partition every tile width is divisible by d.
Statement
theorem mondrian_partition_width_dvd_of_height_prime_chain (n d p C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)
(hdn : d ∣ n) (hp : Nat.Prime p) (hC : 0 < C)
(hheight : ∀ r ∈ P, ¬ d ∣ mondrian_rect_width r →
∃ a, mondrian_rect_height r = C * p ^ a) :
∀ r ∈ P, d ∣ mondrian_rect_width r- Source
- For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- 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_isolated_height_residueLet d divide the square side. If every tile except r either has width divisible by d or height divisible by m, and r has height…
- mondrian_perfect_height_injectiveThe heights of the tiles in a perfect admissible square partition are pairwise distinct.
- 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₁).
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.
The proof, explained
The proof proceeds by contradiction. Assuming there is a tile whose width is not divisible by d, we consider the non-empty set S of all such tiles and choose a tile z of minimal height, which has height C * p^a. Setting m = C * p^(a+1), the height of z is strictly smaller than m and therefore not divisible by m. Moreover, every other tile s ≠ z either has width divisible by d or, by height minimality and the injectivity of heights in a defect-zero partition, has height C * p^b with b ≥ a + 1, so m divides its height. The isolated height residue theorem then implies d must divide the width of z, contradicting that z belongs to S.
Assume for contradiction that there exists a tile r ∈ P whose width is not divisible by d.
We proceed by contradiction: assuming it is not the case that every tile in P has width divisible by d, negation yields an explicit witness tile r ∈ P such that d does not divide the width of r.
have hp0 := hp.pos by_contra hh push_neg at hh obtain ⟨r, hr, hrd⟩ := hh
There is a tile z ∈ P whose width is not divisible by d that minimizes height among all such tiles, with height equal to C * p^a for some natural number a.
Let S be the sub-collection of tiles in P with width indivisible by d. Because r ∈ S, the finite set S is non-empty and therefore contains an element z that achieves the minimal height. By the hypothesis on tile heights, z must have height C * p^a for some exponent a.
uses
Finset.mem_filter.mp,List.mem_toFinset.mplet S := P.toFinset.filter (fun s => ¬ d ∣ mondrian_rect_width s) have hS : S.Nonempty := ⟨r, by simp [S, hr, hrd]⟩ obtain ⟨z, hzS, hzmin⟩ := S.exists_min_image mondrian_rect_height hS obtain ⟨hzP, hzd⟩ := Finset.mem_filter.mp hzS have hzP' : z ∈ P := List.mem_toFinset.mp hzP obtain ⟨a, hza⟩ := hheight z hzP' hzd
For m = C * p^(a + 1), m does not divide the height of z.
If m divided the height of z, then because the height C * p^a is strictly positive, m would have to be less than or equal to the height of z. But since p > 1 and a < a + 1, we have p^a < p^(a+1), so the height C * p^a is strictly less than m = C * p^(a+1), which is a contradiction.
uses
Nat.le_of_dvd,Nat.mul_lt_mul_of_pos_left,Nat.pow_lt_pow_iff_rightlet m := C * p ^ (a + 1) have hzm : ¬ m ∣ mondrian_rect_height z := by intro hm have hzpos : 0 < mondrian_rect_height z := by rw [hza]; positivity have hmle := Nat.le_of_dvd hzpos hm have hlt : mondrian_rect_height z < m := by rw [hza] dsimp [m] apply Nat.mul_lt_mul_of_pos_left _ hC exact (Nat.pow_lt_pow_iff_right hp.one_lt).mpr (by omega) omega
Every other tile s ≠ z in P either has width divisible by d or height divisible by m.
Take any tile s ∈ P with s ≠ z. If d divides the width of s, we are done. Otherwise, s ∈ S, so its height is C * p^b for some b and is at least the height of z by minimality. Because the partition has defect 0, distinct tiles cannot share the same height (mondrian_perfect_height_injective), so height(z) < height(s). This implies C * p^a < C * p^b and thus a < b, so a + 1 ≤ b. Consequently, p^(a+1) divides p^b, so m = C * p^(a+1) divides C * p^b = height(s).
uses
mondrian_perfect_height_injective,Nat.pow_lt_pow_iff_right,Nat.mul_dvd_mul_left,pow_dvd_powhave hothers : ∀ s ∈ P, s ≠ z → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by intro s hs hne by_cases hsd : d ∣ mondrian_rect_width s · exact Or.inl hsd right obtain ⟨b, hsb⟩ := hheight s hs hsd have hmem : s ∈ S := by simp [S, hs, hsd] have hle := hzmin s hmem have hneq : mondrian_rect_height z ≠ mondrian_rect_height s := by intro he exact hne (mondrian_perfect_height_injective n P hP hz z hzP' s hs he).symm have hab : a < b := by have hlt : C * p ^ a < C * p ^ b := by rw [← hza, ← hsb]; omega have hpow : p ^ a < p ^ b := by nlinarith exact (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow rw [hsb] apply Nat.mul_dvd_mul_left exact pow_dvd_pow p (by omega : a + 1 ≤ b)
Contradiction: d divides the width of z, contradicting the choice of z.
The isolated height residue theorem states that if a tile z in an admissible partition has height indivisible by m, while all other tiles have width divisible by d or height divisible by m, then d must divide the width of z. Applying this theorem to z yields d ∣ width(z), contradicting the definition of z as an element of S.
uses
mondrian_partition_isolated_height_residueexact hzd (mondrian_partition_isolated_height_residue n d m P hP hdn z hzP' hzm hothers)
Finset.mem_filter.mp- If an element belongs to a filtered finset {x ∈ s | P x}, it belongs to s and satisfies the predicate P.
List.mem_toFinset.mp- If an element belongs to the finset of elements of a list, then it is an element of that list.
Nat.le_of_dvd- If a divides a positive integer b, then a ≤ b.
Nat.mul_lt_mul_of_pos_left- Strict inequality between natural numbers is preserved under multiplication by a strictly positive natural number on the left.
Nat.pow_lt_pow_iff_right- For a base strictly greater than 1, powers of that base are strictly ordered by their exponents.
mondrian_perfect_height_injective- In a defect-zero partition of a square, distinct tiles have distinct heights.
Nat.mul_dvd_mul_left- If b divides c, then a * b divides a * c for any natural number a.
pow_dvd_pow- In any monoid, if m ≤ n, then a^m divides a^n.
mondrian_partition_isolated_height_residue- In a partition of an n × n square with d ∣ n, if a tile r has height not divisible by m, and every other tile either has width divisible by d or height divisible by m, then d divides the width of 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_width_dvd_of_height_prime_chain (n d p C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hdn : d ∣ n) (hp : Nat.Prime p) (hC : 0 < C) (hheight : ∀ r ∈ P, ¬ d ∣ mondrian_rect_width r → ∃ a, mondrian_rect_height r = C * p ^ a) : ∀ r ∈ P, d ∣ mondrian_rect_width r := by have hp0 := hp.pos by_contra hh push_neg at hh obtain ⟨r, hr, hrd⟩ := hh let S := P.toFinset.filter (fun s => ¬ d ∣ mondrian_rect_width s) have hS : S.Nonempty := ⟨r, by simp [S, hr, hrd]⟩ obtain ⟨z, hzS, hzmin⟩ := S.exists_min_image mondrian_rect_height hS obtain ⟨hzP, hzd⟩ := Finset.mem_filter.mp hzS have hzP' : z ∈ P := List.mem_toFinset.mp hzP obtain ⟨a, hza⟩ := hheight z hzP' hzd let m := C * p ^ (a + 1) have hzm : ¬ m ∣ mondrian_rect_height z := by intro hm have hzpos : 0 < mondrian_rect_height z := by rw [hza]; positivity have hmle := Nat.le_of_dvd hzpos hm have hlt : mondrian_rect_height z < m := by rw [hza] dsimp [m] apply Nat.mul_lt_mul_of_pos_left _ hC exact (Nat.pow_lt_pow_iff_right hp.one_lt).mpr (by omega) omega have hothers : ∀ s ∈ P, s ≠ z → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by intro s hs hne by_cases hsd : d ∣ mondrian_rect_width s · exact Or.inl hsd right obtain ⟨b, hsb⟩ := hheight s hs hsd have hmem : s ∈ S := by simp [S, hs, hsd] have hle := hzmin s hmem have hneq : mondrian_rect_height z ≠ mondrian_rect_height s := by intro he exact hne (mondrian_perfect_height_injective n P hP hz z hzP' s hs he).symm have hab : a < b := by have hlt : C * p ^ a < C * p ^ b := by rw [← hza, ← hsb]; omega have hpow : p ^ a < p ^ b := by nlinarith exact (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow rw [hsb] apply Nat.mul_dvd_mul_left exact pow_dvd_pow p (by omega : a + 1 ≤ b) exact hzd (mondrian_partition_isolated_height_residue n d m P hP hdn z hzP' hzm hothers)