Additive set with small sum set and large difference set

2012-10-13T01:28:40Z

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$)?

Answer by Seva for Additive set with small sum set and large difference set

2012-10-13T11:05:37Z

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

Additive set with small sum set and large difference set - MathOverflow

Additive set with small sum set and large difference set

Answer by Seva for Additive set with small sum set and large difference set