mondrian_partition_isolated_row_function
Let 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 tile whose width is indivisible by d, then the selected width is divisible by d.
Statement
theorem mondrian_partition_isolated_row_function (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (hdn : d ∣ n)
(r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (f : ℕ → ℤ)
(hrstep : f r.2.2.2 - f r.2.2.1 = 1)
(hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ f s.2.2.2 = f s.2.2.1) :
d ∣ mondrian_rect_width 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 7
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_list_sum_count_modIf each integer list contribution is congruent modulo p to u when its predicate holds and to zero otherwise, their sum is congruent to u…
- mondrian_partition_horizontal_momentFor every integer-valued function f on row levels, the sum over an admissible n-square partition of width times the increment of f across…
- 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).
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- Used by 1
- 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…
The proof, explained
The proof evaluates the horizontal moment sum $\sum_{s \in P} \mathrm{width}(s) \cdot (f(s.y_2) - f(s.y_1))$ in two ways. Globally, by `mondrian_partition_horizontal_moment`, this sum telescopes across the $n \times n$ square to $n \cdot (f(n) - f(0))$, which is divisible by $d$ because $d \mid n$. Locally, every rectangle other than $r$ contributes a quantity divisible by $d$, while $r$ contributes $\mathrm{width}(r) \cdot 1$ with multiplicity one. Subtracting the two divisibility results shows that $d$ must divide $\mathrm{width}(r)$.
Define $g(s) = \mathrm{width}(s) \cdot (f(s.y_2) - f(s.y_1))$ for each rectangle $s$, and note that $g(r) = \mathrm{width}(r)$.
For any rectangle $s$, $g(s)$ is the product of its width and the increment of $f$ between its bottom and top boundaries. On the distinguished rectangle $r$, this increment is $1$ by hypothesis `hrstep`, so $g(r) = \mathrm{width}(r) \cdot 1 = \mathrm{width}(r)$.
let g := fun s : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width s : ℤ) * (f s.2.2.2 - f s.2.2.1) have hgr : g r = (mondrian_rect_width r : ℤ) := by dsimp [g]; rw [hrstep]; ring
For every rectangle $s \in P$, $d$ divides $g(s) - (\text{if } s = r \text{ then } \mathrm{width}(r) \text{ else } 0)$.
We check each rectangle $s \in P$ by cases. When $s = r$, the difference is $g(r) - \mathrm{width}(r) = 0$, which is divisible by $d$. When $s \ne r$, the conditional term is zero, leaving $g(s)$; by hypothesis `hothers`, either $d$ divides the width of $s$ (so $d \mid g(s)$ by `dvd_mul_of_dvd_left`) or $f(s.y_2) = f(s.y_1)$ (so $g(s) = 0$, which is divisible by $d$).
uses
Bool.false_eq_true,if_false,sub_zero,dvd_mul_of_dvd_lefthave hterm : ∀ s ∈ P, (d : ℤ) ∣ g s - if s == r then (mondrian_rect_width r : ℤ) else 0 := by intro s hs by_cases he : s = r · subst s simp [hgr] · have hfalse : (s == r) = false := by simp [he] simp only [hfalse, Bool.false_eq_true, if_false, sub_zero] rcases hothers s hs he with hw | hh · have hwZ : (d : ℤ) ∣ (mondrian_rect_width s : ℤ) := by exact_mod_cast hw exact dvd_mul_of_dvd_left hwZ _ · simp [g, hh]
The list $P$ has no duplicate rectangles, so $r$ appears in $P$ exactly once.
Because $P$ is a valid partition, its rectangles are pairwise non-congruent (`hP.2.2.1`). Congruence is reflexive, so no rectangle can be equal to another, meaning $P$ has no duplicates (`List.nodup_iff_pairwise_ne`, `Or.inl`). Since $r \in P$, it appears with multiplicity $1$ (`List.count_eq_one_of_mem`, `List.count_eq_countP`).
uses
List.nodup_iff_pairwise_ne,Or.inl,List.count_eq_countP,List.count_eq_one_of_memhave hnodup : P.Nodup := by rw [List.nodup_iff_pairwise_ne] apply hP.2.2.1.imp intro a b hab he subst b exact hab.2 (Or.inl ⟨rfl, rfl⟩) have hcount : P.countP (fun s => s == r) = 1 := by simpa only [← List.count_eq_countP] using List.count_eq_one_of_mem hnodup hr
$d$ divides $\sum_{s \in P} g(s) - \mathrm{width}(r)$.
Summing the termwise divisibility across $P$ with `mondrian_list_sum_count_mod` shows that $d$ divides $\sum_{s \in P} g(s) - \mathrm{count}(r) \cdot \mathrm{width}(r)$. Since $r$ occurs with count $1$, this simplifies to $d \mid \sum_{s \in P} g(s) - \mathrm{width}(r)$.
uses
mondrian_list_sum_count_mod,Nat.cast_one,one_mulhave hsum := mondrian_list_sum_count_mod P (d : ℤ) (mondrian_rect_width r : ℤ) g (fun s => s == r) hterm rw [hcount] at hsum simp only [Nat.cast_one, one_mul] at hsum
$d$ divides the total sum $\sum_{s \in P} g(s)$.
By the horizontal moment identity `mondrian_partition_horizontal_moment`, the total sum $\sum_{s \in P} g(s)$ equals $n \cdot (f(n) - f(0))$. Since $d$ divides the square side $n$ (`hdn`), $d$ divides this product by `dvd_mul_of_dvd_left`.
uses
mondrian_partition_horizontal_moment,dvd_mul_of_dvd_lefthave htotal : (d : ℤ) ∣ (P.map g).sum := by rw [show (P.map g).sum = (n : ℤ) * (f n - f 0) from mondrian_partition_horizontal_moment n P hP f] exact dvd_mul_of_dvd_left (by exact_mod_cast hdn) _
$d$ divides $\mathrm{width}(r)$.
Since $d$ divides the total sum and also divides the total sum minus $\mathrm{width}(r)$, it divides their difference by `dvd_sub`. The difference algebraically simplifies to $\mathrm{width}(r)$, and casting from $\mathbb{Z}$ to $\mathbb{N}$ concludes the proof.
uses
dvd_subhave hh := dvd_sub htotal hsum have heq : (P.map g).sum - ((P.map g).sum - (mondrian_rect_width r : ℤ)) = (mondrian_rect_width r : ℤ) := by ring rw [heq] at hh exact_mod_cast hh
Bool.false_eq_true- The boolean false is not equal to true.
if_false- An if-then-else whose condition is false evaluates to the else branch.
sub_zero- Subtracting zero leaves an element unchanged: $a - 0 = a$.
dvd_mul_of_dvd_left- If $a \mid b$, then $a \mid b \cdot c$ for any $c$.
List.nodup_iff_pairwise_ne- A list has no duplicate elements if and only if all pairs of distinct indices have unequal elements.
Or.inl- From a proof of $A$, infer the disjunction $A \lor B$.
List.count_eq_countP- The count of elements equal to $a$ equals the count of elements satisfying the predicate of being equal to $a$.
List.count_eq_one_of_mem- If a list has no duplicates and contains an element $a$, then $a$ occurs exactly once in the list.
mondrian_list_sum_count_mod- If $p$ divides $f(s) - (\text{if } \mathrm{pred}(s) \text{ then } u \text{ else } 0)$ for every element $s \in L$, then $p$ divides the sum of $f$ over $L$ minus $\mathrm{countP}(\mathrm{pred}, L) \cdot u$.
Nat.cast_one- The natural number $1$ cast to another numeric type equals $1$.
one_mul- Multiplying by $1$ on the left leaves an element unchanged: $1 \cdot a = a$.
mondrian_partition_horizontal_moment- For any partition of an $n \times n$ square, the sum over all rectangles of width times the vertical increment $f(y_2) - f(y_1)$ equals $n \cdot (f(n) - f(0))$.
dvd_sub- If $a \mid b$ and $a \mid c$, then $a \mid b - c$.
- Rectangles are represented as tuples $(x_1, x_2, y_1, y_2)$ of type $\mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}$, so $r.2.2.1$ is $y_1$ and $r.2.2.2$ is $y_2$. The divisibility argument is carried out over $\mathbb{Z}$ and then cast back to $\mathbb{N}$.
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_isolated_row_function (n d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (f : ℕ → ℤ) (hrstep : f r.2.2.2 - f r.2.2.1 = 1) (hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ f s.2.2.2 = f s.2.2.1) : d ∣ mondrian_rect_width r := by let g := fun s : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width s : ℤ) * (f s.2.2.2 - f s.2.2.1) have hgr : g r = (mondrian_rect_width r : ℤ) := by dsimp [g]; rw [hrstep]; ring have hterm : ∀ s ∈ P, (d : ℤ) ∣ g s - if s == r then (mondrian_rect_width r : ℤ) else 0 := by intro s hs by_cases he : s = r · subst s simp [hgr] · have hfalse : (s == r) = false := by simp [he] simp only [hfalse, Bool.false_eq_true, if_false, sub_zero] rcases hothers s hs he with hw | hh · have hwZ : (d : ℤ) ∣ (mondrian_rect_width s : ℤ) := by exact_mod_cast hw exact dvd_mul_of_dvd_left hwZ _ · simp [g, hh] have hnodup : P.Nodup := by rw [List.nodup_iff_pairwise_ne] apply hP.2.2.1.imp intro a b hab he subst b exact hab.2 (Or.inl ⟨rfl, rfl⟩) have hcount : P.countP (fun s => s == r) = 1 := by simpa only [← List.count_eq_countP] using List.count_eq_one_of_mem hnodup hr have hsum := mondrian_list_sum_count_mod P (d : ℤ) (mondrian_rect_width r : ℤ) g (fun s => s == r) hterm rw [hcount] at hsum simp only [Nat.cast_one, one_mul] at hsum have htotal : (d : ℤ) ∣ (P.map g).sum := by rw [show (P.map g).sum = (n : ℤ) * (f n - f 0) from mondrian_partition_horizontal_moment n P hP f] exact dvd_mul_of_dvd_left (by exact_mod_cast hdn) _ have hh := dvd_sub htotal hsum have heq : (P.map g).sum - ((P.map g).sum - (mondrian_rect_width r : ℤ)) = (mondrian_rect_width r : ℤ) := by ring rw [heq] at hh exact_mod_cast hh