# Fun question in additive combinatorics

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}.$$

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

$$A=\{2^{i}:i={0,1,\ldots,n-1}\}.$$

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\}.$$

Define the "asymptotic growth exponent" as $$\mathrm{ge_{p}} = \lim_{n\to\infty} {\frac{\log(|A_{p}+A_{p}|)}{\log(n)}}.$$

What is the limit $\mathrm{ge_{p}}$ for $p=2$? In general?

Enjoy! :-)

-
For arithmetic progressions, $|A+A|=2n-1$, hence your first lower bound should be modified. – Did Mar 24 '11 at 14:23
This is not meant as criticism but will determine if any or how much time I spent on this question: do you have a serious interest in this, or is this for fun only? – user9072 Mar 24 '11 at 14:40
Is this a question to which you already know the answer? – JBL Mar 24 '11 at 15:12
If I've understood the question, surely the limit is 2 for all $p$. For squares this is just the fact that $\gg N^{1-o(1)}$ integers less than $N$ are the sum of two squares. For larger $p$ it's certainly known (I don't have a reference to hand). And is $p$ supposed to be an integer? – Ben Green Mar 24 '11 at 19:20
One way of putting Ben's comment when p=2 is to say that it's known that every prime of the form 4m+1 is a sum of two squares. It's easy to see from that that the limit is 2 when p=2. For larger p one would expect the limit to be at least as big, and this is indeed the case. – gowers Mar 24 '11 at 20:53