# If $S$ is a nonempty subset of group $G$, then $S^{|G|}$ is a subgroup of $G$.

Let $$G$$ be a group with $$|G| = n$$ and let $$\emptyset \ne S \subseteq G$$.

I want to show that $$S^n$$ is a subgroup of $$G$$ where by $$S^n$$ I mean the set $$\lbrace s_1\cdots s_n \; | \; s_i \in S\rbrace$$.

• So what are your thoughts? What have you tried?
– user61527
Aug 25, 2013 at 9:07
• $S$ is a subgroup? Aug 25, 2013 at 10:36
• @RicPed - if it were, then $S^n = S$ and the problem would be trivial. Aug 25, 2013 at 10:45
• @DerekHolt: If $G= \mathbb{Z}_3$ and $S= \{2\}$, then $S^{3}= \{0\}$ but $\langle S \rangle= \mathbb{Z}_3$. Aug 25, 2013 at 11:19
• History: OP deleted this question, asked it on MO; then undeleted it here; meanwhile, it got migrated here from MO, so there are now two copies here, this one and math.stackexchange.com/questions/476531/… Aug 26, 2013 at 13:21

Consider the powers of the subset $S$:

$$S, S^2, S^3, S^4, \ldots$$

Because $G$ is finite, there is eventually some repetition. Let $S^r = S^{r+s}$ where $s > 0$ and $r+s$ is as small as possible. Then

$$S, S^2, S^3, \ldots, S^{r-1}, S^r, S^{r+1}, \ldots, S^{r+s-1}$$

are distinct subsets of $G$. Furthermore, $\{S^r, S^{r+1}, \ldots, S^{r+s-1}\}$ is a (cyclic) subgroup of order $s$ in the semigroup of nonempty subsets of $G$. Thus it is equal to $H/K$ for some $K \trianglelefteq H \leq G$ (this is not too difficult to prove, see 3.57 in "A Course in Group Theory" by Rose). Hence $s$ divides the order of $G$.

Next note that for each $t \geq r$, we have that $S^t = S^{t+s}$. Choose $r \leq t < r+s$ so that $s$ divides $t$. Then $S^t = S^{t+t} = (S^t)^2$, so $S^t$ is a subgroup (in fact, it is the only power of $S$ that is a subgroup). Now if would suffice to prove that $|G| \geq r$. If this is the case, then $|G| - t = ks$ for some $k \geq 0$ and so $S^{|G|} = S^{t+ks} = S^t$.

Let $x \in S$. Now $xS^i \subseteq S^{i+1}$, so $|S^i| = |xS^i| \leq |S^{i+1}|$. Thus if $|S^i| = |S^{i+1}|$, then $xS^i = S^{i+1}$. Hence

$$S^{i+2} = S^{i+1}S = xS^iS = xS^{i+1} = x^2S^{i}$$

and similarly $S^{i+k} = x^kS^i$ for all $k \geq 1$. In particular when $k = |G|$, we see that $S^{i+|G|} = S^i$. Thus $i \geq r$, since $S^r$ is the first power of $S$ that repeats. So when $i < r$, we have $|S^i| < |S^{i+1}|$ which gives

$$|S| < |S^2| < |S^3| < \ldots < |S^r|$$

and so we can find at least $r$ distinct elements in $|S^r|$, which proves that $|G| \geq r$.

Related to this answer: cyclic semigroups.

• In the beginning of 2nd paragraph, is it obvious that we can choose $t$ between $r$ and $r+s$ such that $s$ divides $t$? Aug 26, 2013 at 17:25
• @Prism: There are $s$ integers $t$ such that $r \leq t < r+s$. Any set of $s$ consecutive integers is a complete set of representatives modulo $s$. This is fairly intuitive and not very difficult to prove. Aug 26, 2013 at 17:43
• Ah of course! Thanks for clarifying. I have got one more quick question. You write "If this is the case, then $|G|-t=ks$ for some $k\ge 0$." I understand $|G|-t$ is multiple of $s$ (because both $|G|$ and $t$ are multiple of $s$) but how do we know $|G|\ge t$? Is it because $t$ is the smallest multiple of $s$ that is greater than $r$? Aug 26, 2013 at 17:49
• That's basically the reason, yes. Here $|G|$ is a multiple of $s$ and $\geq r$, and $t$ is the unique multiple of $s$ such that $r \leq t < r+s$. If you have a set of $s$ consecutive integers, then distinct elements of that set are not congruent modulo $s$. Aug 26, 2013 at 17:52
• Makes sense :) I like this answer a lot. Very constructive! I am going to give bounty to this once 48 hours has passed. Aug 26, 2013 at 18:02