AFTD Auto-Formalizing Theoretical Domains

mondrian_common_width_divides_side

theoremverified

Every common divisor of the tile widths in an admissible n-square partition divides n.

Statement

theorem mondrian_common_width_divides_side (n d : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
    (hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) : d ∣ n
Source
Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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₁).
Used by 2

The proof, explained

The theorem is trivial when $n = 0$ because every number divides $0$. When $n > 0$, the proof evaluates the partition against a step function $f$ that is $0$ at the origin and $1$ elsewhere. A horizontal moment identity shows that the weighted sum $\sum_{r \in P} \mathrm{width}(r)(f(y_2) - f(y_1))$ equals $n(f(n) - f(0)) = n$. Since $d$ divides the width of every tile, it divides each term of this sum, and therefore $d$ divides $n$.

  1. The claim holds directly if $n = 0$.

    If $n = 0$, the goal becomes $d \mid 0$, which holds trivially because every natural number divides $0$.

    lines 6–7

      by_cases hn : n = 0
      · simp [hn]
  2. Define a step function $f$ and an associated rectangle functional $g$.

    Assuming $n \neq 0$, let $f : \mathbb{N} \to \mathbb{Z}$ be defined by $f(0) = 0$ and $f(y) = 1$ for all $y > 0$. For each rectangle $r$ with width $w(r)$ and vertical coordinate interval $[y_1, y_2]$, define $g(r) = w(r) \cdot (f(y_2) - f(y_1))$.

    lines 8–10

      let f : ℕ → ℤ := fun y => if y = 0 then 0 else 1
      let g := fun r : ℕ × ℕ × ℕ × ℕ =>
        (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)
  3. In the integers, $d$ divides the sum $\sum_{r \in P} g(r)$.

    By assumption, $d$ divides the width of each rectangle $r \in P$, so by `dvd_mul_of_dvd_left`, $d$ divides $g(r) = w(r) \cdot (f(y_2) - f(y_1))$. Applying `mondrian_list_sum_count_mod` with offset $u = 0$ and a trivial predicate that is always false, $d$ divides the sum $\sum_{r \in P} g(r)$.

    lines 11–16

    uses mondrian_list_sum_count_mod, dvd_mul_of_dvd_left

      have hdiv : (d : ℤ) ∣ (P.map g).sum := by
        have hs := mondrian_list_sum_count_mod P (d : ℤ) 0 g (fun _ => false) (by
          intro r hr
          have hw : (d : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hd r hr
          simpa [g] using dvd_mul_of_dvd_left hw (f r.2.2.2 - f r.2.2.1))
        simpa using hs
  4. The sum $\sum_{r \in P} g(r)$ evaluates to $n$.

    The identity `mondrian_partition_horizontal_moment` states that $\sum_{r \in P} w(r)(f(y_2) - f(y_1)) = n(f(n) - f(0))$. Since $n \neq 0$, $f(n) = 1$ and $f(0) = 0$, so $n(f(n) - f(0)) = n \cdot 1 = n$.

    lines 17–18

    uses mondrian_partition_horizontal_moment

      have he : (P.map g).sum = (n : ℤ) := by
        simpa [g, f, hn] using mondrian_partition_horizontal_moment n P hP f
  5. $d$ divides $n$ as a natural number.

    Rewriting the sum as $n$ in the divisibility hypothesis gives $d \mid n$ in $\mathbb{Z}$. Casting this divisibility back from $\mathbb{Z}$ to $\mathbb{N}$ concludes that $d \mid n$.

    lines 19–20

      rw [he] at hdiv
      exact_mod_cast hdiv
mondrian_list_sum_count_mod
if an integer $p$ divides $f(r) - (\text{if } \mathrm{pred}(r) \text{ then } u \text{ else } 0)$ for every element $r$ of a list $L$, then $p$ divides $\sum_{r \in L} f(r) - u \cdot (\text{count of elements satisfying } \mathrm{pred})$
dvd_mul_of_dvd_left
if $a$ divides $b$, then $a$ divides $b \cdot c$ for any $c$
mondrian_partition_horizontal_moment
for any admissible partition $P$ of an $n \times n$ square and any function $f : \mathbb{N} \to \mathbb{Z}$, the sum over rectangles $r \in P$ of $\mathrm{width}(r) \cdot (f(y_2) - f(y_1))$ equals $n \cdot (f(n) - f(0))$

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

open scoped BigOperatorstheorem mondrian_common_width_divides_side (n d : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)    (hd : ∀ r ∈ P, d ∣ mondrian_rect_width r) : d ∣ n := by  by_cases hn : n = 0  · simp [hn]  let f : ℕ → ℤ := fun y => if y = 0 then 0 else 1  let g := fun r : ℕ × ℕ × ℕ × ℕ =>    (mondrian_rect_width r : ℤ) * (f r.2.2.2 - f r.2.2.1)  have hdiv : (d : ℤ) ∣ (P.map g).sum := by    have hs := mondrian_list_sum_count_mod P (d : ℤ) 0 g (fun _ => false) (by      intro r hr      have hw : (d : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hd r hr      simpa [g] using dvd_mul_of_dvd_left hw (f r.2.2.2 - f r.2.2.1))    simpa using hs  have he : (P.map g).sum = (n : ℤ) := by    simpa [g, f, hn] using mondrian_partition_horizontal_moment n P hP f  rw [he] at hdiv  exact_mod_cast hdiv
See it in the graphDiscuss this resultChallenge it