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

Question

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?

Please help.

Answer 1

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.

Answer 2

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.

Answer 3

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