AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_prime_power

theoremverifiedformalization

No square whose integer side length is a prime power has a perfect admissible partition.

Statement

theorem mondrian_no_perfect_prime_power (p e : ℕ) (hp : Nat.Prime p) :
    ¬ ∃ P, mondrian_is_partition (p ^ e) P ∧ mondrian_defect P = 0
Formalizes
arXiv:2007.09639, Theorem 4.1(ii): no perfect partition for a square of prime-power side length; formalized in the cell-based definitions of arXiv:2610.19193, Section 1.
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_no_perfect_of_shape_boundThere is no perfect n-square partition if, for every k at least two and positive A with k times A equal to n squared, fewer than k…
  • mondrian_prime_power_shape_boundFor k at least two and positive A with k times A equal to the area of a p-power square, the number of available shapes is at most the…
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
Used by 2

The proof, explained

The proof uses a counting criterion (mondrian_no_perfect_of_shape_bound): no perfect partition can exist if the number of incongruent rectangle shapes of area A is always strictly less than the number of tiles k required to cover the square. For a square of prime-power side length p^e, any hypothetical partition into k rectangles of uniform area A has at most v_p(k) available shapes. Since the p-adic valuation of any non-zero integer k is strictly less than k itself, the number of shapes is strictly less than k, which rules out any perfect partition.

  1. To show that no perfect partition of the (p^e) × (p^e) square exists, it suffices to show that whenever k ≥ 2 and A > 0 satisfy k * A = (p^e)^2, the number of incongruent rectangle shapes of area A fitting in the square is strictly less than k.

    By mondrian_no_perfect_of_shape_bound, ruling out a perfect partition of an n × n square reduces to proving that candidate partitions into k rectangles of equal area A are impossible because there are fewer than k valid rectangle shapes available. We introduce the tile count k, the tile area A, and the assumptions that k ≥ 2, A > 0, and k * A = (p^e)^2.

    lines 3–4

    uses mondrian_no_perfect_of_shape_bound

      apply mondrian_no_perfect_of_shape_bound
      intro k A hk hA heq
  2. The number of incongruent rectangle shapes of area A fitting in the (p^e) × (p^e) square is at most the p-adic valuation of k.

    Because the side length is a prime power p^e with p prime, mondrian_prime_power_shape_bound bounds the cardinality of available rectangle shapes of area A by the exponent of p in the prime factorization of k (k.factorization p).

    line 5

    uses mondrian_prime_power_shape_bound

      have hcard := mondrian_prime_power_shape_bound p e k A hp hk hA heq
  3. The number of available rectangle shapes of area A is strictly less than k, completing the proof.

    Since k ≥ 2, k ≠ 0 (by linear arithmetic), so Nat.factorization_lt implies that the multiplicity of p in k is strictly less than k. Combining the bound on shapes with this strict inequality via lt_of_le_of_lt shows that there are strictly fewer than k shapes, which satisfies the required condition.

    lines 6–7

    uses Nat.factorization_lt, lt_of_le_of_lt

      have hlt := Nat.factorization_lt p (by omega : k ≠ 0)
      exact lt_of_le_of_lt hcard hlt
mondrian_no_perfect_of_shape_bound
A square of side length n has no perfect partition if, for every k ≥ 2 and A > 0 with k * A = n^2, the number of incongruent rectangle shapes of area A fitting in the square is strictly less than k.
mondrian_prime_power_shape_bound
In a square whose side length is a prime power p^e, if k ≥ 2 and A > 0 satisfy k * A = (p^e)^2, then the number of incongruent rectangle shapes of area A fitting in the square is at most the multiplicity of p in the prime factorization of k.
Nat.factorization_lt
For every non-zero natural number n and any natural number p, the multiplicity of p in the prime factorization of n is strictly less than n.
lt_of_le_of_lt
In a preorder, if a ≤ b and b < c, then a < c.

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_no_perfect_prime_power (p e : ℕ) (hp : Nat.Prime p) :    ¬ ∃ P, mondrian_is_partition (p ^ e) P ∧ mondrian_defect P = 0 := by  apply mondrian_no_perfect_of_shape_bound  intro k A hk hA heq  have hcard := mondrian_prime_power_shape_bound p e k A hp hk hA heq  have hlt := Nat.factorization_lt p (by omega : k ≠ 0)  exact lt_of_le_of_lt hcard hlt
See it in the graphDiscuss this resultChallenge it