Let $G$ be an abelian group. Let $A\subset G$ be a finite set. $\sum_A$ is defined as: $$\left\{\sum_{b\in B}b \mid B\subset A\right\}$$ Is there any result similar to Freiman's Theorem for $\sum_A$? Can we say anything about $A$ if $\sum_A$ is small?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
One way in which $\sum_A$ can be small is if $A$ is a small subgroup of $G$. To exclude such examples, define $X$ to be aperiodic, if the only solution to $X+x=X$ is $x=0$. DeVos, Goddyn, Mohar and Šámal proved that if $\sum_A$ is aperiodic, then $\sum_A$ exhibits quadratic growth.
Theorem. Let $A \subseteq G \setminus \{0\}$, where $G$ is an abelian group. If $\sum_A$ is aperiodic, then $|\sum_A| \geq \frac{|A|^2}{64}$.
answered Jun 1, 2014 at 17:33
$\begingroup$
$\endgroup$
As one can see from Tony's answer, assuming something like $\big|\Sigma_A\big|<C|A|$ (in analogy with Freiman's theorem) would be a terrible overkilling. However, the situation changes if $A$ is a multiset; that is, if $A$ is allowed to contain several instances of the same element. I studied this problem some 15 years ago and was able to show that if $A$ is a multiset of positive integers such that $\big|\Sigma_A\big|\le C|A|-4C^3$ and $|A|\ge 4C^3$, where $C$ is a positive integer, then $\Sigma_A$ is a union of at most $C-1$ arithmetic progressions sharing the same difference. I further conjectured that the assumption can be relaxed to $\big|\Sigma_A\big|\le C|A|-(C-1)^2$ (which would be best possible), but despite my feeling that this should not be difficult to prove, it was never done to my knowledge.
