AFTD Auto-Formalizing Theoretical Domains

mondrian_defect_zero_equal

theoremverified

Any two rectangles in a list of defect zero have equal area.

Statement

theorem mondrian_defect_zero_equal (P : List (ℕ × ℕ × ℕ × ℕ))
    (h : mondrian_defect P = 0) (r s : ℕ × ℕ × ℕ × ℕ)
    (hr : r ∈ P) (hs : s ∈ P) : mondrian_rect_area r = mondrian_rect_area s
Source
arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 13

The proof, explained

The defect of a rectangle partition is defined as the maximum area among its rectangles minus the minimum area. Since the partition contains rectangles r and s, the list of rectangle areas is non-empty, so it admits a well-defined maximum a and minimum b. Every rectangle's area is bounded between b and a; since the defect is zero, a - b = 0 implies a ≤ b, pinching the interval [b, a] to a single point and forcing r and s to have identical areas.

  1. The areas of rectangles r and s belong to the list of rectangle areas of P.

    Because r and s are in P, applying the area function to the elements of P produces a list containing their respective areas, by List.mem_map.mpr.

    lines 4–5

    uses List.mem_map.mpr

      have hr' : mondrian_rect_area r ∈ P.map mondrian_rect_area := List.mem_map.mpr ⟨r, hr, rfl⟩
      have hs' : mondrian_rect_area s ∈ P.map mondrian_rect_area := List.mem_map.mpr ⟨s, hs, rfl⟩
  2. The list of rectangle areas has a well-defined maximum value a.

    We case-split on the maximum of the list of areas, (P.map mondrian_rect_area).max?. If it were none, List.max?_eq_none_iff.mp would imply that the list of areas is empty, which contradicts that the area of r is an element of the list. Thus the maximum is some a for some natural number a.

    lines 6–10

    uses List.max?_eq_none_iff.mp

      cases hmax : (P.map mondrian_rect_area).max? with
      | none =>
        have := List.max?_eq_none_iff.mp hmax
        rw [this] at hr'
        simp at hr'
  3. The list of rectangle areas has a well-defined minimum value b.

    Similarly, we case-split on the minimum of the list of areas, (P.map mondrian_rect_area).min?. If it were none, List.min?_eq_none_iff.mp would imply that the list of areas is empty, contradicting the presence of the area of r. Hence the minimum is some b for some natural number b.

    lines 11–16

    uses List.min?_eq_none_iff.mp

      | some a =>
        cases hmin : (P.map mondrian_rect_area).min? with
        | none =>
          have := List.min?_eq_none_iff.mp hmin
          rw [this] at hr'
          simp at hr'
  4. The areas of r and s are bounded between the minimum area b and the maximum area a.

    By the definitions of maximum and minimum for lists (List.max?_eq_some_iff.mp and List.min?_eq_some_iff.mp), any element in the list is bounded above by a and below by b. Since the areas of r and s belong to the list, we have b ≤ mondrian_rect_area r ≤ a and b ≤ mondrian_rect_area s ≤ a.

    lines 17–23

    uses List.max?_eq_some_iff.mp, List.min?_eq_some_iff.mp

        | some b =>
          have hmax' := List.max?_eq_some_iff.mp hmax
          have hmin' := List.min?_eq_some_iff.mp hmin
          have h1 := hmax'.2 _ hr'
          have h2 := hmax'.2 _ hs'
          have h3 := hmin'.2 _ hr'
          have h4 := hmin'.2 _ hs'
  5. The area of rectangle r is equal to the area of rectangle s.

    By definition, the defect of P is the difference between the maximum and minimum areas, so a - b = 0. On the natural numbers, a - b = 0 implies a ≤ b by Nat.sub_eq_zero_iff_le. Together with b ≤ mondrian_rect_area r ≤ a and b ≤ mondrian_rect_area s ≤ a, linear arithmetic forces both areas to equal a = b, establishing that their areas are equal.

    lines 24–26

    uses Option.getD_some, Nat.sub_eq_zero_iff_le

          simp only [mondrian_defect, hmax, hmin, Option.getD_some,
            Nat.sub_eq_zero_iff_le] at h
          omega
List.mem_map.mpr
An element x belongs to the image list List.map f L if there exists an element in L whose image under f is x.
List.max?_eq_none_iff.mp
The maximum of a list is none if and only if the list is empty.
List.min?_eq_none_iff.mp
The minimum of a list is none if and only if the list is empty.
List.max?_eq_some_iff.mp
If the maximum of a list is some a, then a is in the list and every element of the list is at most a.
List.min?_eq_some_iff.mp
If the minimum of a list is some b, then b is in the list and every element of the list is at least b.
Option.getD_some
Extracting a value from some a with a default fallback returns a.
Nat.sub_eq_zero_iff_le
For natural numbers n and m, the truncated difference n - m is zero if and only if n ≤ m.

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_defect_zero_equal (P : List (ℕ × ℕ × ℕ × ℕ))    (h : mondrian_defect P = 0) (r s : ℕ × ℕ × ℕ × ℕ)    (hr : r ∈ P) (hs : s ∈ P) : mondrian_rect_area r = mondrian_rect_area s := by  have hr' : mondrian_rect_area r ∈ P.map mondrian_rect_area := List.mem_map.mpr ⟨r, hr, rfl⟩  have hs' : mondrian_rect_area s ∈ P.map mondrian_rect_area := List.mem_map.mpr ⟨s, hs, rfl⟩  cases hmax : (P.map mondrian_rect_area).max? with  | none =>    have := List.max?_eq_none_iff.mp hmax    rw [this] at hr'    simp at hr'  | some a =>    cases hmin : (P.map mondrian_rect_area).min? with    | none =>      have := List.min?_eq_none_iff.mp hmin      rw [this] at hr'      simp at hr'    | some b =>      have hmax' := List.max?_eq_some_iff.mp hmax      have hmin' := List.min?_eq_some_iff.mp hmin      have h1 := hmax'.2 _ hr'      have h2 := hmax'.2 _ hs'      have h3 := hmin'.2 _ hr'      have h4 := hmin'.2 _ hs'      simp only [mondrian_defect, hmax, hmin, Option.getD_some,        Nat.sub_eq_zero_iff_le] at h      omega
See it in the graphDiscuss this resultChallenge it