2
$\begingroup$

How can I show that the order of $\mathrm{Aut}(G)$ is less than $(n-1)(n-2)\cdots(n-2^k)$ where $k=[\log 2(n-1)]$?

The book suggests me to use the following result:

Let $d(G)$ be the smallest number of elements necessary to generate a finite group $G$. By convention $d(G)=0$ if $|G|=1$. Then $|G| \ge 2^{d(G)}$.

Thank you so much!

  • 1
    [This question](http://math.stackexchange.com/questions/108923/upper-bounds-on-the-size-of-operatornameautg) is related.2012-05-03

2 Answers 2

0

Let $G$ be a group of order $n> 1$ and let $\{x_1, \ldots, x_{d(G)}\}$ be a minimal set of generators for $G$. Taken, however, an automorphism $f$ of $G$, then it is in particular an application bijective fixing the unit of $G$, therefore, for $f(x_1)$ there are $n-1$ choices, as the order of $G \ {1}$. Choose $f(x_1)$, for $f(x_2)$ there are $| G \setminus \langle {f(x_1 )}\rangle |$ choices because, not being $x_2$ in $\langle{x_1}\rangle$, then $f(x_2) \not\in \langle{f(x_1 )}\rangle$: so the choices for $f(x_2)$ are $n-2$ because, for the exercise above, $|\langle {f(x_1 )}\rangle | \geq 2$. Assigned values to $f(x_1)$ and $f(x_2)$, from the exercise above follows that for $f(x_3)$ there are $|G \setminus \langle{f(x_1),f(x_2 )}\rangle | \leq (n-2^2)$ choices. So proceeding, for $f(x_{d(G)})$ remain at most $(n-2^{d(G) -1})$ choices. Then $|\operatorname{Aut}(G)| \leq \prod_{i = 0}^{d (G) -1} (n-2)^i$. In conclusion, observing that $d(G) \leq log_2 (n)$ then $d(G) -1 < log_2〖(n)〗$, or $2 ^{d(G) -1} < n$; therefore $2^{d(G) -1} \leq n-1$ and thus $d(G) -1 \leq log_2(n-1)$. Then $0 \leq i \leq d(​​G) -1 \leq \lfloor log_2(n-1) \rfloor$ and exercise is proven.

5

Presumably $n = |G|$? Let $g_1,g_2,\ldots,g_m$ generate $G$, where $m=d(G)$. For $0 \le i \le m$, let $G_i$ be the subgroup of $G$ generated by $g_1,\ldots,g_i$. Then $G_0 < G_1 < \cdots G_{n-1} < G_m = G$, and the containments must all be proper, since otherwise one of the generators would be redundant. So $|G_{i+1}:G_i| \ge 2$ and hence $|G_i| \ge 2^i$ and $|G| \ge 2^m$. So $m \le \log_2(|G|)$.

Let $\alpha \in {\rm Aut}(G)$. Then there are $n-1$ possibilities for $\alpha(g_1)$. Given $\alpha(g_1),\alpha(g_2),\ldots, \alpha(g_i)$ for some $i, $\alpha(g_{i+1})$ cannot lie in the subgroup generated by $\alpha(g_1),\alpha(g_2),\ldots, \alpha(g_i)$, which has order at least $2^i$, so there at most $(n-2^i)$ possibilities for $\alpha(g_{i+1})$. Multiplying the numbers of possible $\alpha(g_i)$ together gives the required bound on $|{\rm Aut}(G)|$ (but I don't think you have got the definition of $k$ quite right).

  • 0
    m<=log2(n) not m2012-05-03