Cayley Graphs of Z/nZ with invertible adjacency matrices Let $G = \mathbb Z/n\mathbb Z$ and let $\emptyset\neq S\subseteq G$.  Then the Cayley digraph of $G$ with respect to $S$ has vertex set $G$ and directed edges of the form $g\rightarrow gs$ with $s\in S$.  I don't assume $S$ is symmetric or that $S$ generates $G$.  Let $A_S$ be the adjacency matrix of the corresponding Cayley digraph.  Let us say $S$ is good if $A_S$ is invertible.
Define $p_S(x)=\sum_{k\in S}x^k$ where I identify $G$ with $\lbrace 0,\ldots, n-1\rbrace$ in the usual way.  Discrete Fourier analysis says $S$ is good iff $p_S$ has no root which is an $n^{th}$-root of unity, i.e., $p_S$ is relatively prime to $x^n-1$.  Alternatively, $S$ is good if and only if $\sum_{s\in S}s$ is an invertible element of the group ring $\mathbb CG= \mathbb C[x]/(x^n-1)$.
Obviously if $n$ is prime, then all proper non-empty subsets are good since the cyclotomic polynomial is $p_G$.  On the other hand, if $S$ is a proper subgroup of $G$, then it is easy to see that $S$ is not good.  Let us say that for $S,T\subseteq G$ the sum $S+T$ is unambiguous if each element of $S+T$ can uniquely be expressed as a sum of an element of $S$ with an element of $T$. For example, a coset $g+H$ is unambiguous. Clearly, if $S+T$ is unambiguous, then $p_{S+T}=p_Sp_T\bmod (x^n-1)$ and so if either $S$ or $T$ is bad, then so is $S+T$.


Question. Is there some nice characterization of bad subsets of $G$ as, say, built from proper subgroups via unambiguous sums and perhaps some other operations?


 A: I don't think there is any nice characterization for this problem.
$1+x+x^{7}+x^{13}+x^{19}+x^{20}$ isn't relatively prime to $x^{30}-1$ despite not being characterized by any sort of reasonable construction.
It comes from adding two cosets and subtracting one, like so: $(1+x^{10}+x^{20})+(x+x^7+x^{13}+x^{19}+x^{25})-(x^{10}+x^{25})$. You can't get it by just combining cosets. Choosing elements from cosets doesn't help because that would be the wrong elementary cyclotomic polynomial.
This is equivalent to the problem: When does a (multi)set of roots of unity sum to $0$? You shouldn't expect a particularly good answer. Compare it to the problem "when does a set of complex numbers of norm $1$ sum to $0$", which just asks you to find polygons of side length $1$. There are quite a lot of these.
This problem is more tractable when you can mandate that the size of the set is small. Then you can give an explicit construction for all bad sets. But as far as several graduate students who worked on the problem in the second form can tell, there is not any construction that works in general that is better than "take multiples of an elementary cyclotomic polynomial that have only $0$ and $1$ for coefficients."
