mondrian_perfect_partition_div
Dividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
Statement
theorem mondrian_perfect_partition_div (a c : ℕ) (ha : 0 < a)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P)
(hz : mondrian_defect P = 0)
(hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) :
mondrian_is_partition c (P.map (mondrian_rect_div a)) ∧
mondrian_defect (P.map (mondrian_rect_div 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 12
- 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_divAn admissible partition of the a times c square, with every tile side a multiple of positive a, becomes an admissible partition of the…
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
- 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_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).
- Used by 4
- 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_perfect_partition_div_common_areaIf q divides the square side and both dimensions of every tile in a perfect partition, and the common area is q^2 times B, coordinate…
- 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…
- mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
The proof, explained
The theorem states that dividing all tile coordinates by a positive integer a preserves defect-0 partitions when a divides all tile dimensions. Partition admissibility of the scaled square of side c is supplied by the lemma `mondrian_partition_div`. To show the scaled partition also has defect 0, the proof shows that coordinate division scales every tile's area by 1 / a^2; since all original tiles have equal area (defect 0), all scaled tiles must also have equal area, giving a defect of 0.
The scaled rectangles form an admissible partition of a square of side c, leaving only the defect condition to be proved.
The goal is a conjunction: the scaled tiles must form an admissible partition of size c, and their defect must be 0. The first part is solved directly by applying `mondrian_partition_div` using the hypothesis that a divides the width and height of every rectangle in P and that a > 0.
uses
mondrian_partition_divrefine ⟨mondrian_partition_div a c ha P hp hd, ?_⟩Dividing coordinates by a scales the area of each tile by a factor of 1 / a^2: for any r ∈ P, a^2 * area(r / a) = area(r).
For any tile r ∈ P, the partition hypothesis ensures that r is non-degenerate (r.1 < r.2.1 and r.2.2.1 < r.2.2.2). Because a > 0 divides both the width and height of r, `mondrian_rect_div_dimensions` shows that a * width(r / a) = width(r) and a * height(r / a) = height(r). Unfolding `mondrian_rect_area` as width times height and rearranging factors with `ring` yields a^2 * area(r / a) = (a * width(r / a)) * (a * height(r / a)) = width(r) * height(r) = area(r).
uses
mondrian_rect_div_dimensions,mondrian_rect_areahave hscale : ∀ r ∈ P, a ^ 2 * mondrian_rect_area (mondrian_rect_div a r) = mondrian_rect_area r := by intro r hr obtain ⟨hw, hh⟩ := 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 calc a ^ 2 * mondrian_rect_area (mondrian_rect_div a r) = (a * mondrian_rect_width (mondrian_rect_div a r)) * (a * mondrian_rect_height (mondrian_rect_div a r)) := by dsimp [mondrian_rect_area] ring _ = mondrian_rect_area r := by rw [hw, hh]; rfl
If the list of rectangles P is empty, the defect of the scaled list is 0.
We perform a structural case split on whether P is empty or a cons-cell. If P is empty, mapping coordinate division yields an empty list, whose defect is 0 by definition of `mondrian_defect`.
uses
mondrian_defectcases P with | nil => simp [mondrian_defect]
If P is non-empty (r :: P), all scaled tiles have the same area, so the scaled partition has defect 0.
By `mondrian_defect_zero_of_equal`, it suffices to show that every tile in the scaled list has area equal to that of the first scaled tile, area(r / a). Any tile s in the scaled list is of the form t / a for some t ∈ r :: P by `List.mem_map.mp`. Since a > 0, a^2 > 0 by `pow_pos`, so by left cancellation (`Nat.eq_of_mul_eq_mul_left`), it suffices to show a^2 * area(t / a) = a^2 * area(r / a). Applying the area scaling identity `hscale` rewrites this to area(t) = area(r). Because the original partition has defect 0, lemma `mondrian_defect_zero_equal` guarantees that area(t) = area(r), completing the proof.
uses
mondrian_defect_zero_of_equal,List.mem_map.mp,pow_pos,Nat.eq_of_mul_eq_mul_left,mondrian_defect_zero_equal| cons r P => apply mondrian_defect_zero_of_equal _ (mondrian_rect_area (mondrian_rect_div a r)) intro s hs obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hs apply Nat.eq_of_mul_eq_mul_left (pow_pos ha 2) rw [hscale t ht, hscale r (by simp)] exact mondrian_defect_zero_equal (r :: P) hz t r ht (by simp)
mondrian_partition_div- Dividing coordinates by a > 0 maps an admissible partition of a square of side a * c to an admissible partition of a square of side c, provided a divides the width and height of every rectangle.
mondrian_rect_div_dimensions- For a non-degenerate rectangle whose width and height are divisible by a > 0, multiplying the dimensions of the coordinate-divided rectangle by a recovers the original width and height.
mondrian_rect_area- The area of a rectangle, defined as the product of its width and height.
mondrian_defect- The defect of a list of rectangles, defined as the difference between the maximum and minimum tile areas (or 0 if the list is empty).
mondrian_defect_zero_of_equal- A list of rectangles has defect 0 if all rectangles in the list have the same area.
List.mem_map.mp- An element belongs to the image of a list under a function if and only if it is the image of some element in the list.
pow_pos- A strictly positive number raised to any natural power is strictly positive.
Nat.eq_of_mul_eq_mul_left- If n > 0 and n * m = n * k for natural numbers, then m = k (multiplicative cancellation on the left).
mondrian_defect_zero_equal- If a list of rectangles has defect 0, then any two rectangles in the list have the same area.
- Although an admissible partition by definition contains at least two rectangles, the proof performs a structural case split on the list P, disposing of the empty list case purely syntactically without using the length condition.
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_div (a c : ℕ) (ha : 0 < a) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P) (hz : mondrian_defect P = 0) (hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) : mondrian_is_partition c (P.map (mondrian_rect_div a)) ∧ mondrian_defect (P.map (mondrian_rect_div a)) = 0 := by refine ⟨mondrian_partition_div a c ha P hp hd, ?_⟩ have hscale : ∀ r ∈ P, a ^ 2 * mondrian_rect_area (mondrian_rect_div a r) = mondrian_rect_area r := by intro r hr obtain ⟨hw, hh⟩ := 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 calc a ^ 2 * mondrian_rect_area (mondrian_rect_div a r) = (a * mondrian_rect_width (mondrian_rect_div a r)) * (a * mondrian_rect_height (mondrian_rect_div a r)) := by dsimp [mondrian_rect_area] ring _ = mondrian_rect_area r := by rw [hw, hh]; rfl cases P with | nil => simp [mondrian_defect] | cons r P => apply mondrian_defect_zero_of_equal _ (mondrian_rect_area (mondrian_rect_div a r)) intro s hs obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hs apply Nat.eq_of_mul_eq_mul_left (pow_pos ha 2) rw [hscale t ht, hscale r (by simp)] exact mondrian_defect_zero_equal (r :: P) hz t r ht (by simp)