AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_prime_free_height_dvd

theoremverified

When d divides the square side, every common divisor of the heights of all other tiles with width indivisible by d also divides the height of a given tile whose width is indivisible by d.

Statement

theorem mondrian_partition_prime_free_height_dvd (n d m : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n)
    (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hrd : ¬ d ∣ mondrian_rect_width r)
    (hall : ∀ s ∈ P, s ≠ r → ¬ d ∣ mondrian_rect_width s → m ∣ mondrian_rect_height s) :
    m ∣ mondrian_rect_height r
Source
Helper for OP-280 and the periodic residue approach to arXiv:2610.19193, Section 1.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The theorem is proved by contradiction: assume m does not divide the height of the distinguished tile r. Since every other tile with width not divisible by d has height divisible by m, every tile other than r satisfies the condition that its width is a multiple of d or its height is a multiple of m. An existing result on isolated residue tiles (mondrian_partition_isolated_height_residue) then forces d to divide the width of r, contradicting the hypothesis that d does not divide its width.

  1. It suffices to derive a contradiction under the assumption that m does not divide the height of rectangle r.

    We proceed by proof by contradiction, assuming that m does not divide the height of r.

    line 6

      by_contra hrm
  2. For every rectangle s in the partition other than r, either d divides the width of s or m divides the height of s.

    Let s be any tile in P distinct from r. We perform a case distinction on whether d divides the width of s. If it does, the left alternative holds by Or.inl. If it does not, the hypothesis hall gives that m divides the height of s, so the right alternative holds by Or.inr.

    lines 7–11

    uses Or.inl, Or.inr

      have hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by
        intro s hs hsr
        by_cases hw : d ∣ mondrian_rect_width s
        · exact Or.inl hw
        · exact Or.inr (hall s hs hsr hw)
  3. A contradiction is derived, concluding the theorem.

    Applying mondrian_partition_isolated_height_residue with the contradiction assumption and the dichotomy established for all other tiles shows that d divides the width of r. This directly contradicts the assumption hrd that d does not divide the width of r.

    line 12

    uses mondrian_partition_isolated_height_residue

      exact hrd (mondrian_partition_isolated_height_residue n d m P hP hdn r hr hrm hothers)
Or.inl
If proposition a holds, then the disjunction a ∨ b holds.
Or.inr
If proposition b holds, then the disjunction a ∨ b holds.
mondrian_partition_isolated_height_residue
In a partition of an n × n square where d divides n, if a tile r has height not divisible by m, while every other tile either has width divisible by d or height divisible by m, then d must divide 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_prime_free_height_dvd (n d m : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hdn : d ∣ n)    (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hrd : ¬ d ∣ mondrian_rect_width r)    (hall : ∀ s ∈ P, s ≠ r → ¬ d ∣ mondrian_rect_width s → m ∣ mondrian_rect_height s) :    m ∣ mondrian_rect_height r := by  by_contra hrm  have hothers : ∀ s ∈ P, s ≠ r → d ∣ mondrian_rect_width s ∨ m ∣ mondrian_rect_height s := by    intro s hs hsr    by_cases hw : d ∣ mondrian_rect_width s    · exact Or.inl hw    · exact Or.inr (hall s hs hsr hw)  exact hrd (mondrian_partition_isolated_height_residue n d m P hP hdn r hr hrm hothers)
See it in the graphDiscuss this resultChallenge it