A conjecture concerning primes and algebra

Question

A monoid morphism $\psi:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ is defined by an arbitrary function $f:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ and defines a group homomorphism $\varphi:\mathbb Q_+\!\!\rightarrow\mathbb Q_+$:

$\psi(a\cdot b)=\psi(a)\cdot\psi(b)\Rightarrow\psi(\prod p_i^{n_i})=\prod\psi(p_i)^{n_i}$, so any function $i\mapsto \psi(p_i)$ defines $\psi$. Further, since $\varphi(\frac{1}{n})=\frac{1}{\varphi(n)}$ a function $f$ uniquely defines the group homomorphism $\varphi$.

For fun I intend to study the group homomorphism generated by the identity function $i\mapsto\omega(p_i)=i$. Then $\omega:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ seems to be an algebraic analogue to the analytic approach with $\pi(N)$ since also $\omega$ is a left inverse to the prime number function $p_n$.

In the diagram $\omega$ is the blue curve and $\pi$ the red and one can see (especially if the picture is loaded and viewed in a larger scale) that $\omega(1)>\pi(1),\; \omega(35)>\pi(35)$ and $\omega(49)>\pi(49)$. Of course $\omega$ and $\pi$ coincide for all primes, but also for other values as $91,\;95$ and $133$. However, I have tested all values less than $2^{16}$ and $\omega(N)\leq\pi(N)$ for $N>49$ in this interval.

I have no idea how to prove the conjecture (if possible) but I will try to construct a program that (in principle) can test any interval of integers.

Edit: I realize now that it is virtually impossible to make such a program, but with help of arrays of primes my program have tested all values $< 1\,000\,000$ and the only numbers for which $\omega(N)\geq\pi(N)$ (italic numbers stands for '$>$') are:

$\mathit{1},\,9,\,15,\,21,\,25,\,\mathit{35},\,39,\,\mathit{49},\,57,\,65,\,91,\,95,\,133$.

Conjecture: For $N=\prod p_k^{n_k}>49$ it holds that $\prod k^{n_k}\leq\pi(N)$.

Thoughtful: from an analytic point of view $\omega$ seems to be very irregular, but algebraically it is an almost canonical morphism.

Answer 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.

Answer 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.