# Polyhedra from Cayley Graphs

I was playing around with the Cayley graphs for some simple groups today and stumbled across something interesting, but can't quite figure out if there's something deeper going on. Here's what I did:

Consider the multiplicative group of the integers mod p, $\mathbb{Z}_{p}^{\times}$. We can generate $\mathbb{Z}_{p}^{\times}$ with any single element and obtain a simple Cayley graph. However, consider the Cayley graph generated by all primes strictly less than p, i.e. let $S=\{[a]: a \text{ is prime and } a<p\}$ and let $\Gamma_{p}$ be the Cayley graph $\Gamma_{p} = (\mathbb{Z}_{p}^{\times}, S)$.

Here is the Mathematica code I was using to generate some of the graphs:

plotGraph[p_] := (
primesN := Table[Prime[n], {n, PrimePi[p] - 1}]; (*get generators*)

(*function to compute adjacency matrix entries*)
f[i_, j_] := (If[MemberQ[Mod[i*primesN, p], j], Return[1]];0);

M := Array[f, {p - 1, p - 1}]; (*create adjacency matrix*)
MatrixForm[M]
GraphPlot3D[M, VertexLabeling -> True]
)


I noticed that if n is not prime (and of course, $\mathbb{Z}_{n}-\{[0]\}$ is not a group), then the graph $\Gamma_{n}$ is really not interesting. However, when p is prime, the graphs have some nice structure. p=2 is a point, p=3 is a line segment, p=5 a square, p=7 an octahedron, p=11 looks like a pentagonal antiprism. However, I don't know if there is a pattern, or basically what's going on here. Does anyone have any insight?

-
$\mathbb Z_p^\times$ is always a group (that notation is understood by most people to mean «the set of invertible elements $\mod p$») You probably mean the set of non-zero elements, or something. – Mariano Suárez-Alvarez Jan 11 '12 at 6:43
Kind of beside the point, fixed anyways. – Jackson Jan 11 '12 at 6:47
Correctness is never beside the point (and you did not fix it :) ) – Mariano Suárez-Alvarez Jan 11 '12 at 6:53
Ah! I had assumed $\mathbb{Z}_{n}^{\times}$ was just different notation for the set of nonzero elements. Now it's fixed. – Jackson Jan 11 '12 at 20:32

This does not exactly answer but... there's pictures! :)

I changed to code into

Needs["TetGenLink"];
plot[p_] := Module[{pts},
pts = First@ Cases[
GraphPlot3D@ Flatten@
Table[i -> Mod[i q, p],
{i, 1, p - 1}, {q, Prime[Range[PrimePi[p] - 1]]}],
Pattern[s, Rule[VertexCoordinateRules, c_]] :> c, Infinity];
Graphics3D@ GraphicsComplex[pts, Polygon[TetGenConvexHull[pts]]]
]


Now saying

GraphicsGrid[Partition[plot /@ Prime[Range[3, 11]], 3]]


gets us

TetGenConvexHull` only gets us a triangulation of the convex hull, so there are edges in these pictures that are only apparent.

-
Nice! Yea, the extra lines makes it a little confusing to pick out the edges, but it's nice to see some of the higher order polyhedra. – Jackson Jan 11 '12 at 19:59
Keep in mind that the position of the vertices in these pictures is fixed by Mma in some more or less random way---other arrangements different from the one picked might have more symmetry. – Mariano Suárez-Alvarez Jan 11 '12 at 20:01

You will always get a vertex-transitive graph with $p - 1$ vertices, where the number of edges at each vertex is the cardinality of $S \cup S^{-1}$ (where $S^{-1}$ means the set of inverses of the generators in $S$.)

For the case $p = 5$, we have $[2]^{-1} = [3]$, so we have a 2-regular graph on 4 vertices, which is a square. For $p = 7$, we have $[2]^{-1} = [4]$, while $[3]^{-1} = [5]$, so $S \cup S^{-1} = \{[2],[3],[4],[5]\}$ and we have a 4-regular graph on 6 vertices. Moreover, since $[2][5] = [3]$, etc., we get many 3-cycles (triangles).

For the small numbers, these considerations force the results you give. However, for $p = 11$ the graph is 8-regular, so it's not actually a pentagonal antiprism. In fact, the graph is not planar, so it's not a polyhedron (but it can probably be drawn in the pentagonal antiprism with extra diagonals.) And for $p > 13$, the graphs are at least 6-regular, hence cannot be planar (so are not the graphs of polyhedra.) The same is actually true for $p = 13$, where $S \cup S^{-1} = \{[2],[3],[5],[6],[7],[8],[9],[11]\}$.

I don't think it's true that it's less interesting when $p$ is not prime. In this case, the number of vertices is $\phi(p)$, the cardinality of $\mathbb{Z}_p^\times$, and you will need to restrict your set $S$ to the primes which don't divide $p$. For $p = 4$ or $p = 6$ you get a line segment, same as with $p=3$; with $p = 8$ you get a tetrahedron; with $p = 9$ you get an octahedron; $p = 10$ gives a square, etc.

-