AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_width_dvd_of_height_prime_chain

theoremverified

Suppose 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 positive C. In a perfect admissible partition every tile width is divisible by d.

Statement

theorem mondrian_partition_width_dvd_of_height_prime_chain (n d p C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)
    (hdn : d ∣ n) (hp : Nat.Prime p) (hC : 0 < C)
    (hheight : ∀ r ∈ P, ¬ d ∣ mondrian_rect_width r →
      ∃ a, mondrian_rect_height r = C * p ^ a) :
    ∀ r ∈ P, 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 8
Used by 1
  • mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.

The proof, explained

The proof proceeds by contradiction. Assuming there is a tile whose width is not divisible by d, we consider the non-empty set S of all such tiles and choose a tile z of minimal height, which has height C * p^a. Setting m = C * p^(a+1), the height of z is strictly smaller than m and therefore not divisible by m. Moreover, every other tile s ≠ z either has width divisible by d or, by height minimality and the injectivity of heights in a defect-zero partition, has height C * p^b with b ≥ a + 1, so m divides its height. The isolated height residue theorem then implies d must divide the width of z, contradicting that z belongs to S.

  1. Assume for contradiction that there exists a tile r ∈ P whose width is not divisible by d.

    We proceed by contradiction: assuming it is not the case that every tile in P has width divisible by d, negation yields an explicit witness tile r ∈ P such that d does not divide the width of r.

    lines 7–10

      have hp0 := hp.pos
      by_contra hh
      push_neg at hh
      obtain ⟨r, hr, hrd⟩ := hh
  2. There is a tile z ∈ P whose width is not divisible by d that minimizes height among all such tiles, with height equal to C * p^a for some natural number a.

    Let S be the sub-collection of tiles in P with width indivisible by d. Because r ∈ S, the finite set S is non-empty and therefore contains an element z that achieves the minimal height. By the hypothesis on tile heights, z must have height C * p^a for some exponent a.

    lines 11–16

    uses Finset.mem_filter.mp, List.mem_toFinset.mp

      let S := P.toFinset.filter (fun s => ¬ d ∣ mondrian_rect_width s)
      have hS : S.Nonempty := ⟨r, by simp [S, hr, hrd]⟩
      obtain ⟨z, hzS, hzmin⟩ := S.exists_min_image mondrian_rect_height hS
      obtain ⟨hzP, hzd⟩ := Finset.mem_filter.mp hzS
      have hzP' : z ∈ P := List.mem_toFinset.mp hzP
      obtain ⟨a, hza⟩ := hheight z hzP' hzd
  3. For m = C * p^(a + 1), m does not divide the height of z.

    If m divided the height of z, then because the height C * p^a is strictly positive, m would have to be less than or equal to the height of z. But since p > 1 and a < a + 1, we have p^a < p^(a+1), so the height C * p^a is strictly less than m = C * p^(a+1), which is a contradiction.

    lines 17–27

    uses Nat.le_of_dvd, Nat.mul_lt_mul_of_pos_left, Nat.pow_lt_pow_iff_right

      let m := C * p ^ (a + 1)
      have hzm : ¬ m ∣ mondrian_rect_height z := by
        intro hm
        have hzpos : 0 < mondrian_rect_height z := by rw [hza]; positivity
        have hmle := Nat.le_of_dvd hzpos hm
        have hlt : mondrian_rect_height z < m := by
          rw [hza]
          dsimp [m]
          apply Nat.mul_lt_mul_of_pos_left _ hC
          exact (Nat.pow_lt_pow_iff_right hp.one_lt).mpr (by omega)
        omega
  4. Every other tile s ≠ z in P either has width divisible by d or height divisible by m.

    Take any tile s ∈ P with s ≠ z. If d divides the width of s, we are done. Otherwise, s ∈ S, so its height is C * p^b for some b and is at least the height of z by minimality. Because the partition has defect 0, distinct tiles cannot share the same height (mondrian_perfect_height_injective), so height(z) < height(s). This implies C * p^a < C * p^b and thus a < b, so a + 1 ≤ b. Consequently, p^(a+1) divides p^b, so m = C * p^(a+1) divides C * p^b = height(s).

    lines 28–45

    uses mondrian_perfect_height_injective, Nat.pow_lt_pow_iff_right, Nat.mul_dvd_mul_left, pow_dvd_pow

      have hothers : ∀ s ∈ P, s ≠ z → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by
        intro s hs hne
        by_cases hsd : d ∣ mondrian_rect_width s
        · exact Or.inl hsd
        right
        obtain ⟨b, hsb⟩ := hheight s hs hsd
        have hmem : s ∈ S := by simp [S, hs, hsd]
        have hle := hzmin s hmem
        have hneq : mondrian_rect_height z ≠ mondrian_rect_height s := by
          intro he
          exact hne (mondrian_perfect_height_injective n P hP hz z hzP' s hs he).symm
        have hab : a < b := by
          have hlt : C * p ^ a < C * p ^ b := by rw [← hza, ← hsb]; omega
          have hpow : p ^ a < p ^ b := by nlinarith
          exact (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow
        rw [hsb]
        apply Nat.mul_dvd_mul_left
        exact pow_dvd_pow p (by omega : a + 1 ≤ b)
  5. Contradiction: d divides the width of z, contradicting the choice of z.

    The isolated height residue theorem states that if a tile z in an admissible partition has height indivisible by m, while all other tiles have width divisible by d or height divisible by m, then d must divide the width of z. Applying this theorem to z yields d ∣ width(z), contradicting the definition of z as an element of S.

    line 46

    uses mondrian_partition_isolated_height_residue

      exact hzd (mondrian_partition_isolated_height_residue n d m P hP hdn z hzP' hzm hothers)
Finset.mem_filter.mp
If an element belongs to a filtered finset {x ∈ s | P x}, it belongs to s and satisfies the predicate P.
List.mem_toFinset.mp
If an element belongs to the finset of elements of a list, then it is an element of that list.
Nat.le_of_dvd
If a divides a positive integer b, then a ≤ b.
Nat.mul_lt_mul_of_pos_left
Strict inequality between natural numbers is preserved under multiplication by a strictly positive natural number on the left.
Nat.pow_lt_pow_iff_right
For a base strictly greater than 1, powers of that base are strictly ordered by their exponents.
mondrian_perfect_height_injective
In a defect-zero partition of a square, distinct tiles have distinct heights.
Nat.mul_dvd_mul_left
If b divides c, then a * b divides a * c for any natural number a.
pow_dvd_pow
In any monoid, if m ≤ n, then a^m divides a^n.
mondrian_partition_isolated_height_residue
In a partition of an n × n square with d ∣ n, if a tile r has height not divisible by m, and every other tile either has width divisible by d or height divisible by m, then d divides the width of r.

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_width_dvd_of_height_prime_chain (n d p C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)    (hdn : d ∣ n) (hp : Nat.Prime p) (hC : 0 < C)    (hheight : ∀ r ∈ P, ¬ d ∣ mondrian_rect_width r →      ∃ a, mondrian_rect_height r = C * p ^ a) :    ∀ r ∈ P, d ∣ mondrian_rect_width r := by  have hp0 := hp.pos  by_contra hh  push_neg at hh  obtain ⟨r, hr, hrd⟩ := hh  let S := P.toFinset.filter (fun s => ¬ d ∣ mondrian_rect_width s)  have hS : S.Nonempty := ⟨r, by simp [S, hr, hrd]⟩  obtain ⟨z, hzS, hzmin⟩ := S.exists_min_image mondrian_rect_height hS  obtain ⟨hzP, hzd⟩ := Finset.mem_filter.mp hzS  have hzP' : z ∈ P := List.mem_toFinset.mp hzP  obtain ⟨a, hza⟩ := hheight z hzP' hzd  let m := C * p ^ (a + 1)  have hzm : ¬ m ∣ mondrian_rect_height z := by    intro hm    have hzpos : 0 < mondrian_rect_height z := by rw [hza]; positivity    have hmle := Nat.le_of_dvd hzpos hm    have hlt : mondrian_rect_height z < m := by      rw [hza]      dsimp [m]      apply Nat.mul_lt_mul_of_pos_left _ hC      exact (Nat.pow_lt_pow_iff_right hp.one_lt).mpr (by omega)    omega  have hothers : ∀ s ∈ P, s ≠ z → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by    intro s hs hne    by_cases hsd : d ∣ mondrian_rect_width s    · exact Or.inl hsd    right    obtain ⟨b, hsb⟩ := hheight s hs hsd    have hmem : s ∈ S := by simp [S, hs, hsd]    have hle := hzmin s hmem    have hneq : mondrian_rect_height z ≠ mondrian_rect_height s := by      intro he      exact hne (mondrian_perfect_height_injective n P hP hz z hzP' s hs he).symm    have hab : a < b := by      have hlt : C * p ^ a < C * p ^ b := by rw [← hza, ← hsb]; omega      have hpow : p ^ a < p ^ b := by nlinarith      exact (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow    rw [hsb]    apply Nat.mul_dvd_mul_left    exact pow_dvd_pow p (by omega : a + 1 ≤ b)  exact hzd (mondrian_partition_isolated_height_residue n d m P hP hdn z hzP' hzm hothers)
See it in the graphDiscuss this resultChallenge it