mondrian_perfect_partition_large_prime_iff
For every positive integer c, prime p greater than c, and natural exponent e, the square of side c times p to the e has a perfect admissible integer-rectangle partition if and only if the c-square has one.
Statement
theorem mondrian_perfect_partition_large_prime_iff (c p e : ℕ) (hc : 0 < c)
(hp : Nat.Prime p) (hpc : c < p) :
(∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) ↔
∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0- Related work
- OP-280, arXiv:2610.19193, Section 1, asks whether any perfect partition exists and notes scaling. arXiv:2007.09639, Theorem 4.1, gives prime-power and fixed-exponent exclusions. The uniform p>c prime-removal equivalence is proved here.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
- mondrian_perfect_partition_mulMultiplying all coordinates by a positive integer preserves perfect admissible partitions.
- mondrian_rect_mulMultiply all four rectangle coordinates by a.
The proof, explained
The equivalence is established in two directions. The forward direction applies descent (mondrian_large_prime_descent): when p is a prime strictly larger than c, any defect-0 partition of the square of side c * p^e implies the existence of a defect-0 partition of the square of side c. The reverse direction takes an assumed defect-0 partition of the c-square and scales every rectangle by p^e, which yields a defect-0 partition of the (c * p^e)-square via mondrian_perfect_partition_mul and commutativity of multiplication.
If the square of side c * p^e has a defect-0 partition, then so does the square of side c.
We split the equivalence into two implications. The forward direction is established directly by the descent theorem mondrian_large_prime_descent, which applies because c > 0 and p is a prime strictly greater than c.
uses
mondrian_large_prime_descentconstructor · exact mondrian_large_prime_descent c p e hc hp hpc
If the square of side c has a defect-0 partition, then so does the square of side c * p^e.
Given a defect-0 partition Q of the c-square, we scale each rectangle in Q by the factor p^e. Since p is prime, p > 0, so p^e > 0 by pow_pos. By mondrian_perfect_partition_mul, scaling a defect-0 partition by a positive integer yields a defect-0 partition of the square of side p^e * c. Commuting the factor order to c * p^e using Nat.mul_comm matches the goal.
uses
Nat.mul_comm,mondrian_perfect_partition_mul,pow_pos· rintro ⟨Q, hQ, hz⟩ refine ⟨Q.map (mondrian_rect_mul (p ^ e)), ?_⟩ simpa only [Nat.mul_comm] using mondrian_perfect_partition_mul (p ^ e) c (pow_pos hp.pos e) Q hQ hz
mondrian_large_prime_descent- For c > 0 and prime p > c, if the square of side c * p^e has a defect-0 partition, then so does the square of side c.
mondrian_perfect_partition_mul- Scaling every rectangle in a defect-0 partition of a c-square by a strictly positive factor a produces a defect-0 partition of the (a * c)-square.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
pow_pos- Any natural power of a strictly positive number is strictly positive.
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_perfect_partition_large_prime_iff (c p e : ℕ) (hc : 0 < c) (hp : Nat.Prime p) (hpc : c < p) : (∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) ↔ ∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0 := by constructor · exact mondrian_large_prime_descent c p e hc hp hpc · rintro ⟨Q, hQ, hz⟩ refine ⟨Q.map (mondrian_rect_mul (p ^ e)), ?_⟩ simpa only [Nat.mul_comm] using mondrian_perfect_partition_mul (p ^ e) c (pow_pos hp.pos e) Q hQ hz