25
$\begingroup$

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

$\endgroup$
15
  • 4
    $\begingroup$ So what are your thoughts? What have you tried? $\endgroup$
    – user61527
    Aug 25, 2013 at 9:07
  • $\begingroup$ $S$ is a subgroup? $\endgroup$
    – Riccardo
    Aug 25, 2013 at 10:36
  • 1
    $\begingroup$ @RicPed - if it were, then $S^n = S$ and the problem would be trivial. $\endgroup$ 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
    Aug 25, 2013 at 11:19
  • 4
    $\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$ Aug 26, 2013 at 13:21

1 Answer 1

23
+50
$\begingroup$

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.

$\endgroup$
6
  • $\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
    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$ 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
    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$ 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
    Aug 26, 2013 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .