4
$\begingroup$

Is the following argument sufficient to show that for an integer $x \ge 7, x\# > x^2 + x$.

Please let me know if I made a mistake or if there is a more straight forward way to make the same argument.

Let:

  • $p_n$ be the $n$th prime
  • $p\#$ be the primorial for $p$

Here's the argument by induction:

(1) Base case: $p_4=7$

For $7 \le x < 14, 7\# = 210 > x^2+x$ since:

$$7^2 + 7 < 8^2 + 8 < 9^2 + 9 < 10^2 + 10 < 11^2 + 11 < 12^2 + 12 < 13^2 + 13 = 182 < 210$$

(2) Assume up to some prime $p_n \ge 7$ that for $p_n \le x < 2p_n, p_n\# > x^2+x$.

(3) From Bertrand's Postulate, $p_n < p_{n+1} < 2p_n$

(4) $p_{n+1}\# > p_{n+1}[(2p_n-1)^2 + 2p_n-1] = p_{n+1}(2p_n)^2 - 2p_{n+1}p_n$

(5) Since $p_{n+1} \ge 11$, it follows from Bertrand's Postulate:

$$p_{n+1}(2p_n)^2 - 2p_{n+1}p_n > p_{n+1}(p_{n+1})^2 - 2p_{n+1}p_n > 9(p_{n+1})^2$$

(6) It follows:

$$p_{n+1}\# > (3p_{n+1})^2 > (2p_{n+1})^2 - 2p_{n+1} = (2p_{n+1} - 1)^2 + 2p_{n+1} - 1$$

(7) For any integer $x \ge 7$, let $p_n$ be the highest prime less than or equal to $x$.

(8) If $x$ is prime, from the above, $x\# > x^2 + x$

(9) If $x$ is not prime, from Bertrand's Postulate, it follows:

$$x\# = p_n\# > (2p_n-1)^2 + 2p_n - 1 \ge x^2 + x$$

$\endgroup$
  • 1
    $\begingroup$ You could also use the fact that $p_n\#>p_n^{\lfloor \frac{\theta(p_n)}{\log p_n} \rfloor}$ and use some Dusart bound on $\theta(p_n)$ or use the fact that the exponent is growing with $n$ and is still valid for larger $p_n$ $\endgroup$ – Collag3n May 30 at 16:19
1
$\begingroup$

What you've done looks correct. However, one small thing to note in your step $(1)$ base case, you only need to show $10^2 + 10 = 110 \lt 210$ since $11$ is prime and, as such, will be handled later by induction as $p_5$.

Also, I believe a somewhat simpler way to proceed after your step $(5)$ is to then show, for all $p_{n+1} \le x \lt 2p_{n+1}$, that

$$\begin{equation}\begin{aligned} p_{n+1}\# & \gt 9p_{n+1}^2 \\ & = 4p_{n+1}^2 + 5p_{n+1}^2 \\ & \gt (2p_{n+1})^2 + 2p_{n+1} \\ & \gt x^2 + x \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

As you stated in your step $(3)$, Bertrand's postulate shows there's a prime $p_{n+1} \lt p_{n+2} \lt 2p_{n+1}$. Thus, for all $p_{n+1} \le x \lt p_{n+2}$, you have $x\# = p_{n+1}\#$, with \eqref{eq1A} showing

$$x\# \gt x^2 + x \tag{2}\label{eq2A}$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

As an alternative, let's suppose we've verified the inequality for all integers up to $24$ (a simple extension of the OP's argument taking things up to $13$, since $2\cdot3\cdot5\cdot7\cdot11=2310\gt24^2+24$), and let's invoke Bertrand's Postulate in the equivalent form that for any real number $u\gt1$ there is a prime satisfying $u\lt p\lt2u$.

This version of BP allows for the following conclusion: If $x\gt24$, then there exist prime numbers $p$, $q$, and $r$ such that

$$2\lt3\lt{x\over8}\lt p\lt{x\over4}\lt q\lt{x\over2}\lt r\lt x$$

It follows that

$$\#x\ge6pqr\gt6\cdot{x\over8}\cdot{x\over4}\cdot{x\over2}={3x^3\over32}$$

and it's easy to see that

$${3x^3\over32}\gt x^2+x$$

if $x\gt24$ (in fact, if $x\ge12$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.