, 2019

Solution:
Answer: $4p(p-1)$

First, notice that $(\operatorname{deg} f)(\operatorname{deg} g) = p^{2}$ and both polynomials are clearly nonconstant. Therefore there are three possibilities for the ordered pair $(\operatorname{deg} f, \operatorname{deg} g)$, which are $(1, p^{2})$, $(p^{2}, 1)$, and $(p, p)$.

In the subsequent parts of the solution, equalities are modulo $p$. If $f(x) = a x + b$, $a \neq 0$ is linear, then it is invertible so then $g$ is uniquely determined as $g(x) = f^{-1}(f(g(x))) = \frac{x^{p^{2}} - x - b}{a}$. Similarly, if $g(x) = c x + d$, $c \neq 0$ $(\bmod p)$ is linear then $f$ is uniquely determined as $f(x) = f\left(g\left(g^{-1}(x)\right)\right) = \left(\frac{x-d}{c}\right)^{p^{2}} - \left(\frac{x-d}{c}\right)$. In each case there are $p(p-1)$ compositional pairs.

The last case is $\operatorname{deg} f = \operatorname{deg} g = p$. We take the derivative of both sides (we use the formal derivative $D_{x} f(x) = \sum_{n \geq 1} n f_{n} x^{n-1}$, which satisfies the usual chain and product rules but can be used on arbitrary polynomials, including those in $\mathbb{F}_p[x]$).

Thus
$$f'(g(x)) g'(x) = p^{2} x^{p^{2}-1} - 1 = -1,$$
using that $p = 0$ in $\mathbb{F}_p$. Now $g'(x)$ and $f'(g(x))$ must both be constant polynomials. Since $g$ is nonconstant, this means that $f'(x)$ is also a constant polynomial. We must be careful here, as unlike in $\mathbb{R}$, nonlinear polynomials can have constant derivatives. From the formula of derivative, we see that $h'(x) = 0$ as a polynomial exactly when $h(x)$ is a linear combination of $1, x^{p}, x^{2p}, \ldots$ (remember that $p = 0$). Thus $f', g'$ both being constant and $f, g$ being of degree $p$ tells us
$$f(x) = a x^{p} + b x + c, \quad g(x) = d x^{p} + e x + f$$
where $a, b, c, d, e, f$ are some elements of $\mathbb{F}_p$. Now we must have
$$a\left(d x^{p} + e x + f\right)^{p} + b\left(d x^{p} + e x + f\right) + c = x^{p^{2}} - x$$
over $\mathbb{F}_p[x]$. We use the fact that $(x+y)^{p} = x^{p} + y^{p}$ as polynomials in $\mathbb{F}_p$, since the binomial coefficients $\binom{p}{j} \equiv 0 (\bmod p)$ for $1 \leq j \leq p-1$. This implies $(x+y+z)^{p} = x^{p} + y^{p} + z^{p}$. Therefore we can expand the previous equation as
$$a\left(d^{p} x^{p^{2}} + e^{p} x^{p} + f^{p}\right) + b\left(d x^{p} + e x + f\right) + c = x^{p^{2}} - x.$$
Equating coefficients, we see that
$$\begin{aligned} a d^{p} & = 1, \\ a e^{p} + b d & = 0, \\ b e & = -1, \\ a f^{p} + b f + c & = 0. \end{aligned}$$
The first and third equations imply that $a, d, b, e$ are nonzero $(\bmod p)$ and $a = d^{-p}$, $b = -e^{-1}$. Then $a e^{p} + b d = 0$ gives
$$d^{-p} e^{p} - e^{-1} d = 0$$
or $e^{p+1} = d^{p+1}$. Recalling that $e^{p-1} = d^{p-1} = 1$ in $(\bmod p)$, this tells us $d^{2} = e^{2}$ so $d = \pm e$. Furthermore, any choice of such $(d, e)$ give unique $(a, b)$ which satisfy the first three equations. Finally, once we have determined $a, b, d, e$, any choice of $f$ gives a unique valid choice of $c$.
Thus we have $p-1$ choices for $d$, two choices for $e$ after choosing $d$ (n.b. for $p=2$ there is only one choice for $e$, so the assumption $p>2$ is used here), and then $p$ choices for $f$, for a total of $2p(p-1)$ compositional pairs in this case.

Finally, adding the number of compositional pairs from all three cases, we obtain $4p(p-1)$ compositional pairs in total.

Solution:
The key step is obtaining
$$f(x) = a x^{p} + b x + c, \quad g(x) = d x^{p} + e x + f$$
in the case where $\operatorname{deg} f = \operatorname{deg} g = p$. We present an alternative method of obtaining this, with the rest of the solution being the same as the first solution. Let
$$\begin{aligned} & f(x) = f_{p} x^{p} + f_{p-1} x^{p-1} + \cdots + f_{0} \\ & g(x) = g_{p} x^{p} + g_{p-1} x^{p-1} + \cdots + g_{0} \end{aligned}$$
where $f_{p}, g_{p}$ are nonzero. Like before, we have $g(x)^{p} = g\left(x^{p}\right)$ in $\mathbb{F}_p[x]$, so
$$x^{p^{2}} - x = f_{p} g\left(x^{p}\right) + f_{p-1} g(x)^{p-1} + \cdots + f_{0}$$
Consider the maximal $k < p$ for which $f_{k} \neq 0$. (It is not hard to see that in fact $k \geq 1$, as $f_{p} g\left(x^{p}\right) + f_{0}$ cannot be $x^{p^{2}} - x$.) First assume that $k > 1$. We look at the $x^{k p - 1}$ coefficient, which is affected only by the $f_{k} g(x)^{k}$ term. By expanding, the coefficient is $k f_{k} g_{p}^{k-1} g_{p-1}$. Therefore $g_{p-1} = 0$. Then we look at the $x^{k p - 2}$ coefficient, then the $x^{k p - 3}$ coefficient, etc. down to the $x^{k p - p + 1}$ coefficient to conclude that $g_{p-1} = g_{p-2} = \cdots = g_{1} = 0$. However, then the $x$ coefficient of $f(g(x))$ is zero, contradiction.

Therefore we must have $k = 1$, so $f$ is of the form $a x^{p} + b x + c$. Using the same method as we used when $k > 1$, we get $g_{p-1} = g_{p-2} = \cdots = g_{2} = 0$, though the $x^{k p - p + 1}$ coefficient is now the $x$ coefficient which we want to be nonzero. Hence we do not obtain $g_{1} = 0$ anymore and we find that $g$ is of the form $d x^{p} + e x + f$.