AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_two_prime_powers

theoremverified

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.

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

    lines 4–5

    uses mondrian_no_perfect_prime_power

      induction f with
      | zero => simpa using mondrian_no_perfect_prime_power p e hp
  2. 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.

    lines 6–7

      | succ f ih =>
        rintro ⟨P, hP, hz⟩
  3. 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.

    lines 8–11

        obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by
          cases P with
          | nil => have := hP.1; simp at this
          | cons z P => exact ⟨z, by simp⟩
  4. 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.

    lines 12–14

    uses mondrian_defect_zero_equal

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

    lines 15–21

    uses mondrian_perfect_area_product, mul_pow, pow_mul, dvd_mul_left

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

    lines 22–23

    uses mondrian_two_prime_divisor_encoding

        obtain ⟨s, hs, hArep⟩ := mondrian_two_prime_divisor_encoding p q (2 * e)
          (2 * (f + 1)) A hp hq hpq hdiv
  7. The 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.

    lines 24–27

    uses dvd_mul_of_dvd_left, dvd_pow_self, mondrian_two_prime_area_sides_dvd

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

    lines 28–29

    uses pow_succ, Nat.mul_assoc, Nat.mul_left_comm, Nat.mul_comm

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

    lines 30–31

    uses mondrian_perfect_partition_div

        have 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

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