Take the 2-minute tour ×

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.

share|improve this question
What do you mean by $\mathbb Z_n$? And how does $A$ relate to $A_n$? –  tomasz Jul 8 '12 at 1:37

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
user31373's answer doesn't solve the problem. If you extend the sequence to include "200, 300, etc." and then try to find the difference "85", you find it is nowhere in the set. –  user136176 Mar 18 '14 at 5:20
@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.) –  Willie Wong Mar 18 '14 at 9:07

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

share|improve this answer
Gerry, thanks for your reply. I am wondering if there's an constructive proof for this statement. –  Terry Zhou Jul 8 '12 at 16:16
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. –  Gerry Myerson Jul 9 '12 at 0:42

Your Answer


