I've been learning some elementary number theory purely out of interest since I don't have any number theory courses at Uni yet, I've come across the M$\ddot{o}$bius function $\mu(n)$ which takes on the values $(-1)^k$ if n is the product of k distinct primes, and 0 if n is not square free. One can quite easily show that: $$\mu^2(n) = \sum_{k|n^2}\mu(k)\qquad(1)$$ And, if you define the number of square free numbers less than or equal to N is the 'summatory function' $$Q(x) = \sum_{d \leq N}\mu^2(d)$$ And then by (1), we have $$Q(x) = \sum_{d \leq N}\mu^2(d) = \sum_{d \leq N}\sum_{k|n^2}\mu(k)$$

This is where I get stuck. I'm trying to change the order of summation, I know how to change it when there are bound to infinity, or even just finite bounds from one integer to another, but I'm unfamiliar with number theory and don't know how to deal with the summation. I've seen an example as in Simple Divisor Sum Transformation by Changing the Order of Double Summation, but I just don't know how to do it for this example.

I've done my research, and figured out there may be some kind of inclusion/exclusion argument involved, but I'm not sure I can make sense of it. Is there a general strategy one can employ here in order to change the bounds? I've also read sum squared möbius function which kind of gives me the answer I'm looking for but I just don't understand how they got there.

Any help / pointing in the right direction would be much appreciated.


  • $\begingroup$ First of all, you have the indices wrong. $$ Q(x)=\sum_{n\le x}\mu^2(n)=\sum_{n\le x}\sum_{k\mid n^2}\mu(k).$$ $\endgroup$ Commented Aug 31, 2017 at 6:38

1 Answer 1


Often times when manipulating complex looking sums over multiple indices one can simplify things by introducing indicator functions or some variant of them. In this way we can then let the indices in our summation all range over some nice value, while at the same time preserving our original quantity because when properly defined we can have the indicator functions vanish at all the values we don't want to sum over. For instance using iverson brackets let $[d\mid n]$ take the value $1$ whenever $d$ divides $n$ whereas let it rest at $0$ otherwise. Then if we have two arbitrary arithmetic functions say $f,g:\mathbb{N}\to \mathbb{C}$ we can calculate a sum $\sum_{n\leq x}\left(\sum_{d\mid n}f(d)\right)g(n)$ as follows:

$$\sum_{n\leq x}\left(\sum_{d\mid n}f(d)\right)g(n)=\sum_{n\leq x}\left(\sum_{d\leq x}f(d)[d\mid n]\right)g(n)=\sum_{d\leq x}f(d)\sum_{n\leq x}g(n)[d\mid n]\\=\sum_{d\leq x}f(d)\left(g(d)+g(2d)+g(3d)+\ldots +g\left(d\left\lfloor\frac{x}{d}\right\rfloor\right)\right)=\sum_{d\leq x}f(d)\left(\sum_{k\leq \frac{x}{d}}g(dk)\right)$$

If you spend a little time on your problem, I'm sure you'll get the concept. The same technique can be used for a variety of other arithmetic like convolutions as well.

Edit: If you're still having trouble I found a png of some old notes from hs, just play around with the sums and you should get the intuition. Sorry if I split it up at the bottom, you can alter these sorts of things using techniques like the one here.

Where $f,g,\beta:\mathbb{N}\to \mathbb{C}$ are arbitrary arithmetic functions with any $x,y\in \mathbb{R}$ satisfying $1\leq y\leq x$ for the application of Dirichlet's hyperbola method at $y$ in the second to last sum while for any integers $m,n>1$ the other sums involving Cauchy convolutions and summation by parts hold.

enter image description here

  • $\begingroup$ You're a legend mate thanks heaps. Makes so much more sense and was able to figure it out just using the Indicator function. Cheers $\endgroup$
    – deej
    Commented Sep 1, 2017 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .