Partial 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 group of order $v$ with identity element $0$ then a $(v, k, \lambda)$-difference set in this group is a nonempty proper subset $D \subset G$ with the properties that:

• 1. $\mid D \mid = k$.

• 2. 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.

We now make note of broader class of "difference sets" called partial difference sets which we define below.

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

In other words, $D$ is a $(v, k, \lambda, \mu)$-partial difference set in $(G, +)$ if the size of $G$ is $v$; the size of $D$ is $k$; and when we consider the multiset of differences $\{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \}$ we see it contains the the non-identity elements of $D$ exactly $\lambda$ times and contains the non-identity elements of $G \setminus D$ exactly $\mu$ times.

Thus, if $\lambda = \mu$ then the multiset of differences contains every element of $G \setminus \{ 0 \}$ exactly $\lambda$ times and $D$ is an ordinary $(v, k, \lambda)$-difference set. So partial difference sets are more general than ordinary difference sets.

For example, consider the following group $(G, \cdot)$ (with identity element $1$) generated as:

(1)

\begin{align} \quad G = \{ a, b : a^2 = b^2 = 1, a \cdot b = b \cdot a \} \end{align}

This is a group that contains $4$ elements, namely $G = \{ 1, a, b, a \cdot b \}$. Consider the subset $D = \{ a, b \} \subset G$. The difference table is given below:

	$a$	$b$
$a$		$b \cdot a^{-1} = b \cdot a = a \cdot b$
$b$	$a \cdot b^{-1} = a \cdot b$

Here we note that $b \cdot a^{-1} = b \cdot a$ since we're given that $a^2 = 1$ (and so $a = a^{-1}$). Then we use the given commutative property that $a \cdot b = b \cdot a$. Similarly, $a \cdot b^{-1} = a \cdot b$ since we're given that $b^2 = 1$ (and so $b = b^{-1}$).

So, the multiset of differences is:

(2)

\begin{align} \quad \{ x - y : x, y \in D \: \mathrm{and} \: x \neq y \} = \{ a \cdot b, a \cdot b \} \end{align}

The non-identity elements of $D$ are $\{ a, b \}$ which appear $\lambda = 0$ times in the multiset above. Meanwhile, the non-identity elements of $G \setminus D$ are $\{ a \cdot b \}$ which appear $\mu = 2$ times in the multiset above.

Therefore, $D$ is a $(4, 2, 0, 2)$-partial difference set in $(G, \cdot)$.