mondrian_factorization_le_scaled_prime_pow
A positive integer at most c times p to the e has p-adic exponent at most e when the prime p exceeds c.
Statement
theorem mondrian_factorization_le_scaled_prime_pow (c p e x : ℕ) (hp : Nat.Prime p)
(hpc : c < p) (hx : 0 < x) (hxn : x ≤ c * p ^ e) :
x.factorization p ≤ e- 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 2
- mondrian_prime_pair_encodingFor an equal-area factor pair fitting in a c times p to the e square with p greater than c, the p-adic exponent of its first side lies…
- mondrian_prime_first_exponent_shape_boundWhen the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A…
The proof, explained
To bound the p-adic valuation of x by e, the proof bounds the prime power p^(x.factorization p) from above. Since x > 0, this prime power is at most x ≤ c * p^e. Because c < p and p^e > 0, it follows that c * p^e < p * p^e = p^(e + 1), and therefore p^(x.factorization p) < p^(e + 1). Since p > 1, strict monotonicity of powers implies x.factorization p < e + 1, which yields x.factorization p ≤ e.
p ^ (x.factorization p) < p ^ (e + 1)
Since x > 0, the prime-power component p^(x.factorization p) is at most x. By assumption, x ≤ c * p^e. Since c < p and p^e > 0, we have c * p^e < p * p^e = p^(e + 1). Chaining these inequalities gives p^(x.factorization p) < p^(e + 1).
uses
Nat.ordProj_le,Nat.ne_of_gt,Nat.mul_lt_mul_of_pos_right,pow_pos,pow_succ,Nat.mul_commhave hpow : p ^ (x.factorization p) < p ^ (e + 1) := by calc p ^ (x.factorization p) ≤ x := Nat.ordProj_le p (Nat.ne_of_gt hx) _ ≤ c * p ^ e := hxn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm]
x.factorization p < e + 1
Because p is prime, p > 1. For any base strictly greater than 1, exponentiation is strictly monotone, so the inequality p^(x.factorization p) < p^(e + 1) implies that the exponents satisfy x.factorization p < e + 1.
uses
Nat.pow_lt_pow_iff_righthave := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpowx.factorization p ≤ e automation
Linear integer arithmetic immediately deduces that x.factorization p ≤ e from x.factorization p < e + 1.
omega
Nat.ordProj_le- For any non-zero natural number n and prime p, the prime-power factor p^(v_p(n)) is at most n.
Nat.ne_of_gt- If b < a, then a ≠ b; in particular, a positive natural number is non-zero.
Nat.mul_lt_mul_of_pos_right- Multiplying a strict inequality n < m of natural numbers by a positive number k preserves strict inequality: n * k < m * k.
pow_pos- Any natural power of a strictly positive element is strictly positive.
pow_succ- The successor power satisfies a^(n + 1) = a^n * a.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.pow_lt_pow_iff_right- For a base a > 1, a^n < a^m if and only if n < m.
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_factorization_le_scaled_prime_pow (c p e x : ℕ) (hp : Nat.Prime p) (hpc : c < p) (hx : 0 < x) (hxn : x ≤ c * p ^ e) : x.factorization p ≤ e := by have hpow : p ^ (x.factorization p) < p ^ (e + 1) := by calc p ^ (x.factorization p) ≤ x := Nat.ordProj_le p (Nat.ne_of_gt hx) _ ≤ c * p ^ e := hxn _ < p * p ^ e := Nat.mul_lt_mul_of_pos_right hpc (pow_pos hp.pos e) _ = p ^ (e + 1) := by rw [pow_succ, Nat.mul_comm] have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow omega