14
$\begingroup$

There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a prime finite field).

I was wondering if the decision problem of "Given an arbitrary polynomial $\in \mathbb{Z} [X]$, is it irreducible over $\mathbb{Q}$ or not?" is decidable or undecidable.

Improve this question
$\endgroup$
2
  • $\begingroup$ The answers from GH from MO and David Speyer are excellent, but I wanted to add a small minor comment. Their positive answers presuppose that the integer polynomial is presented in a way where you can decide what the coefficients actually are, that you can compute with them, etc... So, a (only slightly) better way of expressing the problem might have been: Given an arbitrary polynomial in $\mathbb{Z}[x]$, where the coefficients are given as finite signed bit strings, can we decide if the polynomial is irreducible over $\mathbb{Q}$ or not? $\endgroup$
    – Pace Nielsen
    Commented Feb 22, 2022 at 20:36
  • 1
    $\begingroup$ Even though the irreducibility of any single polynomial is decidable, irreducibility criteria are still interesting because they yield irreducibility of infinite families of polynomials. There are plenty of infinite families for which it is not known whether infinitely many members are irreducible. $\endgroup$
    – Timothy Chow
    Commented Feb 23, 2022 at 3:27

2 Answers 2

Reset to default
24
$\begingroup$

There is a polynomial-time algorithm that decomposes any non-zero polynomial in $\mathbb{Q}[X]$ into irreducible factors. The algorithm is due to Lenstra–Lenstra–Lovász (Factoring Polynomials with Rational Coefficients).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ It's worth mentioning: This answer addresses factoring in $\mathbb{Q}[x]$. If you start with a polynomial $f(x) = \sum f_j x^j$ in $\mathbb{Z}[x]$, then you can compute $g:=GCD(f_0, f_1, \dots, f_n)$ using the Euclidean algorithm and factor $f(x)$ as $g h(x)$ for $h$ primitive. Using LLL to factor $h$ will then give you primitive polynomials in $\mathbb{Z}[x]$. The problem of factoring $g$, of course, is integer factorization, which we don't know how to do efficiently. $\endgroup$
    – David E Speyer
    Commented Feb 22, 2022 at 21:00
24
$\begingroup$

There is a quick way to see that this is decidable (with terrible complexity). Let $h(x) \in \mathbb{Z}[x]$ have degree $d$. Evaluate $h$ at $d+1$ points $u_1$, $u_2$, ..., $u_{d+1}$. If any of the $h(u_i)$ are $0$, we have found a factor and we can reduce to a problem of lower degree, so suppose that $z_i:=h(u_i)$ is nonzero for $1 \leq i \leq d+1$.

There are finitely many ways to split each $z_i$ as $x_i y_i$ for integers $x_i$ and $y_i$, which we can find using a prime factorization of $z_i$.

For each splitting $(x_1, x_2, \dots, x_{d+1}, y_1, y_2, \dots, y_{d+1})$ with $x_i y_i = h(u_i)$, we can use Lagrange interpolation to find the unique polynomials of degree $\leq d$ with $f(u_i) = x_i$ and $g(v_i) = y_i$. If $\deg f + \deg g \leq d$, then we have $f(x) g(x) = h(x)$ at $d+1$ values of $x$, so we must have $f(x) g(x) = h(x)$ as a polynomial identity and we have found a factorization. Conversely, if a factorization $h(x) = f(x) g(x)$ exists, then Lagrange interpolation will find it for the splitting where $x_i = f(u_i)$, $y_i = g(u_i)$.

Of course, this is a terrible algorithm, since it involves taking the prime factorization of $d+1$ integers and then doing exponentially many cases of Lagrange interpolation. But it is the only algorithm which I know how to explain in ten minutes, so it is useful when a student asks this question. See GH from MO's answer for a good algorithm.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ For small degree polynomials this is actually a decent algorithm, which helped me solve many problems from Dummit and Foote's "Abstract Algebra" book. We know that the constant coefficients of the factors must be factors of the constant coefficient (by evaluating at $0$), and so that gives us finitely many options for those constant coefficients, etc... $\endgroup$
    – Pace Nielsen
    Commented Feb 22, 2022 at 20:43
  • 2
    $\begingroup$ Historical remark: this method is due to Kronecker. $\endgroup$
    – François Brunault
    Commented Feb 23, 2022 at 8:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .