AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_partition_mul

theoremverified

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
Used by 1

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

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

    line 6

    uses mondrian_partition_mul

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

    lines 7–8

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

    lines 9–10

    uses mondrian_defect_zero_of_equal

      | cons r P =>
        apply mondrian_defect_zero_of_equal _ (mondrian_rect_area (mondrian_rect_mul a r))
  4. 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.

    lines 11–14

    uses List.mem_map.mp, mondrian_rect_mul_area, mondrian_defect_zero_equal

        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)]
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.

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