AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_of_shape_bound

theoremverified

There is no perfect n-square partition if, for every k at least two and positive A with k times A equal to n squared, fewer than k distinct dimension pairs of area A fit in the square.

Statement

theorem mondrian_no_perfect_of_shape_bound (n : ℕ)
    (hbound : ∀ k A : ℕ, 2 ≤ k → 0 < A → k * A = n ^ 2 →
      (mondrian_factor_shapes n A).card < k) :
    ¬ ∃ P, mondrian_is_partition n P ∧ mondrian_defect P = 0
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 12
  • mondrian_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
  • mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
  • mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • 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).
  • mondrian_partition_boundsEvery rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • 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…
Used by 2

The proof, explained

The proof proceeds by contradiction: suppose there exists a partition P of the n-by-n square with defect 0. Since a valid partition must have at least two rectangles, P is non-empty, and its rectangles all share a positive common area A, giving |P| * A = n^2. Because rectangles in P are pairwise non-congruent, each corresponds to a distinct factor shape fitting in the square, meaning |P| ≤ |mondrian_factor_shapes n A|. However, applying the shape-bound hypothesis with k = |P| ≥ 2 and area A gives |mondrian_factor_shapes n A| < |P|, a contradiction.

  1. Assume for contradiction that a partition P with defect 0 exists; P cannot be empty.

    We assume for contradiction that there exists a partition P of the n-by-n square with defect 0. Splitting on whether P is empty, the empty list case is impossible because any valid partition must contain at least two rectangles (2 ≤ |P|), whereas the empty list has length 0.

    lines 5–7

      rintro ⟨P, hp, hz⟩
      cases P with
      | nil => have := hp.1; simp at this
  2. The partition contains a rectangle r whose area is strictly positive.

    In the non-empty case P = r :: P', rectangle r belongs to the partition. By mondrian_partition_bounds, r has strictly positive width and height, and by Nat.mul_pos their product—the area of r—is strictly positive.

    lines 8–11

    uses mondrian_partition_bounds, Nat.mul_pos

      | cons r P =>
        have hr : r ∈ r :: P := by simp
        have hb := mondrian_partition_bounds n (r :: P) hp r hr
        have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1
  3. The number of rectangles in the partition is at most the number of valid factor shapes of area equal to r's area.

    Because the partition has defect 0, all rectangles in it share the same area as r (by mondrian_defect_zero_equal). Since no two rectangles in a partition are congruent, each rectangle has a distinct shape, so by mondrian_shape_bound the number of rectangles |r :: P'| is at most the number of valid shapes of that area fitting in the n-by-n square.

    lines 12–13

    uses mondrian_shape_bound, mondrian_defect_zero_equal

        have hc := mondrian_shape_bound n (mondrian_rect_area r) (r :: P) hp
          (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr)
  4. The hypothesis implies that the number of valid factor shapes of this area is strictly less than the number of rectangles in the partition.

    By mondrian_perfect_area_product, the number of rectangles multiplied by their common area equals the square's total area, |r :: P'| * area(r) = n^2. Instantiating the hypothesis hbound with k = |r :: P'| and A = area(r) (valid since 2 ≤ k, 0 < A, and k * A = n^2) shows that the number of valid factor shapes is strictly less than |r :: P'|.

    lines 14–15

    uses mondrian_perfect_area_product

        have he := mondrian_perfect_area_product n (r :: P) hp hz r hr
        have hlt := hbound (r :: P).length (mondrian_rect_area r) hp.1 hA he
  5. The upper bound and strict lower bound on the number of rectangles contradict each other.

    The inequalities |r :: P'| ≤ |shapes| and |shapes| < |r :: P'| cannot both hold; linear integer arithmetic (omega) derives False and completes the proof.

    line 16

        omega
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
mondrian_partition_bounds
In a valid partition of an n-by-n square, every rectangle has coordinates within bounds and strictly positive width and height bounded by n.
mondrian_defect_zero_equal
If a partition has defect zero, then all of its rectangles have identical area.
mondrian_shape_bound
If all rectangles in a partition of an n-by-n square have the same area A, then the number of rectangles is at most the number of valid non-congruent factor shapes of area A that fit in the square.
mondrian_perfect_area_product
In a partition of an n-by-n square with defect zero, the number of rectangles multiplied by the area of any rectangle equals n squared.

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_no_perfect_of_shape_bound (n : ℕ)    (hbound : ∀ k A : ℕ, 2 ≤ k → 0 < A → k * A = n ^ 2 →      (mondrian_factor_shapes n A).card < k) :    ¬ ∃ P, mondrian_is_partition n P ∧ mondrian_defect P = 0 := by  rintro ⟨P, hp, hz⟩  cases P with  | nil => have := hp.1; simp at this  | cons r P =>    have hr : r ∈ r :: P := by simp    have hb := mondrian_partition_bounds n (r :: P) hp r hr    have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1    have hc := mondrian_shape_bound n (mondrian_rect_area r) (r :: P) hp      (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr)    have he := mondrian_perfect_area_product n (r :: P) hp hz r hr    have hlt := hbound (r :: P).length (mondrian_rect_area r) hp.1 hA he    omega
See it in the graphDiscuss this resultChallenge it