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
add comment

2 Answers 2

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
add comment

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.

share|improve this answer
add comment

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.