¿Por qué es el tamaño mínimo de un set de generación de energía para un determinado grupo en la mayoría de las $\log_2 n$?

Question

Parece ser que se sabe que el tamaño mínimo de un set de generación de energía para un grupo finito de orden $n$ es en la mayoría de las $\log_2 n$. Puede alguien explicar por qué esto es cierto?

Edit: se observó que el logaritmo de base 2, y $n$ representa el orden del grupo.

Answer 1

Si $G$ es un grupo finito, y $\{g_1,\ldots,g_m\}$ es un conjunto mínimo de generadores, vamos a $G_n = \langle g_1,\ldots,g_n \rangle$. Entonces por minimality $g_k \ne e$ todos los $k$, e $g_{n+1} \notin G_n$ todos los $n$. A continuación, $G_{n+1}$ contiene al menos los dos disjuntas cosets $eG_n=G_n$$g_{n+1}G_n$$G_n$, lo $|G_{n+1}| \ge 2|G_n|$. Por inducción $|G| = |G_m| \ge 2^m$, lo $m \le \log_2 |G|$. Esta desigualdad es fuerte para $G = \mathbb{Z}_2^m$.

Answer 2

Pensar sobre el grupo más pequeño que las necesidades de $r$ generadores - usted encontrará que cada generador es de orden 2, y que el grupo tiene orden de $2^r$ (esto no es una prueba, sino una indicación de un método). Su declaración es la única verdadera, por lo tanto, si su logaritmos están siendo llevados a la base 2.