{"id":"75519adc-fda6-407e-a5fe-c7545382898e","arxiv_id":"2412.14917","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Partition regularity of polynomial equations over Z is undecidable if Hilbert's tenth problem over Q is undecidable, and over function fields it is unconditionally Pi_2^0-complete.","lead":"This paper proves that deciding whether a polynomial equation is partition regular can be undecidable, connecting an old open problem in number theory, Hilbert's tenth problem over the rationals, to Ramsey theory. It also pins down the exact computational complexity of these decision problems over several integral domains.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2 rests on the existence of strong 'master polynomials' (Def. 2.26); Lemma 2.28's one-paragraph justification is inadequate and appears type-incorrect for the additive case, so the central completeness claim is not fully established.","rationale":"The reader correctly identified master polynomials as the weakest assumption. My stress-test sharpens this: the proof of Lemma 2.28 is not merely incomplete but internally problematic in the additive case (identity cannot be a surjective homomorphism Q^x -> Z), and the appeal to the HTP literature does not clearly establish the universal-fiber property. Since Theorem 4.2's Pi_2^0-completeness reductions use this property essentially—both for the density direction and for constructing sets of positive density that avoid solutions—the central claim is conditional on an assumption whose verification is currently inadequate. I do not claim the theorem is false; rather, the paper should be accepted only after the authors supply a rigorous proof or precise references showing that the cited HTP results yield master polynomials in the full sense of Definition 2.26. If such a proof is provided, the rest of the argument appears coherent. Hence the verdict should be CONDITIONAL rather than unconditional ACCEPT.","tokens_in":44305,"tokens_out":22391,"duration_ms":188606,"concrete_test":"Independently verify Lemma 2.28(2) for K=F_q(t), R=F_q[t], g=ord_p: in the construction of Pheidas [50], extract the polynomial P for a universal Sigma_1^0 set S subset of N times Z and test whether P(f(m),b,z) has a root for all b with ord_p(b)=n exactly when S(m,n), or only for the specific element b=t^n. If the latter, the master polynomial condition fails and the unconditional F_q[t] completeness in Theorem 4.2 is unproven.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 2.26 demands, for every Sigma_1^0 set S subset of N times Z, a polynomial p and a surjective homomorphism g: K^x -> Z such that S(m,n) holds iff for every b in K with g(b)=n, the polynomial p(f(m),b,z) has a root in K^x, and not-S(m,n) iff for every such b, p has no root in K. This universal-fiber condition is much stronger than ordinary HTP(K): it requires the Diophantine set {b : exists z p(m,b,z)=0} to be constant on fibers of g and to code S. Lemma 2.28(1) claims Z admits master polynomials if HTP(Q) holds, but its proof says 'let f and g be the identity functions,' which cannot work for the additive case since g must map Q^x onto Z. In the multiplicative case g=id makes each fiber a singleton, so it does not cover the additive fibers used in Theorem 4.2 for function fields. For the unconditional cases, Lemma 2.28(2) simply cites [50,62,57] for master polynomials with g=ord_p, without construction or theorem numbers, and the universal-fiber property is not the standard formulation of HTP(K). If those results only provide a Diophantine model of N via t^n rather than a fiber-uniform saturation, then Definition 2.26 may fail, and the density/partition-regularity reductions in Theorem 4.2 would not go through for the claimed domains. The reader's weakest_assumption identifies exactly this point; the paper's brief verification is not sufficient to rule it out.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the lightface descriptive complexity of Ramsey-theoretic sets of polynomials over computable integral domains R: partition-regular polynomials PR_R, injectively partition-regular IPR_R, and injective multiplicative/additive density-regular polynomials IMDR_R and IADR_R. The main completeness result is Theorem 4.2: if R admits master polynomials (Definition 2.26), then PR_R, IPR_R, PR_R∩H_R, IPR_R∩H_R, and IMDR_R∩H_R are Π_2^0-complete. Theorem 4.1 gives Σ_1^0-completeness of fixed-color and fixed-density versions under the undecidability of HTP(K). The paper also proves compactness and uniformity principles for density Ramsey theory on countable cancellative left amenable semigroups and constructs natural extensions of measure-preserving actions. The proofs are built from explicit transfer lemmas (Lemma 2.15, Corollary 2.21, Lemma 2.23), Rado's theorem over integral domains, and tiling arguments. Unconditional conclusions are claimed for F_q[t] and rings of integers of algebraic function fields over finite fields, and the Z case is conditional on HTP(Q).","tokens_in":44651,"tokens_out":25184,"duration_ms":195223,"significance":"If the master-polynomial hypothesis is fully established, the exact Π_2^0-completeness results are substantial and novel: they give a precise sense in which deciding partition regularity and density regularity of polynomial equations is as hard as the universal fragment of arithmetic. The compactness principle (Theorem 3.1), uniformity principle (Theorem 3.7), and natural extension construction (Theorem 2.9) are useful contributions in their own right, and the paper is explicit about which claims are conditional, including open questions and concrete falsifiable predictions such as PR_{F_q[t]} being Π_2^0-complete. The main weakness is that the upgrade from Σ_1^0-hardness to Π_2^0-completeness rests on the unproved existence of master polynomials in the strong sense of Definition 2.26; the current verification in Lemma 2.28 is too terse and appears type-incorrect in the additive case.","major_comments":[{"comment":"The proof says 'we let f and g be the identity functions' and concludes that Z admits master polynomials. This is type-incorrect for the additive case of Definition 2.26: g must be a surjective homomorphism from Q^x to Z, so g = id is impossible. The argument at best establishes the multiplicative case, where g: Q^x → Q^x can be the identity and HTP(Q) gives the required reduction. Since Theorem 4.2 invokes master polynomials without specifying which type is used, the conditional result for R = Z is not proved as written.","section":"§2.7, Lemma 2.28(1)"},{"comment":"For function fields, the proof consists of citing [50, 62, 57] and asserting that these results 'construct master polynomials' with g = ord_p. Definition 2.26 requires much more than ordinary Diophantine undecidability: for each fiber of g, either every b in the fiber admits a root in K^x (if S holds) or no b in the fiber admits a root in K at all (if S fails). This universal-fiber property, together with the negative 'no root in K' condition, is not the standard formulation of HTP(K), and no construction or theorem number is supplied. The unconditional Π_2^0-completeness claims in Theorem 4.2 are therefore not supported as they stand.","section":"§2.7, Lemma 2.28(2)"},{"comment":"In the converse direction, the proof chooses a monotile T for (Q,+) with center set C, asserts d*(C) = 1/|T|, and uses this to produce a positive-density set avoiding the forbidden differences. But IADR_Z requires a subset of Z, not of Q. For a general center set C of an additive tiling of Q, the intersection C∩Z need not have positive density in Z; the argument needs an explicit construction (for example, a coset M·Z chosen to avoid the finite set T) with a proof that the resulting set lies in Z and has positive density.","section":"§4, Theorem 4.3(i)"}],"minor_comments":[{"comment":"Footnote 7 says that a universal Σ_1^0 set S ⊆ N×Q admits 'an additive master polynomial'; this should read 'a multiplicative master polynomial'.","section":"§2.7, Definition 2.26"},{"comment":"In the proof of part (i), the text says 'M P2(m, y1, y2, z1, ..., z4k)' in the converse directions; the intended polynomial is M P1. The same typo appears in the multiplicative case.","section":"§4, Theorem 4.2"},{"comment":"The displayed verification 'for all m, n ∈ N' is appropriate for the additive formulation but not for the multiplicative master polynomial; in the multiplicative case n should range over Q.","section":"§2.7, Lemma 2.28(1)"},{"comment":"The transformation from a Π_2^0 set A to a Σ_1^0 set S with A(m) iff ∀n≠0 S(m,n) is stated correctly but deserves a short explicit proof; the current text compresses the quantifier manipulation and could confuse readers.","section":"§2.7"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be correct in its main architecture once the master-polynomial existence is proved or the theorems are restated with an explicit hypothesis. The use of the authors' own [29] for Lemma 2.23 seems legitimate and independent. The anonymous overlap with Briceño–Bustos-Gajardo–Donoso-Echenique is acknowledged in the introduction, so I see no novelty-disclosure problem. My main advice to the editor is to send the paper back with a request for a rigorous treatment of Definition 2.26, since the current one-paragraph verification is the load-bearing point of the unconditional claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one because it connects two big programs: Hilbert's tenth problem over Q and the descriptive complexity of partition- and density-regular polynomial equations. The main claims are that the sets PR, IPR, IMDR are Pi_2^0-complete over suitable domains, with Z conditional on HTP(Q). The reductions themselves are clever and, as far as I can see, correct: they realize ratios inside dense or partition-regular sets and use the master polynomial as a bridge. The compactness and uniformity principles in Section 3 look solid and are independently useful.\n\nBut the load-bearing assumption is Definition 2.26, the 'master polynomial,' and Lemma 2.28 that supposedly guarantees its existence. This is the weak spot. For Z, the proof says 'let f and g be the identity functions.' In the additive formulation that is type-incorrect—g would need to map Q^x onto Z, and identity maps to Q^x. The multiplicative version with g=id is fine for the cases where a single parameter n in Q is used, and HTP(Q) does give that. So the Z part may survive with a rewrite.\n\nThe bigger problem is the function-field case. Lemma 2.28(2) cites Pheidas, Videla, Shlapentokh for the existence of master polynomials with g=ord_p, but gives no theorem numbers and no construction. The cited results are about Diophantine models of N over F_q(t), not about the universal-fiber condition in Definition 2.26. That condition requires that for every n in the image of g, the Diophantine set {b in K : g(b)=n, p(m,b,z)=0 has a root} is actually constant on the whole fiber. Standard Diophantine models give you one parameter t^n per n, not uniformity across the infinitely many unit multiples. I don't see how the citations as written deliver that. If this cannot be proved, the Pi_2^0-completeness for IMDR and PR over F_q(t) does not go through.\n\nI want to be clear: this is not a fatal disorganization. The motivation is good, the paper is honest about what is conditional, and the reductions between the Ramsey-theoretic sets and HTP are the opposite of circular—they reduce HTP to the Ramsey sets. But the master polynomial lemma is underproved, and it is central.\n\nVerdict: send it to a serious referee. The referee should ask for a full proof or a precise reference of the master polynomial construction in the function-field setting. If the authors can supply that, this becomes a very nice paper. If not, the completeness results collapse to conditional statements. I would not cite the main theorem as it stands, though the compactness principle in Section 3 is worth a look.","headline":"Strong paper with a real gap: the Pi-2-completeness results are conditional on master polynomials whose existence is asserted but not proved for the function-field cases.","tokens_in":45158,"tokens_out":5121,"would_cite":false,"duration_ms":38379,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D80","05D10","11U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Over $F_q(t)$, no algorithm decides which polynomial equations have monochromatic solutions.","keywords":["partition regularity","density Ramsey theory","homogeneous polynomial equations","arithmetical hierarchy","Pi-0-2 completeness","master polynomials","amenable semigroups","undecidability"],"falsifier":"Take the standard 'for all $n$ there exists $m$' complete problem and run the paper's reduction over $F_q(t)$: it outputs a homogeneous polynomial $p_m$ for each index $m$. If one could exhibit an $m$ where $p_m=0$ is partition regular but the universal statement is false, or $p_m=0$ is not partition regular but the universal statement is true, the reduction would be refuted; the theorem asserts no such $m$ exists.","tokens_in":1990,"feed_emoji":"🧩","tokens_out":3410,"duration_ms":164813,"temperature":0.7,"pith_summary":"This paper asks how hard it is to decide whether a given polynomial equation has a monochromatic solution in every finite coloring of a number system's nonzero elements. It proves that for many integral domains, including rational function fields such as $F_q(t)$, this decision problem is not merely undecidable but sits exactly at the $\\Pi^0_2$ level of the arithmetical hierarchy, and that the same holds for the injective and density-regular variants. Over the integers the result is conditional on the undecidability of the rational analogue of the classic integer-root problem, which is still open. The proof works by encoding arbitrary $\\Pi^0_2$ questions as the partition regularity or density regularity of homogeneous polynomials, using what the paper calls master polynomials.","feed_headline":"No algorithm decides if a polynomial has monochromatic roots","feed_subtitle":"For F_q(t) the problem is Pi-0-2-complete; over Z it depends on the open question of rational roots.","key_machinery":"The engine is the master polynomial. For a domain $R$ with fraction field $K$, a master polynomial for a $\\Sigma^0_1$ set $S\\subseteq\\mathbb{N}\\times\\mathbb{Z}$ (or $\\mathbb{N}\\times\\mathbb{Q}$) is a fixed polynomial $p(x,y,z_1,\\dots,z_k)$ together with computable maps $f:\\mathbb{N}\\to R$ and $g:K^\\times\\to\\mathbb{Z}$ (or $g:K^\\times\\to\\mathbb{Q}^\\times$) such that $S(m,n)$ holds exactly when $p(f(m),b,z_1,\\dots,z_k)$ has a root in $K^\\times$ for every $b$ with $g(b)=n$, and fails exactly when it has no root in $K$ for every such $b$. The paper converts these into homogeneous polynomials by substituting scaled quotients such as $(z_i-z_j)/(z_k-z_\\ell)$ or $(z_i-z_j)/z_k$, so that a root of the master polynomial becomes an injective root of a homogeneous polynomial. Two self-contained tools carry the density arguments: a compactness principle saying that density regularity of a right-translation-invariant family of finite configurations is equivalent to a statement about a single finite set, and a uniformity principle producing a finite subfamily with a uniform positive recurrence bound; both are proved for countable cancellative left amenable semigroups.","core_discovery":"The paper's central result is a complexity classification. If a computable integral domain $R$ admits master polynomials, then the set of homogeneous polynomials $p$ for which $p=0$ is partition regular over $R\\setminus\\{0\\}$ is $\\Pi^0_2$-complete, and the same is true for the injective partition-regular version and for the multiplicative density-regular analogue $\\mathrm{IMDR}_R\\cap H_R$. When the number of cells in the partition is fixed at $\\ell$, the corresponding sets are $\\Sigma^0_1$-complete rather than $\\Pi^0_2$-complete, assuming the undecidability of the root-existence problem over the fraction field. An unconditional special case is $R=F_q[t]$ with fraction field $F_q(t)$: deciding whether a homogeneous polynomial is partition regular over $F_q(t)\\setminus\\{0\\}$ is $\\Pi^0_2$-complete, hence undecidable. For $R=\\mathbb{Z}$, the same conclusion is conditional on the open problem of deciding whether polynomials over $\\mathbb{Q}$ have rational roots. Along the way the paper proves compactness and uniformity principles for density Ramsey theory on countable cancellative left amenable semigroups, and constructs natural extensions of measure-preserving semigroup actions for countable cancellative left reversible semigroups.","pith_inferences":["The paper does not claim that every domain with an undecidable root-existence problem over its fraction field yields $\\Pi^0_2$-completeness, but the master-polynomial mechanism suggests the conclusion should extend to any such domain once a suitable valuation homomorphism is available.","Beyond the paper's scope, a settled answer to the rational-root question would automatically resolve the integer case, so the polynomial partition-regularity problem can be read as a reformulation of that open problem.","An unstated practical upshot of the uniformity principle is that verifying density regularity of a specific polynomial could be reduced to a finite search over one large finite set, turning a $\\Pi^0_2$ condition into an explicit finite certificate check."],"forward_implications":["For every domain covered by the theorem, the set of homogeneous polynomials $p$ for which $p=0$ is partition regular over $R\\setminus\\{0\\}$ is $\\Pi^0_2$-complete, so no algorithm can decide it.","The injective version, where the monochromatic solution must use distinct variables, has the same $\\Pi^0_2$-complete complexity, and the multiplicative density-regular analogue does too.","Fixing the number of colors $\\ell$ changes the complexity: the $\\ell$-partition-regular sets are $\\Sigma^0_1$-complete, so the quantifier over all $\\ell$ is what raises the problem to $\\Pi^0_2$.","For $R=\\mathbb{Z}$, deciding partition regularity of homogeneous polynomials would be $\\Pi^0_2$-complete if the open question of rational-root existence over $\\mathbb{Q}$ has a negative answer; the function-field cases give unconditional instances.","The compactness and uniformity principles imply that density regularity has finite witnesses: if every set of upper Banach density at least $\\delta$ contains a configuration from a right-translation-invariant family, then a single finite subfamily works uniformly for all such sets."],"supporting_citations":[{"why":"Supplies the columns-condition criterion for partition-regular linear systems, used to prove that the ratio systems in the reductions are partition regular.","marker":"[52]"},{"why":"Establishes undecidability of root existence over $F_q(t)$ in odd characteristic, one of the inputs guaranteeing master polynomials in the unconditional cases.","marker":"[50]"},{"why":"Establishes the analogous undecidability over $F_q(t)$ in characteristic 2, covering the remaining unconditional function-field cases.","marker":"[62]"},{"why":"Extends undecidability to algebraic function fields over finite fields of characteristic greater than two, supporting the more general ring-of-integers versions.","marker":"[57]"},{"why":"Constructs congruent tilings of amenable groups with invariant shapes, used in the compactness and uniformity principles for density regularity.","marker":"[25]"},{"why":"Provides the pointwise ergodic theorem for amenable groups, used to connect upper Banach density to measure-preserving systems in the density-Ramsey equivalences.","marker":"[46]"}],"fun_headline_variants":["No algorithm for polynomial partition regularity over F_q(t)","Polynomial root coloring undecidable even over function fields","Hilbert's tenth problem meets Ramsey: undecidability for polynomial equations","Pi-0-2-complete: the exact complexity of polynomial partition regularity","No algorithm for monochromatic polynomial roots, even over F_q(t)"],"cache_read_input_tokens":47232,"weakest_assumption_plain":"The load-bearing premise is that the ring admits master polynomials, which for $\\mathbb{Z}$ is equivalent to the open question of whether rational-root existence is undecidable, and for the function fields is inherited from known undecidability results.","fun_headline_variants_meta":{"raw":{"variants":["No algorithm for polynomial partition regularity over F_q(t)","Polynomial root coloring undecidable even over function fields","Hilbert's tenth problem meets Ramsey: undecidability for polynomial equations","Pi-0-2-complete: the exact complexity of polynomial partition regularity","No algorithm for monochromatic polynomial roots, even over F_q(t)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000803,"raw_usage":{"total_tokens":3586,"prompt_tokens":1058,"completion_tokens":2528,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":2437}},"tokens_in":674,"tokens_out":2528,"duration_ms":16689,"temperature":1.0,"reasoning_tokens":2437,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:48:51.268445+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the standard 'for all $n$ there exists $m$' complete problem and run the paper's reduction over $F_q(t)$: it outputs a homogeneous polynomial $p_m$ for each index $m$. If one could exhibit an $m$ where $p_m=0$ is partition regular but the universal statement is false, or $p_m=0$ is not partition regular but the universal statement is true, the reduction would be refuted; the theorem asserts no such $m$ exists.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the columns-condition criterion for partition-regular linear systems, used to prove that the ratio systems in the reductions are partition regular."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes undecidability of root existence over $F_q(t)$ in odd characteristic, one of the inputs guaranteeing master polynomials in the unconditional cases."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the analogous undecidability over $F_q(t)$ in characteristic 2, covering the remaining unconditional function-field cases."},{"cited_title":"Shlapentokh","cited_arxiv_id":null,"evidence_quote":"Extends undecidability to algebraic function fields over finite fields of characteristic greater than two, supporting the more general ring-of-integers versions."},{"cited_title":"Downarowicz, D","cited_arxiv_id":null,"evidence_quote":"Constructs congruent tilings of amenable groups with invariant shapes, used in the compactness and uniformity principles for density regularity."},{"cited_title":"Lindenstrauss","cited_arxiv_id":null,"evidence_quote":"Provides the pointwise ergodic theorem for amenable groups, used to connect upper Banach density to measure-preserving systems in the density-Ramsey equivalences."}],"review_version":1}