MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Also posted to Math StackExchange,… --- 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$.

share|cite|improve this answer
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.

share|cite|improve this answer
@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$.

share|cite|improve this answer
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

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.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.