In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, and specifically graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, Paley graphs, named after Raymond Paley

Raymond Paley

Raymond Edward Alan Christopher Paley was an English mathematician. Paley was born in Bournemouth, England. He was educated at Eton. From there he entered Trinity College, Cambridge where he showed himself the most brilliant student among a remarkable collection of fellow undergraduates...

, are dense

Dense graph

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...

 undirected graphs constructed from the members of a suitable finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

 by connecting pairs of elements that differ in a quadratic residue. The Paley graphs form an infinite family of conference graph

Conference graph

In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, and It is the graph associated with a symmetric conference matrix, and consequently its order v must be 1 and a sum of two squares....

s, which yield an infinite family of symmetric conference matrices

Conference matrix

In mathematics, a conference matrix is a square matrix C with 0 on the diagonal and +1 and −1 off the diagonal, such that CTC is a multiple of the identity matrix I...

. Paley graphs allow graph-theoretic tools to be applied to the number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

 of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

Paley graphs are closely related to the Paley construction for constructing Hadamard matrices

Hadamard matrix

In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...

 from quadratic residues .
They were introduced as graphs independently by and .