Partition-regularity characterization by computable finite partitions

About 2 years old · traced to

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 n∈Nn\in\mathbb{N} and r∈R∖{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)PRR⟺for every n∈N, 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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.