10
$\begingroup$

While testing my system Zet for computational mathematics I find possible relations now and then. The latest is:

Conjecture:

For all $(m,n)\in\mathbb Z_+^2$ except $(3,4),(4,3) \text{ and } (4,4)$ it holds that $p_m\cdot p_n > p_{m\cdot n}$

$\endgroup$
  • 3
    $\begingroup$ Since $p_n\approx{n}\ln{n}$ it should be pretty easy to prove. $\endgroup$ – barak manos May 24 '16 at 10:29
  • 3
    $\begingroup$ Better yet, see here, the bounds are $n(\ln{n}+\ln\ln{n}-1)<p_n<n(\ln{n}+\ln\ln{n})$. $\endgroup$ – barak manos May 24 '16 at 10:31
  • $\begingroup$ That's right. Follows immediately even from your first consideration. If I were the OP, I'd give you the bounty. $\endgroup$ – Yiannis Galidakis May 26 '16 at 14:48
  • $\begingroup$ @YiannisGalidakis, prove it and earn 75p. $\endgroup$ – Lehs May 26 '16 at 17:11
  • $\begingroup$ Prove it using somebody else's idea? No. That's not fair to barak manos. Ask him to prove it if he wants or prove it yourself. Cheers. $\endgroup$ – Yiannis Galidakis May 26 '16 at 17:29
15
+50
$\begingroup$

Both the methods represent a partial proof of the conjecture. For a complete proof see Winther's answer below.

First Method

We know that, $$\dfrac{x}{\ln x}<\pi(x)<\dfrac{2x}{\ln x}\tag{1}$$

for all $x\ge 17$ (see Greg Martin's comment below).

We prove the following theorem,

Theorem. For all $x,y\in \mathbb{N}$ and $x,y\ge 24154953$ we have $\pi(xy)>\pi(x)\pi(y)$ where $\pi(x)$ denotes the prime counting function.

Sketch of the proof. If we can show that, \begin{align}\dfrac{xy}{\ln xy}>\dfrac{4xy}{(\ln x)(\ln y)}&\implies \dfrac{(\ln x)(\ln y)}{\ln xy}>\dfrac{1}{4}\\&\implies\dfrac{(\ln x)(\ln y)}{(\ln x+\ln y)}>\dfrac{1}{4}\tag{2}\end{align}Then we are done. Let us now suppose that $a=\ln x$ and $b=\ln y$. Then, we are to show that for all sufficiently large $a,b\in\mathbb{R}$ we have, $$\dfrac{4 ab}{a+b}>1\implies 4>\dfrac{1}{a}+\dfrac{1}{b}\tag{3}$$ Then if we take $a\ge 17(=\max(4, C))$, we have $(3)$. This in turn shows that for all $x,y\ge e^{17}$ we have $(2)$. Since $24154953>e^{17}$, we are done.

When we have this theorem, what we need to do is to choose both $p_n$ and $p_m$ such that $p_n,p_m\ge e^{17}$. Then we can say that, $$\pi(p_mp_n)>\pi(p_m)\pi(p_n)\implies \pi(p_mp_n)>mn\implies \pi(p_mp_n)>\pi(p_{mn})\implies p_mp_n>p_{mn}$$All that remains is to check the remaining cases.

Remarks

We have proved that $\pi(xy)>\pi(x)\pi(y)$ for all sufficiently large $x,y\in\mathbb{N}$. But now we pose the question that for which functions $f:D\to \mathbb{N}$ with $\mathbb{N}\subseteq D\subseteq \mathbb{R}$ we can say that $\pi(f(xy))>\pi(f(x))\pi(f(y))$?

Examining the proof carefully we can find a sufficient condition for such $f$'s.

  • Since $(1)$ is always valid for $x\ge \max(2,C)$, if we take $f(x)\ge \max(2,C)$ for all $x\in \mathbb{N}$, $(1)$ will hold for our case too.

  • Observe that we have written, $$\dfrac{xy}{\ln xy}>\dfrac{4xy}{(\ln x)(\ln y)}\implies \dfrac{(\ln x)(\ln y)}{\ln xy}>\dfrac{1}{4}$$To satisfy this requirement we take $f(xy)\ge f(x)f(y)$

Furthermore observe that any function satisfying these two requirements also satisfies $(3)$ because, $$\dfrac{1}{\ln f(x)}+\dfrac{1}{\ln f(y)}\le \dfrac{1}{\ln 2}+\dfrac{1}{\ln 2}=\dfrac{2}{\ln 2}<4$$

Hence the complete statement of the theorem can be written as,

Let $f:D\to \mathbb{N}$ (where $\mathbb{N} \subseteq D\subseteq \mathbb{R}$),

  • $f(x)\ge 2$ for all $x\in \mathbb{N}$

  • $f(xy)\ge f(x)f(y)$

Then $\pi(f(xy))>\pi(f(x))\pi(f(y))$ for all $f(x),f(y)\ge e^{17}$.

But the bound obtained here is a pretty large bound. To remove this obstacle, we prove the conjecture by following method.

Second Method

We know that for all $n\ge 6$ we have, $$n\ln n<p_n<2n\ln n\tag{4}$$Hence to prove the conjecture we first need to show that for all $m,n\ge 6$, $$2mn\ln (mn)\le mn(\ln m)(\ln n)$$Which is equivalent to showing that, $$2\ln (mn)\le (\ln m)(\ln n)\tag{5}$$Now let $a=\ln m$ and $b=\ln n$. Then observe that $(5)$ holds for $\min(a,b)\ge 4$ because, $$2(a+b)\le 4\max(a,b)\le \min(a,b)\max(a,b)=ab$$Hence we conclude that for all $m,n\ge 55$ (because $e^4<55$) we have $p_mp_n>p_{mn}$.

$\endgroup$
4
+100
$\begingroup$

The proof of the conjecture for sufficiently large $n,m$ has been given in the other answer. I will here focus on getting control on the "sufficiently large" part thereby giving a way to make a proof of the conjecture for all $n,m$. I will stick to simply presenting the inequalities and the range for which they are satisfied without showing all the hairy calculations so you should try to verify these for yourself.


For $n\geq 6$ Rosser's theorem gives precice inequalities for the $n$'th prime number $$\log(n) + \log\log(n) - 1 < \frac{p_n}{n} < \log(n) + \log\log(n)$$ From this we get $[\log(n) +\log\log(n)-1][\log(m)+\log\log(m)-1] < \frac{p_np_m}{nm}$ and $\frac{p_{nm}}{nm} < \log(nm) + \log\log(nm)$ so the conjecture follows if we can prove

$$\log(nm) + \log\log(nm) < [\log(n) +\log\log(n)-1][\log(m)+\log\log(m)-1]$$

This inequality can be shown to hold for all $n,m\geq 15$. The cases $n,m<15$ can be done by brute force and shows only three cases where it's violated: $(3,4),(4,3)$ and $(4,4)$. The remaining cases follows if we can prove

$$\log(mn) + \log\log(mn) < \frac{p_m}{m}[\log(n) + \log\log(n)-1]$$

for $m=1,2,3,\ldots,14$ for $n\geq 15$. This inequality can again be shown to hold for $n\geq 33$. A final brute-force check of the cases $n\in[15,33]$ and $m\in[1,14]$ completes the proof of the conjecture.


Note that one does not need to prove the best possible version of the inequalities above (i.e. $15$ for the first inequality and $33$ for the second inequality). We can strick with a worse value at the expence of checking more cases numerically. Replacing $15$ and $33$ by $100$ and $1000$ should make the proof of the inequalities easier and it will still be fast to verify the remaining cases $(n \leq 100, m \leq 1000)$ numerically.

$\endgroup$
  • $\begingroup$ I see now that I was wrong. You are right. For the present moment I think we can't avoid using stronger results. $\endgroup$ – user 170039 May 31 '16 at 13:06
  • $\begingroup$ @user170039 Ok. Well if you find a better way then let me know. The current way to prove it is a bit clumpsy in my opinion so it would be nice to see if there is a better/simpler way. $\endgroup$ – Winther May 31 '16 at 13:09

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.