Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.