AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_isolated_height_residue

theoremverified

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

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

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

    lines 7–9

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

    lines 10–14

    uses Nat.modEq_iff_dvd', Nat.le_of_lt

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

    lines 15–27

    uses Bool.false_eq_true, if_false, sub_zero, dvd_mul_of_dvd_left, Nat.modEq_iff_dvd', Nat.le_of_lt

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

    lines 28–35

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

    lines 36–39

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

    lines 40–43

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

    lines 44–48

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

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