AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_partition_div

theoremverified

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

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.

  1. 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.

    line 7

    uses mondrian_partition_div

      refine ⟨mondrian_partition_div a c ha P hp hd, ?_⟩
  2. 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).

    lines 8–19

    uses mondrian_rect_div_dimensions, mondrian_rect_area

      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
  3. 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`.

    lines 20–21

    uses mondrian_defect

      cases P with
      | nil => simp [mondrian_defect]
  4. 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.

    lines 22–28

    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.

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

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)
See it in the graphDiscuss this resultChallenge it