mondrian_partition_bounds
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
- mondrian_no_perfect_three_prime_area_one_factorFor three distinct primes p,q,r with p>r+1, no perfect admissible integer square partition has common tile area q^s*r*p^a, for arbitrary…
- mondrian_perfect_prime_free_side_countsIn any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not…
- mondrian_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
- mondrian_perfect_area_three_prime_factorsEvery tile area in a perfect admissible integer square partition has at least three distinct prime factors.
- mondrian_perfect_min_width_layer_countFor a perfect admissible n-square partition and prime p dividing n, suppose b is the minimum p-adic exponent of tile widths. Then b is at…
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- mondrian_partition_prime_free_shape_count_boundIn an admissible equal-area partition, any selected collection of tiles each having a side indivisible by q has cardinality at most the…
- 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_no_perfect_of_shape_boundThere 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…
- mondrian_perfect_width_free_count_ne_twoIn a perfect admissible square partition, for any divisor d of the square side, exactly two tiles cannot have widths indivisible by d.
- mondrian_perfect_height_injectiveThe heights of the tiles in a perfect admissible square partition are pairwise distinct.
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
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.
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$.
obtain ⟨hx, hy⟩ := h.2.1 r hrThe 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$.
uses
Finset.mem_product,Finset.mem_Icohave 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
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$.
uses
Finset.mem_biUnion.mpr,List.mem_toFinset.mpr,Finset.mem_product,Finset.mem_rangehave 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
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.
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$.
- In Lean, a 4-tuple $r : \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}$ is right-associated as $(x_1, (x_2, (y_1, y_2)))$. Consequently, $r.1$ is $x_1$, $r.2.1$ is $x_2$, $r.2.2.1$ is $y_1$, and $r.2.2.2$ is $y_2$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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