mondrian_prime_cofactor_le
When k times A is the area of a c times p to the e square with p greater than c, the p-free part of A is at most c squared.
Statement
theorem mondrian_prime_cofactor_le (c p e k A : ℕ) (hc : 0 < c)
(hp : Nat.Prime p) (hpc : c < p) (heq : k * A = (c * p ^ e) ^ 2) :
A / p ^ (A.factorization p) ≤ c ^ 2- Source
- Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mondrian_prime_shape_boundIf k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the…
The proof, explained
The theorem bounds the p-free part of A when k * A = (c * p ^ e) ^ 2 with prime p > c > 0. Since A divides (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 and p cannot divide c, the maximal power of p dividing the square is exactly p ^ (2 * e), leaving c ^ 2 as its p-free part. Because removing the p-part preserves divisibility, the p-free part of A divides c ^ 2, and since c ^ 2 > 0, it must be at most c ^ 2.
p does not divide c
Since c is positive and strictly smaller than p, p cannot divide c by Nat.not_dvd_of_pos_of_lt.
uses
Nat.not_dvd_of_pos_of_lthave hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc(c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2
The product in the exponent 2 * e is commuted to e * 2, expressing p ^ (2 * e) as (p ^ e) ^ 2 via pow_mul. Ring arithmetic then simplifies the squared product (c * p ^ e) ^ 2 into (p ^ e) ^ 2 * c ^ 2.
uses
Nat.mul_comm,pow_mulhave hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by rw [Nat.mul_comm 2 e, pow_mul] ring
The p-free part of (c * p ^ e) ^ 2 equals c ^ 2
Substituting (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2, removing the maximal power of p dividing it leaves c ^ 2 by Nat.ordCompl_pow_mul_of_not_dvd, provided p does not divide c ^ 2. If p did divide c ^ 2, primality of p would imply p divides c by hp.dvd_of_dvd_pow, contradicting ¬(p ∣ c).
uses
Nat.ordCompl_pow_mul_of_not_dvd,hp.dvd_of_dvd_powhave hnc : ((c * p ^ e) ^ 2) / p ^ (((c * p ^ e) ^ 2).factorization p) = c ^ 2 := by rw [hnn] exact Nat.ordCompl_pow_mul_of_not_dvd (2 * e) hp (fun hh => hcnot (hp.dvd_of_dvd_pow hh))
A divides (c * p ^ e) ^ 2
Replacing (c * p ^ e) ^ 2 with k * A using the hypothesis heq, A divides k * A directly by dvd_mul_left.
uses
dvd_mul_lefthave hdiv : A ∣ (c * p ^ e) ^ 2 := by rw [← heq]; exact dvd_mul_left A k
The p-free part of A is at most c ^ 2
Because A divides (c * p ^ e) ^ 2, taking the p-free part preserves divisibility (Nat.ordCompl_dvd_ordCompl_of_dvd), so the p-free part of A divides that of (c * p ^ e) ^ 2, which was shown to be c ^ 2. Since c > 0 implies c ^ 2 > 0 by pow_pos, a divisor of a positive integer is at most that integer (Nat.le_of_dvd).
uses
Nat.ordCompl_dvd_ordCompl_of_dvd,pow_pos,Nat.le_of_dvdhave hh := Nat.ordCompl_dvd_ordCompl_of_dvd hdiv p rw [hnc] at hh exact Nat.le_of_dvd (pow_pos hc 2) hh
Nat.not_dvd_of_pos_of_lt- A strictly larger natural number cannot divide a positive natural number strictly smaller than it.
Nat.mul_comm- Multiplication of natural numbers is commutative.
pow_mul- In a monoid, a power with an exponent product satisfies a ^ (m * n) = (a ^ m) ^ n.
Nat.ordCompl_pow_mul_of_not_dvd- If a prime p does not divide m, dividing p ^ k * m by the highest power of p dividing it leaves m.
hp.dvd_of_dvd_pow- If a prime p divides a power m ^ n, it divides m.
dvd_mul_left- Any element a divides a multiple b * a.
Nat.ordCompl_dvd_ordCompl_of_dvd- If a divides b, then the p-free part of a divides the p-free part of b.
pow_pos- A power of a strictly positive number is strictly positive.
Nat.le_of_dvd- If a natural number divides a positive natural number, it is less than or equal to it.
- The expression `A / p ^ A.factorization p` represents the $p$-free part of $A$ (the quotient of $A$ by the maximal power of $p$ dividing $A$), which Mathlib defines as `Nat.ordCompl p A`. This is why library lemmas named `ordCompl` apply directly to it.
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_prime_cofactor_le (c p e k A : ℕ) (hc : 0 < c) (hp : Nat.Prime p) (hpc : c < p) (heq : k * A = (c * p ^ e) ^ 2) : A / p ^ (A.factorization p) ≤ c ^ 2 := by have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc have hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by rw [Nat.mul_comm 2 e, pow_mul] ring have hnc : ((c * p ^ e) ^ 2) / p ^ (((c * p ^ e) ^ 2).factorization p) = c ^ 2 := by rw [hnn] exact Nat.ordCompl_pow_mul_of_not_dvd (2 * e) hp (fun hh => hcnot (hp.dvd_of_dvd_pow hh)) have hdiv : A ∣ (c * p ^ e) ^ 2 := by rw [← heq]; exact dvd_mul_left A k have hh := Nat.ordCompl_dvd_ordCompl_of_dvd hdiv p rw [hnc] at hh exact Nat.le_of_dvd (pow_pos hc 2) hh