mondrian_height_graph_walk_signed_heights
Every walk in the height graph of a positive-height rectangle list is represented by a list of width-indivisible tiles with orientation signs; their signed height sum is the difference of the endpoint row levels, and their unordered endpoint pairs are exactly the walk edges.
Statement
theorem mondrian_height_graph_walk_signed_heights (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hpos : ∀ r ∈ P, r.2.2.1 ≤ r.2.2.2) (u v : ℕ) (w : (mondrian_height_graph d P).Walk u v) : ∃ L : List ((ℕ × ℕ × ℕ × ℕ) × Bool), (L.map (fun t => Sym2.mk t.1.2.2.1 t.1.2.2.2)) = w.edges ∧ (∀ t ∈ L, t.1 ∈ P ∧ ¬ d ∣ mondrian_rect_width t.1) ∧ (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (v : ℤ) - (u : ℤ)
- 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
Quot.soundpropext- Built on 3
- 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_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- 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 theorem is proved by induction on the walk $w$. For an empty walk, the empty list of tiles trivially witnesses the claim. For a non-empty walk starting with edge $(u, v)$ followed by tail walk $w$, the induction hypothesis yields a signed list $L$ for $w$, while the graph adjacency provides a width-indivisible rectangle $r \in P$ connecting row levels $u$ and $v$. Prepending $r$ to $L$ with sign `true` (if traversing upward) or `false` (if traversing downward) matches the initial edge and adds signed height $v - u$, which telescopes with the tail sum $z - v$ to yield the desired difference $z - u$.
The claim holds for the empty walk from $u$ to $u$.
We proceed by induction on the walk $w$. For the base case of an empty walk from $u$ to $u$, the empty list $L = []$ serves as a witness: its mapped edge list is empty (matching the edges of the empty walk), every element vacuously satisfies the membership and width-indivisibility condition, and its sum of signed heights is $0 = u - u$.
induction w with | nil => exact ⟨[], by simp, by simp, by simp⟩
For an edge $(u, v)$ followed by a tail walk $w$ from $v$ to $z$, there is a width-indivisible rectangle $r \in P$ connecting $u$ and $v$ with integer height $r.y_2 - r.y_1$.
By the induction hypothesis on the tail walk $w$ from $v$ to $z$, there is a list $L$ of signed rectangles satisfying the theorem. By definition of adjacency in the height graph, the step $(u, v)$ implies $u \ne v$ and the existence of a rectangle $r \in P$ whose width is not divisible by $d$, such that either $(u = r.y_1 \land v = r.y_2)$ or $(u = r.y_2 \land v = r.y_1)$. Since $r.y_1 \le r.y_2$ by assumption, the integer height of $r$ is $r.y_2 - r.y_1$.
uses
Int.ofNat_sub| @cons u v z hadj w ih => obtain ⟨L, hL, hmem, hsum⟩ := ih have hdata : u ≠ v ∧ ∃ r ∈ P, ¬ d ∣ mondrian_rect_width r ∧ ((u = r.2.2.1 ∧ v = r.2.2.2) ∨ (u = r.2.2.2 ∧ v = r.2.2.1)) := hadj obtain ⟨_, r, hr, hfree, hxy⟩ := hdata have hheight : (mondrian_rect_height r : ℤ) = (r.2.2.2 : ℤ) - (r.2.2.1 : ℤ) := by exact_mod_cast Int.ofNat_sub (hpos r hr)It suffices to consider whether the edge $(u, v)$ traverses $r$ in the upward or downward direction.
We split into two cases based on the orientation of the step along $r$: either $u = r.y_1$ and $v = r.y_2$ (upward traversal), or $u = r.y_2$ and $v = r.y_1$ (downward traversal).
rcases hxy with ⟨hu, hv⟩ | ⟨hu, hv⟩
When the edge traverses $r$ upward ($u = r.y_1$ and $v = r.y_2$), prepending $(r, \mathrm{true})$ to $L$ satisfies all three conditions for the extended walk.
We witness the existential by prepending the tile $r$ with positive orientation `true` to the inductive witness $L$. This verifies the three properties: 1. Edges (lines 20–22): Prepending $(r, \mathrm{true})$ prepends the unordered pair $\{r.y_1, r.y_2\} = \{u, v\}$ to the edge list of $L$, which matches the prepended initial edge $\{u, v\}$ of the extended walk. 2. Validity (lines 23–26): Any tile in $(r, \mathrm{true}) :: L$ is either the new head $r$—which belongs to $P$ and is width-indivisible by $d$ by adjacency—or belongs to $L$, which satisfies both properties by the induction hypothesis. 3. Signed height sum (lines 27–31): Because the sign is `true`, the new head contributes $+\mathrm{height}(r) = r.y_2 - r.y_1 = v - u$. Adding the induction hypothesis sum $z - v$, the total sum telescopes to $(v - u) + (z - v) = z - u$.
uses
SimpleGraph.Walk.edges_cons,List.map_cons,congrArg,List.mem_cons.mp· refine ⟨(r, true) :: L, ?_, ?_, ?_⟩ · rw [SimpleGraph.Walk.edges_cons] simp only [List.map_cons, hL] exact congrArg (fun e => e :: w.edges) (by rw [hu, hv]) · intro t ht rcases List.mem_cons.mp ht with ht | ht · subst t; exact ⟨hr, hfree⟩ · exact hmem t ht · change (mondrian_rect_height r : ℤ) + (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (z : ℤ) - (u : ℤ) rw [hsum, hheight, hu, hv] ring
When the edge traverses $r$ downward ($u = r.y_2$ and $v = r.y_1$), prepending $(r, \mathrm{false})$ to $L$ satisfies all three conditions for the extended walk.
We witness the existential by prepending $r$ with negative orientation `false` to $L$. 1. Edges (lines 33–35): The edge corresponding to $(r, \mathrm{false})$ is $\{r.y_1, r.y_2\} = \{v, u\}$, which equals $\{u, v\}$ by symmetry (`Sym2.eq_swap`), matching the walk's first edge. 2. Validity (lines 36–39): The head $r$ is valid by the adjacency hypothesis and tail elements are valid by induction. 3. Signed height sum (lines 40–44): With orientation `false`, the height contributes $-\mathrm{height}(r) = -(r.y_2 - r.y_1) = r.y_1 - r.y_2 = v - u$. Adding the tail sum $z - v$, the sum telescopes to $(v - u) + (z - v) = z - u$.
uses
SimpleGraph.Walk.edges_cons,List.map_cons,congrArg,Sym2.eq_swap,List.mem_cons.mp· refine ⟨(r, false) :: L, ?_, ?_, ?_⟩ · rw [SimpleGraph.Walk.edges_cons] simp only [List.map_cons, hL] exact congrArg (fun e => e :: w.edges) (by rw [hu, hv]; exact Sym2.eq_swap) · intro t ht rcases List.mem_cons.mp ht with ht | ht · subst t; exact ⟨hr, hfree⟩ · exact hmem t ht · change -(mondrian_rect_height r : ℤ) + (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (z : ℤ) - (u : ℤ) rw [hsum, hheight, hu, hv] ring
Int.ofNat_sub- For natural numbers $m \le n$, the integer cast of their difference equals the difference of their integer casts: $(n - m : \mathbb{Z}) = (n : \mathbb{Z}) - (m : \mathbb{Z})$.
SimpleGraph.Walk.edges_cons- The edge list of a walk formed by prepending an edge $(u, v)$ to a walk $p$ is the unordered pair $\{u, v\}$ followed by the edge list of $p$.
List.map_cons- Mapping a function over a non-empty list $a :: l$ yields $f(a)$ prepended to the result of mapping over $l$.
congrArg- Applying a function to equal arguments produces equal results.
List.mem_cons.mp- An element belongs to $a :: l$ only if it is equal to $a$ or belongs to the tail $l$.
Sym2.eq_swap- An unordered pair is symmetric: $\{a, b\} = \{b, a\}$.
- In the formalization, rectangles are represented as 4-tuples $(x_1, x_2, y_1, y_2)$ of natural numbers, where $r.2.2.1$ is $y_1$ (the bottom row coordinate) and $r.2.2.2$ is $y_2$ (the top row coordinate).
- Unordered pairs of vertices forming edges in the simple graph are represented using Lean's `Sym2` type, with $s(u, v)$ denoting $\{u, v\}$.
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_height_graph_walk_signed_heights (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hpos : ∀ r ∈ P, r.2.2.1 ≤ r.2.2.2) (u v : ℕ) (w : (mondrian_height_graph d P).Walk u v) : ∃ L : List ((ℕ × ℕ × ℕ × ℕ) × Bool), (L.map (fun t => Sym2.mk t.1.2.2.1 t.1.2.2.2)) = w.edges ∧ (∀ t ∈ L, t.1 ∈ P ∧ ¬ d ∣ mondrian_rect_width t.1) ∧ (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (v : ℤ) - (u : ℤ) := by induction w with | nil => exact ⟨[], by simp, by simp, by simp⟩ | @cons u v z hadj w ih => obtain ⟨L, hL, hmem, hsum⟩ := ih have hdata : u ≠ v ∧ ∃ r ∈ P, ¬ d ∣ mondrian_rect_width r ∧ ((u = r.2.2.1 ∧ v = r.2.2.2) ∨ (u = r.2.2.2 ∧ v = r.2.2.1)) := hadj obtain ⟨_, r, hr, hfree, hxy⟩ := hdata have hheight : (mondrian_rect_height r : ℤ) = (r.2.2.2 : ℤ) - (r.2.2.1 : ℤ) := by exact_mod_cast Int.ofNat_sub (hpos r hr) rcases hxy with ⟨hu, hv⟩ | ⟨hu, hv⟩ · refine ⟨(r, true) :: L, ?_, ?_, ?_⟩ · rw [SimpleGraph.Walk.edges_cons] simp only [List.map_cons, hL] exact congrArg (fun e => e :: w.edges) (by rw [hu, hv]) · intro t ht rcases List.mem_cons.mp ht with ht | ht · subst t; exact ⟨hr, hfree⟩ · exact hmem t ht · change (mondrian_rect_height r : ℤ) + (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (z : ℤ) - (u : ℤ) rw [hsum, hheight, hu, hv] ring · refine ⟨(r, false) :: L, ?_, ?_, ?_⟩ · rw [SimpleGraph.Walk.edges_cons] simp only [List.map_cons, hL] exact congrArg (fun e => e :: w.edges) (by rw [hu, hv]; exact Sym2.eq_swap) · intro t ht rcases List.mem_cons.mp ht with ht | ht · subst t; exact ⟨hr, hfree⟩ · exact hmem t ht · change -(mondrian_rect_height r : ℤ) + (L.map (fun t => if t.2 then (mondrian_rect_height t.1 : ℤ) else -(mondrian_rect_height t.1 : ℤ))).sum = (z : ℤ) - (u : ℤ) rw [hsum, hheight, hu, hv] ring