AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_isolated_row_function

theoremverified

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

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

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

    lines 7–9

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

    lines 10–20

    uses Bool.false_eq_true, if_false, sub_zero, dvd_mul_of_dvd_left

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

    lines 21–28

    uses List.nodup_iff_pairwise_ne, Or.inl, List.count_eq_countP, List.count_eq_one_of_mem

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

    lines 29–32

    uses mondrian_list_sum_count_mod, Nat.cast_one, one_mul

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

    lines 33–36

    uses mondrian_partition_horizontal_moment, dvd_mul_of_dvd_left

      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) _
  6. $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.

    lines 37–41

    uses dvd_sub

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

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