mondrian_partition_mul
Multiplying all rectangle coordinates by a positive integer a sends an admissible c-square partition to an admissible a times c square partition.
Statement
theorem mondrian_partition_mul (a c : ℕ) (ha : 0 < a)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P) :
mondrian_is_partition (a * c) (P.map (mondrian_rect_mul 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 8
- 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_mulMultiply all four rectangle coordinates by a.
- mondrian_rect_mul_cellsA cell belongs to a rectangle with coordinates multiplied by positive a exactly when its quotient cell belongs to the original rectangle.
- mondrian_rect_mul_dimensionsMultiplying coordinates by a multiplies both side lengths 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_mulMultiplying all coordinates by a positive integer preserves perfect admissible partitions.
The proof, explained
The theorem verifies the four conditions of an admissible partition for the scaled rectangles: size, non-degeneracy, pairwise disjointness and non-congruence, and exact coverage of the scaled square. List length and strict coordinate inequalities are preserved under scaling by a positive factor a. Disjointness, non-congruence, and square coverage reduce directly to the corresponding properties of the original partition because scaling scales dimensions linearly and maps a cell (i, j) to the scaled rectangle if and only if (⌊i/a⌋, ⌊j/a⌋) lies in the original rectangle.
The scaled list contains at least two rectangles.
Mapping the scaling function over the list P preserves its length by List.length_map. Because P has length at least 2 by hypothesis hp.1, the scaled list also has length at least 2.
uses
List.length_maprefine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
Every rectangle in the scaled list is non-degenerate (has strictly positive width and height).
Any rectangle r in the scaled list is the image mondrian_rect_mul a s of some rectangle s ∈ P (by List.mem_map.mp). Since P is a valid partition, s has strictly positive width and height. Multiplying these strict inequalities by the positive factor a via Nat.mul_lt_mul_of_pos_left shows that r also has strictly positive width and height.
uses
List.mem_map.mp,Nat.mul_lt_mul_of_pos_left· intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr obtain ⟨hx, hy⟩ := hp.2.1 s hs exact ⟨Nat.mul_lt_mul_of_pos_left hx ha, Nat.mul_lt_mul_of_pos_left hy ha⟩
The rectangles in the scaled list are pairwise disjoint and pairwise non-congruent.
By List.pairwise_map, it suffices to show that if two rectangles r, s ∈ P are disjoint and non-congruent, their scalings remain disjoint and non-congruent. If a cell (i, j) belonged to both scaled rectangles, then (⌊i/a⌋, ⌊j/a⌋) would belong to both r and s by mondrian_rect_mul_cells, contradicting disjointness via Finset.disjoint_left.mp. Furthermore, mondrian_rect_mul_dimensions shows that scaling multiplies dimensions by a; if the scaled rectangles were congruent, cancelling the positive factor a using Nat.eq_of_mul_eq_mul_left would imply r and s are congruent, contradicting the non-congruence hypothesis.
uses
List.pairwise_map,Finset.disjoint_left,Finset.disjoint_left.mp,mondrian_rect_mul_cells,mondrian_rect_mul_dimensions,Nat.eq_of_mul_eq_mul_left· rw [List.pairwise_map] apply hp.2.2.1.imp intro r s hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨i, j⟩ hi hj exact Finset.disjoint_left.mp hrs.1 ((mondrian_rect_mul_cells a ha r i j).mp hi) ((mondrian_rect_mul_cells a ha s i j).mp hj) · intro hcong apply hrs.2 obtain ⟨hrw, hrh⟩ := mondrian_rect_mul_dimensions a r obtain ⟨hsw, hsh⟩ := mondrian_rect_mul_dimensions a s rcases hcong with ⟨hw, hh⟩ | ⟨hw, hh⟩ · left constructor · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrw, hsw] using hw · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrh, hsh] using hh · right constructor · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrw, hsh] using hw · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrh, hsw] using hh
Every cell belonging to a scaled rectangle is contained in the scaled square [0, a * c) × [0, a * c).
If a cell (i, j) belongs to some scaled rectangle mondrian_rect_mul a s for s ∈ P, then by mondrian_rect_mul_cells the cell (i / a, j / a) belongs to s, and thus to the union of rectangles in P. Since P partitions [0, c) × [0, c), we have i / a < c and j / a < c. By Nat.div_lt_iff_lt_mul and commutativity of multiplication, this is equivalent to i < a * c and j < a * c, showing that (i, j) lies in the product of ranges.
uses
Finset.mem_biUnion.mp,List.mem_map.mp,List.mem_toFinset.mp,mondrian_rect_mul_cells,Finset.mem_biUnion.mpr,List.mem_toFinset.mpr,Finset.mem_product,Finset.mem_range,Nat.div_lt_iff_lt_mul,Nat.mul_comm· 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_mul_cells a ha s i j).mp hi have hu : (i / a, j / a) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩ rw [hp.2.2.2] at hu simpa only [Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hu
Every cell in the scaled square [0, a * c) × [0, a * c) is covered by some scaled rectangle.
Given a cell (i, j) in [0, a * c) × [0, a * c), the equivalence Nat.div_lt_iff_lt_mul ensures that (i / a, j / a) ∈ [0, c) × [0, c). Because P covers [0, c) × [0, c), there is some rectangle r ∈ P containing (i / a, j / a). Applying mondrian_rect_mul_cells in reverse shows that (i, j) belongs to mondrian_rect_mul a r, which is an element of the scaled partition.
uses
Finset.mem_product,Finset.mem_range,Nat.div_lt_iff_lt_mul,Nat.mul_comm,Finset.mem_biUnion.mp,Finset.mem_biUnion.mpr,mondrian_rect_mul_cells,List.mem_toFinset.mpr,List.mem_map.mpr,List.mem_toFinset.mp· intro hi have hu : (i / a, j / a) ∈ Finset.range c ×ˢ Finset.range c := by simpa only [Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hi rw [← hp.2.2.2] at hu obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr refine ⟨mondrian_rect_mul a r, ?_, (mondrian_rect_mul_cells a ha r i j).mpr hm⟩ exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)
List.length_map- The length of a list is invariant under mapping a function over it.
List.mem_map.mp- An element belongs to the image of a list under a map if and only if it is the image of some element in the list.
List.mem_map.mpr- An element is in the image of a list under a map if it is the image of an element belonging to the list.
Nat.mul_lt_mul_of_pos_left- Multiplying both sides of a strict inequality by a positive natural number preserves the inequality.
List.pairwise_map- A mapped list satisfies a pairwise relation if and only if the original list satisfies the relation pulled back along the mapping function.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set is in the second set.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element of the first is not an element of the second.
mondrian_rect_mul_dimensions- Scaling a rectangle by a positive factor a multiplies both its width and its height by a.
mondrian_rect_mul_cells- A cell (i, j) belongs to a rectangle scaled by a if and only if (⌊i/a⌋, ⌊j/a⌋) belongs to the unscaled rectangle.
Nat.eq_of_mul_eq_mul_left- A strictly positive natural number can be cancelled from the left of an equality of products.
Finset.mem_biUnion.mp- An element belongs to a union of a family of finite sets only if it belongs to one of the sets in the family.
Finset.mem_biUnion.mpr- If an element belongs to one member of a family of finite sets, it belongs to the big union of the family.
List.mem_toFinset.mp- An element of the finite set constructed from a list is an element of that list.
List.mem_toFinset.mpr- An element belonging to a list belongs to the finite set constructed from that list.
Finset.mem_product- A pair belongs to a Cartesian product of 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 is in Finset.range n if and only if it is strictly less than n.
Nat.div_lt_iff_lt_mul- For a positive divisor k, integer division x / k < y is equivalent to x < y * k.
Nat.mul_comm- Multiplication of natural numbers is commutative.
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_mul (a c : ℕ) (ha : 0 < a) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P) : mondrian_is_partition (a * c) (P.map (mondrian_rect_mul a)) := by refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩ · intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr obtain ⟨hx, hy⟩ := hp.2.1 s hs exact ⟨Nat.mul_lt_mul_of_pos_left hx ha, Nat.mul_lt_mul_of_pos_left hy ha⟩ · rw [List.pairwise_map] apply hp.2.2.1.imp intro r s hrs refine ⟨?_, ?_⟩ · rw [Finset.disjoint_left] rintro ⟨i, j⟩ hi hj exact Finset.disjoint_left.mp hrs.1 ((mondrian_rect_mul_cells a ha r i j).mp hi) ((mondrian_rect_mul_cells a ha s i j).mp hj) · intro hcong apply hrs.2 obtain ⟨hrw, hrh⟩ := mondrian_rect_mul_dimensions a r obtain ⟨hsw, hsh⟩ := mondrian_rect_mul_dimensions a s rcases hcong with ⟨hw, hh⟩ | ⟨hw, hh⟩ · left constructor · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrw, hsw] using hw · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrh, hsh] using hh · right constructor · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrw, hsh] using hw · apply Nat.eq_of_mul_eq_mul_left ha simpa only [hrh, hsw] using 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_mul_cells a ha s i j).mp hi have hu : (i / a, j / a) ∈ P.toFinset.biUnion mondrian_rect_cells := Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩ rw [hp.2.2.2] at hu simpa only [Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hu · intro hi have hu : (i / a, j / a) ∈ Finset.range c ×ˢ Finset.range c := by simpa only [Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hi rw [← hp.2.2.2] at hu obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu apply Finset.mem_biUnion.mpr refine ⟨mondrian_rect_mul a r, ?_, (mondrian_rect_mul_cells a ha r i j).mpr hm⟩ exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)