Does a polynomial $P(x)$ of degree $n$ over $\mathbb{F_q}$ which satisfy $P(x)|x^{l}-1$ only for $l\ge q^n-1$ is irreducible?

Question

Does a polynomial $P(x)$ of degree $n$ over $\mathbb{F_q}$ which satisfies $$P(x)|x^{l}-1$$ only for $l\ge q^n-1$ is irreducible?

If it's, how it can proven?

Answer 1

It's true iff $P(0)\ne0$ or $P=X$. These are obviously necessary conditions, since otherwise $P$ never divides $X^\ell-1$. By the way note that the problem statement isn't a necessary condition for $P$ to be irreducible, since $X-1\mid X^1-1$, yet is irreducible.

Let $P=\prod_{i=1}^kP_i^{a_i}$, where $P_1,\ldots,P_k\ne X$ are pairwise distinct irreducible polynomials in $\mathbb F_q[X]$ and $a_1,\ldots,a_k\ge1$ are integers. Further, let $d_i=\deg P_i$. We wish to prove that $k=1$ and $a_i=1$.

It is well known that the splitting field of $P_i$ is $\mathbb F_{q^{d_i}}$ (see for example http://www.math.rwth-aachen.de/~Max.Neunhoeffer/Teaching/ff/ffchap3.pdf page 27 for a proof).

Since $X^{q^{d_i}}-X$ is identically zero in $\mathbb F_{q^{d_i}}$, $X^{q^{d_i}-1}-1$ is identically zero in $\mathbb F_{q^{d_i}}^\times$. Therefore, $P_i\mid X^{q^{d_i}-1}-1$ in $\mathbb F_{q^{d_i}}$ ($P_i$ has no double roots), so $P_i$ also divides $X^{q^{d_i}-1}$ in $\mathbb F_q$ (by the Euclidean algorithm).

We have $P_i\mid X^{q^{d_i}-1}-1\mid X^{(q^{d_1}-1)\dotsm(q^{d_k}-1)}-1$ for $i=1,\ldots,k$. Let $m$ be the smallest integer such that $p^m\ge a_i$ for all $i$ ($p$ is the characteristic of $\mathbb F_q$). We have $$X^{p^m(q^{d_1}-1)\dotsm(q^{d_k}-1)}-1=\left(X^{(q^{d_1}-1)\dotsm(q^{d_k}-1)}-1\right)^{p^m}$$ by the Frobenius automorphism, so $$P_i^{a_i}\mid X^{p^m(q^{d_1}-1)\dotsm(q^{d_k}-1)}-1.$$ Since $P_1^{a_1},\ldots,P_k^{a_k}$ are irreducible and pairwise distinct, they are also pairwise coprime so $$P=\prod_i P_i^{a_i}\mid X^{p^m\prod_i(q^{d_i}-1)}-1.$$

Without loss of generality, assume $a_1=\max(a_i):=a$.

$\textbf{Lemma.}$ $p^mq^{d_1}\le q^{a_1d_1}$.

$\textit{Proof.}$ It suffices to show that $p^m\le q^{a-1}$, since this would imply $p^m\le q^{d_1(a_1-1)}\iff p^mq^{d_1}\le q^{a_1d_1}$.

If $m=0$ this is obvious. If $m=1$, then $a\ge2$. Since $q$ is a power of $p$, we have $p^m=p\le q\le q^{a-1}$. Otherwise, assume $m\ge2$. Since $p^{m-1}<a$, we have $$p^m\le(a-1)^{m/(m-1)}\le (a-1)^2.$$ If $q\ge3$, trivial analysis shows that $(a-1)^2<3^{a-1}\le q^{a-1}$ so we're done. If $q=2$, trivial analysis shows that $(a-1)^2\le2^{a-1}$ for $a\ge5$. It remains to treat the cases where $2\le a\le 4$.

If $a>2$, $p^k=4$ and $p^k=4=q^{3-1}\le q^{a-1}$. If $a=2$, then $2=p^k\le 2=q^{a-1}$ which ends the proof of the lemma. $\blacksquare$

Now, assume for the sake of a contradiction that $k>1$. We have \begin{align*} p^m\prod_i(q^{d_i}-1)&<p^m(q^{d_k}-1)\cdot\prod_{i<k}q^{d_i}\\ &=p^mq^{d_1}(q^{d_k}-1)\cdot\prod_{1<i<k}q^{d_i}\\ &\le q^{a_1d_1}(q^{d_k}-1)\cdot\prod_{1<i<k}q^{d_i}&\text{by the lemma}\\ &\le q^{a_1d_1}(q^{a_kd_k}-1)\cdot\prod_{1<i<k}q^{a_id_i}\\ &=q^{a_1d_1+\ldots+a_kd_k}-q^{a_1d_1+\ldots+a_{k-1}d_{k-1}}\\ &<q^n-1 \end{align*} which contradicts the assumption that $P\nmid X^\ell-1$ whenever $\ell<q^n-1$ (with $\ell=p^m\prod_i(q^{d_i}-1)$.

$\blacksquare$