mondrian_partition_area_one_impossible
An admissible square partition cannot have every tile of area one.
Statement
theorem mondrian_partition_area_one_impossible (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (harea : ∀ r ∈ P, mondrian_rect_area r = 1) : False- 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 6
- 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_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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…
- Used by 2
- mondrian_perfect_area_three_prime_factorsEvery tile area in a perfect admissible integer square partition has at least three distinct prime factors.
- 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.
The proof, explained
By the definition of an admissible Mondrian partition, the partition must contain at least two tiles, ruling out lists of length zero or one. In any partition with at least two rectangles r and s, the hypothesis that every tile has area 1 forces both r and s to have width 1 and height 1, as their dimensions are natural numbers whose product is 1. Consequently, r and s have identical dimensions and are congruent, contradicting the partition requirement that all tiles must be pairwise non-congruent.
The partition P must contain at least two rectangles; it cannot have zero or one rectangle.
By the definition of an admissible partition, P must contain at least two tiles (2 ≤ |P|). Case analysis on P tests whether P is empty or a singleton [r]. If P is empty, the length condition requires 2 ≤ 0; if P = [r], it requires 2 ≤ 1. In both cases, simplifying the inequality against the list length yields a contradiction, ruling out partitions of length less than two.
cases P with | nil => have := hP.1; simp at this | cons r P => cases P with | nil => have := hP.1; simp at this
The first two rectangles r and s in the partition both have width 1 and height 1.
With the smaller cases eliminated, P decomposes into r :: s :: P', containing at least two rectangles r and s. By assumption (harea), every rectangle in P has area 1, defined as width * height. Since rectangle dimensions are natural numbers, Nat.eq_one_of_mul_eq_one_right and Nat.eq_one_of_mul_eq_one_left establish that both r and s have width 1 and height 1.
uses
Nat.eq_one_of_mul_eq_one_right,Nat.eq_one_of_mul_eq_one_left| cons s P => have hrw := Nat.eq_one_of_mul_eq_one_right (harea r (by simp)) have hrh := Nat.eq_one_of_mul_eq_one_left (harea r (by simp)) have hsw := Nat.eq_one_of_mul_eq_one_right (harea s (by simp)) have hsh := Nat.eq_one_of_mul_eq_one_left (harea s (by simp))Rectangles r and s are congruent, contradicting the partition requirement that distinct tiles are pairwise non-congruent.
An admissible partition requires distinct tiles to be pairwise disjoint and non-congruent. Extracting this pairwise property for the pair (r, s) using List.pairwise_cons.mp shows that r and s cannot be congruent. However, since both r and s have width 1 and height 1, their dimensions match, so they are congruent by the first disjunct of rectangle congruence via Or.inl (with width and height equality closed by linear arithmetic). This contradiction completes the proof.
uses
List.pairwise_cons.mp,Or.inlhave hpair := (List.pairwise_cons.mp hP.2.2.1).1 s (by simp) exact hpair.2 (Or.inl ⟨by omega, by omega⟩)
Nat.eq_one_of_mul_eq_one_right- If the product of two natural numbers is 1, then the first factor is 1 (m * n = 1 → m = 1).
Nat.eq_one_of_mul_eq_one_left- If the product of two natural numbers is 1, then the second factor is 1 (m * n = 1 → n = 1).
List.pairwise_cons.mp- If a list starting with head a and tail l is pairwise related by a relation R, then a is related by R to every element of l, and l is pairwise related under R.
Or.inl- From a proof of proposition a, deduce the disjunction a ∨ b.
- In Mathlib, `Nat.eq_one_of_mul_eq_one_right` deduces that the left factor is 1, while `Nat.eq_one_of_mul_eq_one_left` deduces that the right factor is 1; the names reflect the factor being eliminated rather than the one being retained.
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_partition_area_one_impossible (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (harea : ∀ r ∈ P, mondrian_rect_area r = 1) : False := by cases P with | nil => have := hP.1; simp at this | cons r P => cases P with | nil => have := hP.1; simp at this | cons s P => have hrw := Nat.eq_one_of_mul_eq_one_right (harea r (by simp)) have hrh := Nat.eq_one_of_mul_eq_one_left (harea r (by simp)) have hsw := Nat.eq_one_of_mul_eq_one_right (harea s (by simp)) have hsh := Nat.eq_one_of_mul_eq_one_left (harea s (by simp)) have hpair := (List.pairwise_cons.mp hP.2.2.1).1 s (by simp) exact hpair.2 (Or.inl ⟨by omega, by omega⟩)