AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_log_gap

theoremverified

For distinct primes p and q, p to floor(log_p(q)) is strictly less than q, q is below the next power, and floor(log_p(q)) plus one is strictly less than q.

Statement

theorem mondrian_prime_log_gap (p q : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)
    (hpq : p ≠ q) :
    p ^ Nat.log p q < q ∧ q < p ^ (Nat.log p q + 1) ∧ Nat.log p q + 1 < 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 2

The proof, explained

The proof establishes the three inequalities one by one. The lower bound p ^ floor(log_p(q)) ≤ q is made strict because equality would force the primes p and q to be equal, contradicting p ≠ q. The upper bound q < p ^ (floor(log_p(q)) + 1) is the standard upper property of the discrete logarithm. Finally, because the prime base p satisfies p ≥ 2, the power dominates its exponent, yielding floor(log_p(q)) + 1 ≤ p ^ floor(log_p(q)), which chains transitively with the strict lower bound to give floor(log_p(q)) + 1 < q.

  1. p ^ Nat.log p q < q

    By the definition of the integer logarithm on positive integers, p ^ Nat.log p q ≤ q (via Nat.pow_log_le_self, since the prime q is non-zero). If equality held, q would be a power of p; since q is prime, this forces p = q, contradicting the hypothesis p ≠ q. Combining the inequality and non-equality using lt_of_le_of_ne yields the strict bound p ^ Nat.log p q < q.

    lines 4–8

    uses Nat.pow_log_le_self, lt_of_le_of_ne

      have hlo := Nat.pow_log_le_self p hq.ne_zero
      have hne : p ^ Nat.log p q ≠ q := by
        intro hh
        exact hpq ((hq.pow_eq_iff.mp hh).1)
      have hlt : p ^ Nat.log p q < q := lt_of_le_of_ne hlo hne
  2. Nat.log p q + 1 ≤ p ^ Nat.log p q automation

    Because p is prime, 1 < p. Thus Nat.lt_pow_self gives Nat.log p q < p ^ Nat.log p q. Linear integer arithmetic (discharged by the omega tactic) turns this strict inequality between natural numbers into Nat.log p q + 1 ≤ p ^ Nat.log p q.

    lines 9–11

    uses Nat.lt_pow_self

      have hpow : Nat.log p q + 1 ≤ p ^ Nat.log p q := by
        have := Nat.lt_pow_self (n := Nat.log p q) hp.one_lt
        omega
  3. p ^ Nat.log p q < q ∧ q < p ^ (Nat.log p q + 1) ∧ Nat.log p q + 1 < q

    The goal is a three-way conjunction. The first conjunct is the strict lower bound established in the first step. The second conjunct, q < p ^ (Nat.log p q + 1), is the standard upper bound from Nat.lt_pow_succ_log_self (since 1 < p). The third conjunct, Nat.log p q + 1 < q, follows by chaining the inequality Nat.log p q + 1 ≤ p ^ Nat.log p q with p ^ Nat.log p q < q.

    line 12

    uses Nat.lt_pow_succ_log_self

      exact ⟨hlt, Nat.lt_pow_succ_log_self hp.one_lt q, hpow.trans_lt hlt⟩
Nat.pow_log_le_self
For any base b and positive integer x, b raised to floor(log_b(x)) is at most x.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Nat.lt_pow_self
If the base a is strictly greater than 1, then n < a^n for every natural number n.
Nat.lt_pow_succ_log_self
For any base b > 1 and integer x, x is strictly less than b raised to floor(log_b(x)) + 1.

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_log_gap (p q : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q)    (hpq : p ≠ q) :    p ^ Nat.log p q < q ∧ q < p ^ (Nat.log p q + 1) ∧ Nat.log p q + 1 < q := by  have hlo := Nat.pow_log_le_self p hq.ne_zero  have hne : p ^ Nat.log p q ≠ q := by    intro hh    exact hpq ((hq.pow_eq_iff.mp hh).1)  have hlt : p ^ Nat.log p q < q := lt_of_le_of_ne hlo hne  have hpow : Nat.log p q + 1 ≤ p ^ Nat.log p q := by    have := Nat.lt_pow_self (n := Nat.log p q) hp.one_lt    omega  exact ⟨hlt, Nat.lt_pow_succ_log_self hp.one_lt q, hpow.trans_lt hlt⟩
See it in the graphDiscuss this resultChallenge it