3
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Could you please provide more details, e.g. examples of Mathematica code or graphs that CayleyGraph doesn’t support? $\endgroup$
    – Victor K.
    Jan 16, 2023 at 20:51
  • $\begingroup$ 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 $\endgroup$
    – sra
    Jan 16, 2023 at 20:56
  • $\begingroup$ It doesn’t have to be a named group though, does it? Does this help: reference.wolfram.com/language/tutorial/PermutationGroups.html? $\endgroup$
    – Victor K.
    Jan 16, 2023 at 21:02
  • $\begingroup$ It might. But how do I construct an SL group in Mathematica? $\endgroup$
    – sra
    Jan 16, 2023 at 21:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – A. Kato
    Jan 17, 2023 at 6:47

2 Answers 2

2
$\begingroup$

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]]

enter image description here

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

GraphPlot3D[g]

enter image description here

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – user64494
    Jun 19, 2023 at 13:15
0
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thank you. Isn't the determinant of every element of sl[2,3] = 1? $\endgroup$
    – sra
    Jan 19, 2023 at 5:56
  • $\begingroup$ @psimeson: Yes, of course. This is guaranteed by Mod[Det[#], p] == 1. $\endgroup$
    – user64494
    Jan 19, 2023 at 5:59
  • $\begingroup$ 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} $\endgroup$
    – sra
    Jan 19, 2023 at 6:02
  • $\begingroup$ @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. $\endgroup$
    – user64494
    Jan 19, 2023 at 6:06
  • 1
    $\begingroup$ See Wiki to this end as a first reading. $\endgroup$
    – user64494
    Feb 18, 2023 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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