Polynomials in $\mathbb{F}_{q}[x]$ invariant under translation of $x$ 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]
$$
 A: 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]$.
