Cayley for SL group

In this paper, they are using an expander graph. It seems like it's just a Cayley graph for $$SL(2,Z_p)$$, where $$P$$ is a prime number.

How do I go about making a Cayley graph as shown in the first of the algorithm using mathematica. Mathematica CayleyGraph seems to only support certain kinds of graph.

• Could you please provide more details, e.g. examples of Mathematica code or graphs that CayleyGraph doesn’t support? Jan 16, 2023 at 20:51
• CayleyGraph function takes a group. However, mathematica doesn't have (or I couldn't find) Special Linear (SL) group : reference.wolfram.com/language/guide/NamedGroups.html
– sra
Jan 16, 2023 at 20:56
• It doesn’t have to be a named group though, does it? Does this help: reference.wolfram.com/language/tutorial/PermutationGroups.html? Jan 16, 2023 at 21:02
• It might. But how do I construct an SL group in Mathematica?
– sra
Jan 16, 2023 at 21:12
• Cayley graph is determined by the presentation (generators + relations) of the group; two different presentation of the same group usually gives non-isomorphic Cayley graphs. So you need to specify a presentation, not just the group. Jan 17, 2023 at 6:47

Generating the Cayley graph for $$SL_2(\mathbb{Z}_3)$$ can be done by brute force. As you point outCayleyGraph does special cases with nice structure.

For what its worth, here is a brute force way for $$SL_2(\mathbb{Z}_3)$$.

If I have made errors (conceptual or otherwise) I will happily delete.

The elements of the group

mat = Select[Mod[Det@#, 3] == 1 &][
Partition[#, 2] & /@ Tuples[Range[0, 2], 4]];


Some vertex labeling functions

rule = Thread[Range[24] -> mat];
irule = Reverse /@ rule;


The generators for the group

s = {{0, 2}, {1, 0}};
t = {{1, 1}, {0, 1}};


Note s is order 4 and t is order 3.

Creating Cayley graph

def[u_] := DirectedEdge @@@ Partition[u, 2, 1]
tup = Tuples[{s, t}, 7];
orb = FoldList[Mod[#1 . #2, 3] &, #] /. irule & /@ tup;
g = Union[Join @@ (def /@ orb)];


Visualizing the graph

HighlightGraph[g,
Join @@ {Style[#, Green] & /@ FindCycle[g, {4}, All],
Style[#, Red] & /@ FindCycle[g, {3}, All]},
VertexLabels -> Thread[Range[24] -> MatrixForm /@ mat]]


The green arrows are the action of s and the red arrows actions of t.

GraphPlot3D[g]


• A good code is a commented code. Your construction of the Cayley graph is very poorly commented. For example, from where are the generators known? I think the construction is done by hand with Mathematica as a pen Jun 19, 2023 at 13:15

Too long for a comment. The $$SL(2,Z_p)$$ group can be created as follows. This is the set

sl[2, p_] :=  Select[Partition[Partition[Flatten[Table[{{a, b}, {c, d}}, {a, 0, p - 1}, {b, 0, p - 1}, {c,
0, p - 1}, {d, 0, p - 1}]], 2], 2], Mod[Det[#], p] == 1 &]


with the multiplication defined by Mod[k.n],p]. For example,

sl[2, 3]


{{0, 1}, {2, 0}}, {{0, 1}, {2, 1}}, {{0, 1}, {2, 2}}, {{0, 2}, {1, 0}}, {{0, 2}, {1, 1}}, {{0, 2}, {1, 2}}, {{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 0}, {2, 1}}, {{1, 1}, {0, 1}}, {{1, 1}, {1, 2}}, {{1, 1}, {2, 0}}, {{1, 2}, {0, 1}}, {{1, 2}, {1, 0}}, {{1, 2}, {2, 2}}, {{2, 0}, {0, 2}}, {{2, 0}, {1, 2}}, {{2, 0}, {2, 2}}, {{2, 1}, {0, 2}}, {{2, 1}, {1, 1}}, {{2, 1}, {2, 0}}, {{2, 2}, {0, 2}}, {{2, 2}, {1, 0}}, {{2, 2}, {2, 1}}}

and

Mod[ {{1, 2}, {2, 2}}. {{2, 0}, {0, 2}},3]


{{2, 1}, {1, 1}}

Its Cayley graph is huge and unuseful for big values of p. In my opinion (and not only in my one) most of modern mathematics is useless scholasticism.

• Thank you. Isn't the determinant of every element of sl[2,3] = 1?
– sra
Jan 19, 2023 at 5:56
• @psimeson: Yes, of course. This is guaranteed by Mod[Det[#], p] == 1. Jan 19, 2023 at 5:59
• But if I do g= sl[2, 3] and Map[Det, g], I get {-2, -2, -2, -2, -2, -2, 1, 1, 1, 1, 1, -2, 1, -2, -2, 4, 4, 4, 4, 1, \ -2, 4, -2, -2}
– sra
Jan 19, 2023 at 6:02
• @psimeson: Think of Mod[Map[Det, sl[2,3]],3] which results in {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}. Don't hesitate to ask for further explanation in need. Jan 19, 2023 at 6:06
• See Wiki to this end as a first reading. Feb 18, 2023 at 10:16