I'm working out of Godsil and Royle's Algebraic Graph Theory text, and I'm trying to understand Paley graphs. My book gives as a definition the following:

Let $q$ be a prime power such that $q\equiv 1\pmod{4}$. The Paley graph $P(q)$ has as vertex set the elements of the finite field $GF(q)$, with two vertices adjacent if and only if their difference is a nonzero square in $GF(q)$.

In case it isn't clear, $GF(q)=\mathbb{F}_q$. My text also includes the following sentence:

The congruence condition on $q$ implies that $-1$ is a square in $GF(q)$, and hence the graph is undirected.

My book doesn't provide any illustrations of Paley graphs so I tried to contruct a couple. First, I made $P(5)\cong C_5$. This is very straightforward and didn't present any problems. Next, I tried to construct $P(9)$ and here I just don't understand what to do.

First, I computed the nonzero squares mod $9$. There are only three: $1,4,7$. Specifically $$ (\pm 1)^2\equiv1 \qquad 2^2\equiv 4\equiv 7^2 \qquad 4^2\equiv7\equiv5^2 \pmod{4} $$ First, notice that by the extra note, $8$ should be a square mod $9$, but that isn't the case. I have determined that, by Fermat's Little Theorem, if $q$ is a prime number rather than a prime power, this would be true. Is my text just incorrect or am I misunderstanding something?

Second, I tried to construct the actual graph. I started by labeling $9$ vertices $0,1,\dotsc,8$ in a circle. Then because $1$ is a square, I added edges around the entire thing, making a $9$-cycle. Because a Paley graph is supposed to be strongly regular, by examining the edges of a single vertex, I gain information about every other vertex. So consider the vertex labeled $0$. From the above, there are edges $01$ and $80$. Because $4$ is a square, there should be edges $04$ and $05$. Because $7$ is a square, there should be edges $02$ and $07$. Similarly, there should be $4$ edges for each vertex in addition to the $2$ that come from $1$ being a square, each corresponding to adding or subtracting $4$ or $7$.

However, the actual Paley graph on $9$ vertices is highly asymmetric. There's an image here (I'm not sure how to add an image to a post). http://mathworld.wolfram.com/PaleyGraph.html Labeling the northernmost vertex $0$ and labeling each consecutive vertex counterclockwise shows that there are edges $01, 08, 02$, and $04$ all incident with vertex $0$. But notice that there is not an edge $24$. However, $2-4\equiv 7\pmod{9}$ which is a square mod $9$. There are numerous additional edges that are not present, but should be according to the definition. Furthermore, $8$ is not a square mod $9$. so how can this graph be undirected? I've been playing with this for a long time and I just don't understand how the image on the link given corresponds to the $P(9)$ given by the definition. Can anyone offer any help?


The field with 9 elements is not the field with elements $0, 1, 2, \ldots, 8$ mod 9. In fact, that is not a field as fields have no zero divisors and $6^2 = 36$ is congruent to 0 mod 9. You are assuming it is and thus most of your calculations are wrong. See this, for example.

Thus, start with the field of 3 elements, $\{0, 1, 2\}$. Since 2 is not a square, we know that $x^2 + 1 = 0$ has no solutions in this field. So, let $x$ be a solution to this equation in this field. Since nothing in $\mathbb{F}_3$ is a solution to $x^2 + 1 = 0$, this $x$ must be in some bigger field. Since the degree of the polynomial is 2, the field has $3^2$ elements. And, in fact the 9 elements are $\{0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2\}$ where $3 \equiv 0$ and $x^2 + 1 \equiv 0$.

As $x^2 + 1 \equiv 0$, we know that $x^2 \equiv -1$. This shows that $-1$ is indeed a square!

Lastly, I would like to point out that the pictures you give for the Paley graphs show that the graphs are in fact highly symmetric, not asymmetric. In fact, the Paley graphs are vertex transitive and strongly regular, both of which are ways to say that the graphs are pretty symmetric.

  • $\begingroup$ Thank you so much. My professor and I were pounding our heads against a wall for about an hour an a half yesterday trying to understand this. I guess we both forgot that $\mathbb{F}_p\cong \mathbb{Z}_p\Leftrightarrow p$ is prime, not a power of a prime. Again, thanks. $\endgroup$ – chris Dec 6 '12 at 18:28
  • $\begingroup$ @chris Hehe, yea, it happens to all of us sometimes, especially when you are studying complex subjects that involve the intermingling of several different subjects, like algebraic graph theory. $\endgroup$ – Graphth Dec 6 '12 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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