AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_area_three_prime_factors

theoremverified

Every tile area in a perfect admissible integer square partition has at least three distinct prime factors.

Statement

theorem mondrian_perfect_area_three_prime_factors (n : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
    (hz : mondrian_defect P = 0) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) :
    3 ≤ (mondrian_rect_area r).primeFactors.card
Source
Corollary of mondrian_no_perfect_two_prime_area for OP-280, arXiv:2610.19193, Section 1.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10

The proof, explained

The proof proceeds by contradiction. If any rectangle in a perfect (defect-zero) admissible partition has fewer than three distinct prime factors, its number of prime factors must be 0, 1, or 2. In each case, its prime factorization forces the tile's area to be 1, a prime power p^t, or a product of two prime powers q^s * p^t. Since zero defect implies all tiles have identical area, each case is ruled out by established impossibility results for Mondrian partitions with unit area, prime power area, or two-prime-factor area.

  1. The area of rectangle r is non-zero.

    From the geometric bounds on admissible partitions (mondrian_partition_bounds), the width and height of rectangle r are strictly positive. Since the area is defined as width × height, it is strictly positive and therefore non-zero.

    lines 5–10

    uses mondrian_partition_bounds

      have hb := mondrian_partition_bounds n P hP r hr
      have hw := hb.2.2.1
      have hh := hb.2.2.2.1
      have hA : mondrian_rect_area r ≠ 0 := by
        dsimp [mondrian_rect_area]
        positivity
  2. Assuming for contradiction that the area has fewer than three distinct prime factors, it must have 0, 1, or 2 prime factors.

    We assume for contradiction that the number of prime factors of the area of r is strictly less than 3. By integer arithmetic, the cardinality of this finite set of primes can only be 0, 1, or 2, which gives three cases to analyze.

    lines 11–15

      by_contra! hc
      have h_cases : (mondrian_rect_area r).primeFactors.card = 0 ∨
          (mondrian_rect_area r).primeFactors.card = 1 ∨
          (mondrian_rect_area r).primeFactors.card = 2 := by omega
      rcases h_cases with h0 | h1 | h2
  3. Case 0: The area cannot have 0 prime factors.

    If the set of prime factors has size 0, it must be empty (Finset.card_eq_zero). Reconstructing the non-zero area from its prime factorization (Nat.prod_primeFactors_pow_factorization) yields the empty product, which is 1 (Finset.prod_empty). Because the defect of partition P is 0, all rectangles in P share the same area as r (mondrian_defect_zero_equal), meaning every tile has area 1. However, an admissible partition cannot consist entirely of unit-area tiles (mondrian_partition_area_one_impossible), yielding a contradiction.

    lines 16–22

    uses Finset.card_eq_zero, Nat.prod_primeFactors_pow_factorization, Finset.prod_empty, mondrian_partition_area_one_impossible, mondrian_defect_zero_equal

      · rw [Finset.card_eq_zero] at h0
        have h := Nat.prod_primeFactors_pow_factorization hA
        rw [h0] at h
        simp only [Finset.prod_empty] at h
        apply mondrian_partition_area_one_impossible n P hP
        intro s hs
        exact (mondrian_defect_zero_equal P hz s r hs hr).trans h
  4. Case 1: The area cannot have 1 prime factor.

    If the set of prime factors has cardinality 1, it consists of a single prime p (Finset.card_eq_one, Nat.mem_primeFactors.mp). The prime factorization formula (Nat.prod_primeFactors_pow_factorization) simplifies via the singleton product (Finset.prod_singleton) to p^t, where t is the exponent of p in the factorization of the area of r. Since the defect is zero, every tile in P must have area equal to p^t (mondrian_defect_zero_equal). But a perfect partition cannot consist of tiles whose areas are all equal to the same prime power (mondrian_no_perfect_prime_power_area), giving a contradiction.

    lines 23–32

    uses Finset.card_eq_one, Nat.mem_primeFactors.mp, Nat.prod_primeFactors_pow_factorization, Finset.prod_singleton, mondrian_no_perfect_prime_power_area, mondrian_defect_zero_equal

      · rw [Finset.card_eq_one] at h1
        obtain ⟨p, hp⟩ := h1
        have hp_mem : p ∈ (mondrian_rect_area r).primeFactors := by simp [hp]
        have hp_prime : Nat.Prime p := (Nat.mem_primeFactors.mp hp_mem).1
        have h := Nat.prod_primeFactors_pow_factorization hA
        rw [hp] at h
        simp only [Finset.prod_singleton] at h
        apply mondrian_no_perfect_prime_power_area p ((mondrian_rect_area r).factorization p) n hp_prime P hP hz
        intro s hs
        exact (mondrian_defect_zero_equal P hz s r hs hr).trans h
  5. Case 2: The area cannot have 2 prime factors.

    If the set of prime factors has cardinality 2, it consists of two distinct primes p and q (Finset.card_eq_two, Nat.mem_primeFactors.mp). The prime factorization (Nat.prod_primeFactors_pow_factorization, Finset.prod_pair) shows that the area of r is p^t * q^s, which equals q^s * p^t by commutativity (mul_comm). Since the partition has defect zero, every tile in P shares this same area (mondrian_defect_zero_equal). This contradicts the fact that no perfect partition can have all tiles of area equal to a product of powers of two distinct primes (mondrian_no_perfect_two_prime_area).

    lines 33–44

    uses Finset.card_eq_two, Nat.mem_primeFactors.mp, Nat.prod_primeFactors_pow_factorization, Finset.prod_pair, mondrian_no_perfect_two_prime_area, mondrian_defect_zero_equal, mul_comm

      · rw [Finset.card_eq_two] at h2
        rcases h2 with ⟨p, q, hpq, hpq_set⟩
        have hp_mem : p ∈ (mondrian_rect_area r).primeFactors := by simp [hpq_set]
        have hq_mem : q ∈ (mondrian_rect_area r).primeFactors := by simp [hpq_set]
        have hp_prime : Nat.Prime p := (Nat.mem_primeFactors.mp hp_mem).1
        have hq_prime : Nat.Prime q := (Nat.mem_primeFactors.mp hq_mem).1
        have h := Nat.prod_primeFactors_pow_factorization hA
        rw [hpq_set] at h
        rw [Finset.prod_pair hpq] at h
        apply mondrian_no_perfect_two_prime_area p q ((mondrian_rect_area r).factorization q) ((mondrian_rect_area r).factorization p) n hp_prime hq_prime hpq P hP hz
        intro s hs
        exact (mondrian_defect_zero_equal P hz s r hs hr).trans (h.trans (mul_comm _ _))
mondrian_partition_bounds
In any admissible partition of an n × n square, every tile has coordinates bounded by n, and its width and height are strictly positive and at most n.
Finset.card_eq_zero
A finite set has cardinality 0 if and only if it is empty.
Nat.prod_primeFactors_pow_factorization
Any non-zero natural number equals the product of p^k over its prime factors p, where k is the multiplicity of p in its prime factorization.
Finset.prod_empty
The product of an indexed family over the empty set is 1.
mondrian_partition_area_one_impossible
There is no admissible partition of a square in which every tile has area 1.
mondrian_defect_zero_equal
If a partition has defect 0, then all tiles in the partition have the same area.
Finset.card_eq_one
A finite set has cardinality 1 if and only if it is a singleton set.
Nat.mem_primeFactors.mp
If p is in the set of prime factors of n, then p is prime (as well as a divisor of n, with n ≠ 0).
Finset.prod_singleton
The product of an indexed family over a singleton set {a} is the value at a.
mondrian_no_perfect_prime_power_area
A perfect (defect-zero) admissible partition cannot have all tiles of the same prime power area p^t.
Finset.card_eq_two
A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.prod_pair
The product over a set of two distinct elements {a, b} is f(a) * f(b).
mondrian_no_perfect_two_prime_area
A perfect (defect-zero) admissible partition cannot have all tiles of the same area q^s * p^t for two distinct primes p and q.
mul_comm
Multiplication is commutative: a * b = b * a.

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_perfect_area_three_prime_factors (n : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)    (hz : mondrian_defect P = 0) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) :    3 ≤ (mondrian_rect_area r).primeFactors.card := by  have hb := mondrian_partition_bounds n P hP r hr  have hw := hb.2.2.1  have hh := hb.2.2.2.1  have hA : mondrian_rect_area r ≠ 0 := by    dsimp [mondrian_rect_area]    positivity  by_contra! hc  have h_cases : (mondrian_rect_area r).primeFactors.card = 0 ∨      (mondrian_rect_area r).primeFactors.card = 1 ∨      (mondrian_rect_area r).primeFactors.card = 2 := by omega  rcases h_cases with h0 | h1 | h2  · rw [Finset.card_eq_zero] at h0    have h := Nat.prod_primeFactors_pow_factorization hA    rw [h0] at h    simp only [Finset.prod_empty] at h    apply mondrian_partition_area_one_impossible n P hP    intro s hs    exact (mondrian_defect_zero_equal P hz s r hs hr).trans h  · rw [Finset.card_eq_one] at h1    obtain ⟨p, hp⟩ := h1    have hp_mem : p ∈ (mondrian_rect_area r).primeFactors := by simp [hp]    have hp_prime : Nat.Prime p := (Nat.mem_primeFactors.mp hp_mem).1    have h := Nat.prod_primeFactors_pow_factorization hA    rw [hp] at h    simp only [Finset.prod_singleton] at h    apply mondrian_no_perfect_prime_power_area p ((mondrian_rect_area r).factorization p) n hp_prime P hP hz    intro s hs    exact (mondrian_defect_zero_equal P hz s r hs hr).trans h  · rw [Finset.card_eq_two] at h2    rcases h2 with ⟨p, q, hpq, hpq_set⟩    have hp_mem : p ∈ (mondrian_rect_area r).primeFactors := by simp [hpq_set]    have hq_mem : q ∈ (mondrian_rect_area r).primeFactors := by simp [hpq_set]    have hp_prime : Nat.Prime p := (Nat.mem_primeFactors.mp hp_mem).1    have hq_prime : Nat.Prime q := (Nat.mem_primeFactors.mp hq_mem).1    have h := Nat.prod_primeFactors_pow_factorization hA    rw [hpq_set] at h    rw [Finset.prod_pair hpq] at h    apply mondrian_no_perfect_two_prime_area p q ((mondrian_rect_area r).factorization q) ((mondrian_rect_area r).factorization p) n hp_prime hq_prime hpq P hP hz    intro s hs    exact (mondrian_defect_zero_equal P hz s r hs hr).trans (h.trans (mul_comm _ _))
See it in the graphDiscuss this resultChallenge it