AFTD Auto-Formalizing Theoretical Domains

mondrian_height_graph_walk_signed_heights

theoremverified

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

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

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

    lines 9–10

      induction w with
      | nil => exact ⟨[], by simp, by simp, by simp⟩
  2. 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$.

    lines 11–17

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

    line 18

        rcases hxy with ⟨hu, hv⟩ | ⟨hu, hv⟩
  4. 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$.

    lines 19–31

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

    lines 32–44

    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\}$.

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