I am currently working on a solution to a problem related to the density of finite coprime sets. I believe that I have found a solution to this problem – though it can only be expressed in terms of the sum of Euler's totient function:
$$\Phi(N) = \sum_{i=1}^N \phi(i)$$
Although $\Phi(N)$ is well studied, many of the expressions for this term are not easy to work with from an analytical perspective (i.e. they depend on the Möbius function, or on recursive formulations….)
I am wondering if anyone knows of a closed-form expression which provides an upper-bound approximation to $\Phi(N)$.
The best one that I can come up with is somewhat obvious:
$$S_N = \sum_{i=1}^N \phi(i) \leq \sum_{i=1}^N i = \frac{N(N+1)}{2} $$
A better version of this bound exploits the fact that $\phi(i) \leq \frac{i}{2}$, for even numbers (proposed by Hagen von Eitzen in the comments). This leads to:
$$ \begin{align} S_N &= \sum_{i=1}^N \phi(i) \\
&\leq \sum_{k=1}^{\lfloor \frac{N}{2} \rfloor} \phi(2k) + \sum_{k=1}^{\lfloor \frac{N+1}{2} \rfloor} \phi(2k-1)\\
&\leq \sum_{k=1}^{\lfloor \frac{N}{2} \rfloor} \phi(k) + \sum_{k=1}^{\lfloor \frac{N+1}{2} \rfloor} \phi(2k-1)\\
&\leq \sum_{k=1}^{\lfloor \frac{N}{2} \rfloor} k + \sum_{k=1}^{\lfloor \frac{N+1}{2} \rfloor} 2k-1\\
&=\frac{1}{2} \Bigg(\bigg \lfloor \frac{N}{2} \bigg \rfloor \Bigg) \Bigg(\bigg \lfloor \frac{N}{2} \bigg \rfloor + 1\Bigg) + \Bigg(\bigg \lfloor \frac{N+1}{2} \bigg \rfloor \Bigg)^2\\
\end{align}
$$
Best Answer
The proof of the asymptotic formula
$$ \Phi(n) = \frac{3}{\pi^2} n^2 + O(n\log n) $$
can be modified to give a simple upper bound that has the right asymptotic character (but is not very accurate). We'll follow the proof in Chandrasekharan's Introduction to Analytic Number Theory.
By interpreting $\Phi(n)$ as the number of lattice points with relatively prime coordinates in or on the triangle $0 < y \leq x \leq n$, Chandrasekharan obtains the formula
$$ \Phi(n) = \frac{\Psi(n)+1}{2}, $$
where
$$ \Psi(n) = \sum_{1 \leq d \leq n} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor^2. $$
If we write
$$ \left\lfloor \frac{n}{d} \right\rfloor = \frac{n}{d} - \left\{\frac{n}{d}\right\}, $$
then
$$ \begin{align} \Psi(n) &= \sum_{1 \leq d \leq n} \mu(d)\left(\frac{n}{d} - \left\{\frac{n}{d}\right\}\right)^2 \\ &= n^2 \sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} - 2n \sum_{1 \leq d \leq n} \frac{\mu(d)}{d}\left\{\frac{n}{d}\right\} + \sum_{1 \leq d \leq n} \mu(d) \left\{\frac{n}{d}\right\}^2. \end{align} $$
Now
$$ \begin{align} -2n \sum_{1 \leq d \leq n} \frac{\mu(d)}{d}\left\{\frac{n}{d}\right\} &< 2n \sum_{1 \leq d \leq n} \frac{1}{d} \\ &< 2n \left(1+\int_1^n \frac{du}{u}\right) \\ &= 2n(1+\log n) \end{align} $$
and
$$ \sum_{1 \leq d \leq n} \mu(d) \left\{\frac{n}{d}\right\}^2 < \sum_{1 \leq d \leq n} 1 = n, $$
giving us
$$ \Psi(n) < n^2 \sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} + 2n\log n + 3n. $$
For the sum we get
$$ \begin{align} \sum_{1 \leq d \leq n} \frac{\mu(d)}{d^2} &= \sum_{1 \leq d \leq \infty} \frac{\mu(d)}{d^2} - \sum_{n+1 \leq d \leq \infty} \frac{\mu(d)}{d^2} \\ &= \frac{6}{\pi^2} - \sum_{n+1 \leq d \leq \infty} \frac{\mu(d)}{d^2} \\ &< \frac{6}{\pi^2} + \sum_{n+1 \leq d \leq \infty} \frac{1}{d^2} \\ &< \frac{6}{\pi^2} + \int_n^\infty \frac{du}{u^2} \\ &= \frac{6}{\pi^2} + \frac{1}{n}, \end{align} $$
so that, in total,
$$ \Psi(n) < \frac{6}{\pi^2} n^2 + 2n\log n + 4n $$
and hence
$$ \Phi(n) < \frac{3}{\pi^2} n^2 + n\log n + 2n + \frac{1}{2}. $$