AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_power_side_log_bound

theoremverified

A pure p-power side fitting in a q times p^e square has exponent at most e plus floor(log_p(q)).

Statement

theorem mondrian_prime_power_side_log_bound (p q e a : ℕ) (hp : Nat.Prime p)
    (h : p ^ a ≤ q * p ^ e) : a ≤ e + Nat.log p q
Source
Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The proof bounds p^a strictly above by a single power of p using the upper bound property of the discrete logarithm: since p > 1, q < p^(⌊log_p(q)⌋ + 1), which leads to p^a ≤ q * p^e < p^(⌊log_p(q)⌋ + 1 + e). By the strict monotonicity of powers with base p > 1, the exponent a must be strictly less than ⌊log_p(q)⌋ + 1 + e. Linear integer arithmetic on natural numbers then yields a ≤ e + ⌊log_p(q)⌋.

  1. p^a < p^(Nat.log p q + 1 + e)

    Since p is prime, p > 1, so by the definition of the discrete logarithm, q < p^(Nat.log p q + 1). Multiplying both sides by the positive quantity p^e and combining with the hypothesis p^a ≤ q * p^e gives p^a < p^(Nat.log p q + 1) * p^e. Rewriting the product of powers on the right as p^(Nat.log p q + 1 + e) yields the desired bound.

    lines 3–5

    uses Nat.mul_lt_mul_of_pos_right, Nat.lt_pow_succ_log_self, pow_pos, pow_add

      have hh := h.trans_lt (Nat.mul_lt_mul_of_pos_right
        (Nat.lt_pow_succ_log_self hp.one_lt q) (pow_pos hp.pos e))
      rw [← pow_add] at hh
  2. a < Nat.log p q + 1 + e

    Since the base p is strictly greater than 1, the power function is strictly monotone. Thus, the inequality p^a < p^(Nat.log p q + 1 + e) implies the same strict inequality between the exponents.

    line 6

    uses Nat.pow_lt_pow_iff_right

      have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hh
  3. a ≤ e + Nat.log p q

    From the strict inequality of natural numbers a < Nat.log p q + 1 + e, linear integer arithmetic immediately concludes that a ≤ e + Nat.log p q.

    line 7

      omega
Nat.mul_lt_mul_of_pos_right
Multiplying a strict inequality between natural numbers by a positive natural number preserves the strict inequality.
Nat.lt_pow_succ_log_self
For base b > 1 and any natural number x, x is strictly less than b^(⌊log_b(x)⌋ + 1).
pow_pos
A positive element raised to any natural power is strictly positive.
pow_add
The product of powers with the same base equals the base raised to the sum of the exponents: a^(m + n) = a^m * a^n.
Nat.pow_lt_pow_iff_right
For 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_prime_power_side_log_bound (p q e a : ℕ) (hp : Nat.Prime p)    (h : p ^ a ≤ q * p ^ e) : a ≤ e + Nat.log p q := by  have hh := h.trans_lt (Nat.mul_lt_mul_of_pos_right    (Nat.lt_pow_succ_log_self hp.one_lt q) (pow_pos hp.pos e))  rw [← pow_add] at hh  have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hh  omega
See it in the graphDiscuss this resultChallenge it