9
$\begingroup$

A difference set of a group $G$ is a subset $D\subseteq G$ with the property that there exists an integer $\lambda>0$ such that for every non-identity member $g$ of $G$, there exist exactly $\lambda$ ordered pairs $(a,b)\in D\times D$ such that $g=ab^{-1}$. Note that $D=G$ is a difference set with $\lambda=|G|$, and so we typically only consider nontrival difference sets.

Davis showed that $(\mathbb{Z}/n\mathbb{Z})^2$ admits a nontrivial difference set when $n$ is a power of $2$. Are there any known difference sets when $n$ is odd? Perhaps cyclotomic difference sets?

As far as I know, the Paley-type construction Douglas Zare suggests in the comments (letting $D$ be the set of nonzero perfect squares in $\mathrm{GF}(n^2)$ when $n$ is prime) is only guaranteed to work when $n^2$ is $3\bmod 4$ (which never happens). However, there are hopefully weaker sufficient conditions for $n$ to satisfy, and I think the literature discusses this in the context of "cyclotomic difference sets," but I am not familiar with these results.

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ What is a difference set? $\endgroup$
    – Will Sawin
    Commented Jul 17, 2013 at 3:02
  • $\begingroup$ A reference to Davis's paper, and a clarification as to what ${\mathbb Z}_n$ is (cyclic group, cyclotomic integers, or p-adics?) would also help. $\endgroup$
    – Terry Tao
    Commented Jul 17, 2013 at 3:07
  • $\begingroup$ @WillSawin a difference set in an abelian group $G$ is any subset $D \subset G$ so that each non-identity $g \in G$ is expressible as a difference $d-d'$ of elements in $D$. One typically extends this by requiring that each $g$ be so expressible in $k \geq 1$ different ways. $\endgroup$
    – Vidit Nanda
    Commented Jul 17, 2013 at 3:42
  • $\begingroup$ @TerryTao see Davis, Difference sets in abelian 2-groups, Journal of Combinatorial Theory, Series A Volume 57, Issue 2, July 1991, Pages 262–286. Elsevier paywall here: sciencedirect.com/science/article/pii/009731659190050Q $\endgroup$
    – Vidit Nanda
    Commented Jul 17, 2013 at 3:43
  • $\begingroup$ Are you restricting to having one repetition of each possible difference? If not, then you can do things like look at the squares in $\mathbb{F}_{p^2}$, a classic construction. $\endgroup$
    – Douglas Zare
    Commented Jul 17, 2013 at 7:10

1 Answer 1

Reset to default
9
$\begingroup$

Such difference sets exist. There exist (nontrivial) difference sets with

$|G| = q^{d+1}[1+(q^{d+1}-1)/(q-1)]$,

$|D| = q^d(q^{d+1}-1)/(q-1)$,

$\lambda = q^d(q^d-1)/(q-1)$,

whenever $q$ is a prime power (R. L. McFarland, A family of difference sets in non-cyclic groups, JCT A, 15 (1973), pp. 1-10). More precisely, such difference sets exist in any abelian group of order $v$ which contains an elementary abelian subgroup of order $q^{d+1}$.

Take $q=7$ and $d=1$, for instance. This shows that a nontrivial difference set in $(\mathbb{Z}/21\mathbb{Z})^2$ exists.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .