Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$\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 Walters Jan 11 '12 at 6:47
1  
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 Walters Jan 11 '12 at 20:32

2 Answers 2

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

enter image description here

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

share|improve this answer
    
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 Walters 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.