# The Paley Graph with $9$ vertices

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!
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. – chris Dec 6 '12 at 18:28