Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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}$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.