Partition-regularity characterization by computable finite partitions
Partition-regularity characterization by computable finite partitions
Let be a computable integral domain, and let denote partition regularity over for polynomial equations, with denoting the corresponding injective notion. A computable collection of finite partitions of is one for which an algorithm, given and , determines the cell of containing .
Partition-regularity characterization conjecture. There exists such a computable collection of finite partitions , with , such that
Without the computability requirement, the assertion follows from countability of the polynomials over . The computable version is not resolved in general; complexity results show that it cannot be replaced by a computable or characterization in settings where or is -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
Sign in to submit a solution.
No solutions have been posted yet.