Paley graph
In graph theory, a Paley graph of order q is an undirected graph defined on the finite field \mathbb{F}_q, where q is a prime power congruent to 1 modulo 4, with vertices corresponding to the elements of \mathbb{F}_q and an edge between distinct vertices u and v if and only if u - v is a nonzero quadratic residue in \mathbb{F}_q.[1][2] These graphs form an infinite family of strongly regular graphs with parameters (q, (q-1)/2, (q-5)/4, (q-1)/4), meaning each vertex has degree (q-1)/2, adjacent vertices share exactly (q-5)/4 common neighbors, and nonadjacent vertices share (q-1)/4 common neighbors.[1][2] The construction underlying Paley graphs traces back to a 1933 paper by mathematician Raymond Clare Archibald Paley, who used quadratic residues over finite fields to build orthogonal matrices as part of the Paley construction for Hadamard matrices, though he did not explicitly define the graphs.[2] The graphs themselves were introduced in the early 1960s—first by Hans Sachs in 1962 as examples of self-complementary graphs, and independently by Paul Erdős and Alfréd Rényi in 1963 in their work on random graphs—and were retrospectively named "Paley graphs" in the 1970s to honor Paley's foundational contribution.[2] Paley, who died young in a climbing accident at age 26, made significant advances in analysis and number theory, but his finite field techniques proved enduring in combinatorial contexts.[2] Paley graphs exhibit several notable structural properties that make them a cornerstone of algebraic graph theory: they are self-complementary (isomorphic to their complements), vertex-transitive (with automorphism group of order q(q-1)/2), Hamiltonian, and conference graphs, which relate to symmetric designs and block designs in combinatorial design theory.[1][2] Their clique number is known to be \sqrt{q} for q a square (achieved via subfields), and they play a key role in extremal graph theory, including bounds on Ramsey numbers—for instance, the Paley graph of order 17 and its complement are both K_4-free, showing that R(4,4) > 17 and contributing to the establishment that R(4,4) = 18.[1] Beyond pure theory, Paley graphs appear in applications to coding theory, pseudorandomness (as explicit constructions mimicking random graph behaviors), and cryptography, due to their balanced properties derived from finite field arithmetic.[2][3]Construction and Definition
Finite Field Foundation
The Paley graph of order q is constructed over a finite field \mathbb{F}_q, where q is a prime power satisfying q \equiv 1 \pmod{4}.[4] Finite fields \mathbb{F}_q exist uniquely up to isomorphism for every prime power q = p^n, with p prime and n \geq 1, and consist of q elements equipped with addition and multiplication operations that satisfy the field axioms.[4] The condition q \equiv 1 \pmod{4} ensures that -1 is a quadratic residue in \mathbb{F}_q, which is essential for the symmetric properties of the resulting graph.[4] Examples of such fields include the prime field \mathbb{F}_5 \cong \mathbb{Z}/5\mathbb{Z}, which has elements \{0, [1](/page/1), 2, [3](/page/3), 4\} under modular arithmetic, and the extension field \mathbb{F}_9 = \mathrm{GF}(9), constructed as \mathbb{F}_3[\alpha]/(\alpha^2 + [1](/page/1)) where \alpha is a root of the irreducible polynomial x^2 + [1](/page/1) over \mathbb{F}_3.[4] In \mathbb{F}_5, addition and multiplication are performed modulo 5, while in \mathbb{F}_9, elements are pairs (a, b) representing a + b\alpha with arithmetic defined by the field operations.[4] The multiplicative group \mathbb{F}_q^\times of nonzero elements is cyclic of order q-1, generated by a primitive element, and since q \equiv 1 \pmod{4}, the order q-1 is divisible by 4.[4] This cyclicity allows for the identification of quadratic residues as the unique subgroup of index 2 in \mathbb{F}_q^\times, consisting of the squares of nonzero elements.[4] In the Paley graph construction, the vertices are labeled by the elements of \mathbb{F}_q, leveraging the field's addition to define differences between vertices and multiplication to determine structural properties via residues.[4] This field-theoretic labeling provides a natural algebraic framework for the graph's symmetry and regularity.[4] The foundational use of quadratic residues in finite fields for such constructions was introduced by Raymond Paley in his 1933 paper on orthogonal matrices, motivated by the generation of Hadamard matrices.[2] Paley's work, published in the Journal of Mathematics and Physics (vol. 12, pp. 311–320), established the quadratic residue method over \mathbb{F}_q for constructing Hadamard matrices via orthogonal matrices, with direct constructions for q \equiv 3 \pmod{4} (order q+1) and augmented ones for q \equiv 1 \pmod{4} (order $2(q+1)); this method was later adapted for Paley graphs in the case q \equiv 1 \pmod{4}.[2]Quadratic Residue Edges
In the Paley graph of order q, where q is a prime power congruent to 1 modulo 4, the vertices are the elements of the finite field \mathbb{F}_q. An undirected edge exists between distinct vertices x and y if and only if y - x is a nonzero quadratic residue in \mathbb{F}_q. This construction relies on the quadratic residues, as introduced in the work of Raymond Paley, to define the adjacency relation.[5][2] The nonzero quadratic residues in \mathbb{F}_q are precisely the squares z^2 for z \in \mathbb{F}_q \setminus \{0\}. These form the kernel of the quadratic character \chi: \mathbb{F}_q^* \to \{\pm 1\}, making them a subgroup of index 2 in the multiplicative group \mathbb{F}_q^*. Since |\mathbb{F}_q^*| = q-1, there are exactly (q-1)/2 nonzero quadratic residues.[2] The adjacency can be formally described using the quadratic character \chi, which coincides with the Legendre symbol \left( \frac{\cdot}{q} \right) when q is prime and extends naturally to prime powers. Here, \chi(z) = 1 if z is a nonzero quadratic residue, \chi(z) = -1 if z is a quadratic nonresidue, and \chi(0) = 0. An edge joins x and y if \chi(y - x) = 1. The adjacency matrix A satisfies A_{x,y} = 1 if x \neq y and \chi(y - x) = 1, and A_{x,y} = 0 otherwise (including the diagonal). Equivalently, off the diagonal, A_{x,y} = \frac{\chi(y - x) + 1}{2}. The signed matrix with entries \chi(y - x) (for x \neq y) is the Jacobsthal matrix associated to the Paley construction.[2] The relation is symmetric, ensuring the graph is undirected, because \chi(-1) = 1 if and only if q \equiv 1 \pmod{4}; thus, if y - x is a quadratic residue, so is its negative x - y. No loops occur, as \chi(0) = 0 \neq 1.[2]Examples and Small Cases
Orders up to 17
The Paley graph of order 5 is constructed over the finite field GF(5) with vertices labeled 0 through 4. Two vertices are adjacent if their difference is a nonzero quadratic residue modulo 5, which are 1 and 4 (equivalent to ±1 modulo 5). This results in the cycle graph C_5 with edges 0–1, 1–2, 2–3, 3–4, and 4–0.[4] The adjacency matrix for the Paley graph of order 5, with rows and columns ordered 0 to 4, is:| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 0 | 1 | 0 |