2
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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? $\endgroup$
    – user9072
    Commented Mar 24, 2011 at 14:40
  • 4
    $\begingroup$ Is this a question to which you already know the answer? $\endgroup$
    – JBL
    Commented Mar 24, 2011 at 15:12
  • 10
    $\begingroup$ 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? $\endgroup$
    – Ben Green
    Commented Mar 24, 2011 at 19:20
  • 5
    $\begingroup$ 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. $\endgroup$
    – gowers
    Commented Mar 24, 2011 at 20:53
  • 1
    $\begingroup$ @gowers: I don't see the relation between the fact that every prime of the form $4m+1$ can be written as a sum of two squares with my question. The intuition under the fact that the limit is 2 is that there are very few possibilities for $a^2+b^2=c^2+d^2$ with $\{a,b\}\neq\{c,d\}$ and $a,b,c,d\in\{1,2,\ldots,n\}$. I'm sure that I'm missing something elementary here. Thanks! $\endgroup$
    – ght
    Commented Mar 25, 2011 at 21:25

0

Reset to default

You must log in to answer this question.