Fun question in additive combinatorics - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T07:04:11Z http://mathoverflow.net/feeds/question/59432 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59432/fun-question-in-additive-combinatorics Fun question in additive combinatorics ght 2011-03-24T13:53:05Z 2011-07-29T06:19:55Z <p>It is easy to see that for a finite set of integers $A$ of cardinality $n$, the cardinality of the sumset $A+A$ satisfies $$2n-1\leq |A+A|\leq \frac{n(n+1)}{2}.$$</p> <p>The lower bound is essentially attained when the set $A$ is an arithmetic progression while the upper bound is attained for sets such that $a_{i}+a_{j}=a_{p}+a_{q}$ implies that $\{i,j\}=\{p,q\}$. An example of this set is </p> <p>$$A=\{2^{i}:i={0,1,\ldots,n-1}\}.$$</p> <p>I think is a fun problem (probably not very difficult) to study what is the rate of growth of $|A_{p}+A_{p}|$ as $n\to\infty$ where $$A_p=\{1^p,2^p,\ldots,n^p\}.$$</p> <p>Define the "asymptotic growth exponent" as $$\mathrm{ge_{p}} = \lim_{n\to\infty} {\frac{\log(|A_{p}+A_{p}|)}{\log(n)}}.$$</p> <p>What is the limit $\mathrm{ge_{p}}$ for $p=2$? In general? </p> <p>Enjoy! :-)</p>