Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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! :-)

share|improve this question
1  
For arithmetic progressions, $|A+A|=2n-1$, hence your first lower bound should be modified. –  Did Mar 24 '11 at 14:23
1  
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? –  quid Mar 24 '11 at 14:40
4  
Is this a question to which you already know the answer? –  JBL Mar 24 '11 at 15:12
7  
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
4  
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
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.