By accident I have found the following characterization of irreducible polynomials over $\mathbb{F}_p$.
Lemma. Let $g \in \mathbb{F}_p[T]$ be a monic polynomial of degree $m \geq 1$. Then, $g$ is irreducible if and only if $$g(Y) \equiv \prod_{i<m} (Y – X^{p^i}) \bmod g(X)$$
holds in $\mathbb{F}_p[X,Y]$.
Actually, this is just a reformulation of standard facts about the finite field $\mathbb{F}_{p^m}$ and Galois theory: a polynomial is irreducible iff the Galois group acts transitively on its roots. But when we phrase the characterization as above, this asks for a more direct proof. Is it available? Can we prove the Lemma just by using the definition of an irreducible polynomial? Also, is any constructive proof available?
Also, has this Lemma (literally, in this form as a relation in $\mathbb{F}_p[X,Y]$) appeared in the literature before?
Best Answer
The following uses only
For any $\mathbb F_p$-algebra $A$, let $F_A\colon A\to A$ be the map given by $F_A(a)=a^p$. Then $F_A$ is an $\mathbb F_p$-algebra endomorphism of $A$ which is injective (and thus, if $A$ is finite-dimensional over $\mathbb F_p$, bijective) if and only if $\text{rad}(A)=\{0\}$, i.e., $A$ is semisimple.
Let $g(X)\in \mathbb F_p[X]$ be a given monic polynomial of degree $m$. Let $R= \mathbb F_p[X]/\langle g(X)\rangle$, let $q\colon \mathbb F_p[X]\to R$ be the quotient map, and set $x:=q(X)\in R$. Note that $R[Y]\cong \mathbb F_p[X,Y] / \langle g(X)\rangle$. Moreover, $R$ is an $m$-dimensional $\mathbb F_p$-algebra which is an integral domain if and only if $g$ is irreducible.Let $$ p(Y) = \prod_{t=0}^{m-1}(Y-x^{p^t}) \in R[Y] $$
Proposition: The polynomial $g(Y)$ is irreducible in $\mathbb F_p[Y]$ if and only if $g(Y)=p(Y) \in R[Y]$.
We will prove the proposition using a sequence of Lemmas:
Lemma 1: If $E$ is a field extension of $\mathbb F_p$ which contains a root $r_E$ of $g$, then if $S = \{r_E^{p^i}: i \in \mathbb Z_{\geq 0}\}$, it follows that there is some $k \leq m$ such that $S = \{r_E^{p^i}: 0\leq i <k\}$ and moreover if $$ p_E(Y) = \prod_{t=0}^{k-1}(Y-r_E^{p^t}) $$ then $p_E(Y)\in \mathbb F_p[Y]$ and $p_E(Y)$ divides $g(Y)$ in $\mathbb F_p[Y]$. In particular, if $g$ is irreducible, then $g$ splits over $E$ and $g(Y)=p_E(Y)$.
Proof: Replacing $E$ by $\mathbb F_p[r_0]\subseteq E$ if necessary, we may assume that $E$ is finite over $\mathbb F_p$, and hence $F_E\colon E \to E$ is bijective. Since $g(Y)\in \mathbb F_p[Y]\subseteq E[Y]$, if $a \in E$ then $F_E(g(a)) = g(a^p)$. It follows that $g(r_E^p)=0$ and hence by induction on $n$ we see that $g(r_E^{p^n})=0$ for all $n \in \mathbb Z_{\geq 0}$. Let $S = \{r_E^{p^n}: n\in \mathbb Z_{\geq 0}\}$. Now $g(Y)\in E[Y]$ has at most $m$ roots, hence $S$ is a finite set. But then as $F_E(S)\subseteq S$ and $F_E$ is injective, it follows $F_E(S)=S$, and hence $S = \{r_E, r_E^{p},\ldots,r_E^{p^{k-1}}\}$ where $k=|S|\leq m$, and $r_E^{p^{k}}=r_E$.
Now by the division algorithm $(Y-r_E^{p^i})$ divides $g$ in $E[Y]$ for each $i \in \{0,1,\ldots,k-1\}$, and thus, since $E[Y]$ is a PID and $\{(Y-r_E^{p^i}): 0\leq i \leq k-1\}$ are pairwise coprime, their product, $p(Y) = \prod_{i=0}^{k-1}(Y-r_E^{p^i})$ divides $g(Y)$. But
$$ F_E(p_E(Y)) = F_E\big(\prod_{i=0}^{k-1}(Y-r_E^{p^i})\big) = \prod_{i=0}^{k-1}(Y-r_E^{p^{i+1}}) = p_E(Y) $$
It follows that the coefficients of $p_E(Y)$ are fixed by $F_E$. But if $a \in E$, then $F_E(a)=a$ if and only if $a$ satisfies $Y^p-Y=0$. Since the elements of $\mathbb F_p$ give $p$ roots of $Y^p-Y$, and $E$ is an integral domain, it follows $F_E(a)=a$ if and only if $a\in\mathbb F_p$, and hence $p(Y)\in \mathbb F_p[Y]\subseteq E[Y]$ . Since $p_E(Y)$ divides $g(Y)$ in $E[Y]$, it must do so in $\mathbb F_p[Y]$ (e.g., because Euclid's algorithm will be unchanged by extending scalars) and thus if $g(Y)$ is irreducible in $\mathbb F_p[Y]$, then we must have $g(Y)=p_E(Y)$ and so $k=m$.
$\fbox{$\phantom{a}$}$
Lemma 1 proves the "only if" part of Proposition 1, since if $g$ is irreducible we may take $(E,r_E)$ to be $(R,x)$. For the other implication we need two more lemmas:
Lemma 2: If $p(Y) \in \mathbb F_p[Y]$ then $p(Y)$ divides $Y^{p^m}-Y$ in $\mathbb F_p[Y]$.
Proof: Let $h(Y) = \prod_{r=1}^{m-1}(Y-x^{p^r})$. If $p(Y) \in \mathbb F_p[Y]$ then $$ 0=p(Y)-F_R(p(Y)) = h(Y)(x^{p^m}-x). $$ Since $h(Y)$ is a monic polynomial of degree $m-1$ it follows that $x^{p^m}-x=0$. But now $p(Y)$ is monic of degree $m<p^m$, so by the division algorithm in $R[Y]$ we have $Y^{p^m}-Y = p(Y).q(Y)+r(Y)$, for some $r(Y)$ with $\text{deg}(r)<m$. But then substituting $Y=x$ we find $0=x^{p^m}-x=r(x)$, and hence $r(Y)=0$ (since $\{1,x,x^2,\ldots,x^{m-1}\}$ is a basis of the $\mathbb F_p$-vector space $R$). Thus $p(Y)$ divides $Y^{p^m}-Y$ as required.
$\fbox{$\phantom{a}$}$
With this in hand, we can complete the proof of the other implication of the Proposition:
Lemma 3 If $g(Y)=p(Y) \in R[Y]$ then $g$ is irreducible.
Proof: Since $g(Y)\in \mathbb F_p[Y]$, if $g(Y)=p(Y)$ then by Lemma 2 it follows that $g(Y)$ divides $Y^{p^m}-Y$. Now $Y^{p^m}-Y$ factorizes into a product of distinct irreducibles, hence the same must be true of $g(Y)$. Thus we may write $g(Y) = g_1(Y).g_2(Y)$ where $g_1(Y)$ is an irreducible factor of $g(Y)$ of minimal degree and $g_2$ is coprime to $g_1$. It follows that $R=R_1\oplus R_2$ and $R_1 = \mathbb F_p[X]/\langle g_1(X)\rangle$, $R_2 = \mathbb F_p[X]/\langle g_2(X)\rangle$, and so $R[Y] = R_1[Y]\oplus R_2[Y]$. Thus $g(Y)=p(Y)$ in $R[Y]$ if and only if $g(Y)=p(Y)$ in both $R_1[Y]$ and $R_2[Y]$.
But in $R_1[Y]$, by Lemma 1 applied to $E=R_1$ and $r_E = x_1= X+\langle g_1(X)\rangle$, we see that if $m=q_1m_1+r_1$ then $p(Y) = g_1(Y)^{q_1}.p_{r_1}(Y)$ where $p_{r_1}(Y)=\prod_{i=0}^{r_1-1}(Y-x_1^{p^i})$. In particular, since $m\geq m_1$, the roots of $p(Y)$ in $R_1[Y]$ are precisely the roots of $g_1(Y)$, thus if $p(Y)=g(Y)$ in $R_1[Y]$ then the roots of $g_2(Y)$ must be a subset of the roots of $g_1$. But since $g_1,g_2$ are coprime, this is possible only if $g_2$ has degree $0$, that is, $g_2$ is a unit, and hence $g(Y)=g_1(Y)$ is irreducible.
$\fbox{$\phantom{a}$}$