Skip to main content
MathOverflow

Return to Question

Added a potential clarification to the question
Source Link
Timothy Chow
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

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.

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?

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.

Became Hot Network Question
Source Link
Timothy Chow
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

Undecidability of irreducibility of infinite families of integer polynomials?

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?