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.

  • $\begingroup$ 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}$ $\endgroup$ – Max Apr 1 '17 at 14:09
  • $\begingroup$ @Max : Sorry, but it doesn't help for me. It doesn't give a simpler sum. $\endgroup$ – MathBeginner Apr 1 '17 at 15:35
  • $\begingroup$ 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. $\endgroup$ – 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$$


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.