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

-
Also posted to Math StackExchange, math.stackexchange.com/questions/212076/… --- with no cross-reference on either site. Shame. –  Gerry Myerson Oct 14 '12 at 11:48

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 –  Gerhard Paseman Oct 14 '12 at 20:57
Moreover, the whole argument breaks down if 1 is not in X. –  Misha Oct 14 '12 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? –  Ilya Bogdanov Oct 14 '12 at 21:58
@Misha: Notice that I do not say $X^I$ lies in $X^{i+1}$; I speak only about cardinalities... –  Ilya Bogdanov Oct 14 '12 at 22:28
@Ilya: very nice proof. I like it a lot. I do not think that anything is missing. –  Jérémy Blanc Oct 15 '12 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? –  Mikhail Borovoi Oct 14 '12 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 '12 at 10:52
You want $1\in X$ for this to work. –  Benjamin Steinberg Oct 14 '12 at 11:07
As Benjamin implicitly says, you have only proved that $H = \cup_{j=1}^{n}X^{j}$ by this argument. –  Geoff Robinson Oct 14 '12 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 '12 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 –  Gerhard Paseman Oct 15 '12 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. –  Benjamin Steinberg Oct 15 '12 at 16:34