1
$\begingroup$

Consider the following algorithm from page 240 of this pdf:

Irreducibility-Test(f)
1 $n ← \deg(f)$
2 if $X^{p^n} \not\equiv X (\mod f)$
3 $\quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $\quad$ do if $X^{p^{n/r}} \equiv X (\mod f)$
6 $\quad\quad$ then return "no"
7 return "yes"

Now, this algorithm basically checks if $\deg(f)$ is the smallest positive integer $d$ such that $ f \,\mid\, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).

However, the assumed implication isn't right, see the answer to my question.

Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?

$\endgroup$
  • 3
    $\begingroup$ The linked source has non-congruence in line 2 (which makes more sense). $\endgroup$ – Andreas Blass Nov 21 '18 at 15:12
  • 3
    $\begingroup$ Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)\neq 1$" would suffice ? Just a silly thought... $\endgroup$ – user120527 Nov 21 '18 at 15:22
  • $\begingroup$ @user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out. $\endgroup$ – polynomial_donut Nov 21 '18 at 19:05
  • $\begingroup$ This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)\cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$. $\endgroup$ – Jyrki Lahtonen Nov 22 '18 at 6:28
  • 1
    $\begingroup$ Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm\{3,2,1\}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm\{5,2,2,1\}$. I don't see a remedy other than to calculate $\gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility. $\endgroup$ – Jyrki Lahtonen Nov 22 '18 at 6:45
3
$\begingroup$

The algorithm should work out with the change that user120527 suggested in a comment on this question.

If $f$ is irreducible, then if we have $f \,\mid\, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $\deg(f) \,\mid\, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $\mathbb{F}_q[X]$ whose degree divides $d$. Hence, $\deg (f) \leq d$.
This implies that $f \,\not\mid\, P_{n/r}$ for all prime factors $r$ of $n = \deg (f)$, because $\deg(f) > \deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f \,\not\mid\, P_{n/r} \overset{f\, \text{prime}}\iff \gcd\left(f, P_{n/r}) \neq 1 \right)$.

Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g \,\mid\, f \,\mid\, P_{\deg(f)}$, so that $$ \deg (g) \,\mid\, \deg (f) $$ Now, since $h$ is nontrivial we know $\deg (g) < \deg (f)$, so that with the above, there is a prime factor $r$ of $\deg(f)$ such that $\deg (g) \,\mid\, \deg(f)/r = n/r$ and then, $$ g \,\mid\, P_{n/r} \iff \gcd\left(g, P_{n/r}\right) \neq 1 \implies \gcd\left(f, P_{n/r}\right) \neq 1 $$ and $f$ will fail the test in line 5 of the changed algorithm here:

Irreducibility-Test(f)
1 $n ← \deg(f)$
2 if $X^{p^n} \not\equiv X (\mod f)$
3 $\quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $\quad$ do if $\;\mathbf{\,\textbf{gcd}\left(f,\, X^{p^{n/r}} - X \right) \neq 1}$
6 $\quad\quad$ then return "no"
7 return "yes"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.