Additive set with small sum set and large difference set - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T13:08:41Z http://mathoverflow.net/feeds/question/109504 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109504/additive-set-with-small-sum-set-and-large-difference-set Additive set with small sum set and large difference set liana 2012-10-13T01:28:40Z 2012-10-13T12:23:09Z <p>I have a question! </p> <p>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$)?</p> http://mathoverflow.net/questions/109504/additive-set-with-small-sum-set-and-large-difference-set/109524#109524 Answer by Seva for Additive set with small sum set and large difference set Seva 2012-10-13T11:05:37Z 2012-10-13T12:23:09Z <p>A great work on this has been done by Imre Ruzsa; see, for instance, his paper <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=Ruzsa%2C%20I%2A&amp;s5=Sums%20and%20differences&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=1&amp;mx-pid=2567492" rel="nofollow">"Many differences, few sums"</a> in <em>Ann. Univ. Sci. Budapest. Eötvös Sect. Math.</em> <strong>51</strong> (2008), 27–38 (2009).</p> <p>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.</p> <hr> <p>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&lt;\beta$, then $|A-A|$ is much larger than $|2A|$ (for $k$ large).</p>