mondrian_prime_log_gap
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
- mondrian_prime_square_cofactor_side_boundA side q^2 times p^a fitting in a q times p^e square satisfies a plus floor(log_p(q)) plus one at most e, for distinct primes.
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
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.
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.
uses
Nat.pow_log_le_self,lt_of_le_of_nehave 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
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.
uses
Nat.lt_pow_selfhave 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
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.
uses
Nat.lt_pow_succ_log_selfexact ⟨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.
- The deduction of $\lfloor \log_p q \rfloor + 1 \le p^{\lfloor \log_p q \rfloor}$ from $\lfloor \log_p q \rfloor < p^{\lfloor \log_p q \rfloor}$ is discharged automatically by the `omega` tactic using linear integer arithmetic.
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_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⟩