Show that the complement of a difference set is a difference set

Question

In combinatorics, a $(v,k,\lambda)$ difference set is a subset $D$ of cardinality $k$ of a group $G$ of order $v$ such that every nonidentity element of $G$ can be expressed as a product $d_1d_2^{-1}$ of elements of $D$ in exactly $\lambda$ ways.

Let $D$ be a difference set with parameters $\left( {v,k,\lambda } \right)$. Show that its complement is also a difference set and determine its parameters.

My attempt: They have the same first parameter $v$, since they are subsets of the same group. The second parameter is obviously $v - k$. However, I have no idea how to show that differences of the complement of $D$ cover each of $G\backslash \left\{ e \right\}$ exactly ${\lambda _C}$ times.

Assuming that they do, we would have ${\lambda _C} = \frac{{\left( {v - k} \right)\left( {v - k - 1} \right)}}{{v - 1}}$ since there are ${\left( {v - k} \right)\left( {v - k - 1} \right)}$ differences and each of ${v - 1}$ in $G\backslash \left\{ e \right\}$ would be covered ${\lambda _C}$ times.

Answer 1

This is unfamiliar territory for me, but here’s something that should at least get you started.

Fix a non-identity element $g\in G$; $g=d_1d_2^{-1}$ iff $gd_2=d_1$, so $|gD\cap D|=\lambda$. Thus, $|gD\cap D|=\lambda$ for each $g\in G\setminus\{1_G\}$. Let $E=G\setminus D$. Then for any $g\in G\setminus\{1_G\}$ we have

$$gE\cap E=(G\setminus gD)\cap(G\setminus D)=G\setminus(gD\cup D)\;,$$

and hence

$$|gE\cap E|=|G\setminus(gD\cup D)|=v-\left(|gD|+|D|-|gD\cap D|\right)=v-2k+\lambda\;.$$

Now try to reverse the first step.

As evidence that we’re on the right track, note that

$$\begin{align*} \lambda_C(v-1)&=(v-k)^2-(v-k)\\ &=v^2-2kv+k^2-v+k\\ &=v^2-v-2kv+2k-k+k^2\\ &=v(v-1)-2k(v-1)+k^2-k\\ &=v(v-1)-2k(v-1)+\lambda(v-1)\;, \end{align*}$$

so $\lambda_C$ really is $v-2k+\lambda$.

Answer 2

I know this question was asked a long time ago, but I was searching for a proof of this, and then came up with a simpler argument myself, so I'll post it in case anyone else finds it useful in future.

For any element $ g \in G \setminus \{ e\}$, $g$ occurs as a difference between any two elements of $G$ exactly $v$ times (since we can choose any element to be the first component of the difference, and then the second element is immediately determined).

Out of these $v$ differences, $k$ of them have an element from $D$ as the first component; $k$ have an element of $D$ as the second component; and, by assumption, $\lambda$ have an element of $D$ in both components. Thus by inclusion/exclusion there are $v - k - k + \lambda = v - 2k + \lambda$ differences between elements not in $D$ that equal $g$.