In my previous post, we saw that adding up all the complex th roots of unity always yields zero (unless , in which case the sum is ). Intuitively, this is because the roots are symmetrically distributed around the unit circle, so their contributions to the sum all cancel out.

Today I want to consider the question: what happens when we add up only the *primitive* th roots of unity? Recall that a *primitive* th root is one which is not also an th root for some smaller . As points on the unit circle, the primitive roots correspond to the spokes which are relatively prime to .

In some cases we clearly still get zero, again because of symmetry. Shown below are , , , and :

For we of course get again:

For the only primitive root is , so the sum is clearly . It’s not too hard to see that the sum of primitive roots for will also be :

Why is that? Well, when , the only root that is not a primitive root is , so if we subtract out from the sum of *all* roots, we are left with the sum of the remaining, primitive roots. But we know the sum of all roots is zero, and hence the sum of the remaining primitive roots must be . In fact, this is not specific to ; the same argument applies to any prime number. When is prime, every root is primitive except for itself, so in order for the sum of all the roots to be zero, the sum of all the primitive roots must be .

However, this still leaves other values of where it is not obvious what we will get as the sum of primitive roots. For example, here are , , and :

Let’s look at . The primitive roots have reflection symmetry across the -axis, so their sum must lie somewhere on the -axis (since their “up-down pulls” cancel out). Since they are leaning more in the positive direction, the sum will be bigger than zero. But how much bigger? Just thinking about the components, we are adding together irrational numbers involving things like the cosine of , so maybe we just get some weird irrational sum like ? It seems plausible, but actually, we don’t: we instead get a sum of… exactly ! And the sums for and … are also exactly . Something strange is going on.

But you don’t have to take my word for it! Next time we’ll put together what we know about the sum of all roots and how the set of th roots is made up of primitive roots for the divisors of to compute sums of primitive roots.

##
About Brent

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

You are asking about coefficients of cyclotomic polynomials, specifically, the coefficient of the second highest power of x in $\Phi_n(x)$. Gauss showed it’s always an integer, wikipedia said coefficients can go arbitrarily high… but the coefficient of the second highest power?

Both Wikipedia and Wolfram Mathworld give a formula for $\Phi_n(x)$ in terms of Mobius functions, which boils down to a ratio of two products of $x^k – 1$ for various (different collections of) factors $k$ of $n$. The numerator and denominator are therefore of the form $x^p + a x^{p-1} + …$ and $x^q + b x^{q-1} + …$, with at most one of $a$ and $b$ being nonzero, and that nonzero coefficient being -1 or 1. The ratio, $\Phi_n (x)$, therefore has second highest coefficient either -1, 1 or 0.

You could dig further into the Mobius formula to predict which sums of primitive roots will give each of the three possible values -1, 0 or 1.

Yes, you’re way ahead of me. =) I will get around to discussing the Mobius function in a few more posts!

😀

Pingback: Computing sums of primitive roots | The Math Less Traveled