AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_three_prime_area_one_factor

theoremverifiedoriginal

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

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.

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

    lines 7–8

    uses Nat.strong_induction_on

      induction s using Nat.strong_induction_on generalizing n P with
      | h s ih =>
  2. 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.

    lines 9–12

    uses mondrian_no_perfect_two_prime_area, pow_zero, one_mul, pow_one

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

    lines 13–16

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

    lines 17–22

    uses mondrian_perfect_area_product, dvd_mul_of_dvd_right, dvd_mul_of_dvd_left, dvd_pow_self

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

    line 23

    uses mondrian_three_prime_common_area_sides_divide

        have hd := mondrian_three_prime_common_area_sides_divide n p q r a s P hp hq hr hpr hP hz hqn harea
  6. q^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.

    lines 24–28

    uses pow_two, mondrian_rect_area, Nat.mul_dvd_mul, Nat.mul_assoc

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

    lines 29–38

    uses Nat.dvd_prime

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

    lines 39–44

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

    lines 45–46

    uses Nat.pow_dvd_pow_iff_le_right

        have hs2 : 2 ≤ s :=
          (Nat.pow_dvd_pow_iff_le_right hq.one_lt).mp (hcop.dvd_mul_right.mp hqq)
  10. 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).

    lines 47–53

    uses pow_add

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

    lines 54–56

    uses mondrian_perfect_partition_div_common_area

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

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