Polynomials in $\mathbb{F}_{q}[x]$ invariant under translation of $x$

Question

Let $p$ be prime, $r \in \mathbb{N}_{>0}$ , $q = p^r $ and $ K := \mathbb{F}_{q}$ the finite field with $q$ elements. Let $F$ be the set of polynomials, which do not change under translation: $$ F := \{ ~f \in K[x] \mid \forall \alpha \in K ~:~ f(x) = f(x + \alpha )~ \} $$ prove that $$ F = K[ x^q - x] $$

Answer 1

The inclusion $K[x^q - x] \subseteq F$ is relatively straightforward.

Assume $f \in K[x^q - x]$ and $\alpha \in K$. Then there is a $\bar{f} \in K[x]$, with $f(x) = \bar{f}(x^q-x)$. Since $(K^\times,\cdot)$ is a group with a finite number of elements, we have that $ 1 = \alpha^{\vert K^\times \vert} = \alpha^{q-1}$. Hence we get \begin{align*} f(x + \alpha) &= \bar{f}( (x + \alpha)^q - x - \alpha ) \\ &= \bar{f}( x^q + \alpha^q - x - \alpha ) \\ &= \bar{f}( x^q + \alpha - x - \alpha ) \\ &= \bar{f}( x^q - x ) \\ &= f(x) \end{align*} Which implies $K[x^q-x] \subseteq F$.

For the other direction, let's first note a useful observation about multiplicities. For $f \in K[x]$ and $\alpha \in K$, let $\mu(f, \alpha)\in \mathbb{N}$ denote the multiplicity of $\alpha$ in $f$ (it can also be $0$). Any polynomial $p \in K[x]$ of degree $1$ is invertible, and we have $$ \mu(f, \alpha) = \mu (f \circ p^{-1}, p(α)) $$ i.e. shifting the polynomial by $p^{-1}$ will shift any zero $\alpha$ to $p(\alpha)$, and it will keep the same multiplicity. (I will leave this without proof here)

We can now immediately make use of this to show that $\mu(f, \cdot)$ is a constant function for every polynomial $f \in F$. Given $p(x) := x + (\beta - \alpha)$ we have $f \circ p^{-1} = f$ due to the translation invariance, and therefore $$ \mu(f, \alpha) = \mu( ~f \circ p^{-1}, \, p(\alpha)~) = \mu( ~f, \, \alpha + (\beta - \alpha) ~) = \mu( f, \beta) $$ We will now proceed by showing $ f \in F ~\Rightarrow~ f \in K[x^q - x] $ by strong induction on the degree of $f$. So let $f \in F$.

If $\deg f = 0$ it trivially holds that $f \in K[x^q - x]$.

Otherwise we continue by considering $\bar{f} := f - f(0)$, which has the same degree as $f$ and a root at $0$ by definition. This means $n := \mu(f, 0) > 0$ and by what we discussed above, it means every element is a root of $\bar f$ with the same multiplicity. Thus $\bar{f}$ has the following form $$ \bar{f} = g \cdot \prod_{a \in K} (x-a)^n = g \cdot \Big( \prod_{a \in K} (x-a) \Big)^n = g \cdot (x^q - x)^n $$ With $g \in K[x]$, not having any zeroes in $K$. Using once more the translation invariance of $\bar f$ we get \begin{align*} g(x) (x^q - x)^n &= \bar{f}(x) \\ &= \bar{f}(x + \alpha) \\ &= g(x + \alpha) ( (x + \alpha)^q - x - \alpha )^n \\ &= g(x + \alpha) (x^q - x)^n \end{align*} Which shows that $g \in F$. Since $n>0$ we have that $\deg g < \deg g + n q = \deg f$, which allows us to conclude $g \in K[x^q - x]$ by strong induction.

Thus there exists a $\bar{g} \in K[x]$, such that $g(x) = \bar{g}(x^q - x)$ and therefore giving us $$ f(x) = \bar{g}(x^q - x)(x^q - x)^n + f(0) \in K[x^q - x] $$ which finally establishes $F \subseteq K[x^q - x]$.