Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
add comment

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 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 at 9:07
add comment

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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