MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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$ be a finite set of integers with $|A \hat{+} A| \leq K|A|$, where the $\hat{+}$ denotes restricted sumset: the set of all $a_1 + a_2$ with $a_1, a_2 \in A$ and $a_1 \neq a_2$.

Claim: $|A + A| \leq (K + o(1))|A|$, where $o(1)$ denotes a quantity tending to 0 as $|A|$ tends to $\infty$.

Sketch proof: Let $A'$ be the set of all $a \in A$ for which $2a$ cannot be represented as $a_1 + a_2$ with $a_1, a_2 \in A$, $a_1 \neq a_2$. Note that $2A' = (A + A) \setminus (A \hat{+} A)$, so it suffices to show that $A'$ is small. But $A'$ has no 3-term arithmetic progressions. But by standard results (Freiman, Ruzsa...) a set $A'$ with no 3-term progressions has $|A' + A'| \gg |A'| \log^c |A'|$. Thus indeed $|A'| = o(|A|)$.

I know I've seen this argument in the literature, and my question is simply: where?

share|cite|improve this question
up vote 5 down vote accepted

For a somewhat similar argument, see Proposition 2.5 from Alon's 1987 paper ``Subset sums", available here.

share|cite|improve this answer
Thanks Seva - but I'm sure I've seen this exact argument somewhere. I guess not in one of your papers then? – Ben Green Apr 19 '13 at 11:30
Not that I could recall it, at least... – Seva Apr 19 '13 at 11:50
I finally dug out the reference myself using a MathSciNet search. MR1931192 (2003f:11016) Reviewed Schoen, Tomasz(PL-POZN) The cardinality of restricted sumsets. (English summary) J. Number Theory 96 (2002), no. 1, 48–54. – Ben Green Apr 19 '13 at 16:02

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.