# Paley Difference Sets

Recall from the Difference Sets page that if $v$, $k$, and $\lambda$ are positive integers such that $2 \leq k < v$ and $(G, +)$ is a group of order $v$ with identity $0$, then a $(v, k, \lambda)$-difference set is a nonempty proper subset $D \subset G$ such that $\mid D \mid = k$ and the multiset $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \}$ contains every element of $G \setminus \{ 0 \}$ exactly $\lambda$ times.

We will now describe a special type of difference set known as the Paley difference sets in the following theorem.

Definition: Let $q = 4n - 1$ be a prime power and let $(\mathbb{Z}_q, +)$ be the additive group of integers modulo $q$. The Paley Difference Set in this group is the subset $D \subset \mathbb{Z}_q$ of nonzero squares modulo $q$. |

*The requirement that $q = 4n - 1$ is equivalent to $q \equiv 3 \pmod 4$. Since $q$ must also be a prime power, the first few $q$ satisfying the requirement for Theorem 1 are $q = 3, 7, 11, 19, 23, 27, ...$.*

For example, take $q = 11$. Note that $q = 4(3) - 1$ and $q$ is indeed a prime power (since $q = 11^1$). The nonzero squares modulo $11$ are listed below:

$1^2 \equiv 1 \pmod {11}$ |

$2^2 \equiv 4 \pmod {11}$ |

$3^2 \equiv 9 \pmod {11}$ |

$4^2 \equiv 5 \pmod {11}$ |

$5^2 \equiv 3 \pmod {11}$ |

$6^2 \equiv 3 \pmod {11}$ |

$7^2 \equiv 5 \pmod {11}$ |

$8^2 \equiv 9 \pmod {11}$ |

$9^2 \equiv 4 \pmod {11}$ |

$10^2 \equiv 1 \pmod {11}$ |

Therefore the set $D$ is:

(1)The difference table for the set $D$ above is:

$1$ | $3$ | $4$ | $5$ | $9$ | |
---|---|---|---|---|---|

$1$ | $2$ | $3$ | $4$ | $8$ | |

$3$ | $9$ | $1$ | $2$ | $6$ | |

$4$ | $8$ | $10$ | $1$ | $5$ | |

$5$ | $7$ | $9$ | $10$ | $4$ | |

$9$ | $3$ | $5$ | $6$ | $7$ |

So indeed, $D$ is a $(11, 5, 2)$-difference set in $(\mathbb{Z}_{11}, +)$.