MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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})? $$


share|cite|improve this question
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: 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. ) – 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.

Update: After thinking about it a little more, I realize this doesn't prove anything, so it should perhaps have been a comment rather than an answer.

share|cite|improve this answer
It doesn't prove anything, but the answer is indeed no, for essentially the reason you say. It can be proven rigorously using the circle method a la Vinogradov. – Ben Green May 16 '11 at 18:50

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.