The powers of non-empty subset of a group that generate a subgroup - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:39:00Z http://mathoverflow.net/feeds/question/109590 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109590/the-powers-of-non-empty-subset-of-a-group-that-generate-a-subgroup The powers of non-empty subset of a group that generate a subgroup katie 2012-10-14T09:19:02Z 2012-10-15T15:35:11Z <p>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.</p> <p><strong>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.</strong></p> <p>this is quite easy to prove for abelian groups, so I mostly like to see a short nice proof for the general case.</p> http://mathoverflow.net/questions/109590/the-powers-of-non-empty-subset-of-a-group-that-generate-a-subgroup/109593#109593 Answer by Jérémy Blanc for The powers of non-empty subset of a group that generate a subgroup Jérémy Blanc 2012-10-14T09:31:55Z 2012-10-15T08:09:24Z <p>Here is an answer $\mathbf{if}$ $1\in X$:</p> <p>Denote by $H$ the subgroup of $G$ being generated by $X$.</p> <p>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$. </p> <p>This follows from the fact that the size of $H$ is at most $n$:</p> <p>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.</p> <p>$\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.</p> http://mathoverflow.net/questions/109590/the-powers-of-non-empty-subset-of-a-group-that-generate-a-subgroup/109652#109652 Answer by Ilya Bogdanov for The powers of non-empty subset of a group that generate a subgroup Ilya Bogdanov 2012-10-14T20:39:55Z 2012-10-14T23:26:52Z <p>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}|$.</p> <p>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.</p> <p><b>NB.</b> 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$. </p> <p>Now the arguments above show that $|X^i|=|X^{i+1}|$ iff $X^i$ <b>is</b> 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$.</p> http://mathoverflow.net/questions/109590/the-powers-of-non-empty-subset-of-a-group-that-generate-a-subgroup/109732#109732 Answer by Benjamin Steinberg for The powers of non-empty subset of a group that generate a subgroup Benjamin Steinberg 2012-10-15T15:35:11Z 2012-10-15T15:35:11Z <p>The following is a rewrite of the proof of Ilya in a different language. If you like it, upvote his answer.</p> <p>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$. </p> <p>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$. </p> <p>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}|$. </p> <p><strong>Claim</strong>. TFAE.</p> <p>(1) $|X^i|=|X^{i+1}|$</p> <p>(2) $|X^i|=|X^{i+j}|$ for $j\geq 0$</p> <p>(3) $X^i\in N_G(H)/H$</p> <p>(4) $|X^i|=|H|$.</p> <p>Pf. Suppose first (3) holds. Then $|X^i|=|H|$ so (3) implies (4).</p> <p>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</p> <p>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.</p> <p>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.</p> <p>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$.</p>