For a prime $p$, let $S$ be the set of all $p$-roots of unity in the complex plane. Now, consider the sum, $W(R)$ of the members of a set $R$ which is a proper subset of $S$. I suspect that $R \ne R'$ implies $W(R) \ne W(R')$. Is this true?
I further ask whether there is sub-exponential method for calculating $R$ from $W(R)$?
This article discusses a related problem.
This problem can be thought of as a diophantine equation over the roots of unity.
The part about $W(R) \neq W(R')$ when $R \neq R'$ are proper subsets of $S$ is true:
All the $p$-th roots of unity are powers of $\omega := e^{2 \pi i / p}$, and when $p$ is prime, the minimal polynomial of $\omega$ is well-known to be $f(x):=x^{p-1} + x^{p-2} + \cdots + 1$. A relation of the form $W(R) = W(R')$ would lead to $\omega$ satisfying the polynomial equation $g(x):=\sum_{j \in J} x^j - \sum_{j \in J'} x^j = 0$ where $J$ is the subset of $\{0,1,\ldots,p-1\}$ defined by $R = \{ \omega^j : j \in J \}$ (and $J'$ is defined analogously in terms of $R'$). Since $g(x)$ is either $0$ or a polynomial with leading coefficient $\pm 1$ of degree at most $p-1$, $\omega$ can only satisfy $g(\omega)=0$ if $g(x)=0$ or $g(x) = \pm f(x)$. If $g(x)=0$, then $R = R'$; if $g(x) = f(x)$ then $R =S, R' = \emptyset$; if $g(x) = -f(x)$, then $R=\emptyset, R'=S$.
I don't know about the algorithm, but I can tell you that to get answers about that part you should specify what format you want the input in. For example, the input could be a floating point approximation to $W(R)$,
(For that my instinct is to use the LLL algorithm to guess an integer linear combination of $W(R), 1, \omega, \omega^2, \ldots, \omega^{p-2}$, and hope the coefficients of the $\omega^j$ turn out to be $0$ or $1$. I don't know if that works, and as Gerry Myerson points out that strategy can get confused by small root sums.)
