Roots of unity (group theory)

Question

Let $p$ be a prime and $T$ the set of ALL $n$-th roots of unity $\zeta_n \pmod p$: $T=[1, \zeta_n, \zeta_n^2, \zeta_n^3...\zeta_n^{n-1}]$ ($n$ is odd). Find the smallest (non-empty) subset (in length) $S ⊂ T$ such that the sum of all elements in $S$ is $0\pmod p$. I suspect that the quickest way to accomplish this is the LLL Algorithm and hope that the coefficients of $\zeta_n^k$ are either $0$ or $1$ but I'm not sure.

Answer 1

I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.

You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^\times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $\zeta_n$.

From here on, everything seems to take place in the subgroup $\langle g^d\rangle=T\subset k^\times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^\times$ form a (cyclic) subgroup of $T$ of order $m$, and if $\xi$ is a generator of this group, then $\{1,\xi,\cdots\xi^{m-1}\}$ form one of your sets $S$, since their sum is $(\xi^m-1)/(\xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.

Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.

EDIT — Amendment:

Your single example of elements of $\Bbb F_{53}$, $1+24+28\equiv0\pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $\Bbb F_p$ was immaterial to the problem.

Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $\Bbb F_p^\times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:

Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $\Bbb F_p$, namely $\{1,a,-a-1\}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $\Bbb F_p^\times$, even with your restriction that this subgroup should be of odd order.

Unfortunately, I have no idea and no tools in my kit that could help you with this problem.