Paley graphs in Sage

Let q be a prime power such that q\equiv 1 \pmod 4. Note that this implies that the unique finite field of order q, GF(q), has a square root of -1. Now let V=GF(q) and

E = \{(a,b)\in V\times V\ |\ a-b\in GF(q)^2\}.
By hypothesis, (a,b)\in E if and only if (b,a)\in E. By definition G = (V, E) is the Paley graph of order q.

Paley was a brilliant mathematician who died tragically at the age of 26. Paley graphs are one of the many spin-offs of his work. The following facts are known about them.

  1. The eigenvalues of Paley graphs are \frac{q-1}{2} (with multiplicity 1) and
    \frac{-1 \pm \sqrt{q}}{2} (both with multiplicity \frac{q-1}{2}).
  2. It is known that a Paley graph is a Ramanujan graph.
  3. It is known that the family of Paley graphs of prime order is a vertex expander graph family.
  4. If q=p^r, where p is prime, then Aut(G) has order rq(q-1)/2.

Here is Sage code for the Paley graph (thanks to Chris Godsil, see [GB]):

def Paley(q):
    K = GF(q)
    return Graph([K, lambda i,j: i != j and (i-j).is_square()])

(Replace “K” by “K.\langle a\rangle” above; I was having trouble rendering it in html.) Below is an example.

sage: X = Paley(13)
sage: X.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: X.is_vertex_transitive()
True
sage: X.degree_sequence()
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
sage: X.spectrum()
[6, 1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?]
sage: G = X.automorphism_group()
sage: G.cardinality()
78

We see that this Paley graph is regular of degree 6, it has only three distinct eigenvalues, and its automorphism group is order 13\cdot 12/2 = 78.

Here is an animation of this Paley graph:

The frames in this animation were constructed one-at-a-time by deleting an edge and plotting the new graph.

Here is an animation of the Paley graph of order 17:

The frames in this animation were constructed using a Python script:

X = Paley(17)
E = X.edges()
N = len(E)
EC = X.eulerian_circuit()
for i in range(N):
    X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%i))+".png")
    X.delete_edge(EC[i])
X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%N))+".png")

Instead of removing the frames “by hand” they are removed according to their occurrence in a Eulerian circuit of the graph.

Here is an animation of the Paley graph of order 29:

[GB] Chris Godsil and Rob Beezer, Explorations in Algebraic Graph Theory with Sage, 2012, in preparation.

One thought on “Paley graphs in Sage

  1. Pingback: Carnival of Mathematics #101: Prime Numbered Special Edition | The Aperiodical

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s