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)

\begin{align} \quad D = \{ 1, 3, 4, 5, 9 \} \end{align}

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}, +)$.