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

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.

-

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$.

-