Partition-regularity characterization by computable finite partitions

From papers

Let RR be a computable integral domain, and let PRRPR_R denote partition regularity over R{0}R\setminus\{0\} for polynomial equations, with (I)PRR(I)PR_R denoting the corresponding injective notion. A computable collection of finite partitions {Cn}n=1\{\mathcal{C}_n\}_{n=1}^{\infty} of R{0}R\setminus\{0\} is one for which an algorithm, given nNn\in\mathbb{N} and rR{0}r\in R\setminus\{0\}, determines the cell of Cn\mathcal{C}_n containing rr.

Partition-regularity characterization conjecture. There exists such a computable collection of finite partitions {Cn}n=1\{\mathcal{C}_n\}_{n=1}^{\infty}, with Cn={Cn,i}i=1n\mathcal{C}_n=\{C_{n,i}\}_{i=1}^{n_\ell}, such that

p(I)PRRfor every nN, p has an injective root in some cell of Cn.p\in (I)PR_R\quad\Longleftrightarrow\quad \text{for every }n\in\mathbb{N},\ p\text{ has an injective root in some cell of }\mathcal{C}_n.

Without the computability requirement, the assertion follows from countability of the polynomials over RR. The computable version is not resolved in general; complexity results show that it cannot be replaced by a computable or Π10\Pi^0_1 characterization in settings where PRRPR_R or IPRRIPR_R is Π20\Pi^0_2-complete.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Sohail Farhangi, Steve Jackson and Bill Mance, “Undecidability in the Ramsey theory of polynomial equations and Hilbert's tenth problem”, arXiv:2412.14917 (2025).

Solutions 0

No solutions have been posted yet.