The Trivial 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 finite group of order $v$ then a $(v, k, \lambda)$-difference set in $G$ is a nonempty proper subset $D \subset G$ such that the multiset of differences $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \}$ contains each element of $G \setminus \{ 0 \}$ exactly $\lambda$ times.
It is often noted that if $(G, +)$ is a finite group of order $v \geq$ then for any $g \in G$, $D = \{ g \}$ is a difference set. However, this does not agree with the definition we made above for if $D = \{ g \}$ then $\mid D \mid = k = 1 < 2$. Nevertheless, for completeness we will state that such a set is indeed a difference set.
A more interesting (but still trivial) type of difference set is describe in the proposition below.
| Proposition 1: If $(G, +)$ is a finite group of order $v \geq 2$ and $g \in G$ then $D = G \setminus \{ g \}$ is a difference set. |
- Proof: Let $g \in G$ and $D = G \setminus \{ g \}$. Since $\mid G \mid = v$, $\mid D \mid = v - 1$. We denote this set by $D = \{ g_1, g_2, ..., g_{v-1} \}$. We consider the multiset of differences:
- This multiset of differences can be obtained by the difference table:
| $g_1$ | $g_2$ | $\cdots$ | $g_{v-1}$ | |
|---|---|---|---|---|
| $g_1$ | $g_2 - g_1$ | $\cdots$ | $g_{v-1} - g_1$ | |
| $g_2$ | $g_1 - g_2$ | $\cdots$ | $g_{v-1} - g_2$ | |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ |
| $g_{v-1}$ | $g_1 - g_{v-1}$ | $g_2 - g_{v-1}$ | $\cdots$ |
- Consider the first row of differences above, i.e., the set of differences $\{ g_2 - g_1, g_3 - g_1, ..., g_{v-1} - g_1 \}$. This set contains $v - 2$ differences. Each of these differences are also distinct, since if $g_j - g_1 = g_k - g_1$ then this would imply $g_j = g_k$ which is a contradiction since the elements of $D$ are distinct.
- For the second row of differences, i.e., the set of differences $\{ g_1 - g_2, g_3 - g_2, ..., g_{v-1} - g_2 \}$, the same logic applies. This set contains $v - 2$ differences, each of which is distinct.
- Of course, the same applies all $v - 1$ rows.
- Each row contains $v - 2$ elements and the set of such elements is a $(v - 2)$-subset of $G \setminus \{ 0 \}$. Note that $G \setminus \{ 0 \}$ contains $v - 1$ elements. The number of ways to construct a $(v - 2)$-subset from a set of $(v - 1)$ elements is $\binom{v-1}{v-2} = v - 1$. So each row of the difference table above is a unique $(v - 2)$-subset of $G \setminus \{ 0 \}$.
- Hence the $v - 1$ elements of $D$ must appear in the difference table an equal number of times. In particular, since the difference table above contains $(v - 1) \cdot (v - 2)$ elements we must have that $D$ is a difference set with $\displaystyle{\lambda = \frac{(v - 1) \cdot (v - 2)}{v - 1} = v - 2}$, that is, $D$ is a $(v, v-1, v-2)$ difference set. $\blacksquare$
Once again, it is important to note that if $v = 2$ then $D = G \setminus \{ g \}$ contains only one element which does not first our original definition of a difference set since we require $2 \leq k$. Regardless, we will still denote such cases as difference sets of completeness.
The two examples mentioned above are what as known as trivial difference sets in a group. We formally define them below.
| Definition: If $(G, +)$ is a finite group of order $v \geq 2$ then for any $g \in G$, $\{ g \}$ and $G \setminus \{ g \}$ are called Trivial Difference Sets. |