Let be a prime power such that . Note that this implies that the unique finite field of order , , has a square root of . Now let and

By hypothesis, if and only if . By definition is the **Paley graph** of order .

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.

- The eigenvalues of Paley graphs are (with multiplicity ) and

(both with multiplicity ). - It is known that a Paley graph is a Ramanujan graph.
- It is known that the family of Paley graphs of prime order is a vertex expander graph family.
- If , where is prime, then has order .

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 “” 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 , it has only three distinct eigenvalues, and its automorphism group is order .

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 :

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 :

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