mondrian_two_prime_area_width_dvd
For 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.
Statement
theorem mondrian_two_prime_area_width_dvd (n p q s t : ℕ)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)
(harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) :
∀ r ∈ P, q ∣ 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_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_partition_width_dvd_of_height_prime_chainSuppose 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…
- mondrian_prime_free_height_encodingIf x*y=q^s*p^t for primes p and q and q does not divide x, then y is q^s times a power of p; the primes need not be distinct.
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- 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₁).
- Used by 1
- mondrian_two_prime_area_sides_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are…
The proof, explained
The theorem reduces the global divisibility property to a local arithmetic condition via mondrian_partition_width_dvd_of_height_prime_chain. That lemma guarantees that q divides every tile's width in the partition provided that any counterexample tile has height of the form q^s * p^a. Since each tile has area width * height = q^s * p^t, any tile whose width is coprime to q must absorb all q-factors into its height, immediately matching this required form by mondrian_prime_free_height_encoding.
To show that q divides the width of every tile in P, it suffices to show that any tile whose width is not divisible by q has height of the form q^s * p^a for some exponent a.
We apply mondrian_partition_width_dvd_of_height_prime_chain with divisor d = q, prime p, and constant C = q^s. Since P is a defect-free partition of a square of side n, q divides n, p is prime, and q^s > 0 (by pow_pos, since the prime q is strictly positive), the lemma reduces the conclusion to showing that every tile r ∈ P with width not divisible by q has height q^s * p^a for some a.
uses
mondrian_partition_width_dvd_of_height_prime_chain,pow_posapply mondrian_partition_width_dvd_of_height_prime_chain n q p (q ^ s) P hP hz hqn hp (pow_pos hq.pos s)Any tile r ∈ P whose width is not divisible by q has height equal to q^s * p^a for some exponent a.
Let r be a tile in P and assume q does not divide its width. The area of r is width(r) * height(r) = q^s * p^t. Applying mondrian_prime_free_height_encoding to this product, the fact that q is prime and does not divide width(r) implies that all factors of q must belong to height(r), so height(r) = q^s * p^a for some a.
uses
mondrian_prime_free_height_encodingintro r hr hqr exact mondrian_prime_free_height_encoding p q s t (mondrian_rect_width r) (mondrian_rect_height r) hp hq (harea r hr) hqr
mondrian_partition_width_dvd_of_height_prime_chain- In a defect-free partition of an n × n square where d divides n and p is prime, if every tile whose width is not divisible by d has height equal to C * p^a for a fixed C > 0 and varying a, then every tile's width is divisible by d.
pow_pos- A positive integer raised to any natural power is strictly positive.
mondrian_prime_free_height_encoding- If x * y = q^s * p^t for primes p, q and q does not divide x, then y must be of the form q^s * p^a for some natural number a.
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_two_prime_area_width_dvd (n p q s t : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n) (harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) : ∀ r ∈ P, q ∣ mondrian_rect_width r := by apply mondrian_partition_width_dvd_of_height_prime_chain n q p (q ^ s) P hP hz hqn hp (pow_pos hq.pos s) intro r hr hqr exact mondrian_prime_free_height_encoding p q s t (mondrian_rect_width r) (mondrian_rect_height r) hp hq (harea r hr) hqr