 PaleyGraph - Maple Help

GraphTheory[SpecialGraphs]

 PaleyGraph
 construct Paley graph Calling Sequence PaleyGraph(p) PaleyGraph(p,k) PaleyGraph(p,k,m) Parameters

 p - prime integer k - positive integer m - irreducible univariate polynomial of degree k over GF(p) Description

 • If the input is PaleyGraph(p) where p is congruent to 1 modulo 4, then the output is an unweighted undirected graph G on p vertices labeled 0,1,...,p-1 where the edge {i,j}, with i
 • If the input is PaleyGraph(p) where p is congruent to 3 modulo 4, then the output is an unweighted directed graph G on p vertices labeled 0,1,...,p-1 where the arc [i,j] is in G iff j-i is a quadratic residue in Zp.
 • If the input is PaleyGraph(p,k) where $q={p}^{k}$ is congruent to 1 modulo 4, then the output is an unweighted undirected graph G on $q$ vertices labeled 0,1,...,q-1 where the edge {i,j}, i
 • Similarly, if the input is PaleyGraph(p,k) where $q={p}^{k}$ is congruent to 3 modulo 4, then the output is an unweighted directed graph G on $q$ vertices labeled 0,1,...,q-1 where the arc [i,j] is in G iff y-x is a square in the finite field GF(q), where x is the $i$th element and y is the $j$th element in GF(q). The numbering of the elements in GF(q) is lexicographical.
 • The vertex label for the element f(x) in Zp[x] is f(p). For example, in GF(23) the elements are ordered $0,1,x,x+1,{x}^{2},{x}^{2}+1,{x}^{2}+x,{x}^{2}+x+1$. Thus the label for element ${x}^{2}+1$ is ${2}^{2}+1=5$.
 • The field can be specified by the user by specifying the extension polynomial for GF(q), a monic irreducible polynomial m(x) in Zp[x] of degree k. Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PaleyGraph}\left(5\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(P\right)$ > $E≔\mathrm{Edges}\left(P\right)$
 ${E}{≔}\left\{\left\{{0}{,}{1}\right\}{,}\left\{{0}{,}{4}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{3}{,}{4}\right\}\right\}$ (2)
 > $P≔\mathrm{PaleyGraph}\left(2,2\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (3)
 > $\mathrm{DrawGraph}\left(P\right)$ > $E≔\mathrm{Edges}\left(P\right)$
 ${E}{≔}\left\{\left\{{0}{,}{1}\right\}{,}\left\{{0}{,}{2}\right\}{,}\left\{{0}{,}{3}\right\}{,}\left\{{1}{,}{2}\right\}{,}\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{3}\right\}\right\}$ (4)
 > $P≔\mathrm{PaleyGraph}\left(3,2,{y}^{2}+1\right)$
 ${P}{≔}{\mathrm{Graph 3: a directed unweighted graph with 9 vertices and 18 arc\left(s\right)}}$ (5)
 > $\mathrm{DrawGraph}\left(P\right)$ 