Sum of subsets is the whole set?

76 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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