mondrian_partition_div
An admissible partition of the a times c square, with every tile side a multiple of positive a, becomes an admissible partition of the c-square after dividing coordinates by a.
Statement
theorem mondrian_partition_div (a c : ℕ) (ha : 0 < a)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P)
(hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) :
mondrian_is_partition c (P.map (mondrian_rect_div a))- Source
- Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- mondrian_interval_divAn integer cell i belongs to the coordinatewise quotient of an interval precisely when the last cell of its a-block belongs to the…
- 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…
- mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
- mondrian_rect_div_cellsMembership in a coordinatewise divided rectangle is equivalent to membership of the corresponding last cell of the original square block.
- mondrian_rect_div_dimensionsDividing coordinates of a positive rectangle whose side lengths are multiples of a divides its width and height exactly by a.
- 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_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- Used by 1
- mondrian_perfect_partition_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
The proof, explained
The proof verifies that dividing coordinates by $a$ transforms a partition of the $(a \cdot c) \times (a \cdot c)$ square into an admissible partition of the $c \times c$ square. Preserving list length and scaling the positive dimensions by $a$ guarantees at least two non-degenerate rectangles. The key link is that a cell $(i, j)$ lies in a divided rectangle $r/a$ if and only if the representative point $(a(i+1)-1, a(j+1)-1)$ lies in $r$; this equivalence directly preserves both pairwise disjointness and complete grid coverage. Finally, non-congruence is preserved because any congruence between divided rectangles would scale up by $a$ to a congruence between the original rectangles.
For every rectangle $r \in P$, scaling the dimensions of the divided rectangle by $a$ recovers the original width and height of $r$.
Since $a > 0$, each rectangle $r \in P$ is non-degenerate (positive width and height), and $a$ divides both dimensions of $r$ by assumption, the lemma `mondrian_rect_div_dimensions` shows that $a \cdot \text{width}(r / a) = \text{width}(r)$ and $a \cdot \text{height}(r / a) = \text{height}(r)$.
uses
mondrian_rect_div_dimensionshave hdim : ∀ r ∈ P, a * mondrian_rect_width (mondrian_rect_div a r) = mondrian_rect_width r ∧ a * mondrian_rect_height (mondrian_rect_div a r) = mondrian_rect_height r := by intro r hr exact mondrian_rect_div_dimensions a ha r (hp.2.1 r hr).1 (hp.2.1 r hr).2 (hd r hr).1 (hd r hr).2
The partition definition decomposes into three remaining goals, and the list of divided rectangles contains at least two rectangles.
An admissible Mondrian partition requires at least two rectangles, valid positive dimensions, pairwise disjointness and incongruence, and covering the square. Mapping preserves list length by `List.length_map`, so the divided list retains length at least 2 from $P$.
uses
List.length_maprefine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
Every divided rectangle is non-degenerate (its width and height are strictly positive).
Any rectangle in the mapped list is the division of some original rectangle $s \in P$. Because $s$ has positive width and height, and multiplying the divided rectangle's dimensions by $a$ yields the original dimensions, the divided dimensions must also be positive by `Nat.pos_of_mul_pos_left`, which implies the bottom-left coordinate is strictly less than the top-right coordinate.
uses
List.mem_map.mp,Nat.sub_pos_of_lt,Nat.pos_of_mul_pos_left,Nat.lt_of_sub_pos· intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr have h1 := (hdim s hs).1 have h2 := (hdim s hs).2 have hpos := hp.2.1 s hs have hw : 0 < mondrian_rect_width (mondrian_rect_div a s) := by have : 0 < mondrian_rect_width s := Nat.sub_pos_of_lt hpos.1 exact Nat.pos_of_mul_pos_left (by rwa [h1]) have hh : 0 < mondrian_rect_height (mondrian_rect_div a s) := by have : 0 < mondrian_rect_height s := Nat.sub_pos_of_lt hpos.2 exact Nat.pos_of_mul_pos_left (by rwa [h2]) exact ⟨Nat.lt_of_sub_pos hw, Nat.lt_of_sub_pos hh⟩
Divided rectangles are pairwise disjoint.
Via `List.pairwise_map`, the pairwise property on the mapped list reduces to checking disjointness and non-congruence for any pair of distinct rectangles $r, s \in P$. If a cell $(i, j)$ belonged to the intersection of two divided rectangles, then by `mondrian_rect_div_cells` the representative point $(a(i+1)-1, a(j+1)-1)$ would belong to both $r$ and $s$, contradicting their disjointness.
uses
List.pairwise_map,Finset.disjoint_left,Finset.disjoint_left.mp,mondrian_rect_div_cells· rw [List.pairwise_map] apply hp.2.2.1.imp_of_mem intro r s hr hs hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨i, j⟩ hi hj exact Finset.disjoint_left.mp hrs.1 ((mondrian_rect_div_cells a ha r i j).mp hi) ((mondrian_rect_div_cells a ha s i j).mp hj)
Divided rectangles are pairwise non-congruent.
If two divided rectangles were congruent (having matching dimensions either directly or after swapping width and height), then multiplying each dimension by $a$ would imply that the original rectangles $r$ and $s$ are congruent, contradicting the pairwise non-congruence of $P$.
· intro hc apply hrs.2 obtain ⟨hrw, hrh⟩ := hdim r hr obtain ⟨hsw, hsh⟩ := hdim s hs rcases hc with ⟨hw, hh⟩ | ⟨hw, hh⟩ · left constructor · rw [← hrw, ← hsw, hw] · rw [← hrh, ← hsh, hh] · right constructor · rw [← hrw, ← hsh, hw] · rw [← hrh, ← hsw, hh]
The union of the divided rectangles is contained in the $c \times c$ grid.
If a cell $(i, j)$ belongs to a divided rectangle $s / a$, then $(a(i+1)-1, a(j+1)-1)$ belongs to $s$, hence to the $(a \cdot c) \times (a \cdot c)$ grid covered by $P$. Applying `mondrian_interval_div` and canceling $a \cdot c / a = c$ via `Nat.mul_div_cancel_left` shows that $i < c$ and $j < c$, so $(i, j)$ is in the $c \times c$ grid.
uses
Finset.mem_biUnion.mp,List.mem_map.mp,List.mem_toFinset.mp,mondrian_rect_div_cells,Finset.mem_biUnion.mpr,List.mem_toFinset.mpr,Finset.mem_product,Finset.mem_range,mondrian_interval_div,Nat.zero_le,Nat.mul_div_cancel_left,And.intro· ext ⟨i, j⟩ constructor · intro hi obtain ⟨r, hr, hi⟩ := Finset.mem_biUnion.mp hi obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr) have hi' := (mondrian_rect_div_cells a ha s i j).mp hi have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩ rw [hp.2.2.2] at hu simp only [Finset.mem_product, Finset.mem_range] at hu ⊢ have hiq := (mondrian_interval_div a 0 (a * c) i ha).mpr ⟨Nat.zero_le _, hu.1⟩ have hjq := (mondrian_interval_div a 0 (a * c) j ha).mpr ⟨Nat.zero_le _, hu.2⟩ simpa only [Nat.mul_div_cancel_left c ha] using And.intro hiq.2 hjq.2
Every cell in the $c \times c$ grid is covered by some divided rectangle.
Given $(i, j) \in [0, c) \times [0, c)$, we have $i < (a \cdot c) / a$ and $j < (a \cdot c) / a$. By `mondrian_interval_div`, the point $(a(i+1)-1, a(j+1)-1)$ lies in the $(a \cdot c) \times (a \cdot c)$ grid, so it belongs to some rectangle $r \in P$. Then $(i, j)$ belongs to the divided rectangle $r / a$ by `mondrian_rect_div_cells`.
uses
Finset.mem_product,Finset.mem_range,mondrian_interval_div,Nat.mul_div_cancel_left,Finset.mem_biUnion.mp,Finset.mem_biUnion.mpr,mondrian_rect_div_cells,List.mem_toFinset.mpr,List.mem_map.mpr,List.mem_toFinset.mp· intro hi simp only [Finset.mem_product, Finset.mem_range] at hi have hi1 := (mondrian_interval_div a 0 (a * c) i ha).mp ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.1⟩ have hi2 := (mondrian_interval_div a 0 (a * c) j ha).mp ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.2⟩ have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈ Finset.range (a * c) ×ˢ Finset.range (a * c) := by simp only [Finset.mem_product, Finset.mem_range] exact ⟨hi1.2, hi2.2⟩ rw [← hp.2.2.2] at hu obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr refine ⟨mondrian_rect_div a r, ?_, (mondrian_rect_div_cells a ha r i j).mpr hm⟩ exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)
And.intro- Given proofs of propositions $a$ and $b$, constructs a proof of their conjunction $a \land b$.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element belonging to the first cannot belong to the second.
Finset.mem_biUnion.mp- If an element belongs to a big union of finsets, it belongs to at least one component finset in the family.
Finset.mem_biUnion.mpr- If an element belongs to one of the component finsets in a family, it belongs to their big union.
Finset.mem_product- A pair belongs to the Cartesian product of two finite sets if and only if its first component is in the first set and its second component is in the second set.
Finset.mem_range- A natural number $m$ belongs to `Finset.range n` if and only if $m < n$.
List.length_map- Mapping a function over a list preserves the length of the list.
List.mem_map.mp- If an element belongs to the image of a list under a function, it is the image of some element of that list.
List.mem_map.mpr- If an element is the image of some element in a list, it belongs to the mapped list.
List.mem_toFinset.mp- If an element belongs to the finite set associated with a list, it belongs to the list.
List.mem_toFinset.mpr- If an element belongs to a list, it belongs to the finite set associated with that list.
List.pairwise_map- A mapped list is pairwise related by a relation $R$ if and only if the original list is pairwise related by the pullback of $R$ along the map.
mondrian_interval_div- For $a > 0$, an integer index $i$ lies in the interval $[x/a, y/a)$ if and only if $a(i+1)-1$ lies in $[x, y)$.
mondrian_rect_div_cells- A grid cell $(i, j)$ belongs to the divided rectangle $r/a$ if and only if the point $(a(i+1)-1, a(j+1)-1)$ belongs to $r$.
mondrian_rect_div_dimensions- If a rectangle has positive dimensions that are divisible by $a > 0$, multiplying the dimensions of its coordinate division by $a$ recovers its original dimensions.
Nat.lt_of_sub_pos- If $n - m > 0$ for natural numbers, then $m < n$.
Nat.mul_div_cancel_left- For positive $n$, multiplying $m$ by $n$ and then dividing by $n$ yields $m$.
Nat.pos_of_mul_pos_left- If a product of natural numbers $a \cdot b$ is strictly positive, then $b > 0$.
Nat.sub_pos_of_lt- If $m < n$ for natural numbers, then $n - m > 0$.
Nat.zero_le- Every natural number is greater than or equal to zero.
- To connect a cell $(i, j)$ in the divided rectangle to a cell in the original rectangle, the proof uses the top-right corner point $(a(i+1)-1, a(j+1)-1)$ as a canonical representative point via `mondrian_rect_div_cells`.
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_div (a c : ℕ) (ha : 0 < a) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P) (hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) : mondrian_is_partition c (P.map (mondrian_rect_div a)) := by have hdim : ∀ r ∈ P, a * mondrian_rect_width (mondrian_rect_div a r) = mondrian_rect_width r ∧ a * mondrian_rect_height (mondrian_rect_div a r) = mondrian_rect_height r := by intro r hr exact mondrian_rect_div_dimensions a ha r (hp.2.1 r hr).1 (hp.2.1 r hr).2 (hd r hr).1 (hd r hr).2 refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩ · intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr have h1 := (hdim s hs).1 have h2 := (hdim s hs).2 have hpos := hp.2.1 s hs have hw : 0 < mondrian_rect_width (mondrian_rect_div a s) := by have : 0 < mondrian_rect_width s := Nat.sub_pos_of_lt hpos.1 exact Nat.pos_of_mul_pos_left (by rwa [h1]) have hh : 0 < mondrian_rect_height (mondrian_rect_div a s) := by have : 0 < mondrian_rect_height s := Nat.sub_pos_of_lt hpos.2 exact Nat.pos_of_mul_pos_left (by rwa [h2]) exact ⟨Nat.lt_of_sub_pos hw, Nat.lt_of_sub_pos hh⟩ · rw [List.pairwise_map] apply hp.2.2.1.imp_of_mem intro r s hr hs hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨i, j⟩ hi hj exact Finset.disjoint_left.mp hrs.1 ((mondrian_rect_div_cells a ha r i j).mp hi) ((mondrian_rect_div_cells a ha s i j).mp hj) · intro hc apply hrs.2 obtain ⟨hrw, hrh⟩ := hdim r hr obtain ⟨hsw, hsh⟩ := hdim s hs rcases hc with ⟨hw, hh⟩ | ⟨hw, hh⟩ · left constructor · rw [← hrw, ← hsw, hw] · rw [← hrh, ← hsh, hh] · right constructor · rw [← hrw, ← hsh, hw] · rw [← hrh, ← hsw, hh] · ext ⟨i, j⟩ constructor · intro hi obtain ⟨r, hr, hi⟩ := Finset.mem_biUnion.mp hi obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr) have hi' := (mondrian_rect_div_cells a ha s i j).mp hi have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩ rw [hp.2.2.2] at hu simp only [Finset.mem_product, Finset.mem_range] at hu ⊢ have hiq := (mondrian_interval_div a 0 (a * c) i ha).mpr ⟨Nat.zero_le _, hu.1⟩ have hjq := (mondrian_interval_div a 0 (a * c) j ha).mpr ⟨Nat.zero_le _, hu.2⟩ simpa only [Nat.mul_div_cancel_left c ha] using And.intro hiq.2 hjq.2 · intro hi simp only [Finset.mem_product, Finset.mem_range] at hi have hi1 := (mondrian_interval_div a 0 (a * c) i ha).mp ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.1⟩ have hi2 := (mondrian_interval_div a 0 (a * c) j ha).mp ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.2⟩ have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈ Finset.range (a * c) ×ˢ Finset.range (a * c) := by simp only [Finset.mem_product, Finset.mem_range] exact ⟨hi1.2, hi2.2⟩ rw [← hp.2.2.2] at hu obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr refine ⟨mondrian_rect_div a r, ?_, (mondrian_rect_div_cells a ha r i j).mpr hm⟩ exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)