Lagrange's theorem (Group Theory) applications

Question

How can we prove that every finite group $G$ has a generating set of size not more than $\log_2|G|$?

Can someone give me an hint.

Answer 1

The proof goes by induction on $|G|$. If $|G|=2$, then $G$ is cyclic. If $|G|>2$, let $x_1,\dots,x_n\in G$ be a minimal system of generators for $G$. If $n=1$ there is nothing to prove. Assume that $n\ge 2$. Set $G'= \langle x_1,\dots,x_{n-1}\rangle$. Then $G'$ is a nontrivial subgroup of $G$. By the induction hypothesis $G'$ has a system of generators of size $k$, say $y_1,\dots,y_k$, such that $2^k\le|G'|$. By Lagrange we have $|G|=|G'|[G:G']$ and since $[G:G']\ge 2$ we get $|G|\ge 2^{k+1}$. Since $G=\langle y_1,\dots,y_k,x_n\rangle$ we are done.

Answer 2

Consider $M≤G, M \not= G$ so that $\forall {P≤G, M\subsetneq P : M≤P≤G \implies P=G}$

I think $M$ is called a maximal subgroup of $G$.

Consider $x\notin M$, then $M \subsetneq \langle M,x \rangle \subseteq G \implies \langle M,x\rangle = G$

By induction the theorem is true for $M$.

$m=|M|$, $n=|G|$

$M$ is generated with $\log_2m$ elements $\implies G$ is generated with $\log_2 m+1$.

$m\mid n$, $ m<n \implies m≤n/2$

$\log_2m+1≤\log_2n/2 + 1=\log_2n - \log_22 + 1 =\log_2n $

The logaritm - Lets have $G=H_0\supset H_1 \supset H_2 \supset \dots \supset H_s={1}$ a chain of maximal subgroups.

Because $[H_i:H_{i-1}]≥2, i=0,1,\dots,{s-1}$, and $n=|G|=\prod_1^s[H_i:H_{i-1}]≥2*2*\dots*2=2^s \implies s≤\log_2n$

So to prove that $G$ can be generated with $≤\log_2n$ elements, lets take $x_1 \in G\setminus H_1$, and we have that $G=\langle x_1,H_1\rangle$. We continue by taking $x_2 \in H_1\setminus H_2$, and we have that $G=\langle x_1,x_2,H_2\rangle$, $\dots$, in the end we arrive at $G=\langle x_1,\dots,x_s\rangle$, with $s≤\log_2n$.