mondrian_twice_exponent_lt_prime_power
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- 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 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.
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$.
have hh : ∀ r ≥ 3, 2 * r < 2 ^ r := by intro r hr
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`).
uses
Nat.le_inductioninduction r, hr using Nat.le_induction with | base => norm_num
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.
uses
pow_succ| succ r hr ih => rw [pow_succ]; nlinarith
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$.
uses
trans_le,Nat.pow_le_pow_leftexact (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$.
- The nonlinear arithmetic tactic `nlinarith` automatically handles the inequality $2(r+1) < 2^r \cdot 2$ in the inductive step using the induction hypothesis $2r < 2^r$ and $r \ge 3$.
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_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)