AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_partition_large_prime_iff

theoremverifiedoriginal

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.

  1. 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.

    lines 5–6

    uses mondrian_large_prime_descent

      constructor
      · exact mondrian_large_prime_descent c p e hc hp hpc
  2. 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.

    lines 7–10

    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

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
See it in the graphDiscuss this resultChallenge it