AFTD Auto-Formalizing Theoretical Domains

mondrian_factorization_le_scaled_prime_pow

theoremverified

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.

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

    lines 4–9

    uses Nat.ordProj_le, Nat.ne_of_gt, Nat.mul_lt_mul_of_pos_right, pow_pos, pow_succ, Nat.mul_comm

      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]
  2. 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.

    line 10

    uses Nat.pow_lt_pow_iff_right

      have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hpow
  3. x.factorization p ≤ e automation

    Linear integer arithmetic immediately deduces that x.factorization p ≤ e from x.factorization p < e + 1.

    line 11

      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

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