Irreducible Factorization of polynomial functions in finite fields

Question

What is known about irreducible factorization of functions $f:F_q\rightarrow F_q$ where $F_q$ is a finite field. It is well known from Lagrange interpolation and the fact that $F_q$ is the splitting field of the polynomial $X^q-X$, that the functions $f$ are polynomial functions in the coset $x=X+(X^q-X)$ hence are polynomials of at most $\deg q-1$ in $x$. Factorization of such $f$ of interest is in terms of compositional products $f(g(x))$ of functions. So the questions are: how to establish existence of an irreducible factorization in composition, is such a factorization unique, how to compute such factorization etc. Most of the literature on polynomial factorization considers factorization of polynomials $f(X)$ in $F_q[X]$ in polynomial products and compositions where $X$ is an indeterminate. So what are known results for factoring $f(x)$ in compositional factors which are also functions in $F_q$?

Answer 1

For short notation, I write $H$ for the set of all functions from $F_q$ to $F_q$. This set endowed with composition $\circ$ of functions forms a monoid with identity $1 = id_{F_p}$. $H$ is the monoid in which you wanted to factorize.

Before we start thinking about factorizations, we should recall what a factorization is: If $S$ is a monoid and $a \in S$, then $a = \varepsilon u_1...u_n$, where $\varepsilon$ is a unit of $S$ (invertible in $S$) and $u_1,...,u_n$ are irreducible elements of $S$, is called a factorization of $a$. Recall that an element $u \in S$ is called irreducible if it is not a unit and $u = ab$ implies that $a$ is a unit or $b$ is a unit, for all $a,b \in S$.

So the first two things to ask before we can even start to factorize are:

1. What are the units of $(H,\circ)$?
2. What are the irreducible elements of $(H,\circ)$?

ad 1.: It is well-known and easy to show that the invertible functions (and therefore the units in our monoid) are exactly the bijective ones. Since $F_q$ is finite, we have that $f \in H$ is invertible iff it is bijective iff it is injective iff it is surjective.

ad 2.: Since we now know how the units of $H$ look like, we can think of what are the irreducibles in $H$. Before we do this, we can't say anything about factorizations, because we don't know into which elements we should factorize. By the definition of irreducible, a function $f \in H$ is non-irreducible iff it is a unit or there exist functions $g,h \in H$ which are non-bijective and such that $f = h \circ g$.

Claim: $(H,\circ)$ has no irreducible elements. In particular, it makes no sense to talk about factorizations in the classical manner.

Proof: Let $f \in H$. If $f$ is injective, then $f$ is bijective and hence a unit in $H$. So it is non-irreducible per definition. Now let $f$ be non-injective. We construct two explicit non-injective functions $g,h \in H$ such that $f = h \circ g$. This then shows that $f$ is not irreducible.

First of all set $h := f$. For the construction of $g$, define an equivalence relation $\sim$ on $F_q$, namely $i \sim j$ iff $f(i) = f(j)$ for $i,j \in F_q$. Denote by $c_1,...,c_n$ the equivalence classes of $F_q$ modulo $\sim$ and by $m_k = \min c_k$ the minimum of each individual equivalence class. Now define $g(i) := m_k$ iff $c_k$ is the unique equivalence class with $i \in c_k$. Since $f$ is non-injective, there exist $i,j \in F_q$ such that $f(i) = f(j)$ but $i \neq j$. Therefore $i \sim j$, say the equivalence class of both is $c_k$. Then $g(i) = m_k = g(j)$, so $g$ is non-injective and therefore no unit.

We claim that $h \circ g = f$. Let $i \in F_q$ and $c_k$ the unique class with $i \in c_k$. Then $(h \circ g)(i) = f(g(i)) = f(m_k) = f(i)$, because $i \sim m_k$. Finally, we have that $f$ is non-irreducible, which proves our claim.