mondrian_perfect_area_three_prime_factors
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
- mondrian_no_perfect_two_prime_areaFor any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile…
- mondrian_no_perfect_prime_power_areaNo perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
- mondrian_partition_area_one_impossibleAn admissible square partition cannot have every tile of area one.
- 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_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
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.
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.
uses
mondrian_partition_boundshave 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
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.
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
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.
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
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.
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
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).
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
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_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 _ _))