mondrian_perfect_partition_mul
Multiplying all coordinates by a positive integer preserves perfect admissible partitions.
Statement
theorem mondrian_perfect_partition_mul (a c : ℕ) (ha : 0 < a)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P)
(hz : mondrian_defect P = 0) :
mondrian_is_partition (a * c) (P.map (mondrian_rect_mul a)) ∧
mondrian_defect (P.map (mondrian_rect_mul a)) = 0- 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_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- mondrian_defect_zero_of_equalA rectangle list whose members all have the same area has defect zero, including the empty list.
- 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_mulMultiplying all rectangle coordinates by a positive integer a sends an admissible c-square partition to an admissible a times c square…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_mulMultiply all four rectangle coordinates by a.
- mondrian_rect_mul_areaMultiplying rectangle coordinates by a multiplies its area by a squared.
- Used by 1
- mondrian_perfect_partition_large_prime_iffFor every positive integer c, prime p greater than c, and natural exponent e, the square of side c times p to the e has a perfect…
The proof, explained
The proof splits the conjunction into showing that scaling preserves the partition structure and preserves defect zero. The partition structure is preserved by `mondrian_partition_mul`. For the defect, the empty list case is trivial, and for a nonempty list r :: P', it suffices by `mondrian_defect_zero_of_equal` to show that every scaled rectangle has the same area as the scaled rectangle a * r. This holds because scaling scales every rectangle's area by a^2 (`mondrian_rect_mul_area`), and all original rectangles had equal area because the initial defect was zero (`mondrian_defect_zero_equal`).
The scaled rectangles form an admissible partition of the square of side a * c.
We split the conjunction into two goals: showing the scaled list is an admissible partition, and showing its defect is zero. The first goal is discharged directly by `mondrian_partition_mul`, leaving only the defect goal.
uses
mondrian_partition_mulrefine ⟨mondrian_partition_mul a c ha P hp, ?_⟩If the list of rectangles is empty, the defect of the scaled list is 0. automation
We case split on the list of rectangles P. When P is empty, mapping over it produces the empty list, whose defect is 0 by definition of `mondrian_defect`.
cases P with | nil => simp [mondrian_defect]
When P has at least one rectangle r, it suffices to show that every rectangle in the scaled list has area equal to the area of the scaled rectangle a * r.
In the cons case P = r :: P', by `mondrian_defect_zero_of_equal`, if every rectangle in the scaled partition has area equal to the area of the scaled first rectangle a * r, then the defect of the scaled partition is 0.
uses
mondrian_defect_zero_of_equal| cons r P => apply mondrian_defect_zero_of_equal _ (mondrian_rect_area (mondrian_rect_mul a r))Every rectangle in the scaled partition has area equal to the area of the scaled rectangle a * r.
Let s be an arbitrary rectangle in the scaled partition. By `List.mem_map.mp`, s = a * t for some rectangle t in the original list r :: P'. Applying `mondrian_rect_mul_area` to both sides expands their areas to a^2 * area(t) and a^2 * area(r). Since the original partition had defect 0, `mondrian_defect_zero_equal` ensures area(t) = area(r) (with membership of r in r :: P' discharged by simplification), which equates the two scaled areas and completes the proof.
uses
List.mem_map.mp,mondrian_rect_mul_area,mondrian_defect_zero_equalintro s hs obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hs rw [mondrian_rect_mul_area, mondrian_rect_mul_area] rw [mondrian_defect_zero_equal (r :: P) hz t r ht (by simp)]
mondrian_partition_mul- Scaling all rectangles in an admissible partition of a square of side c by a positive integer factor a yields an admissible partition of a square of side a * c.
mondrian_defect_zero_of_equal- If every rectangle in a list has the same area A, then the defect of the list is 0.
List.mem_map.mp- If an element belongs to the image of a list under a function, then it is the image of some element of the original list.
mondrian_rect_mul_area- Scaling a rectangle by a factor of a multiplies its area by a^2.
mondrian_defect_zero_equal- If a list of rectangles has defect 0, then any two rectangles in that list have the same area.
- The definition of an admissible partition requires the list of rectangles to have length at least 2, making the empty list case mathematically impossible; the proof handles P = [] directly by simplifying the definition of defect rather than deriving a contradiction from the partition hypothesis.
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_perfect_partition_mul (a c : ℕ) (ha : 0 < a) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P) (hz : mondrian_defect P = 0) : mondrian_is_partition (a * c) (P.map (mondrian_rect_mul a)) ∧ mondrian_defect (P.map (mondrian_rect_mul a)) = 0 := by refine ⟨mondrian_partition_mul a c ha P hp, ?_⟩ cases P with | nil => simp [mondrian_defect] | cons r P => apply mondrian_defect_zero_of_equal _ (mondrian_rect_area (mondrian_rect_mul a r)) intro s hs obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hs rw [mondrian_rect_mul_area, mondrian_rect_mul_area] rw [mondrian_defect_zero_equal (r :: P) hz t r ht (by simp)]