## Monday, May 11, 2015

### Upper and lower bounds on the totient summatory function

In this post I use manipulations as in Ramanujan's proof of Bertrand's postulate to calculate explicit upper and lower bounds on the totient summatory function $\Phi(x) = \sum_{n \le x} \phi(n)$. This shows how Ramanujan's proof works in a simpler situation.

Here we go. Because $\phi \star 1 = n$, it follows that $\sum_{n =1}^\infty \Phi(\frac{x}{n}) = \sum_{n \le x} n \equiv F(x)$. Because $\Phi$ is always positive, the upper bound $F(x) \ge \Phi(x)$ follows trivially. To obtain a lower bound, calculate

\begin{align} F(x) - 2 F(\frac{x}{2} ) &= \Phi(x) + \Phi(\frac{x}{2}) + \Phi(\frac{x}{3}) + \cdots - 2 \Phi(\frac{x}{2}) -2 \Phi(\frac{x}{4 }) -\cdots \\ &= \Phi(x) - \Phi(\frac{x}{2}) + \Phi(\frac{x}{3}) - \cdots \\ \end{align}
This is an alternating series, thus $F(x) - 2 F(\frac{x}{2} ) \le \Phi(x)$. If for simplicity I do not make a distinction between $x$ and $\lfloor x \rfloor$, then $F(x) = \frac{1}{2} x ( x +1 )$ and $F(x) - 2 F(\frac{x}{2} ) = \frac{x^2}{4}$. One has thus
$$\frac{x^2}{4} \le \Phi(x) \le \frac{1}{2} x ( x +1 )$$
I will now check these inequalities in Mathematica. Here is a graph of values of $\Phi(x)$ (blue dots) and the upper and lower bounds (black lines) for $x$ up to 50.

This looks good. I also check for $x$ up to 10000.
Both values are positive; the inequalities thus seem to be valid.
Remarks
• The proof is not complete because I have not made a distinction between $x$ and $\lfloor x \rfloor$
• It is known that $\Phi(x) \sim \frac{3}{\pi^2} x^2$, see here for example.
• The calculations were performed in Mathematica 10 Home Edition.