mondrian_no_perfect_of_shape_bound
There is no perfect n-square partition if, for every k at least two and positive A with k times A equal to n squared, fewer than k distinct dimension pairs of area A fit in the square.
Statement
theorem mondrian_no_perfect_of_shape_bound (n : ℕ)
(hbound : ∀ k A : ℕ, 2 ≤ k → 0 < A → k * A = n ^ 2 →
(mondrian_factor_shapes n A).card < k) :
¬ ∃ P, mondrian_is_partition n P ∧ mondrian_defect P = 0- Source
- arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- mondrian_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
- mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- 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_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_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- 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_no_perfect_sixThe integer square of side six has no perfect admissible partition.
- mondrian_no_perfect_prime_powerNo square whose integer side length is a prime power has a perfect admissible partition.
The proof, explained
The proof proceeds by contradiction: suppose there exists a partition P of the n-by-n square with defect 0. Since a valid partition must have at least two rectangles, P is non-empty, and its rectangles all share a positive common area A, giving |P| * A = n^2. Because rectangles in P are pairwise non-congruent, each corresponds to a distinct factor shape fitting in the square, meaning |P| ≤ |mondrian_factor_shapes n A|. However, applying the shape-bound hypothesis with k = |P| ≥ 2 and area A gives |mondrian_factor_shapes n A| < |P|, a contradiction.
Assume for contradiction that a partition P with defect 0 exists; P cannot be empty.
We assume for contradiction that there exists a partition P of the n-by-n square with defect 0. Splitting on whether P is empty, the empty list case is impossible because any valid partition must contain at least two rectangles (2 ≤ |P|), whereas the empty list has length 0.
rintro ⟨P, hp, hz⟩ cases P with | nil => have := hp.1; simp at this
The partition contains a rectangle r whose area is strictly positive.
In the non-empty case P = r :: P', rectangle r belongs to the partition. By mondrian_partition_bounds, r has strictly positive width and height, and by Nat.mul_pos their product—the area of r—is strictly positive.
uses
mondrian_partition_bounds,Nat.mul_pos| cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds n (r :: P) hp r hr have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1The number of rectangles in the partition is at most the number of valid factor shapes of area equal to r's area.
Because the partition has defect 0, all rectangles in it share the same area as r (by mondrian_defect_zero_equal). Since no two rectangles in a partition are congruent, each rectangle has a distinct shape, so by mondrian_shape_bound the number of rectangles |r :: P'| is at most the number of valid shapes of that area fitting in the n-by-n square.
uses
mondrian_shape_bound,mondrian_defect_zero_equalhave hc := mondrian_shape_bound n (mondrian_rect_area r) (r :: P) hp (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr)
The hypothesis implies that the number of valid factor shapes of this area is strictly less than the number of rectangles in the partition.
By mondrian_perfect_area_product, the number of rectangles multiplied by their common area equals the square's total area, |r :: P'| * area(r) = n^2. Instantiating the hypothesis hbound with k = |r :: P'| and A = area(r) (valid since 2 ≤ k, 0 < A, and k * A = n^2) shows that the number of valid factor shapes is strictly less than |r :: P'|.
uses
mondrian_perfect_area_producthave he := mondrian_perfect_area_product n (r :: P) hp hz r hr have hlt := hbound (r :: P).length (mondrian_rect_area r) hp.1 hA he
The upper bound and strict lower bound on the number of rectangles contradict each other.
The inequalities |r :: P'| ≤ |shapes| and |shapes| < |r :: P'| cannot both hold; linear integer arithmetic (omega) derives False and completes the proof.
omega
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
mondrian_partition_bounds- In a valid partition of an n-by-n square, every rectangle has coordinates within bounds and strictly positive width and height bounded by n.
mondrian_defect_zero_equal- If a partition has defect zero, then all of its rectangles have identical area.
mondrian_shape_bound- If all rectangles in a partition of an n-by-n square have the same area A, then the number of rectangles is at most the number of valid non-congruent factor shapes of area A that fit in the square.
mondrian_perfect_area_product- In a partition of an n-by-n square with defect zero, the number of rectangles multiplied by the area of any rectangle equals n squared.
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_no_perfect_of_shape_bound (n : ℕ) (hbound : ∀ k A : ℕ, 2 ≤ k → 0 < A → k * A = n ^ 2 → (mondrian_factor_shapes n A).card < k) : ¬ ∃ P, mondrian_is_partition n P ∧ mondrian_defect P = 0 := by rintro ⟨P, hp, hz⟩ cases P with | nil => have := hp.1; simp at this | cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds n (r :: P) hp r hr have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1 have hc := mondrian_shape_bound n (mondrian_rect_area r) (r :: P) hp (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr) have he := mondrian_perfect_area_product n (r :: P) hp hz r hr have hlt := hbound (r :: P).length (mondrian_rect_area r) hp.1 hA he omega