AFTD Auto-Formalizing Theoretical Domains

mondrian_height_graph_adj_of_mem

theoremverified

Every positive-height member of the rectangle list whose width is indivisible by d gives a height-graph edge between its bottom and top row levels.

Statement

theorem mondrian_height_graph_adj_of_mem (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r)
    (hpos : r.2.2.1 < r.2.2.2) :
    (mondrian_height_graph d P).Adj 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
none — Lean reports it depends on no axioms
Built on 2
  • 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_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
Used by 2

The proof, explained

To show that the bottom and top vertical coordinates of the rectangle r form an edge in the height graph, we directly verify the definition of adjacency. The strict inequality between the bottom and top coordinates guarantees that the two vertices are distinct, and r itself provides the required rectangle in P whose width is not divisible by d.

  1. The levels r.2.2.1 and r.2.2.2 are adjacent in the height graph mondrian_height_graph d P

    By definition, two vertices x and y are adjacent in the height graph if x ≠ y and there exists a rectangle in P with indivisible width whose bottom and top coordinates are x and y (in either order). We instantiate this definition using r itself: the condition r.2.2.1 ≠ r.2.2.2 follows from r.2.2.1 < r.2.2.2 by Nat.ne_of_lt; the rectangle r belongs to P and has width indivisible by d by the hypotheses hr and hfree; and the coordinate matching holds by reflexivity in the left branch of the disjunction via Or.inl.

    line 5

    uses Nat.ne_of_lt, Or.inl

      exact ⟨Nat.ne_of_lt hpos, r, hr, hfree, Or.inl ⟨rfl, rfl⟩⟩
Nat.ne_of_lt
if a natural number is strictly less than another, it is not equal to it
Or.inl
given a proof of A, establishes the disjunction A ∨ B

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_adj_of_mem (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r)    (hpos : r.2.2.1 < r.2.2.2) :    (mondrian_height_graph d P).Adj r.2.2.1 r.2.2.2 := by  exact ⟨Nat.ne_of_lt hpos, r, hr, hfree, Or.inl ⟨rfl, rfl⟩⟩
See it in the graphDiscuss this resultChallenge it