1
$\begingroup$

Does anyone know any constructions of small set with big difference set. Mathematically speaking:

Let $A\subseteq \mathbb{Z}$, such that $A-A=\mathbb{Z}_n$. Please give a sequence $(A_n)_{n\in \mathbb{N}}$ such that $|A_n|$ is small in terms of $n$.

Thanks in advance.

  • 0
    What do you mean by $\mathbb Z_n$? And how does $A$ relate to $A_n$?2012-07-08

2 Answers 2

2

Here is an example which you can easily generalize: 0,1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100. It gives the best possible order $\sqrt{n}$.

  • 0
    @user136176: 90 - 5 = 85. I am a bit confused as to what you are thinking of. (I've converted your answer to a comment, since it is a comment on an existing answer. You will gain the ability to comment everywhere once you have accrued 50 reputation points on the website.)2014-03-18
1

Do you know about perfect cyclic difference sets? If $q$ is a prime power, than there is a set $A$ of $q+1$ integers such that $A-A$ covers ${\bf Z}/n{\bf Z}$ with $n=q^2+q+1$.

  • 0
    I'm not sure. Here's what Tom Storer had to say in his book, Cyclotomy and Difference Sets, pp 16-17. "...even now no elementary proof of Singer's theorem has been found." He then gives a proof, and writes, "The above method appears to be constructive.... Nevertheless, in practice ... no satisfactory algorithm in this connection is known." Anyway, you've got some search terms: perfect cyclic difference set, finite projective plane, Singer's Theorem. See what you can find.2012-07-09