The Trivial Difference Sets

# 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:
(1)
\begin{align} \quad \{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \} \end{align}
• 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.