AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_prime_mul_prime_pow

theoremverifiedoriginal

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

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.

  1. 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.

    lines 4–8

      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⟩
  2. 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.

    lines 9–17

    uses mondrian_partition_bounds, Nat.mul_pos, mondrian_defect_zero_equal

      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
  3. 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|.

    lines 18–23

    uses mondrian_perfect_area_product, mul_pow, pow_mul, Nat.mul_comm, mondrian_shape_bound

      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
  4. 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.

    lines 24–29

    uses mondrian_two_prime_factor_pair_encoding

      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
  5. 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.

    lines 30–40

    uses pow_zero, one_mul, mondrian_prime_square_area_shape_bound

      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
  6. 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.

    lines 41–49

    uses mondrian_twice_exponent_lt_prime_power

        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
  7. 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.

    lines 50–65

    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_lt

        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)
  8. 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.

    lines 66–72

    uses List.countP_eq_zero.mp, And.intro, mondrian_perfect_partition_div, mondrian_no_perfect_prime_power

        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⟩
  9. 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.

    lines 73–81

    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)
  10. 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.

    lines 82–87

    uses Nat.le_of_dvd, pow_pos, dvd_pow_self, Nat.mul_le_mul_right, mondrian_prime_log_gap, Nat.lt_pow_self

        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
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.

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

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
See it in the graphDiscuss this resultChallenge it