6
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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, 2013 at 11:30
  • $\begingroup$ Not that I could recall it, at least... $\endgroup$
    – Seva
    Apr 19, 2013 at 11:50
  • 4
    $\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, 2013 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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