Computing sums of primitive roots

It, and other pictures like it, express the fact that for a given $n$ , if we take the primitive roots for each of the divisors of $n$ , together they make up exactly the set of all $n$ th roots of unity. The above picture is for the specific case of $n=12$ : the $12$ th roots of unity (the dots on the bottom circle) are composed of the primitive roots for $n=1$ , $2$ , $3$ , $4$ , $6$ , and $12$ (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 $S(n)$ for the sum of all the primitive $n$ th roots: in my previous post we worked out $S(n)$ for certain $n$ 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 $n$ th roots of unity is zero, except when $n=1$ in which case the sum is $1$ . Putting all of this together,

$\displaystyle \sum_{0 \leq k < n} \omega_n^k = \sum_{d \mid n} S(d) = \begin{cases}1 \qquad n=1 \\ 0 \qquad n>1\end{cases}$

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

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

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

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

$\displaystyle \begin{array}{c|rrrrrrrrrrrrrrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline S(n) & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 & -1 & 1 & 1 & 0 & -1 & 0 & -1 & 0 \end{array}$

For example, to fill in $S(20)$ we compute $S(1) + S(2) + S(4) + S(5) + S(10) + S(20) = 1 - 1 + 0 - 1 + 1 + S(20) = 0$ and hence $S(20) = 0$ .

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

About Brent

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

View all posts by Brent →

9 Responses to Computing sums of primitive roots

Michael Paul Goldenberg says:

November 16, 2016 at 5:40 am

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.
- Brent says:
  
  November 16, 2016 at 4:36 pm
  
  Good observations! I can confirm that you have started down an interesting path…
  - Michael Paul Goldenberg says:
    
    November 16, 2016 at 4:44 pm
    
    Your reply was just about simultaneous with my next set of observations. 🙂 Thanks for confirming the first ones.
Michael Paul Goldenberg says:

November 16, 2016 at 4:43 pm

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. 🙂
- Brent says:
  
  November 16, 2016 at 6:46 pm
  
  Nice work!
Michael Paul Goldenberg says:

November 19, 2016 at 8:58 am

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?
- Brent says:
  
  November 21, 2016 at 9:33 pm
  
  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

Comments are closed.