mondrian_no_perfect_two_prime_area
For any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile area q^s*p^t.
Statement
theorem mondrian_no_perfect_two_prime_area (p q s t n : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hpq : p ≠ q) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)
(harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) : False- Related work
- 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
- 27 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_no_perfect_prime_power_areaNo perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
- 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_no_perfect_three_prime_area_one_factorFor three distinct primes p,q,r with p>r+1, no perfect admissible integer square partition has common tile area q^s*r*p^a, for arbitrary…
- mondrian_perfect_area_three_prime_factorsEvery tile area in a perfect admissible integer square partition has at least three distinct prime factors.
Read back from the Lean
For any natural numbers p, q, s, t, and n, assuming:
1. p is prime (Nat.Prime p),
2. q is prime (Nat.Prime q),
3. p ≠ q,
4. P is a list of 4-tuples of natural numbers representing rectangles,
5. P is a valid Mondrian partition of an n × n square (mondrian_is_partition n P),
6. The Mondrian defect of P is 0 (mondrian_defect P = 0), and
7. Every rectangle r in P has area q ^ s * p ^ t (∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t),
the theorem derives a contradiction (False).
In other words, no n × n grid can be partitioned into at least two pairwise disjoint, pairwise non-congruent axis-aligned rectangles that all have the same area of the form q^s * p^t for distinct primes p and q.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof is by strong induction on the exponent s of the prime q. When s = 0, the common tile area is the single prime power p^t, which is impossible by an established theorem on prime-power tiles. When s > 0, the total area formula shows that q divides the side length n, which forces q to divide both the width and the height of every tile in the partition. Consequently, q^2 divides the tile area q^s * p^t, and because p and q are distinct primes, this forces s ≥ 2. Dividing all rectangle dimensions by q produces a smaller square of side n/q with an admissible partition of common tile area q^(s - 2) * p^t, contradicting the induction hypothesis.
The proof proceeds by strong induction on the exponent s, generalizing over the square side n and partition P.
We apply strong induction on s via `Nat.strong_induction_on`. The induction hypothesis ih states that for any smaller exponent m < s, any square size, and any partition whose rectangles all have area q^m * p^t, no perfect admissible partition exists.
uses
Nat.strong_induction_oninduction s using Nat.strong_induction_on generalizing n P with | h s ih =>
The base case s = 0 is impossible.
When s = 0, the common tile area simplifies to q^0 * p^t = p^t. The lemma `mondrian_no_perfect_prime_power_area` proves that no integer square admits a perfect partition into rectangles of equal prime-power area, immediately yielding False.
uses
mondrian_no_perfect_prime_power_areaby_cases hs0 : s = 0 · subst s exact mondrian_no_perfect_prime_power_area p t n hp P hP hz (by simpa using harea)
The partition P contains at least one tile z, and |P| * (q^s * p^t) = n^2.
An admissible partition must contain at least 2 tiles, so P cannot be empty; let z ∈ P be an arbitrary tile. By `mondrian_perfect_area_product`, the number of tiles |P| times the area of z equals the total square area n^2. Substituting the common tile area harea gives |P| * (q^s * p^t) = n^2.
uses
mondrian_perfect_area_productobtain ⟨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
The prime q divides the square side length n.
Since s ≠ 0, q divides q^s by `dvd_pow_self`, and thus q divides |P| * (q^s * p^t) = n^2 via `dvd_mul_of_dvd_right` and `dvd_mul_of_dvd_left`. Because q is prime, q ∣ n^2 implies q ∣ n.
uses
dvd_mul_of_dvd_right,dvd_mul_of_dvd_left,dvd_pow_selfhave hqn : q ∣ n := hq.dvd_of_dvd_pow (show q ∣ n ^ 2 by rw [← heq] exact dvd_mul_of_dvd_right (dvd_mul_of_dvd_left (dvd_pow_self q hs0) _) _)
The prime q divides both the width and the height of every tile in P.
Knowing q ∣ n and that all tile areas equal q^s * p^t, the lemma `mondrian_two_prime_area_sides_dvd` shows that q divides both dimensions of every rectangle r ∈ P.
uses
mondrian_two_prime_area_sides_dvdhave hd := mondrian_two_prime_area_sides_dvd n p q s t P hp hq hP hz hqn hareaThe prime square q^2 divides the tile area q^s * p^t.
For tile z, q divides its width and q divides its height. Multiplying these divisibility relations via `Nat.mul_dvd_mul` shows that q^2 divides width(z) * height(z) = area(z) = q^s * p^t.
uses
pow_two,Nat.mul_dvd_mulhave hqq : q ^ 2 ∣ q ^ s * 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
The exponent s is at least 2.
If q divided p, then by `Nat.dvd_prime` either q = 1 (impossible since q is prime) or q = p (contradicting p ≠ q); thus q ∤ p. Hence q is coprime to p, and so q^2 is coprime to p^t. Since q^2 ∣ q^s * p^t and gcd(q^2, p^t) = 1, it follows that q^2 ∣ q^s. Since q > 1, `Nat.pow_dvd_pow_iff_le_right` implies 2 ≤ s.
uses
Nat.dvd_prime,Nat.pow_dvd_pow_iff_le_righthave hnot : ¬ q ∣ p := by intro hh rcases (Nat.dvd_prime hp).mp hh with hh | hh · exact hq.ne_one hh · exact hpq hh.symm have hcop : (q ^ 2).Coprime (p ^ t) := ((hq.coprime_iff_not_dvd.mpr hnot).pow_right t).pow_left 2 have hs2 : 2 ≤ s := (Nat.pow_dvd_pow_iff_le_right hq.one_lt).mp (hcop.dvd_mul_right.mp hqq)
The common tile area factors as q^s * p^t = q^2 * (q^(s - 2) * p^t).
Since s ≥ 2, we have s = 2 + (s - 2). By `pow_add`, q^s = q^2 * q^(s - 2). Reassociating multiplication with `Nat.mul_assoc` gives q^s * p^t = q^2 * (q^(s - 2) * p^t).
uses
pow_add,Nat.mul_assochave hsplit : q ^ s * p ^ t = q ^ 2 * (q ^ (s - 2) * p ^ t) := by have hh : q ^ s = q ^ 2 * q ^ (s - 2) := by rw [← pow_add]; congr 1; omega rw [hh, Nat.mul_assoc]
There exists a perfect partition Q of an (n / q) × (n / q) square with tile area q^(s - 2) * p^t.
Because q > 0, q ∣ n, every tile has both side lengths divisible by q, and the tile area factors as q^2 * (q^(s - 2) * p^t), `mondrian_perfect_partition_div_common_area` rescales each tile's dimensions by q, producing an admissible partition Q of the scaled square with defect 0 and common tile area q^(s - 2) * p^t.
uses
mondrian_perfect_partition_div_common_areaobtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n q (q ^ s * p ^ t) (q ^ (s - 2) * p ^ t) P hq.pos hqn hP hz harea hsplit hdThe existence of Q contradicts the induction hypothesis, completing the proof.
Since s ≥ 2, we have s - 2 < s. Applying the induction hypothesis ih to exponent s - 2, square side n / q, and partition Q derives False.
exact ih (s - 2) (by omega) (n / q) Q hQP hQZ hQA
dvd_mul_of_dvd_right- If a divides b, then a divides c * b.
dvd_mul_of_dvd_left- If a divides b, then a divides b * c.
dvd_pow_self- Any nonzero power a^n of a is divisible by a.
pow_two- The square of an element equals the element multiplied by itself: a^2 = a * a.
pow_add- Exponents add when multiplying powers with the same base: a^(m + n) = a^m * a^n.
Nat.mul_assoc- Multiplication of natural numbers is associative: n * m * k = n * (m * k).
Nat.strong_induction_on- The principle of strong induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) for all m < n.
Nat.mul_dvd_mul- If a divides b and c divides d, then a * c divides b * d.
Nat.dvd_prime- A natural number m divides a prime p if and only if m = 1 or m = p.
Nat.pow_dvd_pow_iff_le_right- For any base x > 1, x^k divides x^l if and only if k ≤ l.
mondrian_no_perfect_prime_power_area- No integer square admits a perfect admissible partition where every tile has the same prime-power area p^t.
mondrian_perfect_area_product- In any perfect partition of an n × n square, the number of tiles times the area of any tile equals n^2.
mondrian_two_prime_area_sides_dvd- If an n × n square with q ∣ n has a perfect partition where every tile has area q^s * p^t, then q divides both the width and height of every tile.
mondrian_perfect_partition_div_common_area- Given a perfect partition of an n × n square whose tiles have area A = q^2 * B with side lengths all divisible by q, dividing coordinates by q yields a perfect partition of an (n/q) × (n/q) square with common tile area B.
- The base case simplification of q^0 * p^t to p^t on line 9 is handled by `simpa`.
- The linear natural number arithmetic facts that s = 2 + (s - 2) (line 33) and s - 2 < s (line 37) given 2 ≤ s are closed by the Presburger arithmetic tactic `omega`.
- The deduction that q ∣ n from q ∣ n^2 for prime q on line 16 uses `hq.dvd_of_dvd_pow`, and the coprimality of q^2 and p^t on lines 29–30 is established by lifting coprimality across powers.
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_area (p q s t n : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) : False := by induction s using Nat.strong_induction_on generalizing n P with | h s ih => by_cases hs0 : s = 0 · subst s exact mondrian_no_perfect_prime_power_area p t n hp P hP hz (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 hqn : q ∣ n := hq.dvd_of_dvd_pow (show q ∣ n ^ 2 by rw [← heq] exact dvd_mul_of_dvd_right (dvd_mul_of_dvd_left (dvd_pow_self q hs0) _) _) have hd := mondrian_two_prime_area_sides_dvd n p q s t P hp hq hP hz hqn harea have hqq : q ^ 2 ∣ q ^ s * 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 hnot : ¬ q ∣ p := by intro hh rcases (Nat.dvd_prime hp).mp hh with hh | hh · exact hq.ne_one hh · exact hpq hh.symm have hcop : (q ^ 2).Coprime (p ^ t) := ((hq.coprime_iff_not_dvd.mpr hnot).pow_right t).pow_left 2 have hs2 : 2 ≤ s := (Nat.pow_dvd_pow_iff_le_right hq.one_lt).mp (hcop.dvd_mul_right.mp hqq) have hsplit : q ^ s * p ^ t = q ^ 2 * (q ^ (s - 2) * p ^ t) := by have hh : q ^ s = q ^ 2 * q ^ (s - 2) := by rw [← pow_add]; congr 1; omega rw [hh, Nat.mul_assoc] obtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n q (q ^ s * p ^ t) (q ^ (s - 2) * p ^ t) P hq.pos hqn hP hz harea hsplit hd exact ih (s - 2) (by omega) (n / q) Q hQP hQZ hQA