Maps compatible with the Frobenius Let $F$ be a field. Fix a separable closure $F^{sep}$. Consider the monoid whose elements are maps of sets $F^{sep} \to F^{sep}$ which are equivariant with respect to the Galois action. These maps preserve $F$. I ask myself if it is possible to describe the structure of this monoid for specific examples of $F$. It always contains an image of $F[x]$, but it may be larger. For example for $F=\mathbb{R}$ we look at maps $f : \mathbb{C} \to \mathbb{C}$ with $f(\overline{z})=\overline{f(z)}$. And these in turn correspond to maps $\{\mathrm{Im} \geq 0\} \to \mathbb{C}$ that map $\mathbb{R}$ into itsself. So there are lots of them and the monoid is quite boring.
But what happens for other fields, for example the finite field $\mathbb{F}_q$ with $q$ elements? Then we look at maps $f : \overline{\mathbb{F}_q} \to \overline{\mathbb{F}_q}$ with $f(a^q)=f(a)^q$. In particular $a^{q^n}=a \Rightarrow f(a)^{q^n}=f(a)$, i.e. $f(\mathbb{F}_{q^n}) \subseteq \mathbb{F}_{q^n}$. So one might first try to classify the self-maps of $\mathbb{F}_{q^n}$ which are compatible with the Frobenius.
 A: A partial answer summarizing the more or less obvious things.
Let $f$ be a Frobenius compatible mapping from $M=\overline{\mathbb{F}_q}$ to itself, and let $\phi:M\to M$ be the Frobenius automorphism $\phi(z)=z^q$.  If an element $z\in M$ has $k$ conjugates, then these are $\phi^i(z),i=0,1,\ldots,k-1$, and $\phi^k(z)=z$. Therefore $\phi^k(f(z))=f(\phi^k(z))=f(z)$. Consequently the number of conjugates, call it $\ell$, of the element $f(z)$ must be a factor of $k$. 
Let us consider the restriction $f_m$ of $f$ to $L=\mathbb{F}_{q^m}$. The number of conjugates an element $z\in L$ can have is a factor of $m$. By the preceding paragraph the same holds of $f(z)$. Therefore $f(z)\in L$. By Lagrange interpolation formula any mapping from $L$ to itself is a polynomial function of degree $<q^m$ with coefficients in $L$. So we know that there exist (unique!) constants $a_{i,m}\in L$ such that
$$
f_m(z)=\sum_{i=0}^{q^m-1}a_{i,m} z^i
$$
for all $z\in L$. Here $\phi$ generates the group of $F$-automorphisms, so such a polynomial function is compatible with Frobenius, if and only if
$$
\sum_{i=0}^{q^m-1}a_{i,m}^qz^{qi}=\phi(f_m(z))=f_m(z^q)=\sum_{i=0}^{q^m-1}a_{i,m}z^{qi}
$$
for all $z\in L$. As the variable $z$ ranges over $L$, we can reduce the exponents $qi$ modulo $q^m-1$ without changing the function. The result is, again, a polynomial function of degree $<q^m$, whence the coefficients are uniquely determined. So we can conclude that such a polynomial is compatible with Frobenius, if and only if $a_{i,m}=a_{i,m}^q$ for all $i, 0\le i <q^m$. 
In other words all the coefficients $a_{i,m}$ must be elements of $F$.
Let us next compare two such restrictions $f_m$ and $f_n$ with $n\mid m$. Denote
$E=\mathbb{F}_{q^n}$. For all $z\in E$ we have $z^{q^n}=z$, so writing an
exponent $i$ in the range $0<i<q^m$ in the form $i=j+k(q^n-1)$ with $0<j<q^n$ and $0\le k<(q^m-1)/(q^n-1)$, we get $z^i=z^j$ for all $z\in E$ and all $i>0$.
So
$$
f_m(z)=a_{0,m}+\sum_{i=1}^{q^m-1}a_{i,m}z^i=a_{0,m}+\sum_{j=1}^{q^n-1}\left(z^j\sum_{k=0}^{(q^m-1)/(q^n-1)}a_{j+k(q^n-1),m}\right).
$$
We see that $f_m$ restricted to $E$ agrees with $f_n$, iff $a_{0,m}=a_{0,n}$ and
$$
a_{j,n}=\sum_{k=0}^{(q^m-1)/(q^n-1)}a_{j+k(q^n-1),m}
$$
for all $j,0<j<q^n$.
As $M$ is the union of the fields $\mathbb{F}_{q^m}, m>0$ (with suitable identifications in place for pairs of integers such that $n\mid m$),
we can conclude that the Frobenius compatible mappings are limits of polynomials with coefficients in $F$ over the directed system of positive integers ordered by divisibility. The identification mappings along the directed system appear to be messy. We do observe that there are Frobenius compatible mappings that are not polynomials from $F[x]$. An easy example of such a function from $M$ to $M$ is 
$$
f(x)=\begin{cases}0,&\text{if $x=0$},\\1,&\text{otherwise}.\end{cases}
$$ 
With that $f$ we immediately see that $f_m(x)=x^{q^m-1}$ for all $m$.
A: Don't know if it helps, but all mappings of the form $f(F_{q^n}) \subset F_{q^n}$ can be represented as polynomials of degree strictly less than $q^n$ with coefficients in $F_{q^n}$.  This is a consequence of Lagrange interpolation. 
