A conjecture concerning primes and algebra

Solution 1:

Here's at least a good start at a solution. The strategy is to find situations in which we can say: if $\prod p_k^{n_k} \le x$ and $\prod k^{n_k}$ is known to be at most $\pi(x)$, then $p_j \prod k^{n_k} \le \pi(p_j x)$.

Suppose that $x\ge35$ and $y\ge10$, and set $\alpha=1.25506$. Then one can verify the inequalities $$ \log x > 3.55 > \frac{\alpha y\log(y\log y\log\log y)}{y\log y-\alpha y}. $$ Using the Rosser-Schoenfeld bounds $p_j > j\log j$ and $p_j < j\log j\log\log j$, which are valid for $j\ge10$, we deduce that $$ \log x > \frac{\alpha j\log p_j}{p_j-\alpha j} $$ and this can also be verified by hand for $5\le j\le 9$. We rearrange this to $$ \frac{p_jx}{\log p_jx} > j\frac{\alpha x}{\log x}. $$ Using the Rosser-Schoenfeld bounds $\pi(x) > x/\log x$ and $\pi(x) < \alpha x/\log x$, both valid for $x\ge17$, we deduce that $$ \pi(p_jx) > j\pi(x). $$ So we have proved the following: if $N\ge35$ satisfies $\psi(N) \le \pi(N)$, and $j\ge5$, then $$ \pi(p_jN) > j\pi(N) \ge j\psi(N) \ge \psi(p_j N) $$ as well.

This shows that a minimal counterexample to your conjecture, if one exists, must be a number of the form $p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}$, or else a number of the form $2p$, $3p$, ..., $35p$ or $49p$ for some prime $p$. Each of these families can probably be dealt with individually by similar methods.

Solution 2:

It took a long time before I understood how Greg Martin's lemma $$N\ge17\wedge n\ge5\implies \pi(p_nN)>n\pi(N)$$ could be exploited. The method in the proof of the lemma required $n\ge5$, but the lemma is true even for $1\le n\le 4$, which can be proved using an inequality of Pierre Dusart proved in 2010:

$\displaystyle \frac {x} {\ln x - 1} < \pi(x)$, for $x \ge 5393$, and $\displaystyle \pi(x) < \frac {x} {\ln x - 1.1}$, for $x \ge 60184$.

E.g. for $n=4$. If $N$ is sufficiently large: $3\ln N>11.7$ why $\displaystyle\frac{\ln N+1}{7N}<\frac{\ln N-1.1}{4N}$ which implies that $\displaystyle\frac{7N}{\ln N+1}>\frac{4N}{\ln N-1.1}.\;$ Now, due to Dusart, $\displaystyle\pi(7N)>\frac{7N}{\ln 7N-1}>\frac{7N}{\ln N+1}>\frac{4N}{\ln N-1.1}>4\pi(N)$. All four cases ($n=1,2,3,4$) has been tested on my computer and holds for $N>7$ and $p_nN<1\,000\,000$, which is big enought. $\square$

The general lemma is: $N\geq 17\implies\pi(p_nN)>n\pi(N)$. It should be pointed out that in the proof $N$ has to be larger, but the proof is complemented with computer tests.

Hence, suppose $\omega(x)\leq\pi(x)$ for all $x<M=p_nN$, then if $N\ge17$ $\omega(p_nN)=n\omega(N)\leq n\pi(N)<\pi(p_nN)$. If $N<17$ and $p_n\geq17$ it holds that $\pi(p_nN)>\pi(p_n)\omega(N)=\omega(p_n)\omega(N)=\omega(p_nN)$. The case with $N<17$ and $p_n<17$ is covered by the computer test $(x>49)$. So the conjecture is proved by induction.