Olson's dichotomy: either every subset sum is represented twice, or $|\Sigma(A)| > 1 + \frac19|A|^2$

Olson's dichotomy for the set of subset sums, specialised to abelian groups.

For a finite subset $A=\{a_1,\dots,a_s\}$ of an abelian group $G$, write

the set of all subset sums of $A$ (the empty subset contributes $0$, so $0\in\Sigma(A)$ always). A representation of $g\in\Sigma(A)$ is a subset $S\subseteq A$ with $\sum_{x\in S}x=g$; equivalently, in Olson's notation, a tuple $(\varepsilon_1,\dots,\varepsilon_s)\in\{0,1\}^s$ with $g=\sum_i \varepsilon_i a_i$.

The theorem asserts that exactly one of two things can happen, and in either case the set of subset sums is constrained:

1. every element of $\Sigma(A)$ has at least two distinct representations; or
2. $\Sigma(A)$ is large:

This is Theorem 3.2 of Olson's 1975 paper, which is stated there for an arbitrary — possibly non-abelian, possibly infinite — group $G$ and asserts the existence of an arrangement $a_1,\dots,a_s$ of the elements of $A$ for which the dichotomy holds, since for a non-abelian group $\Sigma$ depends on the order in which the elements are listed. In an abelian group $\Sigma(A)$ does not depend on the arrangement, so the existential quantifier over arrangements disappears and the statement takes the form above. Olson proves alternative (2) with the sharper constant $c=\tfrac18-O\!\left(\tfrac{\log s}{s}\right)>\tfrac19$; the uniform constant $\tfrac19$ recorded here is the weaker form that he himself carries through the induction, and is the form in which the theorem is quoted downstream.

On the hypotheses. Olson's statement is about a set of $s$ distinct non-zero elements, so $0\notin A$ is kept here even though it is not needed: if $0\in A$ then for every $g\in\Sigma(A)$ and every representation $S$ of $g$, exactly one of $S\cup\{0\}$ and $S\setminus\{0\}$ is a second representation, so alternative (1) holds automatically. Nonemptiness of $A$, on the other hand, is genuinely needed: for $A=\varnothing$ one has $\Sigma(A)=\{0\}$, whose single element $0$ has only the representation $S=\varnothing$, so (1) fails, while $|\Sigma(A)|=1=1+\tfrac{0^2}{9}$, so (2) fails as well.

Where the dichotomy is used. If $A$ is zero-sum-free — no nonempty subset of $A$ sums to $0$ — then $0\in\Sigma(A)$ is represented only by $S=\varnothing$, so alternative (1) is impossible and alternative (2) must hold. That deduction is exactly Theorem 7 of Erdős–Lev–Rauzy–Sándor–Sárközy, which is how Olson's theorem enters the bound $F(N)<3\sqrt N+1$ for non-dividing sets.

What the proof requires. Olson's proof of Theorem 3.2 is an induction on $s$ resting on three further results of the same paper: Theorem 2.1 (Kemperman–Scherk: if $|A+B|=|A|+|B|-k$ then every element of $A+B$ has at least $k$ representations as $a+b$), Theorem 2.2 (if $0\in A$ is finite then for every $n\ge 1$ either $nA=\langle A\rangle$ or $|nA|\ge |A|+(n-1)\lfloor\tfrac12(|A|+1)\rfloor$), and Lemma 3.1, an averaging estimate on $\lambda(g)=|(B+g)\cap \overline B|$ which feeds Theorem 3.1, the quantitative arrangement theorem. None of these is in Mathlib.