Decidability of partition regularity for a Diophantine equation


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

Cite as: P-200328.1

  • Logic
  • Combinatorics
  • Number Theory
View pdf

Problem's Description

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.

  1. Article On Rado conditions for nonlinear Diophantine equations


No solutions added yet

No remarks yet

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