How to exactly determine whether a sum of n-th roots of unity is zero

Question

Define the set $R = \{e^{2\pi i k/n} | k=0,1,\ldots,n-1\}$ of $n$-th roots of unity.

Let $S \subseteq R$ be a subset. How can I (algorithmically?) determine whether $\sum_{s\in S} s = 0$?

I'm looking for a general way/algorithm that can be implemented without using a CAS or even arbitrary precision arithmetic.

If we model complex numbers using floating point numbers, we quite quickly run into a problem, as we get non-zero sums that get arbitrarily close to zero as $n$ gets bigger. So if we use floats or doubles we end up making errors due to the limited precision. (When you work with floating point numbers you also cannot really check for equality due to rounding, you can only check whether something is within a given distance.)

Is there a way to do the same with integer arithmetic? (If needed including arbitrarily big integers are acceptable.)

Answer 1

We can solve the more general problem of deciding whether, for coefficients $a_k\in \mathbb Z$ the sum $$\sum_{k=0}^{n-1}a_k\zeta^k=0$$ where $\zeta=e^{2\pi i/n}$. Your problem restricts $a_k$ to $\{0,1\}$. In particular, we can apply the following statement (where "polynomial" always refers to one with rational coefficients):

Let $z$ be an algebraic number and $Q$ be the minimal polynomial of $z$. If, for some other polynomial $P$, we have that $P(z)=0$, then $Q$ divides $P$.

The minimal polynomial of $\zeta$ is the $n^{th}$ cyclotomic polynomial, so one can decide whether this sum is zero by dividing the polynomial $P(x)=\sum_{k=0}^{n-1}a_kx^k$ by the $n^{th}$ cyclotomic polynomial (which may be calculated by various means). Since the cyclotomic polynomials are monic, everything here can be calculated using integer arithmetic.

Note that when $k$ is prime, we will find that $R$ has sum zero, but no subset of it does. I am not sure whether there are more general rules for your restricted problem, but one could investigate using the algorithm and theory suggested above.