mondrian_partition_isolated_height_residue
Let d divide the square side. If every tile except r either has width divisible by d or height divisible by m, and r has height indivisible by m, then the width of r is divisible by d.
Statement
theorem mondrian_partition_isolated_height_residue (n d m : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (hdn : d ∣ n)
(r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P)
(hrm : ¬ m ∣ mondrian_rect_height r)
(hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s) :
d ∣ mondrian_rect_width r- Source
- For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
- 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_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_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_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…
- Used by 3
- mondrian_partition_width_dvd_of_height_prime_chainSuppose d divides the square side and all tiles whose widths are indivisible by d have heights C times powers of a fixed prime p, with…
- mondrian_partition_prime_free_height_dvdWhen d divides the square side, every common divisor of the heights of all other tiles with width indivisible by d also divides the height…
- mondrian_perfect_width_free_count_ne_twoIn a perfect admissible square partition, for any divisor d of the square side, exactly two tiles cannot have widths indivisible by d.
The proof, explained
To show that $d \mid \text{width}(r)$, we define an indicator function $f(y)$ for the residue $r.y_2 \pmod m$ and consider the weighted sum $\sum_{s \in P} \text{width}(s)(f(s.y_2) - f(s.y_1))$. By the horizontal moment identity for partitions, the total sum equals $n(f(n) - f(0))$, which is divisible by $d$ because $d \mid n$. On the other hand, term by term, every tile other than $r$ contributes a multiple of $d$ (either because its width is divisible by $d$ or because its height is divisible by $m$, making the $f$-difference vanish), whereas $r$ contributes exactly $\text{width}(r)$ since $m \nmid \text{height}(r)$. Since $r$ appears exactly once in the partition, the difference between the total sum and $\text{width}(r)$ is divisible by $d$, forcing $d \mid \text{width}(r)$.
Define an indicator function $f$ on vertical coordinates and an associated term $g(s)$ for each tile $s$.
We set $f(y)$ to $1$ if $y \equiv r.y_2 \pmod m$ and $0$ otherwise. For each tile $s$, we define $g(s) = \text{width}(s) \cdot (f(s.y_2) - f(s.y_1))$.
let f : ℕ → ℤ := fun y => if y % m = r.2.2.2 % m then 1 else 0 let g := fun s : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width s : ℤ) * (f s.2.2.2 - f s.2.2.1)
The value of $g$ on the distinguished tile $r$ is its width.
Because $m$ does not divide the height of $r$, the lower and upper vertical coordinates $r.y_1$ and $r.y_2$ are not congruent modulo $m$. Therefore, $f(r.y_2) = 1$ and $f(r.y_1) = 0$, so $g(r) = \text{width}(r) \cdot (1 - 0) = \text{width}(r)$.
uses
Nat.modEq_iff_dvd',Nat.le_of_lthave hrmod : r.2.2.1 % m ≠ r.2.2.2 % m := by intro hh apply hrm exact (Nat.modEq_iff_dvd' (Nat.le_of_lt (hP.2.1 r hr).2)).mp hh have hgr : g r = (mondrian_rect_width r : ℤ) := by simp [g, f, hrmod]
Modulo $d$, each term $g(s)$ equals $\text{width}(r)$ if $s = r$, and $0$ otherwise.
If $s = r$, the difference $g(r) - \text{width}(r)$ is zero, which is divisible by $d$. If $s \neq r$, the difference is simply $g(s)$; by hypothesis, either $d \mid \text{width}(s)$ (so $d \mid g(s)$) or $m \mid \text{height}(s)$ (which implies $s.y_1 \equiv s.y_2 \pmod m$, making $f(s.y_2) - f(s.y_1) = 0$ and $g(s) = 0$, also divisible by $d$).
uses
Bool.false_eq_true,if_false,sub_zero,dvd_mul_of_dvd_left,Nat.modEq_iff_dvd',Nat.le_of_lthave 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 _ · have hmod : s.2.2.1 % m = s.2.2.2 % m := (Nat.modEq_iff_dvd' (Nat.le_of_lt (hP.2.1 s hs).2)).mpr hh simp [g, f, hmod]
The list $P$ contains no duplicates, and the distinguished tile $r$ occurs in $P$ exactly once.
The definition of a partition requires distinct tiles in the list to be non-congruent, whereas identical tiles are congruent; thus $P$ has no duplicate elements. Since $r \in P$ and $P$ has no duplicates, the count of tiles equal to $r$ is exactly $1$.
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
The total sum of $g$ minus $\text{width}(r)$ is divisible by $d$.
Summing the term-by-term divisibility over all tiles via `mondrian_list_sum_count_mod`, $d$ divides the total sum $\sum_{s \in P} g(s) - (\text{count of } r) \cdot \text{width}(r)$. Since $r$ appears with count $1$, this simplifies to $d \mid \sum_{s \in P} g(s) - \text{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
The total sum $\sum_{s \in P} g(s)$ is divisible by $d$.
By the horizontal moment identity `mondrian_partition_horizontal_moment`, $\sum_{s \in P} g(s) = n \cdot (f(n) - f(0))$. Since $d$ divides the square side $n$, it divides this product.
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) _
The width of $r$ is divisible by $d$.
Since $d$ divides both the total sum $\sum_{s \in P} g(s)$ and $\sum_{s \in P} g(s) - \text{width}(r)$, it divides their difference, which is $\text{width}(r)$. 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
Nat.modEq_iff_dvd'- For natural numbers $a \le b$, $a \equiv b \pmod n$ if and only if $n$ divides $b - a$.
Nat.le_of_lt- A strict inequality $n < m$ between natural numbers implies $n \le m$.
Bool.false_eq_true- The boolean proposition $\text{false} = \text{true}$ is logically false.
if_false- An if-then-else expression whose condition is false simplifies to the alternative branch.
sub_zero- Subtracting zero from any group element leaves it unchanged.
dvd_mul_of_dvd_left- If $a$ divides $b$, then $a$ divides $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 positions contain unequal elements.
Or.inl- From a proof of $A$, deduce the disjunction $A \lor B$.
List.count_eq_countP- The count of elements matching $a$ by predicate equality equals the count of $a$ in the list.
List.count_eq_one_of_mem- In a list without duplicates, any element belonging to the list has count 1.
mondrian_list_sum_count_mod- If $p$ divides $f(s) - (\text{if } \text{pred}(s) \text{ then } u \text{ else } 0)$ for all $s \in L$, then $p$ divides the total sum $\sum_{s \in L} f(s) - (\text{count of elements matching pred}) \cdot u$.
Nat.cast_one- The natural number $1$ cast into an additive monoid with one is $1$.
one_mul- Multiplying an element by $1$ on the left equals the element itself.
mondrian_partition_horizontal_moment- For any partition $P$ of an $n \times n$ square and function $f$, the sum of $\text{width}(s) \cdot (f(s.y_2) - f(s.y_1))$ over all tiles $s$ equals $n \cdot (f(n) - f(0))$.
dvd_sub- If $a$ divides $b$ and $a$ divides $c$, then $a$ divides their difference $b - c$.
- Rectangles are represented formally as 4-tuples $(x_1, x_2, y_1, y_2)$ of coordinates, where width is $x_2 - x_1$ and height is $y_2 - y_1$.
- Divisibility and moment sums are computed in $\mathbb{Z}$ using integer indicator values before casting back to $\mathbb{N}$ at the end.
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_height_residue (n d m : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hrm : ¬ m ∣ mondrian_rect_height r) (hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s) : d ∣ mondrian_rect_width r := by let f : ℕ → ℤ := fun y => if y % m = r.2.2.2 % m then 1 else 0 let g := fun s : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width s : ℤ) * (f s.2.2.2 - f s.2.2.1) have hrmod : r.2.2.1 % m ≠ r.2.2.2 % m := by intro hh apply hrm exact (Nat.modEq_iff_dvd' (Nat.le_of_lt (hP.2.1 r hr).2)).mp hh have hgr : g r = (mondrian_rect_width r : ℤ) := by simp [g, f, hrmod] 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 _ · have hmod : s.2.2.1 % m = s.2.2.2 % m := (Nat.modEq_iff_dvd' (Nat.le_of_lt (hP.2.1 s hs).2)).mpr hh simp [g, f, hmod] 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