mondrian_partition_swap
Exchanging the x and y coordinate pairs of every rectangle preserves an admissible partition of the n-square.
Statement
theorem mondrian_partition_swap (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hp : mondrian_is_partition n P) :
mondrian_is_partition n (P.map mondrian_rect_swap)- Source
- Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
- 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_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_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_swapExchange the x and y coordinate pairs of an integer rectangle.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- Used by 4
- mondrian_no_perfect_three_prime_area_one_factorFor three distinct primes p,q,r with p>r+1, no perfect admissible integer square partition has common tile area q^s*r*p^a, for arbitrary…
- mondrian_partition_prime_free_height_countFor an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of…
- mondrian_two_prime_area_sides_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are…
- mondrian_three_prime_common_area_sides_divideFor primes p,q,r with p>r+1, if q divides the square side and every tile in a perfect admissible partition has area q^s*r*p^a, then q…
The proof, explained
To prove that exchanging the x and y coordinates of every rectangle preserves an admissible partition of the n × n square, the proof verifies the four partition conditions for the mapped list. The key observation is that swapping a rectangle's coordinate intervals transposes its constituent grid cells, so (x, y) belongs to the swapped rectangle if and only if (y, x) belonged to the original. Because mapping preserves list length, non-degeneracy merely exchanges the width and height strict inequalities, and rectangle congruence is symmetric under interchanging width and height, the swapped rectangles remain non-degenerate, pairwise disjoint, and pairwise non-congruent. Finally, the swapped rectangles cover the n × n square because the square itself is invariant under coordinate transposition.
A cell (x, y) belongs to the swapped rectangle if and only if the transposed cell (y, x) belongs to the original rectangle.
Unfolding the definitions of rectangle swap and rectangle cells, the membership (x, y) ∈ [y₁, y₂) × [x₁, x₂) reduces by Finset.mem_product and Finset.mem_Ico to (y₁ ≤ x ∧ x < y₂) ∧ (x₁ ≤ y ∧ y < x₂). Propositional logic reorders this conjunction to (x₁ ≤ y ∧ y < x₂) ∧ (y₁ ≤ x ∧ x < y₂), which is exactly the condition that (y, x) ∈ [x₁, x₂) × [y₁, y₂).
uses
Finset.mem_product,Finset.mem_Icohave hcell : ∀ r : ℕ × ℕ × ℕ × ℕ, ∀ x y : ℕ, (x, y) ∈ mondrian_rect_cells (mondrian_rect_swap r) ↔ (y, x) ∈ mondrian_rect_cells r := by intro r x y simp only [mondrian_rect_swap, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico] tauto
The swapped partition contains at least two rectangles.
The first requirement of an admissible partition is that the list of rectangles has length at least 2. Mapping the coordinate swap over the list preserves list length by List.length_map, so the swapped list has the same length as P, which is at least 2.
uses
List.length_maprefine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
Every rectangle in the swapped list is non-degenerate.
For every rectangle r in the swapped list, List.mem_map.mp yields a rectangle s in P such that r is the swap of s. Since s has positive width and positive height (s₁ < s₂ and s₃ < s₄), the swapped rectangle r, whose width is s₄ - s₃ and height is s₂ - s₁, also has positive width and positive height (s₃ < s₄ and s₁ < s₂).
uses
List.mem_map.mp· intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr exact ⟨(hp.2.1 s hs).2, (hp.2.1 s hs).1⟩
The rectangles in the swapped partition remain pairwise disjoint and pairwise non-congruent.
By List.pairwise_map, it suffices to show that if two rectangles r and s in P are disjoint and non-congruent, then their swaps are also disjoint and non-congruent. For disjointness, if a cell (x, y) belonged to both swapped rectangles, the cell transposition equivalence from the first step would place (y, x) in both original rectangles r and s, contradicting their disjointness via Finset.disjoint_left and Finset.disjoint_left.mp. For non-congruence, two rectangles are congruent when their dimensions match up to reordering; since swapping interchanges width and height, congruence is invariant under swapping, so the non-congruence of r and s implies the non-congruence of their swaps.
uses
List.pairwise_map,Finset.disjoint_left,Finset.disjoint_left.mp· rw [List.pairwise_map] apply hp.2.2.1.imp intro r s hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨x, y⟩ hr hs exact Finset.disjoint_left.mp hrs.1 ((hcell r x y).mp hr) ((hcell s x y).mp hs) · intro hc apply hrs.2 simp only [mondrian_rect_congruent, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] at hc ⊢ tauto
The union of the cells of the swapped rectangles is the full n × n grid.
Set extensionality reduces the claim to showing that (x, y) is covered by the swapped partition if and only if (x, y) ∈ {0, …, n - 1}². In the forward direction, if (x, y) lies in the swapped partition, decomposing the membership with Finset.mem_biUnion.mp, List.mem_toFinset.mp, and List.mem_map.mp yields an original rectangle s containing (y, x). Recombining via Finset.mem_biUnion.mpr and List.mem_toFinset.mpr shows that (y, x) is in the union of P, which is the n × n square. By Finset.mem_product, Finset.mem_range, and commutativity of conjunction (and_comm), (y, x) ∈ {0, …, n - 1}² implies (x, y) ∈ {0, …, n - 1}². In the reverse direction, if (x, y) is in the square, then (y, x) is also in the square by Finset.mem_product, Finset.mem_range, and and_comm, hence (y, x) is covered by some rectangle r ∈ P via Finset.mem_biUnion.mp. The swapped rectangle of r belongs to the mapped partition by List.mem_toFinset.mpr and List.mem_map.mpr, and contains (x, y) by transposition, completing the union via Finset.mem_biUnion.mpr.
uses
Finset.mem_biUnion.mp,List.mem_map.mp,List.mem_toFinset.mp,Finset.mem_biUnion.mpr,List.mem_toFinset.mpr,Finset.mem_product,Finset.mem_range,and_comm,List.mem_map.mpr· ext ⟨x, y⟩ constructor · intro h obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp h obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr) have hu : (y, x) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, (hcell s x y).mp hc⟩ rw [hp.2.2.2] at hu simpa only [Finset.mem_product, Finset.mem_range, and_comm] using hu · intro h have hu : (y, x) ∈ Finset.range n ×ˢ Finset.range n := by simpa only [Finset.mem_product, Finset.mem_range, and_comm] using h rw [← hp.2.2.2] at hu obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr exact ⟨mondrian_rect_swap r, List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩), (hcell r x y).mpr hc⟩
and_comm- Conjunction is commutative: a ∧ b is logically equivalent to b ∧ a.
Finset.disjoint_left- Two finite sets are disjoint if and only if every element of the first set is not in the second set.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element belonging to the first set cannot belong to the second set.
Finset.mem_Ico- An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.mem_product- A pair (x, y) belongs to the Cartesian product s ×ˢ t if and only if x ∈ s and y ∈ t.
Finset.mem_range- A natural number m belongs to the range {0, …, n - 1} if and only if m < n.
Finset.mem_biUnion.mp- If an element belongs to a big union ⋃_{a ∈ s} t(a), then it belongs to t(a) for some a ∈ s.
Finset.mem_biUnion.mpr- If an element belongs to t(a) for some a ∈ s, then it belongs to the big union ⋃_{a ∈ s} t(a).
List.length_map- Mapping a function over a list preserves its length: length(f(L)) = length(L).
List.mem_map.mp- If an element is in the image List.map f l, then it equals f(a) for some a ∈ l.
List.mem_map.mpr- If an element a is in a list l, then f(a) belongs to List.map f l.
List.mem_toFinset.mp- If an element belongs to the Finset representation of a list, then it belongs to the list.
List.mem_toFinset.mpr- If an element belongs to a list, then it belongs to the Finset representation of that list.
List.pairwise_map- A mapped list List.map f l is pairwise related by R if and only if the original list l is pairwise related by (a, b) ↦ R (f a) (f b).
- In this formalisation, a rectangle is represented as a 4-tuple of natural numbers (x₁, x₂, y₁, y₂) corresponding to the cell product [x₁, x₂) × [y₁, y₂), with width x₂ - x₁ and height y₂ - y₁.
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.
open scoped BigOperatorstheorem mondrian_partition_swap (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition n P) : mondrian_is_partition n (P.map mondrian_rect_swap) := by have hcell : ∀ r : ℕ × ℕ × ℕ × ℕ, ∀ x y : ℕ, (x, y) ∈ mondrian_rect_cells (mondrian_rect_swap r) ↔ (y, x) ∈ mondrian_rect_cells r := by intro r x y simp only [mondrian_rect_swap, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico] tauto refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩ · intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr exact ⟨(hp.2.1 s hs).2, (hp.2.1 s hs).1⟩ · rw [List.pairwise_map] apply hp.2.2.1.imp intro r s hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨x, y⟩ hr hs exact Finset.disjoint_left.mp hrs.1 ((hcell r x y).mp hr) ((hcell s x y).mp hs) · intro hc apply hrs.2 simp only [mondrian_rect_congruent, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] at hc ⊢ tauto · ext ⟨x, y⟩ constructor · intro h obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp h obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr) have hu : (y, x) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, (hcell s x y).mp hc⟩ rw [hp.2.2.2] at hu simpa only [Finset.mem_product, Finset.mem_range, and_comm] using hu · intro h have hu : (y, x) ∈ Finset.range n ×ˢ Finset.range n := by simpa only [Finset.mem_product, Finset.mem_range, and_comm] using h rw [← hp.2.2.2] at hu obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr exact ⟨mondrian_rect_swap r, List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩), (hcell r x y).mpr hc⟩