# Upperbound approximation to the sum of Euler's totient function

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}

-
Well, have the $i$ are even and have $\phi(i)\le \frac i2$. That should give you an improvement to an upper bound $\approx \frac38n^2$ isntead of $\frac12 n^2$, but that'ts not much –  Hagen von Eitzen Oct 15 '13 at 5:53

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}.$$

-

We have the asymptotic behaviour

$$\Phi(N) = \frac{3}{\pi^2}N^2 + O(N\log N).$$

The $\frac{3}{\pi^2}N^2$ is of course not an upper bound (it might be a lower bound, but perhaps not). So that gives us something we can compare our bounds to. The $\frac38$ is then not too terrible, but asymptotically, it is about $23.4\%$ too large.

To get smaller upper bounds, let us give an interpretation to some quantities. $\phi(n)$ is the number of reduced fractions $0 < \frac{k}{n}\leqslant 1$ with denominator $n$. Then $\Phi(N)$ is the number of reduced fractions $0 < \frac{k}{n}$ with denominator $n \leqslant N$. The number of all fractions - reduced or not - $0 < \frac{r}{s} \leqslant 1$ with denominator $1 \leqslant s \leqslant N$ is

$$F(N) = \frac12 \lfloor N\rfloor(\lfloor N\rfloor+1).$$

Since we can write every fraction in a unique way

$$\frac{r}{s} = \frac{g\cdot \rho}{g\cdot\sigma}$$

with $g = \gcd(r,s)$ and $\rho = r/g,\, \sigma = s/g$, we see that

$$F(N) = \sum_{g=1}^\infty \Phi\left(\frac{N}{g}\right)\tag{1}$$

(where, for convenience, we extend $\Phi$ to non-integral arguments by defining $\Phi(x) := \Phi(\lfloor x\rfloor)$ in that case).

Rearranging $(1)$ gives

$$\Phi(N) = F(N) - \sum_{g=2}^\infty \Phi\left(\frac{N}{g}\right),\tag{2}$$

and expanding $\Phi(N/2)$ according to $(2)$ then yields

\begin{align} \Phi(N) &= F(N) - \left(F\left(\frac{N}{2}\right) - \sum_{h=2}^\infty \Phi\left(\frac{N}{2h}\right)\right) - \sum_{g=3}^\infty \Phi\left(\frac{N}{g}\right)\\ &= F(N) - F\left(\frac{N}{2}\right) - \sum_{k=1}^\infty \Phi\left(\frac{N}{2k+1}\right).\tag{3} \end{align}

Since $\Phi(x) \geqslant 0$, you directly get an upper bound $F(N) - F\left(\frac{N}{2}\right)$ that is almost identical to the one you have, with the same asymptotical $\frac38 N^2$ behaviour. But it's easy to get stricter bounds from $(3)$, by expanding further terms.

If we also expand $\Phi\left(\frac{n}{3}\right)$ according to $(3)$, we get

$$\Phi(N) = F(N) - F\left(\frac{N}{2}\right) - F\left(\frac{N}{3}\right) + F\left(\frac{N}{6}\right) - \sum_{\substack{k\geqslant 5\\k\text{ odd}\\3\nmid k}} \Phi\left(\frac{N}{k}\right).$$

Evidently, $F(N) - F\left(\frac{N}{2}\right) - F\left(\frac{N}{3}\right) + F\left(\frac{N}{6}\right) \geqslant \Phi(N)$, and the asymptotic of that bound is $\frac13 N^2$, which is only about $9.66\%$ too large.

Further expanding $\Phi\left(\frac{N}{5}\right)$ by $(3)$ yields

\begin{align} \Phi(N) &= F(N) - F\left(\frac{N}{2}\right) - F\left(\frac{N}{3}\right) + F\left(\frac{N}{6}\right) - F\left(\frac{N}{5}\right) + F\left(\frac{N}{10}\right)\\ &\qquad - \sum_{k}' \Phi\left(\frac{N}{k}\right) + \sum_{m=1}^\infty \Phi\left(\frac{N}{15m}\right) \end{align}

where $\sum\limits_{k}'$ extends over the odd $k > 5$ divisible neither by $3$ nor by $5$. It is easy to see that $F(N) - F\left(\frac{N}{2}\right) - F\left(\frac{N}{3}\right) + F\left(\frac{N}{6}\right) - F\left(\frac{N}{5}\right) + F\left(\frac{N}{10}\right)$ is an upper bound for $\Phi(N)$, since every term $\Phi\left(\frac{N}{15m}\right)$ in the second sum is compensated by the term $\Phi\left(\frac{N}{15m-2}\right)$ in the first. That bound is asymptotically $\frac{191}{600} N^2$, and about $4.7\%$ too large.

Expanding also $\Phi\left(\frac{N}{7}\right)$ gives a bound with asymptotic behaviour $\frac{4567}{14700}N^2$ that is about $2.21\%$ too large, but seeing that all added $\Phi\left(\frac{N}{m}\right)$ are then still compensated by a $\Phi\left(\frac{n}{j}\right)$ with $j < m$ that is subtracted is less obvious. If one wants to continue that route, expanding further $\Phi\left(\frac{N}{k}\right)$ by $(3)$, one needs to expand added terms to keep an upper bound too, and it is probably a good idea to expand $\Phi\left(\frac{n}{15}\right)$ before (or simultaneously with) expanding $\Phi\left(\frac{n}{11}\right)$, and

\begin{align} \Phi(N) &\leqslant F(N) - F\left(\frac{N}{2}\right) - F\left(\frac{N}{3}\right) + F\left(\frac{N}{6}\right) - F\left(\frac{N}{5}\right) + F\left(\frac{N}{10}\right)\\ &\quad - F\left(\frac{N}{7}\right) + F\left(\frac{N}{14}\right) - F\left(\frac{N}{11}\right) + F\left(\frac{N}{22}\right) + F\left(\frac{N}{15}\right) - F\left(\frac{N}{30}\right) \end{align}

gives a bound with asymptotics $\frac{183353}{592900}N^2$, about $1.74\%$ too large.

Better bounds require more and more work. For smallish $N$, computing the exact value very soon is no more work, and for large $N$, you can choose almost any constant larger than $\frac{3}{\pi^2}$ and call it a day.

-