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$.
$\begingroup$ $\endgroup$
15 
- 4$\begingroup$ So what are your thoughts? What have you tried? $\endgroup$user61527– user615272013-08-25 09:07:58 +00:00Commented Aug 25, 2013 at 9:07
- $\begingroup$ $S$ is a subgroup? $\endgroup$Riccardo– Riccardo2013-08-25 10:36:47 +00:00Commented Aug 25, 2013 at 10:36
- 1$\begingroup$ @RicPed - if it were, then $S^n = S$ and the problem would be trivial. $\endgroup$Prahlad Vaidyanathan– Prahlad Vaidyanathan2013-08-25 10:45:10 +00:00Commented Aug 25, 2013 at 10:45
- 3$\begingroup$ @DerekHolt: If $G= \mathbb{Z}_3$ and $S= \{2\}$, then $S^{3}= \{0\}$ but $\langle S \rangle= \mathbb{Z}_3$. $\endgroup$Seirios– Seirios2013-08-25 11:19:53 +00:00Commented Aug 25, 2013 at 11:19
- 5$\begingroup$ 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/… $\endgroup$Gerry Myerson– Gerry Myerson2013-08-26 13:21:46 +00:00Commented Aug 26, 2013 at 13:21
| Show 10 more comments
1 Answer
$\begingroup$ $\endgroup$
6 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.
- $\begingroup$ In the beginning of 2nd paragraph, is it obvious that we can choose $t$ between $r$ and $r+s$ such that $s$ divides $t$? $\endgroup$Prism– Prism2013-08-26 17:25:55 +00:00Commented Aug 26, 2013 at 17:25
- $\begingroup$ @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. $\endgroup$Mikko Korhonen– Mikko Korhonen2013-08-26 17:43:23 +00:00Commented Aug 26, 2013 at 17:43
- $\begingroup$ 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$? $\endgroup$Prism– Prism2013-08-26 17:49:06 +00:00Commented Aug 26, 2013 at 17:49
- $\begingroup$ 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$. $\endgroup$Mikko Korhonen– Mikko Korhonen2013-08-26 17:52:54 +00:00Commented Aug 26, 2013 at 17:52
- $\begingroup$ Makes sense :) I like this answer a lot. Very constructive! I am going to give bounty to this once 48 hours has passed. $\endgroup$Prism– Prism2013-08-26 18:02:52 +00:00Commented Aug 26, 2013 at 18:02