AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_bounds

theoremverified

Every rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.

Statement

theorem mondrian_partition_bounds (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (h : mondrian_is_partition n P) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) :
    r.2.1 ≤ n ∧ r.2.2.2 ≤ n ∧
    0 < mondrian_rect_width r ∧ 0 < mondrian_rect_height r ∧
    mondrian_rect_width r ≤ n ∧ mondrian_rect_height r ≤ n
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 5
  • 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_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • 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_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 12

The proof, explained

To bound the coordinates and side lengths of any rectangle $r$ in the partition, the proof identifies its top-right cell $(x_2 - 1, y_2 - 1)$. Because $r$ is non-degenerate ($x_1 < x_2$ and $y_1 < y_2$), this cell is well-defined and lies in the set of cells covered by $r$. Since the partition covers the entire $n \times n$ square $\{0, \dots, n-1\}^2$, the cell must lie in that square, which forces $x_2 - 1 < n$ and $y_2 - 1 < n$. Finally, linear arithmetic combines these bounds with non-negativity to conclude that the upper coordinates and side lengths are all at most $n$ and the side lengths are strictly positive.

  1. The rectangle $r$ is non-degenerate: $r.1 < r.2.1$ and $r.2.2.1 < r.2.2.2$.

    The partition hypothesis `h` specifies via its second component (`h.2.1`) that every rectangle in $P$ has strictly smaller lower coordinates than upper coordinates. Applying this to $r \in P$ gives $r.1 < r.2.1$ and $r.2.2.1 < r.2.2.2$.

    line 6

      obtain ⟨hx, hy⟩ := h.2.1 r hr
  2. The cell $(r.2.1 - 1, r.2.2.2 - 1)$ belongs to the set of cells of $r$ (`mondrian_rect_cells r`).

    The set `mondrian_rect_cells r` is defined as the Cartesian product $[r.1, r.2.1) \times [r.2.2.1, r.2.2.2)$. Rewriting membership using `Finset.mem_product` and `Finset.mem_Ico` yields the inequalities $r.1 \le r.2.1 - 1 < r.2.1$ and $r.2.2.1 \le r.2.2.2 - 1 < r.2.2.2$, which follow by linear integer arithmetic (`omega`) from the non-degeneracy conditions $r.1 < r.2.1$ and $r.2.2.1 < r.2.2.2$.

    lines 7–9

    uses Finset.mem_product, Finset.mem_Ico

      have hm : (r.2.1 - 1, r.2.2.2 - 1) ∈ mondrian_rect_cells r := by
        simp only [mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]
        omega
  3. The upper coordinates of $r$ satisfy $r.2.1 - 1 < n$ and $r.2.2.2 - 1 < n$.

    Because $r \in P$ (converted to finset membership via `List.mem_toFinset.mpr`) and $(r.2.1 - 1, r.2.2.2 - 1) \in \text{mondrian\_rect\_cells } r$, the cell belongs to the union of all rectangle cells in $P$ by `Finset.mem_biUnion.mpr`. The partition property `h.2.2.2` states that this union equals $\{0, \dots, n-1\} \times \{0, \dots, n-1\}$. Simplifying Cartesian product and range membership using `Finset.mem_product` and `Finset.mem_range` shows that both coordinates of the cell are strictly less than $n$.

    lines 10–14

    uses Finset.mem_biUnion.mpr, List.mem_toFinset.mpr, Finset.mem_product, Finset.mem_range

      have hu : (r.2.1 - 1, r.2.2.2 - 1) ∈
          P.toFinset.biUnion mondrian_rect_cells :=
        Finset.mem_biUnion.mpr ⟨r, List.mem_toFinset.mpr hr, hm⟩
      rw [h.2.2.2] at hu
      simp only [Finset.mem_product, Finset.mem_range] at hu
  4. The upper coordinates and side lengths of $r$ are at most $n$, and both side lengths are strictly positive.

    Unfolding the definitions of `mondrian_rect_width r` ($r.2.1 - r.1$) and `mondrian_rect_height r` ($r.2.2.2 - r.2.2.1$), all six bounds ($r.2.1 \le n$, $r.2.2.2 \le n$, $0 < r.2.1 - r.1$, $0 < r.2.2.2 - r.2.2.1$, $r.2.1 - r.1 \le n$, and $r.2.2.2 - r.2.2.1 \le n$) follow by linear arithmetic (`omega`) from $r.1 < r.2.1$, $r.2.2.1 < r.2.2.2$, $r.2.1 - 1 < n$, and $r.2.2.2 - 1 < n$, along with the non-negativity of natural numbers.

    lines 15–16

      dsimp [mondrian_rect_width, mondrian_rect_height]
      omega
Finset.mem_product
A pair $p$ belongs to the Cartesian product $s \times t$ of two finite sets if and only if $p.1 \in s$ and $p.2 \in t$.
Finset.mem_Ico
An element $x$ belongs to the half-open interval $[a, b)$ if and only if $a \le x$ and $x < b$.
Finset.mem_biUnion.mpr
If an element belongs to the image $t(a)$ for some $a \in s$, then it belongs to the indexed union $\bigcup_{a \in s} t(a)$.
List.mem_toFinset.mpr
An element belonging to a list also belongs to the finite set formed by that list.
Finset.mem_range
A natural number $m$ belongs to `Finset.range n` (the set $\{0, \dots, n-1\}$) if and only if $m < n$.

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_partition_bounds (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (h : mondrian_is_partition n P) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) :    r.2.1 ≤ n ∧ r.2.2.2 ≤ n ∧    0 < mondrian_rect_width r ∧ 0 < mondrian_rect_height r ∧    mondrian_rect_width r ≤ n ∧ mondrian_rect_height r ≤ n := by  obtain ⟨hx, hy⟩ := h.2.1 r hr  have hm : (r.2.1 - 1, r.2.2.2 - 1) ∈ mondrian_rect_cells r := by    simp only [mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]    omega  have hu : (r.2.1 - 1, r.2.2.2 - 1) ∈      P.toFinset.biUnion mondrian_rect_cells :=    Finset.mem_biUnion.mpr ⟨r, List.mem_toFinset.mpr hr, hm⟩  rw [h.2.2.2] at hu  simp only [Finset.mem_product, Finset.mem_range] at hu  dsimp [mondrian_rect_width, mondrian_rect_height]  omega
See it in the graphDiscuss this resultChallenge it