mondrian_shape_bound
A partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
Statement
theorem mondrian_shape_bound (n A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(h : mondrian_is_partition n P)
(hA : ∀ r ∈ P, mondrian_rect_area r = A) :
P.length ≤ (mondrian_factor_shapes n A).card- 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 9
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- 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_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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_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 3
- mondrian_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
- mondrian_no_perfect_of_shape_boundThere 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…
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
The proof, explained
The proof defines a canonical shape function f(r) mapping each rectangle to its sorted dimension pair (min(w, h), max(w, h)). Because a Mondrian partition forbids congruent rectangles, distinct rectangles have distinct shapes under f, so the mapped list has no duplicates. Each rectangle has area A and fits in the n-square, so its shape belongs to the finite set of valid factor shapes of A. The desired bound then follows from the monotonicity of finite set cardinality.
The canonical shape mapping f(r) = (min(width, height), max(width, height)) distinguishes non-congruent rectangles.
We define f(r) as the sorted pair of dimensions of rectangle r. If f(r) = f(s), projecting to the first and second components via congrArg with Prod.fst and Prod.snd shows that r and s share the same minimum and maximum dimensions. By definition of rectangle congruence (mondrian_rect_congruent), two rectangles whose dimensions share the same minimum and maximum are either identical or transposed, which linear arithmetic (omega) verifies.
uses
congrArg,Prod.fst,Prod.sndlet f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r), max (mondrian_rect_width r) (mondrian_rect_height r)) have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by intro r s he have he1 := congrArg Prod.fst he have he2 := congrArg Prod.snd he dsimp [f] at he1 he2 unfold mondrian_rect_congruent omega
The list of rectangle shapes in the partition contains no duplicates.
By List.nodup_iff_pairwise_ne and List.pairwise_map, a mapped list is duplicate-free exactly when f(r) ≠ f(s) for all distinct pairs in the list. By definition of a Mondrian partition, distinct rectangles in P are non-congruent. Since identical shapes imply congruence, non-congruence implies distinct shapes, so P.map f has no duplicates.
uses
List.nodup_iff_pairwise_ne,List.pairwise_maphave hn : (P.map f).Nodup := by rw [List.nodup_iff_pairwise_ne, List.pairwise_map] exact h.2.2.1.imp (fun hh he => hh.2 (hinj _ _ he))
The set of shapes in the partition is a subset of the factor shapes of area A in the n-square.
Any element of the image set is f(r) for some rectangle r in P (by List.mem_toFinset.mp and List.mem_map.mp). By mondrian_partition_bounds, r has strictly positive width and height bounded by n. According to mondrian_mem_factor_shapes, f(r) is a valid factor shape because: (1) min(w, h) * max(w, h) = w * h = A by min_mul_max and the area hypothesis hA; (2) A ≠ 0 by Nat.mul_pos and Nat.ne_of_gt since w > 0 and h > 0; (3) min(w, h) ≤ max(w, h) holds by definition; and (4) max(w, h) ≤ n since both w ≤ n and h ≤ n.
uses
List.mem_toFinset.mp,List.mem_map.mp,mondrian_partition_bounds,mondrian_mem_factor_shapes,min_mul_max,Nat.ne_of_gt,Nat.mul_poshave hsub : (P.map f).toFinset ⊆ mondrian_factor_shapes n A := by intro d hd obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd) obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P h r hr apply (mondrian_mem_factor_shapes n A (f r)).mpr refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩ · dsimp [f] rw [min_mul_max] exact hA r hr · rw [← hA r hr] exact Nat.ne_of_gt (Nat.mul_pos hw hh)
The number of rectangles in the partition is bounded by the cardinality of the factor shapes.
Since the finite set of shapes in P is a subset of the factor shapes, its cardinality is at most that of mondrian_factor_shapes n A (by Finset.card_le_card). Because the list of shapes has no duplicates, its cardinality equals its length (List.toFinset_card_of_nodup), which in turn equals the length of P (List.length_map). Simplifying with these equalities yields the bound P.length ≤ (mondrian_factor_shapes n A).card.
uses
Finset.card_le_card,List.toFinset_card_of_nodup,List.length_maphave hc := Finset.card_le_card hsub simpa only [List.toFinset_card_of_nodup hn, List.length_map] using hc
congrArg- Applying a function to equal inputs yields equal outputs: if a₁ = a₂, then f(a₁) = f(a₂).
Prod.fst- The first projection of an ordered pair, extracting its first component.
Prod.snd- The second projection of an ordered pair, extracting its second component.
List.nodup_iff_pairwise_ne- A list has no duplicate elements if and only if every pair of distinct positions holds unequal elements.
List.pairwise_map- A relation holds pairwise on a mapped list l.map f if and only if the pulled-back relation holds pairwise on the original list l.
List.mem_toFinset.mp- If an element belongs to the finite set converted from a list, then it is an element of the list.
List.mem_map.mp- If an element is in the image list l.map f, then it is the image f(x) of some element x in l.
mondrian_partition_bounds- In a Mondrian partition of an n-square, every rectangle has strictly positive width and height bounded above by n.
mondrian_mem_factor_shapes- A pair of dimensions (d₁, d₂) belongs to the factor shapes of area A in an n-square if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
min_mul_max- The product of the minimum and maximum of two numbers equals their ordinary product: min(a, b) * max(a, b) = a * b.
Nat.ne_of_gt- If a natural number is strictly greater than another, they are unequal.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most that of the superset.
List.toFinset_card_of_nodup- Converting a list with no duplicates to a finite set preserves its length as the set cardinality.
List.length_map- Mapping a function over a list preserves the length of the list.
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_shape_bound (n A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (h : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A) : P.length ≤ (mondrian_factor_shapes n A).card := by let f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r), max (mondrian_rect_width r) (mondrian_rect_height r)) have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by intro r s he have he1 := congrArg Prod.fst he have he2 := congrArg Prod.snd he dsimp [f] at he1 he2 unfold mondrian_rect_congruent omega have hn : (P.map f).Nodup := by rw [List.nodup_iff_pairwise_ne, List.pairwise_map] exact h.2.2.1.imp (fun hh he => hh.2 (hinj _ _ he)) have hsub : (P.map f).toFinset ⊆ mondrian_factor_shapes n A := by intro d hd obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd) obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P h r hr apply (mondrian_mem_factor_shapes n A (f r)).mpr refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩ · dsimp [f] rw [min_mul_max] exact hA r hr · rw [← hA r hr] exact Nat.ne_of_gt (Nat.mul_pos hw hh) have hc := Finset.card_le_card hsub simpa only [List.toFinset_card_of_nodup hn, List.length_map] using hc