mondrian_no_perfect_prime_power
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
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
- mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
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.
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.
uses
mondrian_no_perfect_of_shape_boundapply mondrian_no_perfect_of_shape_bound intro k A hk hA heq
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).
uses
mondrian_prime_power_shape_boundhave hcard := mondrian_prime_power_shape_bound p e k A hp hk hA heqThe 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.
uses
Nat.factorization_lt,lt_of_le_of_lthave 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
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_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