If $|G|=n>1$, then $|{\rm Aut}(G)|\le\prod_{i=0}^k(n-2^i)$ for $k=[\log_2(n-1)]$.

Question

This is Exercise 1.5.16 of Robinson's "A Course in the Theory of Groups (Second Edition)". According to Approach0, it is new to MSE.

The Details:

The exercise comes with a hint:

Use Exercise 1.3.4.

On page 16, ibid., we have

Exercise 1.3.4: Let $d(G)$ be the smallest number of elements necessary to generate a finite group $G$. Prove that $\lvert G\rvert\ge 2^{d(G)}$.

Proof (sketch): Each element of a minimal generating set $\{g_1,\dots, g_{d(G)}\}$ of $G$ maps to two elements in $G$: itself and its inverse (assuming they are distinct), so

$$\begin{align} \lvert G\rvert &\ge \left\lvert \{{\rm itself}, {\rm inverse}\}^{\{g_1,\dots, g_{d(G)}\}}\right\rvert\\ &=2^{d(G)}. \end{align}$$ "$\square$"

(I'm aware that this sketch sweeps a lot under the rug. However, I think it illustrates the general idea.)

The Question:

On page 31, ibid., we have

Exercise 1.5.16: If $G$ has order $n>1$, then $$\lvert {\rm Aut}(G)\rvert\le\prod_{i=0}^k(n-2^i)$$ for $k=[\log_2(n-1)]$.

Thoughts:

Each automorphism of $G$ is determined by what it maps each of $G$'s generating elements $g_\lambda$ (as above) to. This is a key concept, I'm sure.

My first guess was that the $2^i$ in the product corresponds to $2^{d(H)}$ for $H\le G$ generated by a subset of the $g_\lambda$. I don't understand where $k$ comes from if this is the case though.

---

My postgraduate research degree specialises in combinatorial group theory, the study of groups as given by their presentations, so I feel as if I ought to be able to do this exercise without too much help, although I don't work with automorphism groups often.

---

I'm interested in understanding this exercise, in particular, because I think it's rather beautiful, especially with the value of $k$.

---

Perhaps I might have to give Exercise 1.3.4 some more thought in order to do the exercise at hand.

---

Please help :)

Answer 1

Hint: You are right that this exercise plays a key role. If $g_1,\ldots,g_k$ are generators of the group $G$, and $f$ is a automorphism of $G$, then $f(g_1),\ldots,f(g_k)$ are also generators of $G$. Now consider. The element $f(g_1)$ we can choose by $n-1$ ways, the element $f(g_2)$ we can choose by $n-2^1$ ways. And so on.