# The powers of non-empty subset of a group that generate a subgroup

If G is a group and A and B to non-empty subsets of G, then by AB we mean the set consist of all product ab where a is in A and b is in B.(Standard definition) Similarly we can define X^m where X is a non-empty subset and m is a positive integer. So X^m for positive integer m, means the set of all products of length m taken from X.

If G is a group of size n, and X is a non-empty subset of G then prove that X^n is a subgroup of G.

this is quite easy to prove for abelian groups, so I mostly like to see a short nice proof for the general case.

Consider the sets $X, X^2, \dots$. We claim that $|X^i|\leq |X^{i+1}|$, and, moreover, if $|X^i|=|X^{i+1}|$ then $|X^{i+1}|=|X^{i+2}|$. Actually, under the mapping $X^i\times X\to X^{i+1}$, $(b,x)\mapsto bx$, the preimage of any element of $X^{i+1}$ has the cardinality at most $|X|$ since all $x$-coordinates in this preimage should be distinct. Thus, $|X^i|\cdot |X|\leq |X^{i+1}|\cdot |X|$; hence $|X^i|\leq |X^{i+1}|$, and $|X^{i+1}|=|X^i|$ iff this cardinality is always $|X|$, that is -- iff $bxy^{-1}\in X^i$ for all $b\in X^i$ and $x,y\in X$. This obviously implies $cxy^{-1}\in X^{i+1}$ for all $c\in X^{i+1}$ and $x,y\in X$, and, conversely, this means that $|X^{i+1}|=|X^{i+2}|$.

Now, if $|X^n|=n$ then $X^n=G$, and the claim is trivial. Otherwise, $|X^i|=|X^{i+1}|$ for some $i\leq n-1$, and hence $|X^i|=|X^{i+1}|=\dots=|X^n|=\dots=|X^{2n}|$. Since $X^n\subseteq X^{2n}$, the latter implies that $X^n$ is a subgroup.

NB. Some background is left aside this proof. Let $H=\langle X^n\rangle$, $K=\langle X\rangle$. Since $X^{-1}\subseteq X^{n-1}$, we have $H\triangleleft K$; moreover, $XX^{-1}\subset H$, so $X$ lies in one coset modulo $H$. Hence $K/H$ is cyclic, and $X^i$ also lies in one coset modulo $H$.

Now the arguments above show that $|X^i|=|X^{i+1}|$ iff $X^i$ is a coset modulo $H$. Hence, if $k$ is the least multiple of $|K/H|$ which is not less than $|H|$, then even $X^k=H$.

• You have to be more careful with the last inclusion. You have to assert (something like) that X^n contains the identity to make sure the inclusion follows. Gerhard "Ask Me About System Design" Paseman, 2012.10.14 Oct 14, 2012 at 20:57
• Moreover, the whole argument breaks down if 1 is not in X. Oct 14, 2012 at 21:32
• @Gerhard: Well, if $|G|=n$, then surely $1=x^n\in X^n$ since $X$ is nonempty. @Misha: which part breaks down? Oct 14, 2012 at 21:58
• @Misha: Notice that I do not say $X^I$ lies in $X^{i+1}$; I speak only about cardinalities... Oct 14, 2012 at 22:28
• @Ilya: very nice proof. I like it a lot. I do not think that anything is missing. Oct 15, 2012 at 8:07

Here is an answer $\mathbf{if}$ $1\in X$:

Denote by $H$ the subgroup of $G$ being generated by $X$.

What you want is to show that $H=X^n$, which amounts to see that any element of $H$ can be written as a product of at most $n$ elements of $X$.

This follows from the fact that the size of $H$ is at most $n$:

We write an element $h$ of $H$ as a product of $m$ elements of $X$: $h=x_mx_{m-1}\dots x_1$ then we look at the elements $h_i=x_{i}\dots x_{1}$ obtained by the products of $i$ elements only. If $m>n$, there are two $h_i$'s which are equal, say $h_a=h_b$ with $a>b$. We replace $h_a$ with $h_b$ and can write $h$ with less elements.

$\mathbf{Edit}:$ If $1\notin X$, then $X^n$ is maybe not the group generated by $X$ (take for example the case where $X$ is a single element), but is in fact a subgroup, as Ilya showed.

• @Jérémy: "Since the order of $H$ is $\le n$, this is trivial". Could you please elaborate? Oct 14, 2012 at 9:42
• Just a minor detail: if $X$ consists of a single non-identity element, the group $X^n$ is actually just the identity, and not the subgroup generated by $X$!
– M P
Oct 14, 2012 at 10:52
• You want $1\in X$ for this to work. Oct 14, 2012 at 11:07
• As Benjamin implicitly says, you have only proved that $H = \cup_{j=1}^{n}X^{j}$ by this argument. Oct 14, 2012 at 11:53
• @Geoff Robinson: I thought that in the text $n$ was the order of the group, but otherwise I agree with you!
– M P
Oct 14, 2012 at 16:05

The following is a rewrite of the proof of Ilya in a different language. If you like it, upvote his answer.

Let $G$ be a finite group and $P(G)$ be the power set of $G$ which is a monoid. The idempotents of $P(G)$ are precisely the subgroups $H$ of $G$ and the group of units of the submonoid $HP(G)H$ is $N_G(H)/H$ (this is classical finite semigroups theory; google power group). This is the largest subsemigroup of $P(G)$ which is a group with identity $H$.

Let $|G|=n$ and $X\subseteq G$. By general finite semigroup theory, $X^k=X^{k+m}$ for some $k,m$ which we take to be minimal. Then $\{X^k,\ldots, X^{k+m-1}\}$ is a cyclic group with identity $X^r$ where $r$ is the unique power in that range divisible by $m$. Also $XX^j=XX^rX^j$ for $k\leq j\leq k+m-1$. Let $H=X^r$.

By the above discussion, we have that $k$ is the least power such that $X^k\in N_G(H)/H$. Observe first that $|X^{i+1}|\geq |X^i|$ because if $x\in X$, then $|X^i|=|X^ix|\leq |X^iX|=|X^{i+1}|$.

Claim. TFAE.

(1) $|X^i|=|X^{i+1}|$

(2) $|X^i|=|X^{i+j}|$ for $j\geq 0$

(3) $X^i\in N_G(H)/H$

(4) $|X^i|=|H|$.

Pf. Suppose first (3) holds. Then $|X^i|=|H|$ so (3) implies (4).

Suppose (4) holds. Then since $|H|=|X^i|\leq |X^{i+1}|\leq |X^{i+r}|=|H|$ (as $X^{i+r}\in N_G(H)/H$), it follows that $|X^i|=|X^{i+1}|$. Thus (1) holds

Suppose (1) holds and fix $x\in X$. Then $X^{i+1}\supseteq xX^i$ and $|X^{i+1}| = |X^i|=|xX^i|$. Thus $X^{i+1}=xX^i$. Assume inductively that $X^{i+j}=x^jX^i$. Then $X^{i+j+1} =X^{i+j}X=x^jX^{i+1}=x^{j+1}X^i$. Thus $|X^{i+j}|=|X^i|$ for all $j\geq 0$. So (2) holds.

Suppose (2) holds. Then since $1\in H$ we have $X^i\subseteq X^iH=X^{i+r}$ and $|X^i|=|X^{i+r}|$. Thus $X^i=X^{i+r}\in N_G(H)/H$. This proves the claim.

It now follows that the chain $|X^1|\leq |X^2|\leq \cdots$ stabilizes from $|X^{|H|}|$ and onwards and that $X^{|H|}\in N_G(H)/H$. Thus $(X^{|H|})^{[N_G(H):H]}=H$ and so $X^n=H$ as $|H|[N_G(H):H]=|N_G(H)|$ divides $n$.

• I like the intent, but not the execution. My first two quibbles are for sake of clarity: P(G) becomes a monoid (or hypergroup or whatever) when you take the appropriate generalization of the operation of G with the set P(G). (A.k.a. I think most know of P(G) as a set and need more reminding of the operation than "google power group" to turn P(G).) Also, it is not clear if / in NG(H)/H is quotient or set difference. I am leaning toward the latter through type checking, but it would be better to be more explicit. Gerhard "Ask Me About Getting Confused" Paseman, 2012.10.15 Oct 15, 2012 at 16:21
• Gerhard: the power of a semigroup is a semigroup by AB=all products ab with a in A and b in B. I meant quotient not set difference. Oct 15, 2012 at 16:34

I would proove the task as follows for the case $1\in X$:

• If $X$ is a non-empty subset such that there exist an $k\in \mathbb{N}$ such that for all $m\in \mathbb{N}$ the equality $X^{m+k}=X^k$, then $X^k$ is a subgroup: as $X$ is non-empty so is $X^k$. In addition, $X^kX^k=X^k$ by our assumption. As $G$ is finite we are done.
• Why does such an $k$ exist and why is $n$ sufficient for this? In the case where $1\in X$ we have a ascending chain of subsets $X\le X^2\le ... \le X^n$. If all subsets are different $X^n$ reaches $G$ as $G$ has $n$ elements. Then we are done. Otherwise we have that the chian is stable and we are done as well.