11
$\begingroup$

A recent question, Is irreducibility of polynomials $\in\mathbb{Z}[X]$ over $\mathbb{Q}$ an undecidable problem? was quickly answered in the negative. I am wondering if there is a simple example of a family of families of integer polynomials whose irreducibility is undecidable. For example, consider the following computational problem:

Instance: A positive integer $n$.
Question: Does the family of polynomials $\{x^d + x + n : d \in \mathbb{N}\}$ contain infinitely many members that are irreducible over $\mathbb{Q}$?

I don't know off the top of my head whether the above computational problem is undecidable. If it is, then that would answer my question affirmatively. If not, or if its undecidability is unknown, then is there some other problem of comparable simplicity that we can prove is undecidable?


EDIT: Upon further reflection, I suspect that the most promising route for getting an interesting answer to this question is to define some kind of "dynamical system" that generates a sequence of polynomials, and ask if (for example) the process eventually produces an irreducible polynomial. Interesting prior results with a dynamical-systems flavor include The undecidability of the generalized Collatz problem by Kurtz and Simon, and Turing-completeness of various families of PDEs as shown by Tao and others. Such results seem to say something about the complexity of the systems in question, in a way that "artificially" encoding an uncomputable set directly in the parameters of a problem (intuitively) does not. Unfortunately, I do not have a concrete proposal for how to define a suitable dynamical system.

$\endgroup$

2 Answers 2

10
$\begingroup$

I don't know about the family in question but there are families of families for which this is undecidable.

Given a total computable function $f:\mathbb{N}\times\mathbb{N}\to\{0,1\}$ consider the family of families $\mathcal{F}_n = (x^2+(-1)^{f(n,k)})_{k=0}^\infty$. Then asking whether $\mathcal{F}_n$ has infinitely many irreducible elements over $\mathbb{Q}$ is equivalent to asking whether the set $F_n = \{k \in \mathbb{N}\mid f(n,k)=1\}$ is infinite. So every $\Pi^0_2$ set can be encoded as a problem of this form. This is optimal since it is decidable whether a given polynomial is irreducible over $\mathbb{Q}$ according to the question mentioned by the OP.

$\endgroup$
2
  • $\begingroup$ Not bad, although I feel that there are two aesthetic flaws in this example. The first is that ${\cal F}_n$ is a sequence rather than a set. This can probably be fixed. The second, and more serious, flaw is that $(-1)^{f(n,k)}$ is not nearly as simple as a linear function such as $n$ or $k$. So it is not optimally simple. $\endgroup$ Feb 23 at 13:03
  • 1
    $\begingroup$ @TimothyChow The sequence issue is indeed easily resolved, by using the polynomials $x^2+(-1)^{f(n,k)}(n+k)^2$. $\endgroup$ Feb 23 at 15:44
7
$\begingroup$

(This is only a comment.) If you instead look at the family $\{x^d-x+n\}$, then it is known that there are infinitely many irreducible elements (for each positive $n$). It suffices to show that $f(x)=x^p-x+n$ is irreducible in $\mathbb{F}_p$ for any prime $p$ such that $p\nmid n$. This is similar to a homework problem often assigned from Dummit and Foote's "Abstract Algebra" textbook, which is also solved by David Speyer here: Is $x^p-x+1$ always irreducible in $\mathbb{F}_p$? The proof with $1$ replaced by $n$ is unchanged.

I suspect that the example family you gave also is known to contain infinitely many irreducible elements.

$\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.