mondrian_partition_width_free_height_signed_relation
If 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 distinct tiles whose widths are also indivisible by d.
Statement
theorem mondrian_partition_width_free_height_signed_relation (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r) : ∃ L : List ((ℕ × ℕ × ℕ × ℕ) × Bool), (L.map Prod.fst).Nodup ∧ (∀ t ∈ L, t.1 ∈ P ∧ t.1 ≠ r ∧ ¬ 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 = (mondrian_rect_height r : ℤ)
- 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_graph_walk_signed_heightsEvery walk in the height graph of a positive-height rectangle list is represented by a list of width-indivisible tiles with orientation…
- 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_width_free_height_reachableIf 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…
- 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₁).
- 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_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_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
- Used by 1
- mondrian_partition_width_dvd_of_height_two_chainsIf d divides the square side and all width-indivisible tiles have heights in two superincreasing chains C*p^a and C*r*p^a, with p>r+1 and…
The proof, explained
The proof constructs a simple path in an auxiliary height graph connecting the bottom and top $y$-boundaries of the rectangle $r$, using only other rectangles in the partition whose widths are not divisible by $d$. Lifting this path gives a signed sequence of rectangles whose heights telescope to the total height of $r$. Because the path is simple, its edges—and hence the associated rectangles—are pairwise distinct.
There exists a simple path in the height graph of $P \\setminus \\{r\\}$ connecting the bottom coordinate $r.y_1$ and top coordinate $r.y_2$ of $r$.
By `mondrian_partition_width_free_height_reachable`, the assumption that $d \\mid n$ and tile $r$ has width indivisible by $d$ guarantees that the vertical endpoints $r.y_1$ and $r.y_2$ are reachable from each other in the height graph restricted to the remaining tiles $P \\setminus \\{r\\}$. Applying `elim_path` extracts a simple path `path` between these endpoints.
uses
mondrian_partition_width_free_height_reachableclassical have hreach := mondrian_partition_width_free_height_reachable n d P hP hdn r hr hfree apply hreach.elim_path intro path
Traversing `path` yields a sequence $L$ of signed tiles in $P \\setminus \\{r\\}$ whose edges match the path and whose signed height sum equals $r.y_2 - r.y_1$.
We apply `mondrian_height_graph_walk_signed_heights` to the walk of `path`. The prerequisite that every tile has $y_1 \\le y_2$ follows from the partition property ($y_1 < y_2$) via `Nat.le_of_lt` and `List.mem_filter.mp`. This yields a list $L$ of pairs $(t, b)$ of tiles and signs, an equality `hL` equating the $y$-interval edges of $L$ with the edges of `path`, a membership hypothesis `hmem` stating each tile is in $P \\setminus \\{r\\}$ with width not divisible by $d$, and a summation identity `hsum` stating that the signed sum of heights equals $(r.y_2 : \\mathbb{Z}) - (r.y_1 : \\mathbb{Z})$.
uses
mondrian_height_graph_walk_signed_heights,Nat.le_of_lt,List.mem_filter.mpobtain ⟨L, hL, hmem, hsum⟩ := mondrian_height_graph_walk_signed_heights d (P.filter (fun s => decide (s ≠ r))) (by intro s hs exact Nat.le_of_lt (hP.2.1 s (List.mem_filter.mp hs).1).2) r.2.2.1 r.2.2.2 path.val
The tiles appearing in $L$ are pairwise distinct.
Because `path` is a simple path, it is a trail without repeated edges (`path.property.isTrail.edges_nodup`). Rewriting with `hL`, the list of undirected interval edges corresponding to the tiles in $L$ has no duplicates. By `List.Nodup.of_map`, since projecting each tile to its edge interval produces a list with no duplicates, the list of tiles `L.map Prod.fst` itself contains no duplicates. The equality is simplified using `List.map_map` and `Function.comp_def`.
uses
List.Nodup.of_map,Sym2.mk,List.map_map,Function.comp_defhave hnodup : (L.map Prod.fst).Nodup := by apply List.Nodup.of_map (fun s : ℕ × ℕ × ℕ × ℕ => Sym2.mk s.2.2.1 s.2.2.2) have hh := path.property.isTrail.edges_nodup rw [← hL] at hh simpa only [List.map_map, Function.comp_def] using hh
Supplying $L$ and its duplicate-free proof reduces the theorem to verifying tile conditions and total height sum.
We provide $L$ as the existential witness and discharge the distinctness requirement with `hnodup`. This leaves two subgoals: proving that every tile in $L$ belongs to $P \\setminus \\{r\\}$ with width indivisible by $d$, and proving that their signed heights sum to the height of $r$.
refine ⟨L, hnodup, ?_, ?_⟩Every tile in $L$ belongs to $P$, is distinct from $r$, and has width not divisible by $d$.
For any element $t \\in L$, hypothesis `hmem` guarantees that $t.1$ belongs to the filtered list $P \\setminus \\{r\\}$ and has width indivisible by $d$. Applying `List.mem_filter.mp` gives $t.1 \\in P$ and `decide (t.1 ≠ r) = true`, from which `of_decide_eq_true` establishes $t.1 \\neq r$.
uses
List.mem_filter.mp,of_decide_eq_true· intro t ht obtain ⟨htP, htfree⟩ := hmem t ht obtain ⟨htP, htne⟩ := List.mem_filter.mp htP exact ⟨htP, of_decide_eq_true htne, htfree⟩
The signed sum of the heights of the tiles in $L$ equals the height of $r$.
The height of $r$ is by definition $r.y_2 - r.y_1$. Since $r.y_1 < r.y_2$ for any valid rectangle, `Int.ofNat_sub` rewrites the integer cast of this natural difference into the integer difference $(r.y_2 : \\mathbb{Z}) - (r.y_1 : \\mathbb{Z})$, which matches `hsum` exactly.
uses
Int.ofNat_sub,Nat.le_of_lt· change _ = ((r.2.2.2 - r.2.2.1 : ℕ) : ℤ) rw [Int.ofNat_sub (Nat.le_of_lt (hP.2.1 r hr).2)] exact hsum
Function.comp_def- The definition of function composition: $(f \\circ g)(x) = f(g(x))$.
Int.ofNat_sub- For natural numbers with $m \\le n$, the integer subtraction $\\uparrow n - \\uparrow m$ equals the cast of their difference $\\uparrow(n - m)$.
List.map_map- Composing two map operations on a list is equivalent to mapping the composite function: $(l.\\text{map } f).\\text{map } g = l.\\text{map } (g \\circ f)$.
List.mem_filter.mp- If an element belongs to a filtered list `List.filter p l`, then it belongs to $l$ and satisfies the predicate $p$.
List.Nodup.of_map- If mapping a function $f$ over a list produces a list without duplicates, then the original list contains no duplicates.
mondrian_partition_width_free_height_reachable- In the height graph of tiles in $P \\setminus \\{r\\}$, the bottom and top $y$-coordinates of any tile $r$ whose width is not divisible by $d$ are connected by a path.
mondrian_height_graph_walk_signed_heights- Any walk between $u$ and $v$ in the height graph lifts to a list of signed rectangles whose undirected edge intervals match the walk's edges, each having width indivisible by $d$, such that their signed sum of heights equals $v - u$.
Nat.le_of_lt- If $n < m$ for natural numbers, then $n \\le m$.
of_decide_eq_true- If the decidability test `decide p` evaluates to `true`, then the proposition $p$ holds.
Sym2.mk- Constructs an unordered pair $s(a, b)$ of two elements in the symmetric square `Sym2 \\alpha`.
- Rectangles are represented as 4-tuples $(x_1, x_2, y_1, y_2)$ where `r.2.2.1` is $y_1$ and `r.2.2.2` is $y_2$. Signs are represented as booleans, where `true` corresponds to $+1$ and `false` to $-1$.
- The proof relies on Mathlib's graph theory library, where a `Path` is a walk with distinct vertices; this automatically implies `isTrail`, meaning its edges are also pairwise distinct.
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_signed_relation (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r) : ∃ L : List ((ℕ × ℕ × ℕ × ℕ) × Bool), (L.map Prod.fst).Nodup ∧ (∀ t ∈ L, t.1 ∈ P ∧ t.1 ≠ r ∧ ¬ 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 = (mondrian_rect_height r : ℤ) := by classical have hreach := mondrian_partition_width_free_height_reachable n d P hP hdn r hr hfree apply hreach.elim_path intro path obtain ⟨L, hL, hmem, hsum⟩ := mondrian_height_graph_walk_signed_heights d (P.filter (fun s => decide (s ≠ r))) (by intro s hs exact Nat.le_of_lt (hP.2.1 s (List.mem_filter.mp hs).1).2) r.2.2.1 r.2.2.2 path.val have hnodup : (L.map Prod.fst).Nodup := by apply List.Nodup.of_map (fun s : ℕ × ℕ × ℕ × ℕ => Sym2.mk s.2.2.1 s.2.2.2) have hh := path.property.isTrail.edges_nodup rw [← hL] at hh simpa only [List.map_map, Function.comp_def] using hh refine ⟨L, hnodup, ?_, ?_⟩ · intro t ht obtain ⟨htP, htfree⟩ := hmem t ht obtain ⟨htP, htne⟩ := List.mem_filter.mp htP exact ⟨htP, of_decide_eq_true htne, htfree⟩ · change _ = ((r.2.2.2 - r.2.2.1 : ℕ) : ℤ) rw [Int.ofNat_sub (Nat.le_of_lt (hP.2.1 r hr).2)] exact hsum