Hilbert's Tenth Problem over the Rationals

Hilbert's Tenth Problem over the Rationals

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 004; 2026-09-24), the asserted result is that rational solvability of integer-coefficient polynomials with an unrestricted number of variables is undecidable.

Mathematical statement of the claimed result

Manuscript 1.

With $n$ variable and integral polynomial coefficients explicitly encoded, the rational Diophantine decision claim is \[ \{f\in\mathbb Z[X_1,\ldots,X_n]:\exists x\in\mathbb Q^n,\ f(x)=0\} \quad\text{is undecidable}. \] There is no algorithm giving the correct yes/no answer for every such input; the coefficient ring is $\mathbb Z$, but sought solutions lie in $\mathbb Q$.

Outline of the argument

For manuscript 1 (family 004; 2026-09-24), integer solvability is represented by an effective sequence of finite rational tests. Elliptic indices, odd valuation contacts, and a height argument force an ordinary integer witness when every test succeeds; a hypothetical rational decision procedure would then decide the integer problem by two concurrent searches.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 004; 2026-09-24).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

• OpenAI, Hilbert's tenth problem over the rational numbers, 2026-09-24; citation key OAI:Hilberts-tenth-problem-over-the-rational-numbers-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• OpenAI catalogue entry.

Hilbert's Tenth Problem over the Rationals

Definitions and mathematical statement

An input is a finite description of $f\in{\mathbb{Z}}[x_1,\ldots,x_n]$, with no fixed bound on $n$, degree, or coefficient size. Define the decision set \[ \mathcal D_{{\mathbb{Q}}}=\{\langle f\rangle:\exists(q_1,\ldots,q_n)\in{\mathbb{Q}}^n, f(q_1,\ldots,q_n)=0\}. \] Determine whether $\mathcal D_{{\mathbb{Q}}}$ is decidable: one algorithm must halt on every input and return its correct membership bit. Enumeration of rational solutions only semidecides yes-instances and is not a solution. The selected assertion concerns computability, with no polynomial-time demand.

Formulation and concept references: [S1].

Short English statement

Can an algorithm always decide whether a polynomial equation with integer coefficients has a rational solution?

Research attempt

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026, using explicit reductions, source checks, and adversarial verification.

Scope, source check, and attack map.

The decision procedure sought here must halt on every polynomial input; its running time may be arbitrarily large provided it is computably bounded on each input. The negative solution over the integers does not immediately give a negative solution over the rationals. Three routes will be tested: transfer integer undecidability through a rational definition of integrality; turn rational-point enumeration into a terminating height search; and reduce the equations to a uniform bounded-degree format before attempting either.

Two inherited references require particular care. Koymans--Pagano [S2], Theorem 1.1 and Question 6.2, treat infinite finitely generated rings and explicitly leave $\mathbb Q$ outside that result. Garcia-Fritz--Pasten--Vidaux [S3] prove undecidability with extra height-comparison predicates, which are not part of the present input language. Koenigsmann [E1] gives a universal definition of $\mathbb Z$ in $\mathbb Q$; this is not an existential definition. None of these facts is used with its qualifiers removed. The constructions below are elementary reductions, not claims of new undecidability theorems.

First test: clearing denominators does not transfer the answer.

For $f\in\mathbb Z[x_1,\ldots,x_n]$ of total degree $d$, define \[ F(a_1,\ldots,a_n,b)=b^df(a_1/b,\ldots,a_n/b). \] This is an integer polynomial, and $f$ has a rational zero exactly when $F$ has an integer zero with $b\ne0$. The forward direction uses a common positive denominator; the reverse direction divides by a nonzero $b$. The condition $b\ne0$ is essential. For instance, the homogenization of $x^2+y^2+1$ has the zero vector as an integer zero, although the original polynomial is positive on every rational pair. Its zero at the origin of the homogeneous coordinate space is not a rational affine point.

This implication reduces the rational question to a special collection of integer existence questions. Undecidability of the larger collection does not imply undecidability of the special one. In the other direction, an integer polynomial may acquire rational solutions absent over the integers: $2x-1=0$ is the simplest example. Thus simply using the same polynomial does not reduce integer solvability to rational solvability. The missing operation in that proposed reduction is restriction of the quantified variables to integers.

The finite-generation distinction can also be checked without a theorem. For rationals $r_1,\ldots,r_s$, let $D$ be a common multiple of their denominators. Then \[ \mathbb Z[r_1,\ldots,r_s]\subseteq\mathbb Z[1/D]. \] Every denominator on the right has all prime factors dividing $D$. If $p\nmid D$ is prime, $1/p$ is missing. Hence $\mathbb Q$ is not finitely generated as a ring. Taking a union over all finite prime sets does not turn a theorem about any one of these rings into a decision procedure, or an undecidability reduction, over their union.

Lemma 21.1: the exact definability bridge.

Suppose there is a fixed integer polynomial $P(t,u_1,\ldots,u_m)$ such that \begin{equation}\label{wsref-0-63-6f-6e-74-32-31-3a-69-6e-74-65-67-72-61-6c-69-74-79} t\in\mathbb Z\quad\Longleftrightarrow\quad \exists u\in\mathbb Q^m:\ P(t,u)=0 \qquad(t\in\mathbb Q). \end{equation} Then Hilbert's tenth problem over $\mathbb Q$ is undecidable.

Proof. Given any $f\in\mathbb Z[x_1,\ldots,x_n]$, introduce separate witness tuples $u^{(1)},\ldots,u^{(n)}$ and form \[ Q_f(x,u)=f(x)^2+\sum_{i=1}^n P(x_i,u^{(i)})^2. \] Over $\mathbb Q\subset\mathbb R$, a sum of squares vanishes if and only if every summand vanishes. Thus $Q_f$ has a rational zero precisely when $f$ has an integer zero. The map $f\mapsto Q_f$ is effective because $P$ is fixed. A rational-solvability decider would therefore decide the integer problem, contrary to the Matiyasevich--Robinson--Davis--Putnam theorem recalled in [S1].$\square$

The hypothesis is not established here. Replacing it by $t\in\mathbb Z\Longleftrightarrow\forall u\,\Phi(t,u)$ changes the resulting formula to one with universal quantifiers after the existential $x$ variables. The present decision oracle answers only existential polynomial questions. Negating the universal formula provides witnesses for nonintegrality, not witnesses for integrality; negation cannot simply be moved through $\exists x$ while preserving the problem. Consequently Koenigsmann's theorem does not supply the displayed $P$ by a syntactic change of quantifier. A Diophantine model of integer arithmetic would be another sufficient route, but none is constructed in this attempt.

Lemma 21.2: degree four already contains the full difficulty.

Every rational polynomial-solvability question can be effectively converted to one equation of total degree at most four, allowing additional variables.

Proof. Evaluate the input polynomial by a finite arithmetic circuit with addition, multiplication and integer constants. Repeated squaring handles exponents encoded in binary. Attach a rational variable $y_j$ to each gate. An addition gate is enforced by $g_j=y_j-y_a-y_b=0$, a multiplication gate by $g_j=y_j-y_ay_b=0$, and a constant gate by $g_j=y_j-c=0$. Include the output gate equation $y_{\mathrm{out}}=0$. Form \begin{equation}\label{wsref-0-63-6f-6e-74-32-31-3a-71-75-61-72-74-69-63} Q(x,y)=y_{\mathrm{out}}^2+\sum_j g_j(x,y)^2. \end{equation} Each $g_j$ has degree at most two, so $Q$ has degree at most four. If $f(x)=0$, the actual gate values give a rational zero of $Q$. Conversely, a rational zero forces each gate equation to hold; induction in circuit order shows that $y_{\mathrm{out}}=f(x)=0$. The construction terminates and writes an explicit integer polynomial. $\square$

Constants and identically zero polynomials can be handled directly; free unused input variables cause no problem. The ordering of $\mathbb Q$ is used in the sum-of-squares step, so this argument is not asserted over an arbitrary field. The number of variables grows with the circuit. Thus a solution for quartics with unbounded dimension would solve the whole target; a result for one fixed number of variables would not do so without a further reduction.

Attempt B: replace enumeration by a certified height bound.

For a reduced fraction $a/b$, $b>0$, define $H(a/b)=\max\{|a|,b\}$ and $H(q_1,\ldots,q_n)=\max_iH(q_i)$, with height one for an empty tuple. Each bounded-height box is finite and effectively enumerable. Exact rational arithmetic decides whether any given tuple is a zero. Increasing the bound therefore semidecides positive instances.

Proposition 21.3. Fix any effective finite binary encoding of the polynomial inputs, of length $L(f)$. The following are equivalent: (i) the rational-solvability set is decidable; (ii) there is a total computable $B:\mathbb N\to\mathbb N$ such that every solvable $f$ has a zero of height at most $B(L(f))$.

Proof. Given (ii), compute $B(L(f))$, enumerate the finite box, and test every tuple. Return no if none is a zero. This halts and is correct by the bound. For the reverse implication, enumerate all valid input strings of length at most $L$ and use the hypothetical decider on each. There are finitely many. For every one declared solvable, run the rational enumeration until its first solution is found. Each such search halts because its positive decision was correct. Return the maximum of their heights and one. This is a terminating algorithm for $B(L)$ and has the required property.$\square$

This is a proved reduction, not an estimate for $B$. It isolates the effective ingredient missing from brute force. Mere finiteness of the set of inputs at each length gives a mathematical maximum of least solution heights, but it does not establish that the maximum is computable. Conversely, no polynomial, exponential, or otherwise modest growth is required of $B$ for decidability. Showing that one proposed small bound fails cannot disprove existence of every computable bound.

An exact quartic stress test for small-height guesses.

For $m\ge1$, consider \begin{equation}\label{wsref-0-63-6f-6e-74-32-31-3a-63-68-61-69-6e} Q_m(x_1,\ldots,x_m)=(x_1-2)^2 +\sum_{i=1}^{m-1}(x_{i+1}-x_i^2)^2. \end{equation} The nonnegative summands force the unique rational zero \[ x_i=2^{2^{i-1}}\quad(1\le i\le m),\qquad H(x)=2^{2^{m-1}}. \] For $m\ge2$ the degree is four, the coefficients after expansion are bounded independently of $m$, and there are $O(m)$ monomials. In a sparse encoding with binary variable indices the input length is $O(m\log(m+2))$. The largest numerator needs $2^{m-1}+1$ binary digits. It therefore defeats every bound polynomial in input length on the bit length of a required witness. For $m=1$ the equation simply has the unique zero $2$, agreeing with the formula.

This is an obstruction to a small-witness shortcut, not an undecidability proof: the displayed double-exponential height is entirely computable. It also rules out a height bound depending only on degree and the largest coefficient while ignoring the number of variables. The quantifier over dimension in the original question is doing real work.

Why finite local checks are not a general negative certificate.

Even checking integrality of one rational against a fixed list of primes does not enforce integrality at every prime. For any finite set $S$, choose a prime $r\notin S$. Then $1/r$ is integral in $\mathbb Q_p$ for each $p\in S$, but is not an integer. This elementary test invalidates a proposal that simply substitutes finitely many local integrality tests for (cont21:integrality). It does not exclude more sophisticated finite existential encodings using additional variables. Likewise, local-global theorems for special polynomial families require their hypotheses; no general local-global principle is inferred from passing any finite list of congruence tests.

Verification, first gaps, and outcome.

The companion exact-arithmetic checks evaluate the squaring chains, confirm their heights, and test the gate-equation transformation on a small rational grid. The proofs, rather than those finite samples, establish the reductions for every polynomial. The original choice of rational witnesses, all dimensions, and unrestricted computable running time is retained throughout.

UNRESOLVED. The positive route stops at a total computable height bound, and the negative route stops at an existential arithmetic model or a definition such as (cont21:integrality). The quartic reduction and the explicit height family identify constraints any continuation must respect. Next steps are to construct the missing existential model, to obtain certified height bounds on a larger geometric class, or to prove that a proposed local-global algorithm supplies both positive and negative termination certificates. No universal algorithm or proof of its impossibility is obtained here.

Sources

• S1 Sylvy Anscombe, Valentijn Karemaker, Zeynep Kisakürek, Vlerë Mehmeti, Margherita Pagano and Laura Paladino, A survey of local-global methods for Hilbert's Tenth Problem, abstract and Section1. https://arxiv.org/pdf/2309.14987. Formulation source.
• S2 Hilbert's tenth problem for finitely generated rings. https://arxiv.org/html/2602.04468v1. Further reference; not a proof endorsement.
• S3 Effectivity for existence of rational points is undecidable. https://arxiv.org/abs/2311.01958. Further reference; not a proof endorsement.
• E1 Jochen Koenigsmann, Defining $\mathbb Z$ in $\mathbb Q$, Annals of Mathematics 183 $2016$, 73--93; arXiv:1011.3424. https://arxiv.org/abs/1011.3424. Universal definition, not the existential definition assumed in Lemma 21.1; consulted 27 September 2026.

Hilbert's Tenth Problem over the Rationals

Definitions and mathematical statement

An input is a finite description of $f\in{\mathbb{Z}}[x_1,\ldots,x_n]$, with no fixed bound on $n$, degree, or coefficient size. Define the decision set \[ \mathcal D_{{\mathbb{Q}}}=\{\langle f\rangle:\exists(q_1,\ldots,q_n)\in{\mathbb{Q}}^n, f(q_1,\ldots,q_n)=0\}. \] Determine whether $\mathcal D_{{\mathbb{Q}}}$ is decidable: one algorithm must halt on every input and return its correct membership bit. Enumeration of rational solutions only semidecides yes-instances and is not a solution. The selected assertion concerns computability, with no polynomial-time demand.

Formulation and concept references: [S1].

Short English statement

Can an algorithm always decide whether a polynomial equation with integer coefficients has a rational solution?

Research attempt

Current frontier.

Research check: 27 September 2026. The 2026 Koymans--Pagano survey states undecidability over infinite finitely generated rings. It does not include ${\mathbb{Q}}$: a ring generated by finitely many rationals inverts only finitely many primes. [S2]. Garcia-Fritz--Pasten--Vidaux prove undecidability when rational equations are augmented with height-comparison predicates, while explicitly leaving the ordinary rational problem open. Those predicates cannot silently be added to this entry. [S3]. The local-global survey describes the positive-existential definability route and its limitations. [S1].

Attack route.

A negative answer could follow from a Diophantine interpretation of integer arithmetic. A positive answer could follow from a total computable bound for the least rational solution. A third idea is to exhaust localizations with finitely many inverted primes. We investigate the exact height-bound equivalence and use explicit equations to stress test the latter two strategies.

Attempt: computable height versus a decision procedure.

Fix a decidable binary encoding of integer polynomials. For $q=a/b$ in lowest terms with $b>0$, set $H(q)=\max(|a|,b)$ and $H(q_1,\ldots,q_n)=\max(1,H(q_1),\ldots,H(q_n))$. The following two statements are equivalent: \[ \mathcal D_{{\mathbb{Q}}}\text{ is decidable}; \tag{21.1} \] \[ \begin{gathered} \text{there is a total computable }B:{\mathbb{N}}\to{\mathbb{N}}\text{ such that}\\ f\in\mathcal D_{{\mathbb{Q}}},\ |\langle f\rangle|\leq L \ \Longrightarrow\ \exists q:\ f(q)=0,\ H(q)\leq B(L). \end{gathered} \tag{21.2} \] If $21.2$ holds, enumerate all reduced fractions with numerator absolute value and positive denominator at most $B(L)$, and all tuples of the required length. Exact rational arithmetic decides whether any is a zero. The list is finite, and $21.2$ justifies returning no at its end.

Conversely, given a decider in $21.1$, list the finitely many valid polynomial encodings of length at most $L$. Decide each. For every positive instance, enumerate rational tuples in increasing height until one solution is found. Each of these finitely many searches terminates; take the maximum of the found heights and 1. This algorithm computes $B(L)$. Neither its running time nor the size of $B(L)$ is controlled. Thus this is a computability equivalence, exactly at the strength of the selected target, not an effective numerical estimate.

Attempt: reduction to quartic sums of squares.

Every polynomial can be evaluated by a finite straight-line computation using addition and multiplication with integer constants. Give each gate an auxiliary variable $z_j$. Its consistency equation has degree at most two: $z_j-z_a-z_b=0$, $z_j-z_az_b=0$, or $z_j-c=0$. Include the equation setting the final value to zero. If the resulting equations are $g_1=\cdots=g_r=0$, replace them by \[ F(x,z)=\sum_{j=1}^r g_j(x,z)^2=0. \tag{21.3} \] Over ${\mathbb{Q}}\subset{\mathbb{R}}$, a sum of squares is zero exactly when every summand is zero. The auxiliary variables are uniquely determined by the inputs in gate order. Hence $F$ has a rational zero if and only if the original polynomial does, and $\deg F\leq4$. This reduction is effective for all finite inputs; a dense or sparse encoding may change its length but not its computability. A decider for this quartic sum-of-squares subclass would therefore decide the original problem. No fixed bound on the number of variables is asserted.

Now test a proposed small height bound on the especially simple family \[ F_r(x_0,\ldots,x_r)=(x_0-2)^2+ \sum_{j=0}^{r-1}(x_{j+1}-x_j^2)^2. \tag{21.4} \] Its unique rational zero has $x_j=2^{2^j}$, by nonnegativity followed by induction. Thus the least multiplicative height is $2^{2^r}$ even though the degree is four and the sparse description has length $O(r\log(r+2))$. In particular no bound of the form $2^{L^A}$ with fixed $A$ works for all these descriptions: $2^r$ eventually exceeds every fixed power of $r\log(r+2)$. This is not evidence that every computable bound fails; a doubly exponential computable bound easily accommodates this family.

Attempt: why finite localizations do not finish the search.

Let $S$ be a finite prime set and $R_S={\mathbb{Z}}[p^{-1}:p\in S]$. If $p\notin S$, the polynomial $px-1$ has the rational zero $1/p$, but no zero in $R_S$, since every reduced denominator in $R_S$ is supported on $S$. Therefore a negative answer for any one finite localization cannot be promoted to a negative answer over ${\mathbb{Q}}$. Exhausting the primes recovers a semidecision for rational solutions, but no stopping rule for negative instances. The fact that ${\mathbb{Q}}$ is a union of these rings does not transfer their undecidability to the union or provide its decider.

For the opposing route, an explicit polynomial $D(t,u_1,\ldots,u_s)$ defining $t\in{\mathbb{Z}}$ by existential rational quantification would let us replace each integer variable of an integer Diophantine equation by its rational counterpart together with $D=0$. Combining all equations as in $21.3$ would yield a reduction of integer undecidability to this target. The needed existential definition has not been constructed here; a definition containing universal quantifiers or height predicates does not meet this requirement. [S1], [S3].

Stress test.

The equivalence $21.1$--$21.2$ bounds at least one point on each nonempty variety, not every point. Finite rational sets and varieties with infinitely many points are handled in exactly the same way. Zero polynomials and constant nonzero polynomials cause no difficulty. No compactness argument has converted pointwise eventual discovery into an effective bound. The quartic reduction uses order only as a proof that rational squares cannot cancel; it does not add an inequality oracle to the input language.

Outcome.

Outcome: Conditional reduction. The attempt gives an exact reduction to quartic sums of squares and an exact computable-minimal-height criterion, with a double-exponential height stress family. These reformulations are not claimed to be new characterizations. Neither the computable bound nor an existential integer interpretation is established. The selected assertion of a total decider remains undecided by this notebook.

Sources

• S1 Sylvy Anscombe, Valentijn Karemaker, Zeynep Kisakürek, Vlerë Mehmeti, Margherita Pagano and Laura Paladino, A survey of local-global methods for Hilbert's Tenth Problem, abstract and Section1. https://arxiv.org/pdf/2309.14987. Catalogue formulation source.
• S2 Hilbert's tenth problem for finitely generated rings. https://arxiv.org/html/2602.04468v1. Catalogue research/status reference; not a proof endorsement.
• S3 Effectivity for existence of rational points is undecidable. https://arxiv.org/abs/2311.01958. Catalogue research/status reference; not a proof endorsement.