mondrian_no_perfect_prime_power_area
No perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
Statement
theorem mondrian_no_perfect_prime_power_area (p t n : ℕ) (hp : Nat.Prime p)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
(hz : mondrian_defect P = 0) (harea : ∀ r ∈ P, mondrian_rect_area r = p ^ t) : False- 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 11
- 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_area_one_impossibleAn admissible square partition cannot have every tile of area one.
- mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- mondrian_perfect_partition_div_common_areaIf q divides the square side and both dimensions of every tile in a perfect partition, and the common area is q^2 times B, coordinate…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_two_prime_area_sides_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are…
- 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_heightThe height y₁ − y₀ 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…
- Used by 2
- mondrian_perfect_area_three_prime_factorsEvery tile area in a perfect admissible integer square partition has at least three distinct prime factors.
- mondrian_no_perfect_two_prime_areaFor any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile…
The proof, explained
The theorem is proved by strong induction on the exponent t. When t = 0, all tiles would have area 1, which is impossible because an admissible partition requires at least two non-congruent rectangles. When t ≥ 1, the total area relation forces p to divide n, which by a geometric divisibility lemma implies that p divides both the width and height of every rectangle, so p^2 divides p^t and hence t ≥ 2. Scaling the entire configuration down by a factor of p yields an admissible perfect partition of an (n/p) × (n/p) square with common tile area p^(t-2), contradicting the strong induction hypothesis.
The proof proceeds by strong induction on the exponent t, generalizing over the square dimension n and the partition P.
We apply strong induction on t using Nat.strong_induction_on, which allows us to assume as inductive hypothesis that no defect-zero partition exists with common tile area p^m for any m < t, for any square size and partition.
uses
Nat.strong_induction_oninduction t using Nat.strong_induction_on generalizing n P with | h t ih =>
The base case t = 0 is impossible.
If t = 0, every rectangle has area p^0 = 1. By mondrian_partition_area_one_impossible, an admissible partition cannot consist entirely of 1 × 1 rectangles, because it requires at least two pairwise non-congruent rectangles.
uses
mondrian_partition_area_one_impossibleby_cases ht0 : t = 0 · subst t exact mondrian_partition_area_one_impossible n P hP (by simpa using harea)
The partition P contains at least one rectangle z.
By the definition of an admissible partition, P has length at least 2, so it cannot be empty. We pick an element z ∈ 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⟩
The prime p divides the square's side length n.
By mondrian_perfect_area_product, the total area equation is |P| * p^t = n^2. Since t ≠ 0, p divides p^t by dvd_pow_self, so p divides |P| * p^t by dvd_mul_of_dvd_right, which means p ∣ n^2. Because p is prime, p divides n.
uses
mondrian_perfect_area_product,dvd_pow_self,dvd_mul_of_dvd_righthave heq := mondrian_perfect_area_product n P hP hz z hzP rw [harea z hzP] at heq have hpn : p ∣ n := hp.dvd_of_dvd_pow (show p ∣ n ^ 2 by rw [← heq] exact dvd_mul_of_dvd_right (dvd_pow_self p ht0) _)
The prime p divides both the width and height of every rectangle in P.
We invoke mondrian_two_prime_area_sides_dvd with prime q = p, second prime 2 (using Nat.prime_two), exponent s = t, and exponent 0 for 2. Since p ∣ n and each tile has area p^t = p^t * 2^0, p divides both dimensions of every tile.
uses
mondrian_two_prime_area_sides_dvd,Nat.prime_twohave hd := mondrian_two_prime_area_sides_dvd n 2 p t 0 P Nat.prime_two hp hP hz hpn (by simpa using harea)
The exponent t satisfies 2 ≤ t.
Because p divides both the width and height of tile z, p^2 divides the tile area mondrian_rect_area z = p^t by Nat.mul_dvd_mul and pow_two. Since p > 1, Nat.pow_dvd_pow_iff_le_right implies 2 ≤ t.
uses
pow_two,Nat.mul_dvd_mul,Nat.pow_dvd_pow_iff_le_righthave hpp : p ^ 2 ∣ p ^ t := by rw [← harea z hzP] simpa only [pow_two, mondrian_rect_area] using Nat.mul_dvd_mul (hd z hzP).1 (hd z hzP).2 have ht2 : 2 ≤ t := (Nat.pow_dvd_pow_iff_le_right hp.one_lt).mp hpp
The tile area factors as p^t = p^2 * p^(t - 2).
Since 2 ≤ t, we have t = 2 + (t - 2) by linear arithmetic, so pow_add yields p^t = p^2 * p^(t - 2).
uses
pow_addhave hsplit : p ^ t = p ^ 2 * p ^ (t - 2) := by rw [← pow_add] congr 1 omega
Scaling down by p produces a defect-zero partition Q of an (n/p) × (n/p) square with common tile area p^(t - 2).
Since 0 < p, p ∣ n, every tile in P has width and height divisible by p, and the tile area factors as p^2 * p^(t - 2), mondrian_perfect_partition_div_common_area scales down the partition by p, yielding an admissible defect-zero partition Q of an (n/p) × (n/p) square with common tile area p^(t - 2).
uses
mondrian_perfect_partition_div_common_areaobtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n p (p ^ t) (p ^ (t - 2)) P hp.pos hpn hP hz harea hsplit hdA contradiction is reached via the induction hypothesis.
Because 2 ≤ t and t ≠ 0, we have t - 2 < t. The strong induction hypothesis applied to exponent t - 2, side length n/p, and partition Q yields False, completing the proof.
exact ih (t - 2) (by omega) (n / p) Q hQP hQZ hQA
Nat.strong_induction_on- Well-founded strong induction on ℕ: to prove a property holds for all n, it suffices to show that its holding for all m < n implies it holds for n.
mondrian_partition_area_one_impossible- No admissible partition of an n × n square can consist entirely of unit-area (1 × 1) rectangles.
mondrian_perfect_area_product- In any zero-defect partition of an n × n square, the number of rectangles multiplied by the area of any rectangle equals the total area n^2.
dvd_pow_self- For any non-zero exponent n, a number a divides a^n.
dvd_mul_of_dvd_right- If a divides b, then a divides c * b for any c.
mondrian_two_prime_area_sides_dvd- In a zero-defect partition of an n × n square where prime q divides n and all tile areas equal q^s * p^t, q divides both the width and height of every rectangle.
Nat.prime_two- The number 2 is prime.
pow_two- The square of a number a^2 equals a * a.
Nat.mul_dvd_mul- If a divides b and c divides d, then a * c divides b * d.
Nat.pow_dvd_pow_iff_le_right- For an integer base x > 1, x^k divides x^l if and only if k ≤ l.
pow_add- Exponentiation turns addition of exponents into multiplication: a^(m + n) = a^m * a^n.
mondrian_perfect_partition_div_common_area- Scaling down a zero-defect partition of an n × n square by a factor of q (when q divides n and both dimensions of every rectangle) yields a zero-defect partition of an (n/q) × (n/q) square with common tile area divided by q^2.
- The auxiliary lemma mondrian_two_prime_area_sides_dvd is formulated for areas factoring into two prime powers q^s * p^t; here it is instantiated with q = p and the second prime dummy-set to 2 with exponent 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.
theorem mondrian_no_perfect_prime_power_area (p t n : ℕ) (hp : Nat.Prime p) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (harea : ∀ r ∈ P, mondrian_rect_area r = p ^ t) : False := by induction t using Nat.strong_induction_on generalizing n P with | h t ih => by_cases ht0 : t = 0 · subst t exact mondrian_partition_area_one_impossible n P hP (by simpa using harea) obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by cases P with | nil => have := hP.1; simp at this | cons z P => exact ⟨z, by simp⟩ have heq := mondrian_perfect_area_product n P hP hz z hzP rw [harea z hzP] at heq have hpn : p ∣ n := hp.dvd_of_dvd_pow (show p ∣ n ^ 2 by rw [← heq] exact dvd_mul_of_dvd_right (dvd_pow_self p ht0) _) have hd := mondrian_two_prime_area_sides_dvd n 2 p t 0 P Nat.prime_two hp hP hz hpn (by simpa using harea) have hpp : p ^ 2 ∣ p ^ t := by rw [← harea z hzP] simpa only [pow_two, mondrian_rect_area] using Nat.mul_dvd_mul (hd z hzP).1 (hd z hzP).2 have ht2 : 2 ≤ t := (Nat.pow_dvd_pow_iff_le_right hp.one_lt).mp hpp have hsplit : p ^ t = p ^ 2 * p ^ (t - 2) := by rw [← pow_add] congr 1 omega obtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n p (p ^ t) (p ^ (t - 2)) P hp.pos hpn hP hz harea hsplit hd exact ih (t - 2) (by omega) (n / p) Q hQP hQZ hQA