Difference Sets in Non-Abelian Groups

# Difference Sets in Non-Abelian Groups

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$ 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 of $G \setminus \{ 0 \}$ exactly $\lambda$ times.

Thus far, all of the examples of difference sets that we have looked at have involved $(G, +)$ to be an abelian group. This is NOT a necessary condition for the existence of a difference set in a group.

We will construct an example of a difference set coming from a non-abelian group.

Let $G$ be the group with operation $\cdot$ and identity $1$ be defined as follows:

(1)
\begin{align} \quad G = \{ a, b : a^7 = 1, b^3 = 1, bab^{-1} = a^2 \} \end{align}

When we write the restriction $a^7 = 1$ we mean that $m = 7$ is the least positive integer such that $a^m = 1$. Similarly, the restriction $b^3 = 1$ means that $n = 3$ is the least positive integer such that $b^n = 1$. The restriction $bab^{-1} = a^2$ means that conjugation of $a$ by $b$ sends $a$ to $a^2$.

We will show that this group is non-abelian. Suppose that $ab = ba$. Then:

(2)
\begin{align} \quad aba^{-1} = baa^{-1} \\ \quad aba^{-1} = b \\ \quad b^2 = b \\ \quad b^2 b^{-1} = bb^{-1} \\ \quad b = 1 \end{align}

But we are given that $n = 3$ is the least positive integer such that $b^n = 1$ so a contradiction has arisen. Thus $ab \neq ba$, i.e., $(G, \cdot)$ is a non-abelian group.

We now describe a difference set in this group:

(3)
\begin{align} \quad D = \{ 1, a, a^3, b, a^2b^2 \} \end{align}

The difference table for $D$ is:

$1$ $a$ $a^3$ $b$ $a^2b^2$
$1$ $a$ $a^3$ $b$ $a^2b^2$
$a$ $a^{-1}$ $a^2$ $ba^{-1}$ $a^2b^2a^{-1}$
$a^3$ $a^{-3}$ $aa^{-3}$ $ba^{-3}$ $a^2b^2a^{-3}$
$b$ $b^{-1}$ $ab^{-1}$ $a^3b^{-1}$ $a^2b^2b^{-1}$
$a^2b^2$ $(a^2b^2)^{-1}$ $a(a^2b^2)^{-1}$ $a^3 (a^2b^2)^{-1}$ $b(a^2b^2)^{-1}$

The entries in the table above can be rewritten as:

$1$ $a$ $a^3$ $b$ $a^2b^2$
$1$ $a$ $a^3$ $b$ $a^2b^2$
$a$ $a^{6}$ $a^2$ $a^5b$ $a^2b^2a^{-1}$
$a^3$ $a^{4}$ $a^5$ $ab$ $a^2b^2a^{-3}$
$b$ $b^{2}$ $ab^2$ $a^3b^2$ $a^2b$
$a^2b^2$ $a^3b$ $a^4b$ $a^6b$ $ba^2b^2$

So indeed $D$ is a difference set of the non-abelian group $(G, \cdot)$.