# Conjecture: $\pi(x)\ge \pi\circ\pi(x)+\pi\circ\pi\circ\pi(x)+\cdots$

$x\ge 13\implies\pi(x)\ge \pi\circ\pi(x)+\pi\circ\pi\circ\pi(x)+\cdots$

Can this be proved?

• Does $\pi\circ\pi(x)$ mean $\pi(\pi(x))$? – Deepak Aug 11 '16 at 12:02
• This isn't a proof but this was my first thought: Replace Pi(x) by (1/2)*x-a since the around half of the numbers up to x are even primes and the a would just correct this expression to be equal to Pi(x). Then what you end up getting is (1/2 )*x-a >= (1/2)((1/2)x-a)-b + (1/2)((1/2)((1/2)x-a)-b)-c) which seems like it is true since 1/2= 1/4+1/8+1/16... – mtheorylord Aug 11 '16 at 12:08
• Maybe an idea about the sum : We know that $\pi(x) < 4/3\cdot x/\ln(x)$. Also we have $4/3 \cdot 1/\ln(12) < 3/5$ therefore for $x > 12,\ \pi(x) < 3/5x$. The sum on the RHS can be bounded : $\sum_{i=2}^\infty \pi^{\circ^i}(x) < \sum_{i=2}^\infty (\frac{3}{5})^i x = 9/10x$. Also it exists lower-linear bound for $\pi(x)$. So maybe refining a bit this technique and putting the two bounds together could lead to something. – Zubzub Aug 11 '16 at 12:28
• (Actually I don't think it exists lower-linear bound, sorry about that, I was thinking about something $0.9 x/\ln(x) < \pi(x)$ which does not work since $x$ can grow) – Zubzub Aug 11 '16 at 12:35
• I think your best approach is to use bounds from the prime number theorem. Use lower bounds on the right and an upper bound on the left. If we just use the naive $\pi(x) \approx \frac n{\log x}$ you are asking for $\frac 1{\log x} \gt \frac 1{\log x \cdot ( \log x -\log \log x)}+\ldots$ and that factor of $\log^2 x$ in the denominator should be enough – Ross Millikan Aug 11 '16 at 14:31

The inequality is trivially true because from the prime number theorem, the LHS is asymptotic to $\frac{x}{\log x}$ where as the RHS is asymptotic to $\frac{x}{\log^2 x}$ so clearly this is a very weak inequality and is has to be true for all $x$ greater than some minimum value which in this case turns to be 13.

What would make the inequality non-trivial is if the LHS and RHS are of the same asymptotic order. I present a stronger form of the above inequality.

Let $s(x) = \pi(\pi(x)) + \pi(\pi(\pi(x))) + \ldots$.

Pierre Dusart has proved that $$\pi(x) \ge \frac{x}{\log x - 1}, \ x > 5393$$

$$\pi(x) \le \frac{x}{\log x - 1.1}, \ x > 60,184$$

From these two inequalities and little algebraic manipulation we obtain

$$\frac{x}{(\log x - 1)(\log x - 2)} < s(x) < \frac{x}{(\log x - \log\log x)(\log x - \log\log x - 1)}$$

or in the slightly weaker but simpler form

$$\frac{x}{(\log x - 1)^2} < s(x) < \frac{x}{(\log x - \log\log x - 1)^2}$$

for all $x > 60,184$. Clearly the RHS is less than $\pi(x)$ so the weaker original inequality follows.

• The asymptotic behavior of $\pi(x)$ doesn't by itself make the inequality true, even for large $x$. For instance, if you had $\pi(1)=1$ instead of $\pi(1)=0$... a very small change at very small $x$... then the sum on the RHS would diverge instead. – mjqxxxx Aug 12 '16 at 14:31
• Yes, but in this specific case we already knew that $\pi(1) = 0$ hence the argument. – Nilotpal Kanti Sinha Aug 12 '16 at 15:41

Certainly $\pi(x) \le (2/3)x$ for all $x$, so the right-hand side satisfies $$\pi(\pi(x)) + \pi(\pi(\pi(x))) + \pi(\pi(\pi(\pi(x)))) + \ldots \le \pi(\pi(x))\left(1+\frac{2}{3}+\frac{4}{9}+\ldots\right)=3\pi(\pi(x)).$$ Using the inequality $\pi(x) < 1.25506 (x / \ln x)$, then, we have $$3\pi(\pi(x))\le(1.25506\cdot 3 / \ln(\pi(x)))\pi(x) < \pi(x)$$ provided that $\ln(\pi(x)) > 3.76518$, or $\pi(x)\ge44$, or $x \ge p_{44}=191$. And a direct numerical check shows your inequality holds for $13\le x<191$.

Actually, something more general can be proven:

$$n \geq \pi(n) + \pi(\pi(n))+ \pi(\pi(\pi(n))) + \cdots$$

First, note that $\pi(n) \leq \frac23n$ for all $n$. Also, note that $\pi(n) \leq \frac13n$ for $n \geq 35$.

Proof. $\pi(n) \leq \frac12n+1$ for all $n$ follows from the fact that two is the only even prime. This is smaller than $\frac23n$ for all $n\geq 6$. It can be checked manually for $n=1,2,3,4,5$.

For the second inequality, note that every prime not equal to $2,3$ is congruent to $1$ or $-1$ modulo $6$. Now note that $1, 25$ and $35$ do have this form, but are not prime. From this, we also have $\pi(n) \leq \frac13n$ for $n \geq 35$.

Now the main proof:

Let $f^k$ denote function iteration. We have for $n\geq35$ that $$\pi^k(n) = \pi^{k-1}(\pi(n)) \leq \pi^{k-1}\left(\frac13n\right) \leq \left(\frac23\right)^{k-1}\cdot \left(\frac13n\right)$$

Hence we have the inequality $$\sum_{i=1}^{\infty} \pi^i(n) \leq \sum_{i=1}^{\infty} \frac13\left(\frac23\right)^{i-1}n = \frac13n \sum_{i=1}^{\infty} \left(\frac23\right)^{i-1} = \frac13n \cdot \frac1{1-\frac23}=n$$

Now, substituting $n=\pi(x)$ gives the desired result for $x \geq 149$.

Another user already showed this for $13\leq x \leq 2000$, so this gives the result.