Remember this picture?

It, and other pictures like it, express the fact that for a given , if we take the primitive roots for each of the divisors of , together they make up exactly the set of all th roots of unity. The above picture is for the specific case of : the th roots of unity (the dots on the bottom circle) are composed of the primitive roots for , , , , , and (the dots on each of the top circles). I proved this in another post.

Of course, if two *sets* of complex numbers are the same, then their *sums* must also be the same. Let’s write for the sum of all the *primitive* th roots: in my previous post we worked out for certain but weren’t sure how to compute it in other cases. Well, today that’s going to change!

We already know by symmetry that the sum of *all* the th roots of unity is zero, except when in which case the sum is . Putting all of this together,

That is, the sum of all th roots of unity is the same as summing the primitive roots, , for each divisor of . (The notation means evenly divides , so the summation symbol with underneath means we are summing over all divisors of .)

So what have we gained? Well, we can use this equation “backwards” to compute values for !

- We already know .
- When , the equation tells us that , so it must be that . (Of course we already knew that too.)
- When , we have (note that is not included since is not a divisor of ), so as well.
- , so , which also checks out with our previous knowledge.
- Recall that was the first value we were unsure about. Well, , so must be .

And so on. Since each value of can be computed in this way once we know for all the divisors of (which are smaller than ), we can continue filling in a table of values of like this forever.

For example, to fill in we compute and hence .

Do you notice any patterns? It is not too hard to see that must always be an integer (why?), but so far it has always been either , , or ; will it always be one of those three values? Before my next post you might like to try extending the table of values for further and exploring these questions yourself!

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Quick observation: S(p) will be -1 for all primes, since S(1) = 1 and p is divisible only by 1 and p. So given that S(1) + S(p) = 0, it follows that S(p) must equal -1.

If n = p*q with p,q prime, S(1)+ S(p) + S(q) + S(n) = 0

so 1 + -1 + -1 + S(n) = 0 and thus S(n) = 1

It follows that S(n) = 1 for n = the product of any 2 primes.

From that, I expect some sort of generalization follows for n = the product of k primes. If I weren’t finishing breakfast before rushing to work, I’d try to work that out and see what else might follow from it. My hypothesis is that S(n) can’t escape the set {-1,0,1} but I’m not at all sure yet.

Good observations! I can confirm that you have started down an interesting path…

Your reply was just about simultaneous with my next set of observations. 🙂 Thanks for confirming the first ones.

Picking up from my previous comment: it looks like for n = pqr, all primes, S(n) = -1. Again, we have S(1) = 1, S(p) for any prime = -1, S(pq) = 1. For 3 primes, we get S(1) + 3*S(p) + 3*S(a*b) [pairwise prime products] + S(pqr) = 0. Thus S(pqr) = -(1 + -3 + 3) = -1.

Building on this, S(pqrs) = 1 since it is equal to -[1 + 4(-1) + 6(1) + 4(-1)] = -(-8+7) = -(-1) = 1.

The coefficients are coming from the binomial expansion, hence represent rows of Pascal’s triangle. It shouldn’t be hard to write a general formula; if I had some coffee and my neck weren’t tight as a drum from sitting at a desk much of the day, I could likely whip one up. Maybe some interested reader will beat me to the punch. 🙂

Nice work!

I think there’s a not difficult way to write a formula for S(n) with an inductive proof. The connection to Pascal’s Triangle hadn’t occurred to me until I saw it, and then it made sense. Grabbing different groups via (n choose k) was suddenly obvious, and then you’re just multiplying those coefficients by 1 or -1. Either all the terms other than S(n) cancel to 1 or to -1, making S(n) the additive inverse of the sum of the other terms.

So may I assume this leads somewhere(s) deeper?

Your assumption would be correct! If you are impatient you can read http://mathworld.wolfram.com/MoebiusFunction.html (I’d link to Wikipedia as well but it seems to be down for me at the moment…)

Pingback: The Möbius function | The Math Less Traveled

Pingback: The Möbius function proof, part 1 | The Math Less Traveled