5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks Seva - but I'm sure I've seen this exact argument somewhere. I guess not in one of your papers then? $\endgroup$ – Ben Green Apr 19 '13 at 11:30
  • $\begingroup$ Not that I could recall it, at least... $\endgroup$ – Seva Apr 19 '13 at 11:50
  • 2
    $\begingroup$ 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. $\endgroup$ – Ben Green Apr 19 '13 at 16:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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