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.