mondrian_no_perfect_two_prime_powers
For any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer rectangle partition.
Statement
theorem mondrian_no_perfect_two_prime_powers (p q e f : ℕ)
(hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) :
¬ ∃ P, mondrian_is_partition (q ^ f * p ^ e) P ∧ mondrian_defect P = 0- 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 14
- 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_no_perfect_prime_powerNo square whose integer side length is a prime power has a perfect admissible partition.
- 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_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
- 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_two_prime_divisor_encodingEvery divisor x of q^s times p^t, for distinct primes p and q, is q^b times p to the p-adic exponent of x, with b at most s.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
- 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…
The proof, explained
The proof proceeds by induction on the exponent f of the prime q. The base case f = 0 reduces to the known impossibility of a defect-0 partition for a single prime power. For the inductive step, a defect-0 partition forces all rectangles to have identical area A dividing the total square area (q^(f + 1) * p^e)^2, so A has only prime factors p and q. A divisibility property forces q to divide both the width and height of every rectangle in the partition. Scaling the entire partition down by q produces a defect-0 partition of a square of side q^f * p^e, contradicting the induction hypothesis.
The base case f = 0 holds: a square of side p^e has no defect-0 partition.
We argue by induction on the exponent f. When f = 0, the side length q^0 * p^e simplifies to p^e. The result mondrian_no_perfect_prime_power established that no prime-power square has a defect-0 partition.
uses
mondrian_no_perfect_prime_powerinduction f with | zero => simpa using mondrian_no_perfect_prime_power p e hp
Assume for induction that no defect-0 partition exists for side q^f * p^e, and suppose for contradiction that P is a defect-0 partition of side q^(f + 1) * p^e.
In the inductive step, we hypothesize ih (the non-existence of such a partition for exponent f) and assume a counterexample P of defect 0 for side q^(f + 1) * p^e.
| succ f ih => rintro ⟨P, hP, hz⟩The partition P contains at least one rectangle z.
By definition, any admissible partition contains at least 2 rectangles. Hence P cannot be empty, so P must have a head element z.
obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by cases P with | nil => have := hP.1; simp at this | cons z P => exact ⟨z, by simp⟩
Every rectangle in P has the same area A, equal to the area of z.
Let A be the area of z. Because P has defect 0, the difference between the maximum and minimum rectangle areas in P is 0, which by mondrian_defect_zero_equal implies that all rectangles in P have area exactly A.
uses
mondrian_defect_zero_equallet A := mondrian_rect_area z have hareas : ∀ r ∈ P, mondrian_rect_area r = A := fun r hr => mondrian_defect_zero_equal P hz r z hr hzP
The common rectangle area A divides q^(2 * (f + 1)) * p^(2 * e).
By mondrian_perfect_area_product, the total area (q^(f + 1) * p^e)^2 equals the number of rectangles times A, so A divides this total area. Expanding (q^(f + 1) * p^e)^2 using mul_pow and pow_mul yields q^(2 * (f + 1)) * p^(2 * e), which A divides by dvd_mul_left.
uses
mondrian_perfect_area_product,mul_pow,pow_mul,dvd_mul_lefthave heq := mondrian_perfect_area_product (q ^ (f + 1) * p ^ e) P hP hz z hzP have hdiv : A ∣ q ^ (2 * (f + 1)) * p ^ (2 * e) := by have hh : (q ^ (f + 1) * p ^ e) ^ 2 = q ^ (2 * (f + 1)) * p ^ (2 * e) := by rw [mul_pow, ← pow_mul, ← pow_mul] congr 1 <;> congr 1 <;> omega rw [← hh, ← heq] exact dvd_mul_left _ _
The area A factorizes as q^s * p^(ν_p(A)) for some exponent s ≤ 2 * (f + 1).
Because p and q are distinct primes and A divides q^(2 * (f + 1)) * p^(2 * e), mondrian_two_prime_divisor_encoding ensures that A is represented as q^s * p^(ν_p(A)) with s ≤ 2 * (f + 1).
uses
mondrian_two_prime_divisor_encodingobtain ⟨s, hs, hArep⟩ := mondrian_two_prime_divisor_encoding p q (2 * e) (2 * (f + 1)) A hp hq hpq hdivThe prime q divides both the width and the height of every rectangle in P.
Since f + 1 > 0, q divides the square side q^(f + 1) * p^e by dvd_pow_self and dvd_mul_of_dvd_left. Since every rectangle has area q^s * p^(ν_p(A)), the lemma mondrian_two_prime_area_sides_dvd shows that q divides both dimensions of every rectangle in P.
uses
dvd_mul_of_dvd_left,dvd_pow_self,mondrian_two_prime_area_sides_dvdhave hqn : q ∣ q ^ (f + 1) * p ^ e := dvd_mul_of_dvd_left (dvd_pow_self q (by omega : f + 1 ≠ 0)) _ have hd := mondrian_two_prime_area_sides_dvd (q ^ (f + 1) * p ^ e) p q s (A.factorization p) P hp hq hP hz hqn (by intro r hr; exact (hareas r hr).trans hArep)
The side length of the square partitioned by P can be expressed as q * (q^f * p^e).
Using pow_succ, the power q^(f + 1) is rewritten as q * q^f, so by associativity and commutativity of multiplication (Nat.mul_assoc, Nat.mul_left_comm, Nat.mul_comm), the side length is q * (q^f * p^e).
uses
pow_succ,Nat.mul_assoc,Nat.mul_left_comm,Nat.mul_commhave hP' : mondrian_is_partition (q * (q ^ f * p ^ e)) P := by simpa only [pow_succ, Nat.mul_assoc, Nat.mul_left_comm, Nat.mul_comm] using hP
Dividing every rectangle by q yields a defect-0 partition of side q^f * p^e, reaching a contradiction.
Because q is positive and divides both dimensions of every rectangle in P, mondrian_perfect_partition_div scales the partition down by q, producing a valid defect-0 partition of side q^f * p^e. This directly contradicts the induction hypothesis ih.
uses
mondrian_perfect_partition_divhave hQ := mondrian_perfect_partition_div q (q ^ f * p ^ e) hq.pos P hP' hz hd exact ih ⟨_, hQ⟩
mondrian_no_perfect_prime_power- A square whose side length is a prime power has no admissible partition of defect 0.
mondrian_defect_zero_equal- In any rectangle partition with defect 0, all rectangles have identical area.
mondrian_perfect_area_product- In a defect-0 partition of an n × n square, the number of rectangles times the area of any rectangle equals n^2.
mul_pow- In a commutative monoid, (a * b)^n = a^n * b^n.
pow_mul- In a monoid, a^(m * n) = (a^m)^n.
dvd_mul_left- For any element a in a commutative semigroup, a divides b * a.
mondrian_two_prime_divisor_encoding- Any positive divisor x of q^s * p^t (for distinct primes p and q) has prime power representation q^b * p^(ν_p(x)) with b ≤ s.
dvd_pow_self- Any element a divides a^n as long as n ≠ 0.
dvd_mul_of_dvd_left- If a divides b, then a divides b * c.
mondrian_two_prime_area_sides_dvd- In a defect-0 partition of an n × n square where q divides n and every rectangle has area q^s * p^t, q divides both the width and height of every rectangle.
pow_succ- For any element a and natural number n, a^(n + 1) = a^n * a.
Nat.mul_assoc- Multiplication of natural numbers is associative: (n * m) * k = n * (m * k).
Nat.mul_left_comm- Multiplication of natural numbers satisfies n * (m * k) = m * (n * k).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_perfect_partition_div- If a factor a divides both the width and height of every rectangle in a defect-0 partition of an (a * c) × (a * c) square (with a > 0), scaling each rectangle down by a produces a defect-0 partition of a c × c square.
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_two_prime_powers (p q e f : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) : ¬ ∃ P, mondrian_is_partition (q ^ f * p ^ e) P ∧ mondrian_defect P = 0 := by induction f with | zero => simpa using mondrian_no_perfect_prime_power p e hp | succ f ih => rintro ⟨P, hP, hz⟩ 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 A := mondrian_rect_area z have hareas : ∀ r ∈ P, mondrian_rect_area r = A := fun r hr => mondrian_defect_zero_equal P hz r z hr hzP have heq := mondrian_perfect_area_product (q ^ (f + 1) * p ^ e) P hP hz z hzP have hdiv : A ∣ q ^ (2 * (f + 1)) * p ^ (2 * e) := by have hh : (q ^ (f + 1) * p ^ e) ^ 2 = q ^ (2 * (f + 1)) * p ^ (2 * e) := by rw [mul_pow, ← pow_mul, ← pow_mul] congr 1 <;> congr 1 <;> omega rw [← hh, ← heq] exact dvd_mul_left _ _ obtain ⟨s, hs, hArep⟩ := mondrian_two_prime_divisor_encoding p q (2 * e) (2 * (f + 1)) A hp hq hpq hdiv have hqn : q ∣ q ^ (f + 1) * p ^ e := dvd_mul_of_dvd_left (dvd_pow_self q (by omega : f + 1 ≠ 0)) _ have hd := mondrian_two_prime_area_sides_dvd (q ^ (f + 1) * p ^ e) p q s (A.factorization p) P hp hq hP hz hqn (by intro r hr; exact (hareas r hr).trans hArep) have hP' : mondrian_is_partition (q * (q ^ f * p ^ e)) P := by simpa only [pow_succ, Nat.mul_assoc, Nat.mul_left_comm, Nat.mul_comm] using hP have hQ := mondrian_perfect_partition_div q (q ^ f * p ^ e) hq.pos P hP' hz hd exact ih ⟨_, hQ⟩