Counting $K_4$'s in a Paley Graph Let $p \equiv 1 \pmod{4}$ be prime, and let $G$ be a graph such that $|V(G)| = p$ and $\{u,v\} \in E(G) \Longleftrightarrow u-v \equiv x^2 \pmod{p}$ for some integer $x$.
How many times does $G$ contain $K_4$ as a subgraph?

Alternatively, one can ask for the number of subsets $S = \{u_1,\ldots,u_4\} \subset \mathbb{Z}_p$ such that $u_i - u_j$ is a quadratic residue for $i,j \in \{1,\ldots,4\}$, $i \neq j$.
 A: Is there a reason you need to do this, or are you just curious? This paper has a formula, but summarizing the argument would be way to long for me to put here: http://www.math.ucsd.edu/~revans/Pulham.pdf
Computational is nice too (computed in Magma):
p =  5 Number of K4 subgraphs:  0 
p =  13 Number of K4 subgraphs:  0 
p =  17 Number of K4 subgraphs:  0 *
p =  29 Number of K4 subgraphs:  203 
p =  37 Number of K4 subgraphs:  555 
p =  41 Number of K4 subgraphs:  1025 
p =  53 Number of K4 subgraphs:  3445 
p =  61 Number of K4 subgraphs:  6100 
p =  73 Number of K4 subgraphs:  13140 
p =  89 Number of K4 subgraphs:  31328 
p =  97 Number of K4 subgraphs:  46560 
[* It is worth noting that for $p=17$, the Paley graph is the largest graph $G$ for which neither $G$ nor $G^{C}$ contain a copy of $K4$.]
A: Since Paley Graphs are quasi-random, the density of their sub graphs are asymptotically the same as those of the Erdős–Rényi model with the same edge density. QR3 on page 9 of this book by Lovász. For this case, Paley graphs have density 1/2, thus we can instead just think of ER graphs where p=1/2. If you look at any four vertices in an ER graph, the probability that they make a complete subgraph will be $p^6(1-p)^0$ since there must be 6 included edged and 0 excluded edges. There are $\binom{n}{4}$ choices of vertices, each with a $p^6$ probability of being a $K_4$, thus since $p=\frac{1}{2}$, you should expect around $\frac{1}{64}\binom{n}{4}$ $K_4$’s on average for large $n$.
