# 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)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)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.