Proof
For (1), by [
22, Theorem 3] a polynomial
h of degree at most 2 in
n variables in characteristic
\(p = 2\) is a permutation polynomial if and only if
h is equivalent to a polynomial of the form
\(\hat{h} (x_1, \dots , x_{n - 1}) + x_n\) or
\(\hat{h} (x_1, \dots , x_{n - 1}) + x_n^2\). Let us now consider the product
$$\begin{aligned} h (\textbf{x}) = f (\textbf{x}) \cdot g (\textbf{x}) = \left( \sum _{i = 1}^{n} a_i x_i + a \right) \cdot \left( \sum _{i = 1}^{n} b_i x_i + b \right) . \end{aligned}$$
(1)
First we observe that if
\(g = \alpha \cdot f\), where
\(\alpha \in \mathbb {F}_q^\times \), then
\(h = \alpha \cdot f^2\). In characteristic two squaring induces a permutation, so
h is a permutation polynomial. Therefore, we have to rule this case out. Now we do a case distinction on different values for the constant terms
\(a, b \in \mathbb {F}_q\).
Suppose
\(a, b = 0\), we have to make sure that for all variables
\(x_i\) such that
\(x_i^2\) is present in
h at least one mixed term
\(x_i \cdot x_j\),
\(i \ne j\), is present, then the decomposition fails. Suppose there exists a variable for which all mixed terms vanish, say
\(x_1\), but
\(x_1^2\) is present in the product. Then we must have that
$$\begin{aligned} a_1 \cdot b_2 + a_2 \cdot b_1&= 0, \\ \vdots \\ a_1 \cdot b_n + a_n \cdot b_1&= 0. \end{aligned}$$
Of course, if
\(b_j \ne 0\), then also
\(a_j \ne 0\). Now we pick two indices
\(k, l \ge 2\) such that
\(a_k, b_l \ne 0\). We want to show that
\(a_k \cdot b_l + a_l \cdot b_l = 0\). We consider the equations
$$\begin{aligned} a_1 \cdot b_k + a_k \cdot b_1&= 0, \\ a_1 \cdot b_l + a_l \cdot b_1&= 0, \\ \Longrightarrow \\ a_1 \cdot b_k \cdot a_l + a_k \cdot b_1 \cdot a_l&= 0, \\ a_1 \cdot b_l \cdot a_k + a_l \cdot b_1 \cdot a_k&= 0, \\ \Longrightarrow \\ a_1 \cdot \left( a_k \cdot b_l + a_l \cdot b_k \right)&= 0. \end{aligned}$$
Hence, the mixed term
\(x_k \cdot x_l\) must also vanish. So, if all mixed terms in
h that contain
\(x_1\) vanish but
\(a_1 \cdot b_1 \ne 0\), then all mixed terms in
h must vanish. Consequently,
$$\begin{aligned} f (\textbf{x}) \cdot g (\textbf{x}) = \left( \sum _{i = 1}^{n} a_i \cdot b_i \cdot x_i^2 \right) = \left( \sum _{i = 1}^{n} \left( a_i \cdot b_i \right) ^{1 / 2} x_i \right) ^2, \end{aligned}$$
and therefore
\(g = \alpha \cdot f\), where
\(\alpha \in \mathbb {F}_q^\times \).
Now suppose \(a \ne 0\) and \(b = 0\), then any linear term of the product polynomial h must be present in a quadratic or mixed term, so the decomposition fails. By symmetry, we can conclude the same for \(a = 0\) and \(b \ne 0\).
For the last case
\(a, b \ne 0\), we rewrite
$$\begin{aligned} h (\textbf{x}) = \hat{f} (\textbf{x}) \cdot \hat{g} (\textbf{x}) + b \cdot \hat{f} (\textbf{x}) + a \cdot \hat{g} (\textbf{x}) + a \cdot b, \end{aligned}$$
where
\(\hat{f} = f - a\) and
\(\hat{g} = g - b\). Now we have to do a subcase distinction, if
\(b \cdot \hat{f} + a \cdot \hat{g} = 0\), then we can pass to the first case
\(\hat{a}, \hat{b} = 0\) to conclude that if
h is a permutation polynomial, then
\(\hat{g} = \alpha \cdot \hat{f}\), where
\(\alpha \in \mathbb {F}_q^\times \). Consequently, this implies that
\(\alpha \cdot a + b = 0\) and that
$$\begin{aligned} g = \hat{g} + b = \alpha \cdot \hat{f} + \alpha \cdot a = \alpha \cdot f. \end{aligned}$$
On the other hand, if
\(b \cdot \hat{f} + a \cdot \hat{g} \ne 0\), then a decomposition of the form
$$\begin{aligned} h = \hat{h} (x_1, \dots , x_{n - 1}) + \lambda \cdot x_n, \end{aligned}$$
\(\lambda \in \mathbb {F}_q^\times \), is impossible, because if the linear monomial
\(x_n\) is present in
h, then the variable
\(x_n\) must also be present in at least one quadratic term of
h. So, the decomposition must be of the form
$$\begin{aligned} h = \hat{h} (x_1, \dots , x_{n - 1}) + \lambda \cdot x_n^2, \end{aligned}$$
\(\lambda \in \mathbb {F}_q^\times \), then we require that
$$\begin{aligned} a_n \cdot b + b_n \cdot a_n = 0. \end{aligned}$$
Thus, the product
\(\hat{f} \cdot \hat{g}\) may not contain any mixed terms with the variable
\(x_n\), but again this already implies that
\(\hat{g} = \alpha \cdot \hat{f}\) and also
\(\alpha \cdot a + b = 0\).
Finally, if \(g = \alpha \cdot f\), then this property is invariant under any invertible affine coordinate change of the product polynomial \(h = f \cdot g\). Further, any affine coordinate change of h will end up in one of the discussed cases. We have now established that if \(h = f \cdot g\) is equivalent to a permutation polynomial, then \(g = \alpha \cdot f\), where \(\alpha \in \mathbb {F}_q\). By negation, if \(g \ne \alpha \cdot f\), then h cannot be equivalent to a permutation polynomial.
For (2), by [
22, Theorem 2] a polynomial
f of degree at most 2 in
n variables in characteristic
\(p > 2\) is a permutation polynomial if and only if
f is equivalent to a polynomial of the form
\(g (x_1, \dots , x_{n - 1}) + x_n\). Again we do a case distinction. If
\(a, b = 0\), then trivially such a decomposition cannot exist.
Now suppose \(a \ne 0\) and \(b = 0\), then any linear term of the product must be present in a quadratic or mixed term so the decomposition fails. By symmetry, we can conclude the same for \(a = 0\) and \(b \ne 0\).
If \(a, b \ne 0\), assume that \(x_1\) is present in h. Now let us try to do the composition with \(x_1\). If \(a_1, b_1 \ne 0\), then \(x_1^2\) must also be present in h, so the decomposition is impossible. Hence, either \(a_1 \ne 0\) and \(b_1 = 0\) or \(a_1 = 0\) and \(b_1 \ne 0\). If one of them is non-zero, then there still must be a mixed term \(x_1 \cdot x_j\), \(j \ne 1\), present in h since f and g are non-constant. (Also, recall that the mixed terms containing \(x_1\) can only be canceled if \(a_1, b_1 \ne 0\).) So the decomposition fails.
Again, under any invertible affine change of coordinates we end up in one of the three cases.\(\square \)