8
$\begingroup$

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.

$\endgroup$
1

4 Answers 4

9
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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 $\endgroup$ Oct 14, 2012 at 20:57
  • $\begingroup$ Moreover, the whole argument breaks down if 1 is not in X. $\endgroup$
    – Misha
    Oct 14, 2012 at 21:32
  • $\begingroup$ @Gerhard: Well, if $|G|=n$, then surely $1=x^n\in X^n$ since $X$ is nonempty. @Misha: which part breaks down? $\endgroup$ Oct 14, 2012 at 21:58
  • $\begingroup$ @Misha: Notice that I do not say $X^I$ lies in $X^{i+1}$; I speak only about cardinalities... $\endgroup$ Oct 14, 2012 at 22:28
  • 2
    $\begingroup$ @Ilya: very nice proof. I like it a lot. I do not think that anything is missing. $\endgroup$ Oct 15, 2012 at 8:07
2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ @Jérémy: "Since the order of $H$ is $\le n$, this is trivial". Could you please elaborate? $\endgroup$ Oct 14, 2012 at 9:42
  • 1
    $\begingroup$ 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$! $\endgroup$
    – M P
    Oct 14, 2012 at 10:52
  • 1
    $\begingroup$ You want $1\in X$ for this to work. $\endgroup$ Oct 14, 2012 at 11:07
  • 2
    $\begingroup$ As Benjamin implicitly says, you have only proved that $H = \cup_{j=1}^{n}X^{j}$ by this argument. $\endgroup$ Oct 14, 2012 at 11:53
  • 1
    $\begingroup$ @Geoff Robinson: I thought that in the text $n$ was the order of the group, but otherwise I agree with you! $\endgroup$
    – M P
    Oct 14, 2012 at 16:05
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Oct 15, 2012 at 16:21
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2012 at 16:34
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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