5
$\begingroup$

Problem 1. For which $n$ does the cyclic group $C_n$ admit a difference set $D\subset C_n$, i.e., a set such that each non-unit element $x\in C_n$ can be uniquely written as the difference $x=ab^{-1}$ for some $a,b\in D$?

A necessary condition is that $n=1+d+d^2$ for some $d$.

If $p$ is prime, then for $n=1+p+p^2$ the cyclic group $C_n$ admits a difference set according to the classical result of Singer. What about other numbers $d$?

Problem 2. For which $d$ does the cyclic group $C_n$ of order $n=1+d+d^2$ admit a difference set?

Probably this is known, then give me please a proper reference.

$\endgroup$
2
  • 8
    $\begingroup$ This is an open problem. Singer's result holds for all prime powers -- comes from finite fields. And the conjecture is that these are the only values. For example, there is a discussion of this problem in C9 and C10 of Guy's book on Unsolved problems in Number Theory. $\endgroup$
    – Lucia
    Feb 13, 2017 at 23:58
  • 1
    $\begingroup$ I think "(perfect) difference set" is used more generally for subsets (not empty or the whole group) such whose differences cover all nonzero group elements the same number of times. An examples is the quadratic residues in a cyclic group of prime order. Of course the special case you ask about is interesting too. $\endgroup$ Feb 14, 2017 at 3:05

1 Answer 1

9
$\begingroup$

What you called difference sets in cyclic groups are usually called PLANAR cyclic difference sets, namely those with \lambda equal to 1. The question you asked here has been studied for many years. Singer's construction from 1938 shows that for any prime power n, there is a planar cyclic difference set of order n. In the other direction, probably the earliest reference goes back to ``Cyclic projective planes" by Marshall Hall, Jr., published in Duke J. Math. 14 (1947), 1079-1090. The conjecture is that if a planar cyclic difference set of order n exists, then n is a prime power. The conjecture is still open. But many partial results are known. You can find a survey of the currently known results on the conjecture in the following paper:

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1r6/pdf

$\endgroup$
3
  • $\begingroup$ But this PPC goes only the necessary direction. Is it proved that for any prime power $n=p^k$ the cyclic group $C_n$ contains a difference set? $\endgroup$ Feb 14, 2017 at 5:34
  • $\begingroup$ I looked at the internet and found that for prime powers the difference sets I am interested in were constructed by Singer. So, thanks for the answers. $\endgroup$ Feb 14, 2017 at 5:39
  • $\begingroup$ @Taras Banakh I edited my answer slightly to address your question. $\endgroup$
    – Qing Xiang
    Feb 14, 2017 at 5:39

Your Answer

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