Proving that for $x \ge 17$, $\prod\limits_{p < x\text{, prime, & }p \nmid (x^2+x)}p > x^2 + x$

Question

Let:

• $x$ be an integer
• $p_n$ be the $n$th prime
• $x\#$ be the primorial of $x$
• $f(x) = x^2 + x$
• $P(x) = \prod\limits_{p < x\text{, prime, & } p \nmid f(x)}p$
• $m(p_n)$ be the minimum $P(i)$ where $p_n \le i < p_{n+1}$

Does it follow that $P(x) > f(x)$?

The challenge in the argument is to compare a strictly increasing function with a function that is not strictly increasing:

• $P(x)$ is not strictly increasing. In some cases $P(x) > P(x+1)$.

Example: $P(4) = 3$ but $P(5) = 1$

• $f(x)$ is strictly increasing since $x \ge 17$ and:

$$\frac{d}{dx}(x^2 + x) = 2x + 1$$

I handle this situation by leveraging Bertrand's Postulate and attempting to show:

$$m(p_n) > (2p_n - 1)^2 + 2p_n - 1 = (2p_n)^2 - 2p_n$$

Since $m(p_n) > \dfrac{p_n\#}{(p_n)^2}$ and $4(p_n)^2 > (2p_n - 1)^2 - 2p_n$, this will be demonstrated if:

$$p_n\# > 4(p_n)^4$$

(1) Base Case: $p_n = 17$

$17\# = 510,510 > 4(17^4) = 334,084$

(2) Assume up to some $p_n \ge 17$, $p_n\# > 4(p_n)^4$

(3) Since $p_{n+1} \ge 19$, it follows that:

$$p_{n+1}\# \ge (19)(4(p_n)^4) > 4(2p_n)^4) > 4(p_{n+1})^4$$

I believe that the conclusion follows. Please let me know if I made any mistakes in my reasoning or if there is a simpler way to make the same point.

Answer 1

Your conjecture of $P(x) \gt f(x)$ for $x \ge 17$ is true, and your proof procedure is mostly correct, but there are several issues with it. Regarding your $P(x)$, I find it generally easier to deal with primes which are factors of a value rather than primes which are not factors. The product of all primes less than $x$ which don't divide $f(x)$ is the same as the product of all primes less than $x$ divided by the product of primes less than $x$ which do divide $f(x)$. Thus, for simpler algebra, by defining

$$g(x) = \prod_{p \lt x \text{, prime, & } p \mid f(x)}p \tag{1}\label{eq1A}$$

for $p_n + 1 \le x \le p_{n+1}$, we get

$$P(x) = \prod_{p \lt x \text{, prime, & } p \, \nmid f(x)}p = \frac{p_n\#}{g(x)} \tag{2}\label{eq2A}$$

Since $\gcd(x, x + 1) = 1$, the maximum value of $g(x)$ is $x(x + 1)$ when $x$ and $x + 1$ are both square-free integers. This gives, from \eqref{eq2A}, that

$$P(x) \ge \frac{p_n\#}{x(x + 1)} \tag{3}\label{eq3A}$$

With your $m(p_n)$ definition, it straddles $2$ cases in \eqref{eq2A}, with it using $n-1$ for $x = p_{n}$, and $n$ for the rest of the values of $x$. First, with $x = p_n$, since only factors less than $p_n$ are being considered, then $g(p_{n})$ doesn't include $p_{n}$, so we have

$$P(p_n) = \frac{p_{n-1}\#}{g(p_n)} \ge \frac{p_{n-1}\#}{p_n + 1} = \frac{p_{n}\#}{p_n(p_n + 1)} \tag{4}\label{eq4A}$$

Thus, if $p_n + 1$ is square-free, then

$$m(p_n) \le P(p_n) = \frac{p_{n}\#}{p_n(p_n + 1)} \lt \frac{p_{n}\#}{(p_n)^2} \tag{5}\label{eq5A}$$

This already provides a counter-example to your statement $m(p_n) \gt \dfrac{p_n\#}{(p_n)^2}$, plus other larger values where $x$ and $x + 1$ are both square-free will also be additional counter-examples. However, what is true is that

$$m(p_n) \gt \frac{p_n\#}{(p_{n+1})^2} \tag{6}\label{eq6A}$$

Perhaps this is what you had intended. The mechanics of the rest of your proof is correct, but it would need to be adjusted to use something like \eqref{eq6A} instead, which I'll leave to you to do.

---

I would approach solving this a bit differently. With $p_{n} + 1 \le x \lt p_{n+1}$, we have from \eqref{eq3A} that

$$P(x) \ge \frac{p_n\#}{x(x + 1)} \gt \frac{p_n\#}{(p_{n+1})^2} \tag{7}\label{eq7A}$$

For $x = p_{n+1}$, since $p_{n+1}$ is not included in $g(x)$ defined in \eqref{eq1A}, we get

$$P(p_{n+1}) \ge \frac{p_n\#}{p_{n+1} + 1} \gt \frac{p_n\#}{(p_{n+1})^2} \tag{8}\label{eq8A}$$

Thus, in both cases, we get

$$P(x) \gt \frac{p_n\#}{(p_{n+1})^2} \tag{9}\label{eq9A}$$

Since

$$p_{n+1}(p_{n+1} + 1) \ge f(x) \tag{10}\label{eq10A}$$

your conjecture will be true if we can prove

$$\frac{p_n\#}{(p_{n+1})^2} \gt p_{n+1}(p_{n+1} + 1) \iff p_n\# \gt (p_{n+1})^3(p_{n+1} + 1) = p_{n+1}^4 + p_{n+1}^3 \tag{11}\label{eq11A}$$

For $x = 17$, we have $n = 6$ and $p_n = 13$, so the left side of the second part of \eqref{eq11A} is $13\# = 30,030$ but the right side is $17^3(18) = 88,434$, so we need to check this value in particular. We have $P(17) = \frac{13\#}{2(3)} = 5,005$ and $f(17) = 17(18) = 306$, so your conjecture is true in this case.

With $18 \le x \le 23$, then $n = 7$ and $p_{n} = 17$, so the left side of \eqref{eq11A} is $17\# = 510,510$ and the right side is $19^3(20) = 137,180$, so the inequality holds.

As you basically did, using induction, this is the base step. Assume \eqref{eq11A} is true for all $n \le k$ for some $k \ge 7$. Then to check the $n = k + 1$ case, multiply the induction step inequality by $p_{k+1}$, use $p_{k+1} \ge 23$ and Betrand's postulate, to get

$$\begin{equation}\begin{aligned} p_{k+1}\# & \gt p_{k+1}(p_{k+1}^4 + p_{k+1}^3) \\ & \gt 16(p_{k+1}^4) + 16(p_{k+1}^3) \\ & \gt (2p_{k+1})^4 + (2p_{k+1})^3 \\ & \gt p_{k+2}^4 + p_{k+2}^3 \end{aligned}\end{equation}\tag{12}\label{eq12A}$$

This shows \eqref{eq11A} is true also for $n = k + 1$, which proves by induction that it's always true for $n \ge 7$, and thus $x \ge 18$. Altogether, this proves your conjecture, i.e., $P(x) \gt f(x)$, is true for all $x \ge 17$.

Answer 2

Another method, using properties of the first Chebyshev function (by $p$ we mean prime(s) everywhere below) $$\vartheta (x)=\sum _{{p\leq x}}\log p$$ According to this paper, page 20 $${\vartheta (x)>0.985x}, \forall x\geq 11927$$ thus $$\prod\limits_{p\leq x} p=e^{\vartheta (x)}\geq e^{0.985x} \tag{1}$$ It's not too difficult to show that $$e^{0.985x} \geq \left(x^2+x\right)^2 \Rightarrow \frac{e^{0.985x}}{x^2+x}\geq x^2+x \tag{2}$$ Now $$\prod\limits_{p\leq x} p= \left(\prod\limits_{p\leq x \text{ and } p \nmid x^2+x} p \right) \left(\prod\limits_{p\leq x \text{ and } p \mid x^2+x} p \right)$$ thus, from $(1)$ $$\prod\limits_{p\leq x \text{ and } p \nmid x^2+x} p \geq \frac{e^{0.985x}}{\prod\limits_{p\leq x \text{ and } p \mid x^2+x} p} \tag{3}$$ Finally, because the product doesn't consider the multiplicity of the prime factors $$\prod\limits_{p\leq x \text{ and } p \mid x^2+x} p \leq x^2+x \tag{4}$$ and combining $(2)$, $(3)$ and $(4)$ $$\prod\limits_{p\leq x \text{ and } p \nmid x^2+x} p \geq \frac{e^{0.985x}}{x^2+x}\geq x^2+x$$ $\forall x\geq 11927$. The first $11926$ cases can be checked with a computer program.