AFTD Auto-Formalizing Theoretical Domains

mondrian_twice_exponent_lt_prime_power

theoremverified

For p at least two and r at least three, p^r is greater than twice r.

Statement

theorem mondrian_twice_exponent_lt_prime_power (p r : ℕ) (hp : 2 ≤ p) (hr : 3 ≤ r) : 2 * r < p ^ r
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
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The inequality $2r < p^r$ is proved by comparing both terms to $2^r$. First, an auxiliary lemma establishes that $2r < 2^r$ for all $r \ge 3$ by induction on $r$, where the base case $r = 3$ holds numerically ($6 < 8$) and the inductive step follows by expanding $2^{r+1} = 2^r \cdot 2$. Finally, since $2 \le p$, monotonicity of powers yields $2^r \le p^r$, and chaining the inequalities completes the proof.

  1. It suffices to prove the auxiliary inequality $2r < 2^r$ for an arbitrary natural number $r \ge 3$.

    We formulate the auxiliary lemma that $2r < 2^r$ for all $r \ge 3$, and introduce an arbitrary natural number $r$ along with the assumption that $r \ge 3$.

    lines 2–3

      have hh : ∀ r ≥ 3, 2 * r < 2 ^ r := by
        intro r hr
  2. The auxiliary inequality holds in the base case $r = 3$. automation

    We proceed by induction on $r \ge 3$ using `Nat.le_induction`. In the base case $r = 3$, the inequality is $2 \cdot 3 < 2^3$, which evaluates to $6 < 8$ and is closed by numerical evaluation (`norm_num`).

    lines 4–5

    uses Nat.le_induction

        induction r, hr using Nat.le_induction with
        | base => norm_num
  3. For all natural numbers $r \ge 3$, we have $2r < 2^r$. automation

    For the inductive step, assuming $2r < 2^r$ as the induction hypothesis, we rewrite $2^{r+1}$ as $2^r \cdot 2$ using `pow_succ`. The resulting inequality $2(r+1) < 2^r \cdot 2$ is then closed by nonlinear arithmetic (`nlinarith`), completing the proof of the auxiliary lemma.

    line 6

    uses pow_succ

        | succ r hr ih => rw [pow_succ]; nlinarith
  4. For all $p \ge 2$ and $r \ge 3$, $2r < p^r$.

    We specialize the auxiliary lemma to the given $r$ and $hr$ to obtain $2r < 2^r$. Since $2 \le p$, monotonicity of exponentiation (`Nat.pow_le_pow_left`) yields $2^r \le p^r$. Chaining the strict and non-strict inequalities via transitivity (`trans_le`) concludes that $2r < p^r$.

    line 7

    uses trans_le, Nat.pow_le_pow_left

      exact (hh r hr).trans_le (Nat.pow_le_pow_left hp r)
Nat.le_induction
Induction principle for natural numbers starting from a base index $m$: to prove $P(n)$ holds for all $n \ge m$, it suffices to show $P(m)$ and that $P(n) \implies P(n+1)$ for all $n \ge m$.
pow_succ
In any monoid, power by a successor satisfies $a^{n+1} = a^n \cdot a$.
trans_le
In any preorder, if $a < b$ and $b \le c$, then $a < c$.
Nat.pow_le_pow_left
For natural numbers, if $n \le m$, then $n^i \le m^i$ for any exponent $i$.

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_twice_exponent_lt_prime_power (p r : ℕ) (hp : 2 ≤ p) (hr : 3 ≤ r) : 2 * r < p ^ r := by  have hh : ∀ r ≥ 3, 2 * r < 2 ^ r := by    intro r hr    induction r, hr using Nat.le_induction with    | base => norm_num    | succ r hr ih => rw [pow_succ]; nlinarith  exact (hh r hr).trans_le (Nat.pow_le_pow_left hp r)
See it in the graphDiscuss this resultChallenge it