AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_width_free_height_reachable

theoremverified

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

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.

  1. 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.

    lines 5–8

      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
  2. $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$.

    lines 9–10

      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]
  3. 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)$.

    lines 11–20

    uses Or.inl, mondrian_height_graph_adj_of_mem, Or.inr

      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])
  4. 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)$.

    line 21

    uses mondrian_partition_isolated_row_function

      exact 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$.

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_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)
See it in the graphDiscuss this resultChallenge it