The permutation criterion for multivariate polynomial $g_{n,q}^{(\ell)}$ over finite fields

The following stronger statement holds over every finite field and for every outer polynomial.

Theorem. Let $F=\mathbb F_Q$, let $k,\ell\geq1$, and let $f\in F[X]$. Put

$$\Sigma_\ell(x_1,\ldots,x_k)=x_1^\ell+\cdots+x_k^\ell.$$

Then $f\circ\Sigma_\ell$ is a permutation polynomial in $k$ variables, meaning that each element of $F$ has exactly $Q^{k-1}$ preimages, if and only if $f$ permutes $F$ and

$$\gcd(\ell,Q-1)=1.$$

Proof. Suppose $f\circ\Sigma_\ell$ is balanced. Every $a\in F$ therefore occurs as a value of $f\circ\Sigma_\ell$, and hence as a value of $f$. Thus $f:F\to F$ is surjective and therefore bijective. Applying $f^{-1}$ to the outputs shows that $\Sigma_\ell$ itself has exactly $Q^{k-1}$ preimages above every $t\in F$.

Define

$$\mu(t)=\#\{x\in F:x^\ell=t\}.$$

On the additive group of $F$, the number of solutions of

$$x_1^\ell+\cdots+x_k^\ell=t$$

is the $k$-fold convolution $\mu^{*k}(t)$. Therefore

$$\mu^{*k}(t)=Q^{k-1}\qquad(t\in F).$$

For every nontrivial complex additive character $\chi$ of $F$, Fourier transformation gives

$$\left(\sum_{t\in F}\mu(t)\chi(t)\right)^k = \sum_{t\in F}\mu^{*k}(t)\chi(t) = Q^{k-1}\sum_{t\in F}\chi(t) =0.$$

Hence

$$\sum_{t\in F}\mu(t)\chi(t)=0$$

for every nontrivial additive character. The trivial Fourier coefficient equals

$$\sum_{t\in F}\mu(t)=Q.$$

Fourier inversion now gives $\mu(t)=1$ for every $t\in F$. Thus $x\mapsto x^\ell$ permutes $F$. Because $F^\times$ is cyclic of order $Q-1$, this is equivalent to $\gcd(\ell,Q-1)=1$.

Conversely, assume $\gcd(\ell,Q-1)=1$. Then $x\mapsto x^\ell$ permutes $F$. Given $t\in F$ and any $x_1,\ldots,x_{k-1}\in F$, there is exactly one $x_k\in F$ with

$$x_1^\ell+\cdots+x_k^\ell=t.$$

Thus $\Sigma_\ell$ is balanced, and composing with a permutation $f$ preserves balancedness.

Taking $f=g_{n,q}$ proves the conjecture and the missing implication identified in Remark 5.24.