# Problem to permute sum : $\sum_{n\leq x}\sum_{d^2\mid n}=\sum_{d\ ??}\sum_{n\ ??}$

I always have problem to permute such sum : So let $\mu$ the Moebius function (but it's not important).

Could someone explain me how to write $$\sum_{n\leq x}\sum_{d^2\mid n}\mu(d)$$ as $$\sum_{d\ ??}\sum_{n\ ??}\mu(d)\ \ ?$$

I tried to use something like : let $n=k^2m$ where $m$ has no square factor. Then $d^2\mid n\iff d\mid k$, but I can't make it easier.

• Think about this : you sum over couples $(n,d)\in\mathbb{N}^2$ with $n\leq x$ and $d^2 \mid n$, which is the same as summing over couples $(d,n)$ with the same properties. Noting that an empty sum is $0$, we have, symbolically : $\displaystyle\sum_{n\leq x}\displaystyle\sum_{d^2\mid n} = \displaystyle\sum_{d\in \mathbb{N}}\displaystyle\sum_{n\leq x\land d^2\mid n}$ – Max Apr 1 '17 at 14:09
• @Max : Sorry, but it doesn't help for me. It doesn't give a simpler sum. – MathBeginner Apr 1 '17 at 15:35
• Because $\mu (d)$ is unrelated to $n$, you only need to count the number of $n$ satisfying the inner sum condition. It simplifies the equation a lot. – didgogns Apr 1 '17 at 15:41

Instead of iterating over the square divisors of $n$, iterate over square numbers $d^2\leq x$ (which is the same as iterating $d \leq \lfloor\sqrt{x}\rfloor$) and figure out how often that $d$ will be a square divisor that occurs among all the $n$ values $\leq x$, which will be $\lfloor \frac{x}{d^2} \rfloor$ overall per $d$ (so the $n$ loop is not needed):
$$\sum_{d \leq \lfloor\sqrt{x}\rfloor} \left\lfloor\frac{x}{d^2}\right\rfloor \mu(d)$$
$$\sum_{n\leq x}\sum_{d^2\mid n}\mu(d) = \sum_{n=1}^\infty \sum_{d=1}^\infty \mu(d) 1_{d^2 | n} 1_{n \le x}\\ = \sum_{d=1}^\infty \mu(d) \sum_{n=1}^\infty 1_{d^2 | n} 1_{n \le x} = \sum_{d=1}^\infty\mu(d) \sum_{k=1, n = kd^2}^\infty 1_{ kd^2 \le x}$$ And you can simplify further $$= \sum_{d=1}^\infty \mu(d) \sum_{k=1}^{\infty} 1_{k \le \lfloor x/d^2 \rfloor} = \sum_{d=1}^{\lfloor x \rfloor} \mu(d) \lfloor x/d^2 \rfloor$$