mondrian_no_perfect_prime_mul_prime_pow
For every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer rectangle partition.
Statement
theorem mondrian_no_perfect_prime_mul_prime_pow (p q e : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hpq : p ≠ q) :
¬ ∃ P, mondrian_is_partition (q * p ^ e) P ∧ mondrian_defect P = 0- Related work
- Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 26
- 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_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- 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_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_partition_prime_free_shape_count_boundIn an admissible equal-area partition, any selected collection of tiles each having a side indivisible by q has cardinality at most the…
- 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_perfect_prime_free_side_countsIn any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not…
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- mondrian_prime_free_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of pure p-power area p^t fit in the q times p^e…
- mondrian_prime_log_gapFor distinct primes p and q, p to floor(log_p(q)) is strictly less than q, q is below the next power, and floor(log_p(q)) plus one is…
- mondrian_prime_square_area_free_shape_boundFor distinct primes p and q and t+r=2e, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square have a side…
- mondrian_prime_square_area_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most 2r unordered shapes of area q^2 times p^t fit in the q times p^e square.
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- 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₁).
- mondrian_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
- mondrian_twice_exponent_lt_prime_powerFor p at least two and r at least three, p^r is greater than twice r.
- mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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_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…
Read back from the Lean
For all natural numbers $p$, $q$, and $e$, if $p$ is prime, $q$ is prime, and $p \neq q$, then there does not exist a list $P$ of rectangles (4-tuples of natural numbers) such that $P$ is a valid Mondrian partition of a $(q \cdot p^e) \times (q \cdot p^e)$ square and the Mondrian defect of $P$ is 0.
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 proceeds by contradiction: suppose an admissible partition P of the square of side q * p^e has defect 0. The total area equation k * A = q^2 * p^(2e) forces the number of rectangles k and their common area A to factor as k = q^b * p^r and A = q^s * p^t with b + s = 2 and r + t = 2e. Because rectangles must have incongruent shapes, k is bounded by the number of valid factor shapes of area A. If s = 2, the shape bound implies p^r ≤ 2r, forcing p = 2 and r ≤ 2 < q; divisibility constraints then require every rectangle side to be a multiple of q, so scaling by 1/q would yield a defect-0 partition of the square of side p^e, which is known to be impossible. If s ≤ 1, then k ≥ q * p^r, which strictly exceeds the upper bound r + Nat.log p q + 1 on the number of shapes of area A, yielding an arithmetic contradiction.
Assume for contradiction that there exists a defect-0 partition P of the square of side q * p^e, and select an arbitrary rectangle z in P.
We assume for contradiction that an admissible partition P exists with defect 0. By the definition of an admissible partition, P has length at least 2, so it cannot be empty. Case analysis on P allows us to select an arbitrary rectangle z ∈ P.
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⟩
Every rectangle in P has the same positive area A, and the partition length k satisfies k ≥ 2.
We define k = |P|, A as the area of z, r = ν_p(k), and t = ν_p(A). The partition definition gives k ≥ 2. By `mondrian_partition_bounds`, the width and height of z are strictly positive, so by `Nat.mul_pos`, A > 0. Since the defect of P is 0, `mondrian_defect_zero_equal` implies that every rectangle in P has area A.
uses
mondrian_partition_bounds,Nat.mul_pos,mondrian_defect_zero_equallet k := P.length let A := mondrian_rect_area z let r := k.factorization p let t := A.factorization p have hk : 2 ≤ k := hP.1 have hzb := mondrian_partition_bounds (q * p ^ e) P hP z hzP have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1 have hareas : ∀ w ∈ P, mondrian_rect_area w = A := fun w hw => mondrian_defect_zero_equal P hz w z hw hzP
The total area equation k * A = q^2 * p^(2e) holds, and k is bounded by the number of factor shapes of area A.
By `mondrian_perfect_area_product`, the sum of areas k * A equals the square of the board side length, (q * p^e)^2 = q^2 * p^(2e), rewritten using `mul_pow`, `pow_mul`, and `Nat.mul_comm`. Because no two rectangles in P are congruent, each must correspond to a distinct factor shape of area A bounded by side q * p^e, so `mondrian_shape_bound` gives k ≤ |mondrian_factor_shapes (q * p^e) A|.
uses
mondrian_perfect_area_product,mul_pow,pow_mul,Nat.mul_comm,mondrian_shape_boundhave heq : k * A = q ^ 2 * p ^ (2 * e) := by have hh := mondrian_perfect_area_product (q * p ^ e) P hP hz z hzP change k * A = (q * p ^ e) ^ 2 at hh rw [hh, mul_pow, ← pow_mul, Nat.mul_comm e 2] have hcard : k ≤ (mondrian_factor_shapes (q * p ^ e) A).card := mondrian_shape_bound (q * p ^ e) A P hP hareas
The parameters factor as k = q^b * p^r and A = q^s * p^t with b + s = 2, r + t = 2e, and s ≤ 2.
Applying `mondrian_two_prime_factor_pair_encoding` to k * A = q^2 * p^(2e) with distinct primes p and q yields exponents b and s summing to 2 such that k = q^b * p^r, A = q^s * p^t, and r + t = 2e. Linear arithmetic immediately implies s ≤ 2.
uses
mondrian_two_prime_factor_pair_encodingobtain ⟨b, s, hbs, hkrep, hArep, hrt⟩ := mondrian_two_prime_factor_pair_encoding p q (2 * e) 2 k A hp hq hpq (by omega) hA heq change k = q ^ b * p ^ r at hkrep change A = q ^ s * p ^ t at hArep change r + t = 2 * e at hrt have hs : s ≤ 2 := by omega
In the case s = 2, we have b = 0, k = p^r with r > 0, and p^r ≤ 2r.
We split into cases based on whether s = 2. When s = 2, b + s = 2 forces b = 0, which reduces k = q^b * p^r to k = p^r via `pow_zero` and `one_mul`. If r were 0, k would be 1, contradicting k ≥ 2, so r > 0. In this case, A = q^2 * p^t. Applying `mondrian_prime_square_area_shape_bound` bounds the number of shapes by 2r, so k ≤ 2r gives p^r ≤ 2r.
uses
pow_zero,one_mul,mondrian_prime_square_area_shape_boundby_cases hs2 : s = 2 · have hb : b = 0 := by omega have hkp : k = p ^ r := by simpa only [hb, pow_zero, one_mul] using hkrep have hrpos : 0 < r := by by_contra hh have hr0 : r = 0 := by omega simp [hkp, hr0] at hk have hcap := mondrian_prime_square_area_shape_bound p q e t r hp hq hpq (by omega) hrpos have hArep' : A = q ^ 2 * p ^ t := by simpa only [hs2] using hArep rw [hArep'] at hcard have hpowcap : p ^ r ≤ 2 * r := by omega
When s = 2, the inequality p^r ≤ 2r forces r ≤ 2, p = 2, and q ≥ 3.
If r were 3 or larger, `mondrian_twice_exponent_lt_prime_power` would give 2r < p^r, contradicting p^r ≤ 2r; thus r ≤ 2. Testing the remaining values r = 1 and r = 2 against p^r ≤ 2r with p ≥ 2 forces p = 2. Since p and q are distinct primes, q ≠ 2, so q ≥ 3.
uses
mondrian_twice_exponent_lt_prime_powerhave hrle : r ≤ 2 := by by_contra hh have hgap := mondrian_twice_exponent_lt_prime_power p r hp.two_le (by omega) omega have hp2 : p = 2 := by interval_cases r · norm_num at hpowcap; have := hp.two_le; omega · norm_num at hpowcap; have := hp.two_le; nlinarith have hq3 : 3 ≤ q := by have := hq.two_le; omega
When s = 2, every rectangle in P has both width and height divisible by q.
By `mondrian_prime_square_area_free_shape_bound`, the number of factor shapes of A = q^2 * p^t where at least one dimension is not divisible by q is at most r. Applying `mondrian_partition_prime_free_shape_count_bound` with `Or.inl` and `Or.inr` (using `of_decide_eq_true`) shows that the number of rectangles in P whose width is not divisible by q (and similarly for height) is at most r. However, `mondrian_perfect_prime_free_side_counts` with `dvd_mul_right` proves this count is a multiple of q. Because r ≤ 2 < 3 ≤ q, `Nat.eq_zero_of_dvd_of_lt` forces both counts to be 0.
uses
mondrian_prime_square_area_free_shape_bound,mondrian_perfect_prime_free_side_counts,dvd_mul_right,mondrian_partition_prime_free_shape_count_bound,Or.inl,of_decide_eq_true,Or.inr,Nat.eq_zero_of_dvd_of_lthave houter := mondrian_prime_square_area_free_shape_bound p q e t r hp hq hpq (by omega) have hcnt := mondrian_perfect_prime_free_side_counts (q * p ^ e) q P hq (dvd_mul_right q (p ^ e)) hP hz have hwidth := mondrian_partition_prime_free_shape_count_bound (q * p ^ e) A q P hP hareas (fun w => decide (¬ q ∣ mondrian_rect_width w)) (by intro w hw hh exact Or.inl (of_decide_eq_true hh)) have hheight := mondrian_partition_prime_free_shape_count_bound (q * p ^ e) A q P hP hareas (fun w => decide (¬ q ∣ mondrian_rect_height w)) (by intro w hw hh exact Or.inr (of_decide_eq_true hh)) rw [hArep'] at hwidth hheight have hwidth0 : P.countP (fun w => decide (¬ q ∣ mondrian_rect_width w)) = 0 := Nat.eq_zero_of_dvd_of_lt hcnt.1 (by omega) have hheight0 : P.countP (fun w => decide (¬ q ∣ mondrian_rect_height w)) = 0 := Nat.eq_zero_of_dvd_of_lt hcnt.2 (by omega)
Dividing all rectangle dimensions by q produces a defect-0 partition of the square of side p^e, which contradicts the prime-power theorem.
Using `List.countP_eq_zero.mp` and `And.intro`, every rectangle in P has its width and height divisible by q. Applying `mondrian_perfect_partition_div` scales the partition by 1/q to yield a defect-0 partition of the square of side p^e. But `mondrian_no_perfect_prime_power` proves no such partition exists for any prime power, completing the contradiction for the case s = 2.
uses
List.countP_eq_zero.mp,And.intro,mondrian_perfect_partition_div,mondrian_no_perfect_prime_powerhave hd : ∀ w ∈ P, q ∣ mondrian_rect_width w ∧ q ∣ mondrian_rect_height w := by intro w hw have h1 := List.countP_eq_zero.mp hwidth0 w hw have h2 := List.countP_eq_zero.mp hheight0 w hw simpa using And.intro h1 h2 have hdiv := mondrian_perfect_partition_div q (p ^ e) hq.pos P hP hz hd exact mondrian_no_perfect_prime_power p e hp ⟨_, hdiv⟩
In the remaining case s ≤ 1, the number of factor shapes of area A is at most r + Nat.log p q + 1.
Since s ≤ 2 and s ≠ 2, we have s ≤ 1, leaving the possibilities s = 0 and s = 1. If s = 0, A = p^t, and `mondrian_prime_free_area_shape_bound` gives the bound r + Nat.log p q + 1. If s = 1, A = q * p^t, and `mondrian_prime_area_shape_bound` provides the same upper bound r + Nat.log p q + 1.
uses
mondrian_prime_free_area_shape_bound,mondrian_prime_area_shape_bound· have hsle : s ≤ 1 := by omega have hcap : (mondrian_factor_shapes (q * p ^ e) A).card ≤ r + Nat.log p q + 1 := by interval_cases s · have hArep' : A = p ^ t := by simpa using hArep rw [hArep'] exact mondrian_prime_free_area_shape_bound p q e t r hp hq hpq (by omega) · have hArep' : A = q * p ^ t := by simpa using hArep rw [hArep'] exact mondrian_prime_area_shape_bound p q e t r hp hq hpq (by omega)
The lower bound k ≥ q * p^r contradicts the shape upper bound k ≤ r + Nat.log p q + 1, completing the proof. automation
Since b + s = 2 and s ≤ 1, we have b ≥ 1, so q ≤ q^b by `Nat.le_of_dvd`, `pow_pos`, and `dvd_pow_self`. Then `Nat.mul_le_mul_right` gives k = q^b * p^r ≥ q * p^r. Using `mondrian_prime_log_gap` to get Nat.log p q + 1 < q and `Nat.lt_pow_self` to get r + 1 ≤ p^r, nonlinear arithmetic (`nlinarith`) derives the contradiction q * p^r ≥ q * (r + 1) = q * r + q > r + q > r + Nat.log p q + 1 ≥ k.
uses
Nat.le_of_dvd,pow_pos,dvd_pow_self,Nat.mul_le_mul_right,mondrian_prime_log_gap,Nat.lt_pow_selfhave hqb : q ≤ q ^ b := Nat.le_of_dvd (pow_pos hq.pos b) (dvd_pow_self q (by omega : b ≠ 0)) have hlarge : q * p ^ r ≤ k := by rw [hkrep]; exact Nat.mul_le_mul_right _ hqb have hlog := (mondrian_prime_log_gap p q hp hq hpq).2.2 have hpow : r + 1 ≤ p ^ r := by have := Nat.lt_pow_self (n := r) hp.one_lt; omega nlinarith
mondrian_partition_bounds- In an admissible partition of a board of side n, every rectangle has width and height strictly positive and at most n.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
mondrian_defect_zero_equal- In a partition with defect 0, all rectangles have identical area.
mondrian_perfect_area_product- In a defect-0 partition of an n × n square, the product of the number of rectangles and 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).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_shape_bound- In an admissible partition where every rectangle has area A, the number of rectangles cannot exceed the number of factor shapes (d₁, d₂) with d₁ * d₂ = A and d₁ ≤ d₂ ≤ n.
mondrian_two_prime_factor_pair_encoding- If x * y = q^s * p^t with distinct primes p and q, then x = q^b * p^(ν_p(x)) and y = q^c * p^(ν_p(y)) with b + c = s and ν_p(x) + ν_p(y) = t.
pow_zero- Any element raised to power 0 equals 1 (a^0 = 1).
one_mul- One is the left identity for multiplication: 1 * a = a.
mondrian_prime_square_area_shape_bound- For distinct primes p, q and t + r = 2e with r > 0, the number of factor shapes of q^2 * p^t bounded by side q * p^e is at most 2r.
mondrian_twice_exponent_lt_prime_power- For p ≥ 2 and r ≥ 3, 2r < p^r.
mondrian_prime_square_area_free_shape_bound- For distinct primes p, q and t + r = 2e, the number of factor shapes of q^2 * p^t bounded by side q * p^e where at least one factor is not divisible by q is at most r.
mondrian_perfect_prime_free_side_counts- In a defect-0 partition of a board of side n divisible by prime p, the number of rectangles whose width is not divisible by p, and the number whose height is not divisible by p, are both multiples of p.
dvd_mul_right- A number divides any multiple of itself: a ∣ a * b.
mondrian_partition_prime_free_shape_count_bound- In a partition of equal rectangle area A on a board of side n, the count of rectangles satisfying a condition implying at least one side is not divisible by q is bounded by the number of factor shapes of A with at least one side not divisible by q.
Or.inl- Introduces a disjunction A ∨ B from a proof of A.
of_decide_eq_true- If decide p evaluates to true, then the proposition p is true.
Or.inr- Introduces a disjunction A ∨ B from a proof of B.
Nat.eq_zero_of_dvd_of_lt- If a divides b and b < a for natural numbers, then b = 0.
List.countP_eq_zero.mp- If counting elements satisfying a predicate in a list yields 0, then no element in the list satisfies that predicate.
And.intro- Constructs a conjunction A ∧ B from proofs of A and B.
mondrian_perfect_partition_div- If every rectangle in a defect-0 partition of a * c has width and height divisible by a > 0, scaling down each rectangle by a gives a defect-0 partition of c.
mondrian_no_perfect_prime_power- For any prime p and exponent e, the square of side p^e has no defect-0 partition into rectangles.
mondrian_prime_free_area_shape_bound- For distinct primes p, q and t + r = 2e, the number of factor shapes of p^t bounded by q * p^e is at most r + Nat.log p q + 1.
mondrian_prime_area_shape_bound- For distinct primes p, q and t + r = 2e, the number of factor shapes of q * p^t bounded by q * p^e is at most r + Nat.log p q + 1.
Nat.le_of_dvd- If 0 < n and m ∣ n, then m ≤ n.
pow_pos- A strictly positive element raised to any natural power remains strictly positive.
dvd_pow_self- For non-zero n, an element divides its n-th power: a ∣ a^n.
Nat.mul_le_mul_right- Multiplying both sides of an inequality by a non-negative number preserves the inequality: if n ≤ m, then n * k ≤ m * k.
mondrian_prime_log_gap- For distinct primes p and q, Nat.log p q + 1 < q and p^(Nat.log p q) < q < p^(Nat.log p q + 1).
Nat.lt_pow_self- For any base a > 1, n < a^n for all natural numbers n.
- In step 10, the final contradiction is closed by `nlinarith`, which automates nonlinear arithmetic deductions combining q * p^r ≤ k ≤ r + Nat.log p q + 1, Nat.log p q + 1 < q, and r + 1 ≤ p^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_no_perfect_prime_mul_prime_pow (p q e : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) : ¬ ∃ P, mondrian_is_partition (q * p ^ e) P ∧ mondrian_defect P = 0 := by 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 k := P.length let A := mondrian_rect_area z let r := k.factorization p let t := A.factorization p have hk : 2 ≤ k := hP.1 have hzb := mondrian_partition_bounds (q * p ^ e) P hP z hzP have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1 have hareas : ∀ w ∈ P, mondrian_rect_area w = A := fun w hw => mondrian_defect_zero_equal P hz w z hw hzP have heq : k * A = q ^ 2 * p ^ (2 * e) := by have hh := mondrian_perfect_area_product (q * p ^ e) P hP hz z hzP change k * A = (q * p ^ e) ^ 2 at hh rw [hh, mul_pow, ← pow_mul, Nat.mul_comm e 2] have hcard : k ≤ (mondrian_factor_shapes (q * p ^ e) A).card := mondrian_shape_bound (q * p ^ e) A P hP hareas obtain ⟨b, s, hbs, hkrep, hArep, hrt⟩ := mondrian_two_prime_factor_pair_encoding p q (2 * e) 2 k A hp hq hpq (by omega) hA heq change k = q ^ b * p ^ r at hkrep change A = q ^ s * p ^ t at hArep change r + t = 2 * e at hrt have hs : s ≤ 2 := by omega by_cases hs2 : s = 2 · have hb : b = 0 := by omega have hkp : k = p ^ r := by simpa only [hb, pow_zero, one_mul] using hkrep have hrpos : 0 < r := by by_contra hh have hr0 : r = 0 := by omega simp [hkp, hr0] at hk have hcap := mondrian_prime_square_area_shape_bound p q e t r hp hq hpq (by omega) hrpos have hArep' : A = q ^ 2 * p ^ t := by simpa only [hs2] using hArep rw [hArep'] at hcard have hpowcap : p ^ r ≤ 2 * r := by omega have hrle : r ≤ 2 := by by_contra hh have hgap := mondrian_twice_exponent_lt_prime_power p r hp.two_le (by omega) omega have hp2 : p = 2 := by interval_cases r · norm_num at hpowcap; have := hp.two_le; omega · norm_num at hpowcap; have := hp.two_le; nlinarith have hq3 : 3 ≤ q := by have := hq.two_le; omega have houter := mondrian_prime_square_area_free_shape_bound p q e t r hp hq hpq (by omega) have hcnt := mondrian_perfect_prime_free_side_counts (q * p ^ e) q P hq (dvd_mul_right q (p ^ e)) hP hz have hwidth := mondrian_partition_prime_free_shape_count_bound (q * p ^ e) A q P hP hareas (fun w => decide (¬ q ∣ mondrian_rect_width w)) (by intro w hw hh exact Or.inl (of_decide_eq_true hh)) have hheight := mondrian_partition_prime_free_shape_count_bound (q * p ^ e) A q P hP hareas (fun w => decide (¬ q ∣ mondrian_rect_height w)) (by intro w hw hh exact Or.inr (of_decide_eq_true hh)) rw [hArep'] at hwidth hheight have hwidth0 : P.countP (fun w => decide (¬ q ∣ mondrian_rect_width w)) = 0 := Nat.eq_zero_of_dvd_of_lt hcnt.1 (by omega) have hheight0 : P.countP (fun w => decide (¬ q ∣ mondrian_rect_height w)) = 0 := Nat.eq_zero_of_dvd_of_lt hcnt.2 (by omega) have hd : ∀ w ∈ P, q ∣ mondrian_rect_width w ∧ q ∣ mondrian_rect_height w := by intro w hw have h1 := List.countP_eq_zero.mp hwidth0 w hw have h2 := List.countP_eq_zero.mp hheight0 w hw simpa using And.intro h1 h2 have hdiv := mondrian_perfect_partition_div q (p ^ e) hq.pos P hP hz hd exact mondrian_no_perfect_prime_power p e hp ⟨_, hdiv⟩ · have hsle : s ≤ 1 := by omega have hcap : (mondrian_factor_shapes (q * p ^ e) A).card ≤ r + Nat.log p q + 1 := by interval_cases s · have hArep' : A = p ^ t := by simpa using hArep rw [hArep'] exact mondrian_prime_free_area_shape_bound p q e t r hp hq hpq (by omega) · have hArep' : A = q * p ^ t := by simpa using hArep rw [hArep'] exact mondrian_prime_area_shape_bound p q e t r hp hq hpq (by omega) have hqb : q ≤ q ^ b := Nat.le_of_dvd (pow_pos hq.pos b) (dvd_pow_self q (by omega : b ≠ 0)) have hlarge : q * p ^ r ≤ k := by rw [hkrep]; exact Nat.mul_le_mul_right _ hqb have hlog := (mondrian_prime_log_gap p q hp hq hpq).2.2 have hpow : r + 1 ≤ p ^ r := by have := Nat.lt_pow_self (n := r) hp.one_lt; omega nlinarith