Paley Difference Sets

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