How large can the outer automorphism group be?

Solution 1:

This only answers your first question. The groups $(\mathbb Z_2)^k$ have the fastest growing (outer) automorphism groups possible.

We can derive a pretty good upper bound on the size of automorphism groups. In particular, first note that if $G$ is a finite group with $n$ elements, then it has a generating set $S$ of size at most $\log_2(n)$ - we can find such a generating set just by a greedy algorithm in which we start with the empty set, then repeatedly add elements not yet generated until we hit the whole group.

Then, since a group homomorphism is determined by its values on a generating set, there are at most $n^{\log_2(n)}$ endomorphisms of a group $G$. Note that if $G=(\mathbb Z_2)^k$, then $G$ has exactly $n^{\log_2(n)}=2^{k^2}$ endomorphisms and these are the only groups for which this bound is tight (since the bound on the size of the generating set is only tight if no element has order $>2$).

The number of automorphisms of $G=(\mathbb Z_2)^k$ is $$(2^{k}-2^0)(2^k-2^1)\cdots (2^k-2^{k-1})=2^{k^2}\cdot \prod_{i=1}^{k}(1-2^{-i}).$$ Since $\prod_{i=1}^{\infty}(1-2^{-i})$ converges to some positive quantity $c$, the asymptotic growth of the number of (outer) automorphisms of this family of groups grows as $c\cdot n^{\log_2(n)}$, which is a constant factor beneath the theoretical upper bound.

Addendum: Refining the argument slightly actually shows a tighter bound and shows that the groups $(\mathbb Z_2)^k$ simply have the largest automorphism groups of groups of the same size. In particular, let $G$ be a group. Pick some minimal generating set $g_1,\ldots,g_n$ and define $G_i=\langle g_1,\ldots,g_i\rangle$.

Let $n_i$ be the number of injective homomorphisms $G_i\rightarrow G$ for each $i$. Clearly $n_0=1$. Then, observe that $n_{i+1}\leq n_i \cdot (|G|-|G_{i}|)$ since injective homomorphisms $G_i\rightarrow G$ may be identified with a subset of pairs of injective homomorphisms $f:G_{i-1}\rightarrow G$ and elements $g\in G\setminus f(G_{i-1})$. Using that the size of the groups $|G_i|$ must be an ascending tower of divisors of $|G|$, one can derive better bounds on the number of automorphisms - these bounds will be tight for all vector spaces.

In fact, no other groups can make the suggested upper bound hold as an equality: A group for which this bound is tight has the property that its automorphism group acts transitively on the non-identity elements. This means every non-identity element has order $p$ for some prime. However, $p$-groups have a non-trivial center and automorphisms preserve the center. By transitivity, this means that the group must be abelian - which leaves only the finite vector spaces as candidates.