Let $A$ be a finite subset of an abelian group, $G$ (call the operation addition). We say $A$ is a $K$-approximate group if:

1) $e_G \in A$

2) $A^{-1} = \{ a^{-1} \mid a \in A \} = A$

3) $\exists X \subset G, \; |X| \leq K$ such that: $2A \subset X+A$

Where: $A+A = \{a+b \mid a,b \in A\}$

I am asked to show that if $|A+A| \leq K|A|$, then $2A - 2A$ is a $K^{16}$-approximate group.

To this end, I am not entirely sure where to start. The first two properties fall out reasonably easily.

I believe it is well known that $|2A - 2A| \leq K^4|A|$

I am aware of a result that allows me to find an $X \subset G, \; |X| \leq K^4 $ such that $nA - A \subset (n-1)X + A - A$, which I believe implies:

$2A \subset X+A$

What can I do now though? I don't see how I can get the required subset of $G$, and the corresponding bound on the size?

  • $\begingroup$ What is $K{}{}{}?$ $\endgroup$ – Thomas Andrews Feb 11 at 19:39
  • $\begingroup$ @ThomasAndrews $K$ is a constant such that $|A+A| \leq K|A|$ $\endgroup$ – user366818 Feb 11 at 19:43

In $nA-A\subset(n-1)X+A-A$, take $n=2$ to get $$ 2A-A\subset X+A-A. $$ It follows that $$ 2A-2A \subset X+A-2A = X - (2A-A) \subset X-X+A-A. $$ This yields $$ 4A-4A \subset 2(X-X) + (2A-2A). $$ In view of $|2(X-X)|\le|X|^4\le K^{16}$, this shows that $2A-2A$ is a $K^{16}$-approximate group


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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