mondrian_partition_width_free_height_reachable
If d divides the square side and a tile has width indivisible by d, its bottom and top row levels remain connected in the height graph after removing that tile from the rectangle list.
Statement
theorem mondrian_partition_width_free_height_reachable (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r) : (mondrian_height_graph d (P.filter (fun s => decide (s ≠ r)))).Reachable r.2.2.1 r.2.2.2
- Source
- Helper for OP-280, arXiv:2610.19193, Section 1. Height-level networks are motivated by the graph model in arXiv:2007.09639, Section 1; the filtered graph and row-potential cut argument are developed here for the remaining cases with at least three prime factors.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- mondrian_height_graphThe undirected graph on integer row levels whose edges are the bottom and top levels of tiles with width indivisible by d; loops are…
- mondrian_height_graph_adj_of_memEvery positive-height member of the rectangle list whose width is indivisible by d gives a height-graph edge between its bottom and top…
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_partition_isolated_row_functionLet d divide the square side. If an integer row-level function has increment one on a selected tile and has zero increment on every other…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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…
- 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).
- Arena.Reachable.transReachability is transitive.
- Used by 1
- mondrian_partition_width_free_height_signed_relationIf d divides the square side and a selected tile has width indivisible by d, its height is a signed sum of heights of other, pairwise…
The proof, explained
The proof proceeds by contradiction, assuming that the bottom and top boundaries of the tile $r$ are disconnected in the height graph of the remaining tiles. Under this assumption, the indicator function of the connected component containing $r$'s bottom boundary defines a row potential that jumps by $1$ across $r$ but remains constant across the row boundaries of every other tile whose width is indivisible by $d$. The isolated row function lemma (`mondrian_partition_isolated_row_function`) then forces $d$ to divide the width of $r$, contradicting the premise that $r$ has indivisible width.
Assume for contradiction that the row levels of $r$ are disconnected in $H$, and define a component indicator function $f$.
Working classically, let $H$ be the height graph on the partition with $r$ removed. We assume for contradiction that the top row level $r.y_2$ is not reachable from the bottom row level $r.y_1$ in $H$. We then define a row function $f : \mathbb{N} \to \mathbb{Z}$ by $f(y) = 0$ if $y$ is reachable from $r.y_1$ in $H$, and $f(y) = 1$ otherwise.
classical let H := mondrian_height_graph d (P.filter (fun s => decide (s ≠ r))) by_contra hnot let f : ℕ → ℤ := fun y => if H.Reachable r.2.2.1 y then 0 else 1
$f(r.y_2) - f(r.y_1) = 1$.
Because reachability is reflexive, $r.y_1$ can reach itself in $H$, giving $f(r.y_1) = 0$. By the contradiction hypothesis, $r.y_2$ is not reachable from $r.y_1$, so $f(r.y_2) = 1$. Hence $f(r.y_2) - f(r.y_1) = 1 - 0 = 1$.
have hstep : f r.2.2.2 - f r.2.2.1 = 1 := by simp [f, show ¬ H.Reachable r.2.2.1 r.2.2.2 from hnot]
For every other tile $s \in P \setminus \{r\}$, either $d$ divides the width of $s$ or $f(s.y_2) = f(s.y_1)$.
Let $s \in P$ with $s \neq r$. If $d \mid \text{width}(s)$, the claim holds immediately. If $d \nmid \text{width}(s)$, then $s$ belongs to the filtered list $P \setminus \{r\}$. Since $s$ has strictly positive height, `mondrian_height_graph_adj_of_mem` gives that $s.y_1$ and $s.y_2$ are adjacent in $H$, and thus mutually reachable. By transitivity of reachability, $r.y_1$ reaches $s.y_2$ if and only if it reaches $s.y_1$, which means $f(s.y_2) = f(s.y_1)$.
uses
Or.inl,mondrian_height_graph_adj_of_mem,Or.inrhave hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ f s.2.2.2 = f s.2.2.1 := by intro s hs hne by_cases hsd : d ∣ mondrian_rect_width s · exact Or.inl hsd have hadj : H.Adj s.2.2.1 s.2.2.2 := mondrian_height_graph_adj_of_mem d _ s (by simp [hs, hne]) hsd (hP.2.1 s hs).2 have hreach := hadj.reachable have heq : H.Reachable r.2.2.1 s.2.2.2 ↔ H.Reachable r.2.2.1 s.2.2.1 := ⟨fun h => h.trans hreach.symm, fun h => h.trans hreach⟩ exact Or.inr (by simp only [f, heq])
The existence of $f$ implies that $d$ divides the width of $r$, contradicting the hypothesis.
Applying `mondrian_partition_isolated_row_function` to the partition $P$, tile $r$, and the function $f$ shows that $d \mid \text{width}(r)$. This directly contradicts the assumption `hfree` that $d \nmid \text{width}(r)$.
uses
mondrian_partition_isolated_row_functionexact hfree (mondrian_partition_isolated_row_function n d P hP hdn r hr f hstep hothers)
Or.inl- From a proof of $A$, deduce the disjunction $A \lor B$.
Or.inr- From a proof of $B$, deduce the disjunction $A \lor B$.
mondrian_height_graph_adj_of_mem- If a tile $r$ belongs to list $P$, its width is not divisible by $d$, and its height is strictly positive, then its bottom and top row levels are adjacent in the height graph of $P$.
mondrian_partition_isolated_row_function- In a partition of an $n \times n$ square with $d \mid n$, if a row function $f$ jumps by $1$ across a tile $r$ and is constant across the row boundaries of every other tile whose width is not divisible by $d$, then $d$ divides the width of $r$.
- The potential function $f$ takes values in $\mathbb{Z}$ rather than $\{0, 1\}$ to conform to the interface expected by `mondrian_partition_isolated_row_function`.
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_width_free_height_reachable (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r) : (mondrian_height_graph d (P.filter (fun s => decide (s ≠ r)))).Reachable r.2.2.1 r.2.2.2 := by classical let H := mondrian_height_graph d (P.filter (fun s => decide (s ≠ r))) by_contra hnot let f : ℕ → ℤ := fun y => if H.Reachable r.2.2.1 y then 0 else 1 have hstep : f r.2.2.2 - f r.2.2.1 = 1 := by simp [f, show ¬ H.Reachable r.2.2.1 r.2.2.2 from hnot] have hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ f s.2.2.2 = f s.2.2.1 := by intro s hs hne by_cases hsd : d ∣ mondrian_rect_width s · exact Or.inl hsd have hadj : H.Adj s.2.2.1 s.2.2.2 := mondrian_height_graph_adj_of_mem d _ s (by simp [hs, hne]) hsd (hP.2.1 s hs).2 have hreach := hadj.reachable have heq : H.Reachable r.2.2.1 s.2.2.2 ↔ H.Reachable r.2.2.1 s.2.2.1 := ⟨fun h => h.trans hreach.symm, fun h => h.trans hreach⟩ exact Or.inr (by simp only [f, heq]) exact hfree (mondrian_partition_isolated_row_function n d P hP hdn r hr f hstep hothers)