# 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?

• I think it is more likely that there is a characterization of all bad subsets of $G$, because a random element of this sort of ring is invertible, so you might expect a random subset to be good with high probability. For instance one can construct bad subsets by choosing the same number of elements from each residue class mod $p$, with $p$ dividing $n$, or by taking a union of cosets of a nontrivial proper subgroup. – Will Sawin Jun 6 '12 at 20:18
• Or more generally, any set where each residue class mod $b$ that has the same residue mod $a$ has the same number of elements, for $a|b|n$ and $a<b$, This characterization is complete for all prime powers and $n=6$. – Will Sawin Jun 6 '12 at 20:27
• Characterizing bad is really what I want. I think all the bad examples you mention one from unambiguous sums and subgroups. – Benjamin Steinberg Jun 6 '12 at 21:44
• Do they? $x+1$ divides $x^n-1$ for $n$ even. i don't see how that comes from proper subgroups and unambiguous sums. – Will Sawin Jun 6 '12 at 22:42
• Sorry, I spoke to quickly. I should read comments more carefully. – Benjamin Steinberg Jun 6 '12 at 23:27

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."

• Concerning sets of roots of unity summing to zero, reference should be made to Conway and Jones, Trigonometric Diophantine equations (On vanishing sums of roots of unity), Acta Arith. 30 (1976), no. 3, 229–240, MR0422149 (54 #10141). – Gerry Myerson Jun 7 '12 at 5:10
• So this is one of the ones where you can reduce it to an open research question, which has had multiple papers written about it, which is never very satisfying, but is pretty clearly the best you can do without writing another paper. – Will Sawin Jun 7 '12 at 6:16
• Thanks Will for thinking about this. Gerry, I will look at Conway's paper. – Benjamin Steinberg Jun 7 '12 at 12:13