Open

Posted online: 2020-03-28 03:44:47Z by Jordan Mitchell Barrett24

Cite as: P-200328.1

Let $\mathbf{x} = (x_1,\ldots,x_n)$, and $P(\mathbf{x}) \in \mathbb{Z}[\mathbf{x}]$.
A Diophantine equation $P(\mathbf{x}) = 0$ is *partition regular* if, for any $r$-colouring $c: \mathbb{N} \to r$, there exists $c$-monochromatic $\mathbf{m} = (m_1,\ldots,m_n) \in \mathbb{N}^n$ such that $P(\mathbf{m}) = 0$.

Hilbert's 10th problem famously has a negative solution: there is no algorithm which can decide whether a given Diophantine equation has *a* solution. In other words, the decision problem "does $P(\mathbf{x}) = 0$ have a solution in natural numbers" is undecidable for general $P$.

In light of this, is the decision problem "is $P(\mathbf{x}) = 0$ partition regular" decidable or not? To my knowledge, no work has been done on this. One could restrict only to colourings which are computable / low / bounded computational power, to see if that makes a difference.

No solutions added yet

Created at: 2020-03-28 03:44:47Z

No remarks yet