3
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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