6
$\begingroup$

I wanted to know if we know any asymptotic formula/bound for the following sum

$$ \sum_{1 \leq a < n \\(a,n) = 1 } \phi(a) \ .$$

A trivial upper bound could be $$ \sum_{a=1}^{n} \phi(a) = \frac{3}{\pi^2} n^2 + O(n^{1+\epsilon}), $$ but I wanted to know if we could do better than that. Thanks in advance for the help!

References

https://en.wikipedia.org/wiki/Euler%27s_totient_function#Other_formulae

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ You might enjoy working with the complementary sum, where a is 1 or a is not coprime to n. Gerhard "See If It Helps Any" Paseman, 2017.08.13. $\endgroup$ – Gerhard Paseman Aug 13 '17 at 20:05
  • $\begingroup$ OEIS sequence A053570. $\endgroup$ – Robert Israel Aug 13 '17 at 23:02
12
$\begingroup$

The answer here is

$$\frac{3}{\pi^2}n^2\prod_{p\mid n} \frac{p}{p+1}+O(nd(n)\log\log n+ n\log n),$$

where $d(n)$ is a divisor function and product is over prime values of $p$.

To prove this, note first that

$$\sum_{\substack{a\leq n \\ (a,n)=1}} \varphi(a)=\sum_{a \leq n} \varphi(a)\sum_{d \mid (a,n)} \mu(d)=\sum_{d \mid n} \mu(d)\sum_{bd\leq n} \varphi(bd).$$

Now, using the identity

$$\varphi(a)=a\sum_{d \mid a}\frac{\mu(d)}{d}$$

we get

$$\sum_{bd \leq n} \varphi(bd)=\sum_{b \leq \frac{n}{d}}bd\sum_{c\mid bd} \frac{\mu(c)}{c}.$$

Changing order of summation, we obtain

$$\sum_{bd \leq n}\varphi(bd)=d\sum_{c \leq n}\frac{\mu(c)}{c}\sum_{\substack{b \leq n/d \\ \frac{c}{(c,d)} \mid b}}b.$$

As for any $x$ and $y$ the equality

$$\sum_{\substack{b \leq x \\ y \mid b}} b=\frac{x^2}{2y}+O(x)$$

holds, the inner sum equals

$$\sum_{\substack{b \leq n/d \\ \frac{c}{(c,d)} \mid b}}b=\frac{n^2(c,d)}{2cd^2}+O(\frac{n}{d}).$$

Therefore,

$$\sum_{bd \leq n} \varphi(bd)=\frac{n^2}{d}\sum_{c \leq n} \frac{\mu(c)(c,d)}{2c^2}+O(n\log n).$$

Let us now compute the sum in the RHS of this identity:

$$\sum_{c \leq n} \frac{\mu(c)(c,d)}{c^2}=\sum_{c=1}^{+\infty} \frac{\mu(c)(c,d)}{c^2}-\sum_{c>n} \frac{\mu(c)(c,d)}{c^2}=S_1-S_2$$

(both series are obviously convergent) Now we should compute $S_1$ and estimate $S_2$. Note that the function $\frac{\mu(c)(c,d)}{c^2}$ is multiplicative due to the multiplicativity of $\mu(c), c^2$ and $(c,d)$. Thus,

$$S_1=\prod_p (1-\frac{(c,p)}{p^2})=\prod_p (1-1/p^2)\prod_{p \mid d}\frac{p}{p+1}=\frac{6}{\pi^2}\prod_{p \mid d} \frac{p}{p+1}.$$

To obtain the estimate for the $S_2$, observe that

$$|S_2|\leq \sum_{c>n} \frac{(c,d)}{c^2}\leq \sum_{t \mid d} \sum_{ft>n} \frac{t}{(ft)^2}=O\left(\frac{d(n)}{n}\right).$$

So,

$$\sum_{bd \leq n} \varphi(bd)=\frac{3n^2}{\pi^2d}\prod_{p \mid d} \frac{p}{p+1}+O(nd(n)/d+n\log n).$$

Summing this over all $d$, we finally get

$$\sum_{\substack{a\leq n \\ (a,n)=1}} \varphi(a)=\frac{3n^2}{\pi^2}\sum_{d \mid n} \frac{\mu(d)}{d}\prod_{p \mid d} \frac{p}{p+1}+O(nd(n)\log\log n+n\log n)=\frac{3n^2}{\pi^2}f(n)+O(nd(n)\log\log n+\log n).$$

To get a bit more closed-form expression for $f(n)$ note that $f$ is again multiplicative and for any prime $p$ and positive $\alpha$ we have

$$f(p^\alpha)=\frac{\mu(1)}{1}+\frac{\mu(p)}{p}\frac{p}{p+1}=1-\frac{1}{p+1}=\frac{p}{p+1},$$

therefore

$$f(n)=\prod_{p \mid n} \frac{p}{p+1},$$

as needed.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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