# Sum of subsets is the whole set?

Let $$A$$ be subset of $$\mathbb{Z}_n$$.

Define $$A \oplus A = {\{a \oplus a’ : a \in A, a’ \in A}\}$$, where $$a \oplus a’ = a+a \mod n$$.

If $$A$$ is not contained in a coset of a proper additive subgroup of $$\mathbb{Z}_n$$, then there exists a $$k \in \mathbb{N}$$ such that $$A^{\oplus k}= \mathbb{Z}_n$$.

Intuitively I can see why this is true, since $$A$$ never gets ‘trapped’ inside a subgroup.

I’m not sure how to go about proving this. If I can show that $$|A^{\oplus k}| >| A^{\oplus (k-1)}|$$, then this would be sufficient as it would eventually have to be the whole of $$\mathbb{Z}_n$$ as $$\mathbb{Z}_n$$ is finite. But I don’t know how to show this either.

• You seem to have used $n$ twice with different meanings. – Derek Holt May 18 '19 at 19:18
• Fixed it now, thank you. – the man May 18 '19 at 19:55
• This is not a direct sum; I suspect what $A^{\oplus k}$ means is the set of $k$-term sums of elements of $A$. But that is not a “direct sum”, so your title should be edited. – Arturo Magidin May 18 '19 at 20:01

First note that if $$B\subsetneq\mathbb Z_n$$ is not contained in a proper subgroup and contains $$0$$, then $$B\subsetneq B\oplus B$$: $$B\subseteq B\oplus B$$ follows since $$0\in B$$, and $$B\neq B\oplus B$$ since otherwise $$B$$ would be a subgroup of $$\mathbb Z_n$$.
So if $$B$$ is not contained in a proper subgroup and contains $$B$$, we have: $$B\subsetneq B\oplus B$$. If $$B\oplus B\neq\mathbb Z_n$$, then it is not contained in a proper subgroup (as otherwise $$B$$ would be contained in a proper subgroup) and contains $$0$$, so $$B\oplus B\subsetneq B\oplus B\oplus B\oplus B$$. And we continue. Since $$\mathbb Z_n$$ is finite, this procedure has to stop, i.e. we have some $$k$$ such that $$B^{\oplus k}= \mathbb Z_n$$.
Assume now that $$A$$ is not contained in a coset of a proper subgroup of $$\mathbb Z_n$$. Take $$a\in A$$ and consider $$B=A-a$$. Then $$B$$ is not contained in a proper subgroup (as otherwise $$A$$ would be contained in its $$a$$ coset) and $$B$$ contains $$0$$. We have $$B^{\oplus k}=\mathbb Z_n$$ by the previous analysis. On the other hand we easily see that $$A^{\oplus k}= B^{\oplus k}-ka$$, so $$A^{\oplus k}$$ is a translate of $$B^{\oplus k}$$ within $$\mathbb Z_n$$, i.e. $$A^{\oplus k}=\mathbb Z_n$$.
(Note that all calculations are in the group $$\mathbb Z_n$$.)