Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a question!

Can someone explain how (the intuition, method?) one can try to construct an additive set of cardinality $N$ with a small sum set (around $N$) and a very large difference set (say, around $N^2$)?

share|improve this question

1 Answer 1

A great work on this has been done by Imre Ruzsa; see, for instance, his paper "Many differences, few sums" in Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 51 (2008), 27–38 (2009).

As a very brief answer to your question, you cannot have a set $A$ of cardinality $N$ with $|2A|\sim N$ and $|A-A|\sim N^2$ since if $|2A|=\alpha N$, then $$ \sqrt\alpha N \le |A-A| \le \alpha^2 N; $$ you will find this inequality in the aforementioned paper by Ruzsa.


The only way to construct sets with many differences and few sums I can think of (but perhaps, not the only one known to the mankind) is to use the tensor power trick. Start with you favorite set $A_0$ with $|2A_0|=\alpha|A_0|$ and $|A_0-A_0|=\beta|A_0|$, and consider the cartesian power $A:=A_0^k$ with a large $k$. You have $N=|A|=|A_0|^k$, $|2A|=\alpha^k N$, and $|A-A|=\beta^k N$; hence, if $A_0$ is chosen so that $\alpha<\beta$, then $|A-A|$ is much larger than $|2A|$ (for $k$ large).

share|improve this answer
    
thank you a lot –  liana Oct 14 '12 at 2:20

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.