Is every finite group the outer automorphism group of a finite group?

Yes.

For each finite group $Q$ I'll construct a finite group $H$ with $\mathrm{Out}(H)\simeq Q$, moreover $H$ will be constructed as a semidirect product $D\ltimes P$, with $P$ a $p$-group of exponent $p$ and nilpotency class $<p$, (with prime $p$ arbitrary chosen $>|Q|+1$) and $D$ abelian of order coprime to $p$ (actually $D$ being a power of a cyclic group of order $p-1$).

---

I'll use Lie algebras which are convenient tools to encode $p$-groups when $p$ is less than the nilpotency class, taking advantage of linear algebra.

In Lie algebras, we denote $[x_1,\dots,x_m]=[x_1,[x_2,\dots,[x_{m-1},x_m]\cdots]]$. Also I choose the convention to let permutations act on the left.

The base field is $K=\mathbf{F}_p$, $p$ prime. Fix $n\ge 1$. Let $\mathfrak{f}_n$ be the free Lie $K$-algebra on generators $(e_1,\dots,e_n)$. It admits a unique grading in $\mathbf{Z}^n$ such that $e_i$ has degree $E_i$, where $(E_i)$ is the canonical basis of $\mathbf{Z}^n$, it is called multi-grading. For instance, $[e_3,[e_1,e_3]]$ has multi-degree $(1,0,2,0,\dots,0)$.

Let $I$ be a finite-codimensional multi-graded ideal contained in $[\mathfrak{f}_n,\mathfrak{f}_n]$: so the quotient $\mathfrak{g}=\mathfrak{f}_n/I$ is naturally multi-graded. There is a natural action of ${K^*}^n$ on $\mathfrak{g}$: namely $(t_1,\dots,t_n)$ acts on $\mathfrak{g}_{(m_1,\dots,m_n)}$ by multiplication by $\prod_{i=1}^n t_i^{m_i}$. Let $D\subset\mathrm{Aut}(\mathfrak{g})$ be the image of this action. Also denote by $c$ the nilpotency class of $\mathfrak{g}$: we assume $p>c$.

Using that $p>c$, we endow, à la Malcev–Lazard, $\mathfrak{g}$ with the group law given by the Baker-Campbell-Hausdorff formula: $xy=x+y+\frac12[x,y]+\dots$. We thus view $\mathfrak{g}$ as both a Lie algebra and a group; we denote it as $G$ when endowed with the group law (but feel free to refer to the Lie algebra law in $G$); this is a $p$-group of exponent $p$ and nilpotency class $c<p$. Define $H=D\ltimes G$.

Every permutation $\sigma\in\mathfrak{S}_n$ induces an automorphism $u_\sigma$ of $\mathfrak{f}_n$, defined by $u_\sigma(e_i)=e_{\sigma(i)}$. Write $\Gamma_I=\Gamma_{\mathfrak{g}}=\{\sigma\in\mathfrak{S}_n:u_\sigma(I)=I\}$.

Proposition 1. The natural map $\Gamma_\mathfrak{g}\to\mathrm{Out}(H)$ is an isomorphism.

We need a lemma:

Lemma 2. Define $M$ as $\mathbf{F}_p^*\ltimes\mathbf{F}_p$. Then $\mathrm{Out(M^n})$ is reduced to the symmetric group permuting the $n$ factors.

Proof. Let $f$ be an automorphism. This is a product of $n$ directly indecomposable center-free abelian groups, hence its automorphism group permutes the $n$ (isomorphic) factors. Hence after composing with a permutation, we can suppose that $f$ preserves each factor. We are then reduced to checking that every automorphism of $\mathbf{F}_p^*\ltimes\mathbf{F}_p$ is inner. Indeed after composing by an inner automorphism, we can suppose that it maps the Hall subgroup $\mathbf{F}_p^*$ into itself. Then after composing with an inner automorphism, we can also suppose it acts as identity on $\mathbf{F}_p$. It easily follows that this is the identity. (Note for conciseness I used some slightly fancy results in this proof, but this lemma can be checked more elementarily.) $\Box$

Proof of the proposition. After composing with an inner automorphism, we can suppose that $f$ maps the Hall subgroup $D$ into itself.

Next, $f$ induces an automorphism of $H/[G,G]$, which can naturally be identified with $M^n$ of the previous lemma (recall that $I\subset [G,G]=[\mathfrak{g},\mathfrak{g}])$. Hence after composing with conjugation by some element of $D$, we can suppose that $f$ both preserves $D$ and acts on $H/[G,G]\simeq M^n$ by permuting the factors (without changing coordinates). Hence $f$ acts as the identity on $D$, and $f(e_i)=e_{\sigma(i)}+w_i$ for all $i$, with $w_i\in [G,G]$ ($+$ is the Lie algebra addition). Now, for $d\in D$, we have $f(d)=d$, so $f(de_id^{-1})=df(e_i)d^{-1}$. Choose $d$ as the action of $(t,\dots,t)$. Then this gives $t(e_{\sigma(i)}+w_i)=te_{\sigma(t)}+df(w_i)d^{-1}$. Hence $w_i$ is an eigenvector for the eigenvalue $t$ in $[\mathfrak{g},\mathfrak{g}]$, on which $d$ has the eigenvalues $(t^2,t^3,\dots,t^c)$. Choosing $t$ of order $p-1$, we see that $t$ is not an eigenvalue, and hence $w_i=0$. Hence up to inner automorphisms, every automorphism of $H$ is induced by permutation of the $n$ coordinates. Necessarily such a permutation has to be in $\Gamma_\mathfrak{g}$. $\Box$.

To conclude we have to prove:

Proposition 3. For every finite group $Q$ of order $n$ and prime $p>n+1$ there exist $n,p$ and $I$ finite-codimensional multi-graded ideal in $\mathfrak{f}_n(=\mathfrak{f}_n(\mathbf{F}_p)$, such that $\Gamma_I\simeq Q$. (And such that $\mathfrak{f}_n/I$ has nilpotency class $\le n+1$.)

This starts with the following, which provides for each finite group $Q$ a relation whose automorphism group is the group $L_Q\subset\mathfrak{S}(Q)$ of left translations of $Q$.

Lemma 4. Let $Q$ be a group, $n=|Q|$, and $q=(q_1,\dots,q_n)$ an injective $n$-tuple of $Q$. Define $X=Qq\subset Q^n$. Then $L_Q=\{\sigma\in\mathfrak{S}(Q):\sigma X=X\}$.

Proof. Clearly $L_Q$ preserves $X$. Conversely, if $\sigma$ preserves $X$, after composing with a left translation we can suppose that $\sigma(q_1)=q_1$, so $\sigma(q)\in\{q_1\}\times Q^{n-1}$; since $X\cap \{q_1\}\times Q^{n-1}=\{q\}$, we deduce $\sigma(q)=q$, which in turn implies $\sigma=\mathrm{Id}$. $\Box$.

Proof of the proposition. Write $\mathfrak{f}_Q\simeq\mathfrak{f}_n$ as the free Lie algebra over the generating family $(e_q)_{q\in Q}$. It can be viewed as graded in $\mathbf{Z}^G$, with basis $(E_q)_{q\in Q}$. Write $E=\sum_q E_q$.

For $q\in Q^n$, define $\xi_q=[e_{q_n},e_{q_1},e_{q_2},\dots,e_{q_n}]$ (note that it is homogeneous of degree $E+E_{q_n}$; in particular $(\xi_h)_{h\in X}$ is linearly independent. Fix an injective $n$-tuple $q$ and define $X$ as in the proof of the lemma; for convenience suppose $q_n=1$. Define $J$ as the $n$-dimensional subspace of $\mathfrak{f}_Q$ with basis $(\xi_h)_{h\in X}$.

Define $I=J\oplus \mathfrak{f}_Q^{n+2}$, where $\mathfrak{f}_Q^i$ is the $i$-th term in the lower central series. Hence $I$ is an ideal, and $\mathfrak{g}=\mathfrak{f}_Q/I$ is defined by killing all $i$-fold commutators for $i\ge n+1$ and certain particular $(n+1)$-fold commutators. (Since we assume $p>n+1$, we can view it as a group as previously.)

Claim. For $h=(h_1,\dots,h_n)\in Q^n$ with $h_{n-1}\neq h_n$, we have $\xi_h\in I$ if and only if $h\in X$.

By definition, $h\in X$ implies the condition. Now suppose that $h$ satisfies the condition. First, the condition $h_{n-1}\neq h_n$ ensures that $\xi_h\neq 0$; it is homogeneous in the multi-grading. If it belongs to $J$, its multi-degree is therefore some permute of $(2,1,\dots,1)$. This is the case if and only if the $h_i$ are pairwise distinct, so we now assume it; its degree is therefore equal to $E_{h_n}+E$. Now $J_{E+E_{h_n}}$ is 1-dimensional, and generated by $\xi_{h_nq}$. Hence $\xi_h$ is a scalar multiple of $\xi_{h_nq}$: $$[e_{h_n},e_{h_1},\dots,e_{h_{n-1}},e_{h_n}]=\lambda [e_{h_n},e_{h_nq_1},\dots,e_{h_nq_{n-1}},e_{h_n}].$$ The next lemma implies that $h_i=h_nq_i$ for all $i\in\{1,\dots,n-1\}$. So $h\in X$. The claim is proved.

The claim implies that for every permutation $\sigma$ of $Q$, if the automorphism $u_\sigma$ of $\mathfrak{f}_Q$ preserves $I$, then $\sigma$ has to preserve $X$, and hence (Lemma 4) $\sigma$ is a left translation of $Q$. This finishes the proof. $\Box$.

Lemma 5 Consider the free Lie algebra on $(e_1,\dots,e_n)$. If for some permutation $\sigma$ of $\{1,\dots,n-1\}$ and scalar $\lambda$ we have $$[e_n,e_1,\dots,e_{n-1},e_n]=\lambda [e_n,e_{\sigma(1)},\dots,e_{\sigma(n-1)},e_n],$$ then $\sigma$ is the identity and $\lambda=1$.

Proof. Use the representation $f$ in $\mathfrak{gl}_n$ mapping $e_i$ to the elementary matrix $\mathcal{E}_{i-1,i}$ (consider indices modulo $n$). Then $[e_n,e_1,\dots,e_{n-1},e_n]=[e_n,e_1,[e_2,\dots,e_n]]$ maps to $$[\mathcal{E}_{n-1,n},\mathcal{E}_{n,1},\mathcal{E}_{1,n}]=[\mathcal{E}_{n-1,n},\mathcal{E}_{n,n}-,\mathcal{E}_{1,1}]=\mathcal{E}_{n-1,n}.$$ Let by contradiction $j$ be maximal such that $\sigma(j)\neq j$; note that $2\le j\le n-1$ and $n\ge 3$. Then $[e_n,e_{\sigma(1)},\dots,e_{\sigma(n-1)},e_n]=[e_n,e_{\sigma(1)},\dots,e_{\sigma(j)},[e_{j+1},\dots,e_n]]$ maps to $$w=[\mathcal{E}_{n,n-1},\mathcal{E}_{\sigma(1)-1,\sigma(1)},\dots,\mathcal{E}_{\sigma(j)-1,\sigma(j)},\mathcal{E}_{j,n}],$$ which cannot be zero. Hence $[\mathcal{E}_{\sigma(j)-1,\sigma(j)},\mathcal{E}_{j,n}]\neq 0$. Since $\sigma(j)<j$, this implies $\sigma(j)-1=n$ (modulo $n$), that is, $\sigma(j)=1$. So $$w=-[\mathcal{E}_{n,n-1},\mathcal{E}_{\sigma(1)-1,\sigma(1)},\dots,\mathcal{E}_{\sigma(j-1)-1,\sigma(j-1)},\mathcal{E}_{j,1}].$$ In turn, $[\mathcal{E}_{\sigma(j-1)-1,\sigma(j-1)},\mathcal{E}_{j,1}]$, using that $\sigma(j-1)\neq 1$, implies $\sigma(j-1)=j$, and so on, we deduce that $\sigma$ is the cycle $j\mapsto j+1$ (modulo $n-1$). Eventually we obtain $$w=[\mathcal{E}_{n-1,1},\mathcal{E}_{1,2},\mathcal{E}_{2,1}]=\mathcal{E}_{n-1,1}.$$ So $\mathcal{E}_{n-1,n}=\lambda \mathcal{E}_{n-1,1}$, contradiction.

(Note on Lemma 5: one has $[e_1,e_2,e_1,e_2]=[e_2,e_1,e_1,e_2]$, but this and its obvious consequences are probably the only identities between Lie monomials in the free Lie algebra, beyond the ones obtained from skew-symmetry in the last two variables.)

Note on the result: the resulting group $H$ roughly has size $|Q|^{|Q|}$, which is probably not optimal.

In Proposition 4, $I$ is strictly contained in $\mathfrak{f}_Q^{n+1}$, as soon as $|Q|\ge 3$, so the nilpotency class of $G$ is then equal to $n+1$. (For $|Q|=1$, choosing $p\ge 3$ outputs $H$ as the group $M=M_p$ which has trivial Out, and $G$ is abelian then; for $|Q|=2$, this outputs a group $H$ of order $(p-1)^2.p^3$ for chosen prime $p\ge 5$, and $G$ has nilpotency length $2$. For $|Q|=3$ it outputs a group $H$ of order $(p-1)^3.p^{29}$ for $p\ge 5$ which is already quite big.) To improve the bounds in explicit cases by running this method, one should describe $Q$ a permutation group of a set $Y$ that can be described as stabilizer of some $\ell$-ary relation $R$ contained in the set of pairwise distinct $\ell$-tuples of $Y$, for $\ell$ as small as possible.

In [Bryant, R. M.; Kovács, L. G., Lie representations and groups of prime power order. J. London Math. Soc. (2) 17 (1978), no. 415-421], the authors come close to proving what you ask: they show that any group $G < GL(V)$, with $V$ an elementary abelian $p$-group, can be realized as the image of $Aut(P) \rightarrow Aut(P/\Phi(P)) = GL(V)$, for some finite $p$--group $P$ with Frattini quotient $P/\Phi(P) = V$.

I used this in a paper with Frank Adams in the late 1980's, and we also reference Theorem 13.5 of Huppert and Blackburn, Finite Groups II. Section 13 of that book is all about automorphisms of $p$--groups. My memory (30 years old) is that exactly the result you are interested in was proved there. (This is not available online, so I can't easily check this right now.)

Added a little bit later: I should perhaps have explicitly pointed out that the map $Aut(P) \rightarrow Aut(P/\Phi(P))$ factors through $Aut(P) \rightarrow Out(P)$. Also the kernel of this map is a $p$--group: see e.g. [ (24.1), Aschbacher, Finite Group Theory ]. So one knows that, for any prime $p$, any finite group is the quotient of $Out(P)$ for some finite $p$--group $P$, with another $p$--group as kernel.