Difference Sets

# Difference Sets

We now turn our attention to a very nice structure known as a difference set on an algebraic group.

 Definition: Let $v$, $k$, and $\lambda$ be positive integers such that $2 \leq k < v$ and let $(G, +)$ be a finite group of order $v$ with identity element $0$. A $(v, k, \lambda)$-Difference Set in $(G, +)$ is a nonempty proper subset $D \subset G$ such that $\mid D \mid = k$ and the multiset of differences $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \}$ contains every element in $G \setminus \{ 0 \}$ exactly $\lambda$ times.

Let's look at an example of a difference set. Consider the group $(\mathbb{Z}_7, +)$, where $\mathbb{Z}_7 = \{ 0, 1, 2, 3, 4, 5, 6 \}$ and $+$ denotes the operation of addition modulo $7$, for example, $3 + 6 = 2 \pmod 7$. The identity for this group is $0$.

Consider the following set:

(1)
\begin{align} \quad D = \{ 0, 1, 3 \} \subset \mathbb{Z}_7 \end{align}

We claim that $D$ is a $(7, 3, 1)$-Difference set. To verify this, we look at the multiset of all differences $\{ x - y : x, y \in \mathbb{Z}_7 \: \mathrm{and} \: x \neq y \}$ which is given in the following table:

$0$ $1$ $3$
$0$ X $1$ $3$
$1$ $6$ X $2$
$3$ $4$ $5$ X

Hence $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \} = \{ 1, 2, 3, 4, 5, 6 \} = \mathbb{Z}_7 \setminus \{ 0 \}$. Each element in this multiset occurs $\lambda = 1$ time, so indeed, $D$ is a $(7, 3, 1)$-difference set.

For another example of a difference set, consider the group $(\mathbb{Z}_4 \times \mathbb{Z}_4, +)$ where the operation $+$ is defined by $(x, y) + (a, b) = (x + a, y + b)$ (modulo $2$). The identity element for this group is $(0, 0)$. Consider the following set:

(2)
\begin{align} \quad D = \{ (0, 1), (0, 2), (0, 3), (1, 0), (2, 0), (3, 0) \} \end{align}

We construct the following table listing all differences in the multiset $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \}$:

$(0, 1)$ $(0, 2)$ $(0, 3)$ $(1, 0)$ $(2, 0)$ $(3, 0)$
$(0, 1)$ $\color{Red} {(0, 1)}$ $\color{Orange} {(0, 2)}$ $\color{ProcessBlue}{(1, 3)}$ $\color{Fuchsia}{(2, 3)}$ $\color{Magenta}{(3, 3)}$
$(0, 2)$ $\color{Gold} {(0, 3)}$ $\color{Red} {(0, 1)}$ $\color{Green}{(1, 2)}$ $\color{Purple}{(2, 2)}$ $\color{WildStrawberry}{(3, 2)}$
$(0, 3)$ $\color{Orange} {(0, 2)}$ $\color{Gold} {(0, 3)}$ $\color{LimeGreen}{(1, 1)}$ $\color{NavyBlue}{(2, 1)}$ $\color{Pink}{(3, 1)}$
$(1, 0)$ $\color{Pink}{(3, 1)}$ $\color{WildStrawberry}{(3, 2)}$ $\color{Magenta}{(3, 3)}$ $\color{YellowGreen}{(1, 0)}$ $\color{GreenYellow}{(2, 0)}$
$(2, 0)$ $\color{NavyBlue}{(2, 1)}$ $\color{Purple}{(2, 2)}$ $\color{Fuchsia}{(2, 3)}$ $\color{JungleGreen}{(3, 0)}$ $\color{YellowGreen}{(1, 0)}$
$(3, 0)$ $\color{LimeGreen}{(1, 1)}$ $\color{Green}{(1, 2)}$ $\color{ProcessBlue}{(1, 3)}$ $\color{GreenYellow}{(2, 0)}$ $\color{JungleGreen}{(3, 0)}$

Notice that $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \} = \mathbb{Z}_4 \times \mathbb{Z}_4 \setminus \{ (0, 0) \}$ and that this multiset contains each element in $\mathbb{Z}_4 \times \mathbb{Z}_4 \setminus \{ (0, 0) \}$ exactly $\lambda = 2$ times. Therefore, $D$ is a $(16, 6, 2)$-difference set.