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:


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.

  • $\begingroup$ You can probably post this on Mathoverflow to get a higher chance of an answer. $\endgroup$ – Espen Nielsen Oct 29 '14 at 22:57
  • 2
    $\begingroup$ not necessary ... $\endgroup$ – Will Jagy Oct 29 '14 at 23:03
  • $\begingroup$ Is your function $f$ the same as $i\mapsto\psi(p_i)$? $\endgroup$ – Greg Martin Oct 29 '14 at 23:03
  • $\begingroup$ I also would quibble with calling this morphism algebraically canonical: it depends intrinsically on the ordering defined on $\Bbb N$, which is not an algebraic notion. $\endgroup$ – Greg Martin Oct 29 '14 at 23:20
  • $\begingroup$ @Greg: Yes, $f(i)=\psi(p_i)$ and for $f(i)=i$, $(\psi(p_i)=i)$ $f$ is the identity and therefore I mean that it defines almost canonical morphisms in $\mathbb Z_+$ and $\mathbb Q_+$. Thanks for your answer, I'll try to grasp your proof technique. $\endgroup$ – Lehs Oct 30 '14 at 2:35

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.

  • $\begingroup$ I appreciate your answer more and more. The lemma $x\ge 17 \wedge j\ge 5\Rightarrow \pi(p_jx)>j\pi(x)$, shows that $\omega(N)<\pi(N)$ for $N>17\cdot 11$ if $p_n|N,\,n>4$. Since $\omega(N)=\omega(N'p_n)=\omega(N')n\le\pi(N')n<\pi(N)$, for $N>11\cdot 17$. $\endgroup$ – Lehs Nov 3 '14 at 13:36

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.


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.