Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.