# Size of Sum Sets

Let $\{a_{k}\}$ be an increasing sequence of positive real numbers. Let us define $A_{n}:=\{a_1,\ldots,a_{n}\}$ and consider the set

$$S_{n}^{(2)}=\Big \{(x_1,x_2,x_3,x_4)\in A_{n}^4:x_1-x_2+x_3-x_4=0 \Big\}.$$

In other words, the size of the set $S_n^{(2)}$ is equal to the number of solutions to the sum-set equation
$$2A_{n}-2A_{n}=0.$$

For instance, if $a_k=k$ then it is not difficult to see that $$|S_{n}^{(2)}|=\frac{2}{3}n^3+o(n^3),$$ and that if $a_{k}=2^k$ then $$|S_{n}^{(2)}|=2n^2-n.$$

My question is: let $\alpha>0$ and $\alpha\neq 1$ is it true that if we define $a_{k}=k^{\alpha}$ then $$> |S_{n}^{(2)}|=o(n^3)?$$

Update 1: Simulations suggest that the previous statement is true at least for $\alpha=\frac{1}{2},2,3,4$.

However, for the sequence $a_{k}=\text{the k-th prime number}$, simulations again suggest that $$\frac{|S_n^{(2)}|}{n^3}\to \beta>0.$$ Can this be right?

Answer: No. As Ben and Johan pointed out below this is not true and the limit is actually $\beta=0$.

Update 2: Define for $r\geq 2$ the set $S_{n}^{(r)}$ as the solutions to the sumset equation $$> rA_{n}-rA_{n}=0.$$

Is it true that for the sets above ($a_{k}=k^{\alpha}$) $$> |S_{n}^{(r)}|=o(n^{2r-1})?$$

Thanks!

-
Note that if you consider the number $c(n,t)=:|\{(x,y)\in A_n^2 :x-y=t \} |$ then $|S_n|=\sum_{0\le t\le n} c(n,t)^2$ . – Pietro Majer May 16 '11 at 16:12
– Boris Bukh May 16 '11 at 16:38
@Boris: Thanks for the reference. What result from this reference do you think it is relevant to the question? Thanks. – ght May 16 '11 at 18:09
One problem mentioned in Guy's Unsolved Problems in Number Theory is to prove that there are no nontrivial solutions to $$x_1^5-x_2^5+x_3^5-x_4^5=0,$$ in other words, to prove that the fifth powers are a Sidon set. This conjecture implies $|S_n|\sim 2n^2$. – Kevin O'Bryant May 16 '11 at 22:19
Boris's reference will work when combined with the Balog-Szemeredi-Gowers theorem (see e.g. people.math.gatech.edu/~ecroot/BSG7.pdf ) – Terry Tao May 18 '11 at 4:34

If I understand correctly, the question can be phrased as follows (let's take the prime numbers as suggested in the update): If we put the first $n$ prime numbers in a hat, and pull out three of them, $x_1$, $x_2$ and $x_3$, then is there a decent probability $\beta>0$ that $x_1-x_2+x_3$ is also prime?
The answer clearly has to be no, and I guess a proof can be obtained by noting that for every prime $p$, $x_1-x_2+x_3$ will be divisible by $p$ with probability roughly $1/p$ when $n$ is large (because the primes are asymptotically uniformly distributed among the nonzero congruence classes mod $p$). Since $\sum 1/p$ diverges, the probability of $x_1-x_2+x_3$ being prime ought to tend to zero.