mondrian_no_perfect_three_prime_area_one_factor
For 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 natural a and s.
Statement
theorem mondrian_no_perfect_three_prime_area_one_factor (p q r a s n : ℕ)
(hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r)
(hpq : p ≠ q) (hqr : q ≠ r) (hpr : r + 1 < p)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
(hz : mondrian_defect P = 0)
(harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) : False- Related work
- For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 18
- mondrian_partition_width_dvd_of_height_two_chainsIf d divides the square side and all width-indivisible tiles have heights in two superincreasing chains C*p^a and C*r*p^a, with p>r+1 and…
- mondrian_prime_free_height_two_chain_encodingIf x*y=q^s*r*p^a for primes p,q,r with p≠r, and q does not divide x, then y lies in one of the chains q^s*p^b or q^s*r*p^b.
- 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…
- 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_partition_swapExchanging the x and y coordinate pairs of every rectangle preserves an admissible partition of the n-square.
- mondrian_rect_swapExchange the x and y coordinate pairs of an integer rectangle.
- mondrian_defect_zero_of_equalA rectangle list whose members all have the same area has defect zero, including the empty list.
- mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- 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_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_three_prime_common_area_sides_divideFor primes p,q,r with p>r+1, if q divides the square side and every tile in a perfect admissible partition has area q^s*r*p^a, then q…
- 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…
- 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_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
The proof, explained
The theorem is proved by strong induction on the exponent s of the prime q. When s = 0, the tile area involves only two distinct primes p and r, which is ruled out by an existing two-prime nonexistence theorem. When s > 0, the total area n^2 = |P| * (q^s * r * p^a) forces q to divide n, which geometrically implies that q divides both side lengths of every tile; hence q^2 divides the tile area, so s ≥ 2. Scaling all tile dimensions down by q produces a perfect partition of an (n/q) × (n/q) square with common tile area q^(s - 2) * r * p^a, contradicting the induction hypothesis at s - 2 < s.
The result is proved by strong induction on the exponent s.
We set up strong induction on s, generalizing over the square size n and the partition P. In the inductive step, we assume that no such perfect partition exists for any exponent m < s, and we seek a contradiction for the given exponent s.
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 * r * p^a = r^1 * p^a. Because p > r + 1, the primes p and r are distinct. The existing theorem mondrian_no_perfect_two_prime_area asserts that no perfect partition can have tiles of area r^1 * p^a involving only two distinct primes, which closes this case.
uses
mondrian_no_perfect_two_prime_area,pow_zero,one_mul,pow_oneby_cases hs0 : s = 0 · subst s exact mondrian_no_perfect_two_prime_area p r 1 a n hp hr (by omega) P hP hz (by simpa only [pow_zero, one_mul, pow_one] using harea)
The partition P contains at least one rectangle.
By definition, any admissible partition P must contain at least two rectangles (2 ≤ P.length). Thus P cannot be the empty list, and taking its first element provides a tile 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 q divides the square side length n.
For any tile z ∈ P, the total square area n^2 equals the number of tiles |P| times the tile area q^s * r * p^a. Since s ≠ 0, q divides q^s, which in turn divides n^2. Because q is prime, q ∣ n^2 implies q ∣ n.
uses
mondrian_perfect_area_product,dvd_mul_of_dvd_right,dvd_mul_of_dvd_left,dvd_pow_selfhave 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_mul_of_dvd_left (dvd_pow_self q hs0) _) _) _)
Every rectangle in P has both width and height divisible by q.
Applying mondrian_three_prime_common_area_sides_divide with the hypotheses that q ∣ n, p > r + 1, and each tile has area q^s * r * p^a guarantees that q divides both dimensions of every rectangle in P.
uses
mondrian_three_prime_common_area_sides_dividehave hd := mondrian_three_prime_common_area_sides_divide n p q r a s P hp hq hr hpr hP hz hqn hareaq^2 divides the tile area q^s * (r * p^a).
For the tile z ∈ P, both its width and height are multiples of q, so their product—the area of z—is a multiple of q^2. Since the area of z is q^s * (r * p^a), q^2 divides this product.
uses
pow_two,mondrian_rect_area,Nat.mul_dvd_mul,Nat.mul_assochave hqq : q ^ 2 ∣ q ^ s * (r * p ^ a) := by have hh : q ^ 2 ∣ mondrian_rect_area z := by simpa only [pow_two, mondrian_rect_area] using Nat.mul_dvd_mul (hd z hzP).1 (hd z hzP).2 simpa only [harea z hzP, Nat.mul_assoc] using hh
The prime q divides neither p nor r.
Since p is prime, any divisor of p is 1 or p. But q is prime (so q ≠ 1) and p ≠ q by assumption, hence q ∤ p. The exact same argument with r ≠ q and r prime shows q ∤ r.
uses
Nat.dvd_primehave hnotp : ¬ 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 hnotr : ¬ q ∣ r := by intro hh rcases (Nat.dvd_prime hr).mp hh with hh | hh · exact hq.ne_one hh · exact hqr hh
q^2 is coprime to r * p^a.
If the prime q divided r * p^a, it would have to divide r or p^a (and therefore p). Since we established q ∤ r and q ∤ p, q does not divide r * p^a. Consequently q is coprime to r * p^a, which implies q^2 is also coprime to r * p^a.
have hcop : (q ^ 2).Coprime (r * p ^ a) := (hq.coprime_iff_not_dvd.mpr (by intro hh rcases hq.dvd_mul.mp hh with hh | hh · exact hnotr hh · exact hnotp (hq.dvd_of_dvd_pow hh))).pow_left 2
The exponent s is at least 2.
We know that q^2 divides q^s * (r * p^a) and q^2 is coprime to r * p^a. By Gauss's lemma, q^2 must divide q^s. Since q > 1, q^2 ∣ q^s is equivalent to 2 ≤ s.
uses
Nat.pow_dvd_pow_iff_le_righthave hs2 : 2 ≤ s := (Nat.pow_dvd_pow_iff_le_right hq.one_lt).mp (hcop.dvd_mul_right.mp hqq)The tile area factors as q^2 * (q^(s - 2) * r * p^a).
Since s ≥ 2, we can split the power as q^s = q^2 * q^(s - 2) using exponent addition. Distributing over r * p^a gives the factorization q^s * r * p^a = q^2 * (q^(s - 2) * r * p^a).
uses
pow_addhave hsplit : q ^ s * r * p ^ a = q ^ 2 * (q ^ (s - 2) * r * p ^ a) := by have hh : q ^ s = q ^ 2 * q ^ (s - 2) := by rw [← pow_add] congr 1 omega rw [hh] ring
Rescaling by q yields a smaller valid partition, contradicting the induction hypothesis.
Because q ∣ n and q divides both dimensions of every tile in P, dividing all coordinates by q scales P down to a valid perfect partition Q of an (n / q) × (n / q) square with defect 0 and common tile area q^(s - 2) * r * p^a (by mondrian_perfect_partition_div_common_area). Since s ≥ 2, we have s - 2 < s, so the induction hypothesis applies to Q and produces False.
uses
mondrian_perfect_partition_div_common_areaobtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n q (q ^ s * r * p ^ a) (q ^ (s - 2) * r * p ^ a) P hq.pos hqn hP hz harea hsplit hd exact ih (s - 2) (by omega) (n / q) Q hQP hQZ hQA
Nat.strong_induction_on- Strong induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
mondrian_no_perfect_two_prime_area- No square admits a perfect partition into rectangles all having the same area q^s * p^t for distinct primes p and q.
pow_zero- Any element raised to the power 0 equals 1: a^0 = 1.
one_mul- Multiplying 1 by a yields a: 1 * a = a.
pow_one- Any element raised to the power 1 equals itself: a^1 = a.
mondrian_perfect_area_product- In any perfect partition of an n × n square, the number of rectangles multiplied by the area of any tile equals n^2.
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 number a divides a^n for any nonzero exponent n.
mondrian_three_prime_common_area_sides_divide- For distinct primes p, q, r with p > r + 1, if a perfect partition has common tile area q^s * r * p^a and q divides n, then q divides both dimensions of every tile.
pow_two- The square of a number equals its product with itself: a^2 = a * a.
mondrian_rect_area- The area of a rectangle is the product of its width and height.
Nat.mul_dvd_mul- If a divides b and c divides d, then a * c divides b * d.
Nat.mul_assoc- Multiplication on natural numbers is associative: (n * m) * k = n * (m * k).
Nat.dvd_prime- The only natural divisors of a prime number p are 1 and p.
Nat.pow_dvd_pow_iff_le_right- For x > 1, x^k divides x^l if and only if k ≤ l.
pow_add- Exponents add under multiplication of powers: a^(m + n) = a^m * a^n.
mondrian_perfect_partition_div_common_area- If every tile in a perfect partition of an n × n square has both sides divisible by q > 0 and common area q^2 * B, scaling down gives a perfect partition of an (n/q) × (n/q) square with common area B.
- The induction step scales both rectangle dimensions by q, which divides tile area by q^2; this decreases the exponent s to s - 2, which is why strong induction on s is used.
- The base case s = 0 reduces the area formula q^s * r * p^a to r * p^a, which involves only two distinct primes and is directly ruled out by the previously proved two-prime theorem.
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_three_prime_area_one_factor (p q r a s n : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpq : p ≠ q) (hqr : q ≠ r) (hpr : r + 1 < p) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) : 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_two_prime_area p r 1 a n hp hr (by omega) P hP hz (by simpa only [pow_zero, one_mul, pow_one] 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_mul_of_dvd_left (dvd_pow_self q hs0) _) _) _) have hd := mondrian_three_prime_common_area_sides_divide n p q r a s P hp hq hr hpr hP hz hqn harea have hqq : q ^ 2 ∣ q ^ s * (r * p ^ a) := by have hh : q ^ 2 ∣ mondrian_rect_area z := by simpa only [pow_two, mondrian_rect_area] using Nat.mul_dvd_mul (hd z hzP).1 (hd z hzP).2 simpa only [harea z hzP, Nat.mul_assoc] using hh have hnotp : ¬ 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 hnotr : ¬ q ∣ r := by intro hh rcases (Nat.dvd_prime hr).mp hh with hh | hh · exact hq.ne_one hh · exact hqr hh have hcop : (q ^ 2).Coprime (r * p ^ a) := (hq.coprime_iff_not_dvd.mpr (by intro hh rcases hq.dvd_mul.mp hh with hh | hh · exact hnotr hh · exact hnotp (hq.dvd_of_dvd_pow hh))).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 * r * p ^ a = q ^ 2 * (q ^ (s - 2) * r * p ^ a) := by have hh : q ^ s = q ^ 2 * q ^ (s - 2) := by rw [← pow_add] congr 1 omega rw [hh] ring obtain ⟨Q, hQP, hQZ, hQA⟩ := mondrian_perfect_partition_div_common_area n q (q ^ s * r * p ^ a) (q ^ (s - 2) * r * p ^ a) P hq.pos hqn hP hz harea hsplit hd exact ih (s - 2) (by omega) (n / q) Q hQP hQZ hQA