mondrian_partition_prime_free_height_dvd
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
- mondrian_partition_isolated_height_residueLet 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…
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
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.
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.
by_contra hrmFor 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.
uses
Or.inl,Or.inrhave 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)
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.
uses
mondrian_partition_isolated_height_residueexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)