0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You seem to have used $n$ twice with different meanings. $\endgroup$ – Derek Holt May 18 '19 at 19:18
  • $\begingroup$ Fixed it now, thank you. $\endgroup$ – the man May 18 '19 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin May 18 '19 at 20:01
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.