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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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