# If $|G| = 2^n$, then there is a subset $S$ of cardinality $n$ such that $S$ generates $G$.

Let $G$ be a group and suppose that $|G| = 2^n$. Prove that there is a subset $S$ of cardinality $n$ such that $S$ generates $G$.

All I really have so far is that I know a subset $S$ of elements of a group $G$ generates $G$ if $S$ has the property that every element in $G$ can be written as a (finite) product of elements of $S$.

Also, don't we have by Lagrange that $G$ has a subgroup $H$ such that the order of $H$ divides the order of $G$. But we are only asked for a subset of $G$ that generates $G$.

I can't figure out how we have S. Would we prove by induction, maybe?

• Try induction? Can $G$ be a simple group, or must it have a normal subgroup? Commented Dec 27, 2014 at 0:57
• All we're given is that G is a group of order $2^n$. Commented Dec 27, 2014 at 0:57
• Right, but can a group of order $2^n$ be simple, if $n>1$? There are theorems that say it can't but you obviously can't use them if you haven't seen them yet. Commented Dec 27, 2014 at 0:58
• Hints: Take a maximal subgroup $M$ of $G$ ( this is a proper subgroup by definition). Then $M$ has order $2^{m}$ for some $m < n.$ Also $G$ can be generated by $M$ and any element $x \in G \backslash M$. Commented Dec 27, 2014 at 1:01
• This is sort-of a duplicate of math.stackexchange.com/questions/114931/… - that question asks a specific instance of this, but the answers there apply equally well here. Commented Dec 27, 2014 at 5:39

We can prove this is true for any group of order $p^n$ with $p$ prime. If $n=1$, then the group must be cyclic, so the result holds. Otherwise, let $x_1,x_2,\ldots,x_m$ be a minimal generating set. Then $x_1,x_2,\ldots,x_{m-1}$ generates a proper subgroup, say of order $p^k$. By induction, this subgroup has a generating set $y_1,y_2,\ldots,y_k$ with $k$ elements. Then $y_1,y_2,\ldots,y_k,x_m$ are $k+1\leq n$ elements that generate the whole group.

Yes. Induction should work.

For a group of order $2^1$ just take the non identity element (or you can start the induction at $n=0$ using the empty set to generate the trivial group).

Now assume the statement is true for groups of order $2^{n-1}$. Take a group of order $2^n$. Select a subgroup of order $2^{n-1}$ (this exists because it's a p-group). This subgroup is generated by $n-1$ elements (using the inductive hypothesis).

Take any element of your group outside of this subgroup and tack that element onto the set of generators. This set of $n$ elements generates at least the subgroup plus one more element. But there aren't any divisors of 2 between $2^{n-1}+1$ and $2^n$, so these elements must generate the whole group.

More generally, if $G$ is a group of order $p_1p_2\dots p_n$ where $p_1,p_2,\dots,p_n$ are primes, not necessarily distinct, then $G$ is generated by a subset of cardinality at most $n$.

Proof. Let $S=\{x_1,x_2,\dots,x_m\}$ be a minimal generating set, and let $n_i=|\langle x_1,x_2,\dots,x_i\rangle|$. then $1\lt n_1\lt n_2\lt\cdots\lt n_m$ is a chain in the lattice of divisors of $p_1p_2\dots p_n$. Thus each $n_i$ is a product of at least $i$ primes, and so $n_m$ is a product of at least $m$ primes, whence $m\le n$.