corollaryroutine

Degree 0' for rational solvability and quartic forms

So H10(Q) has Turing degree 0′0', even for quartics and sums of squares
payoff of the main theorem
Corollary·thm:degree-normal-form·§7 Turing degree and a quartic normal form

Statement (paper)

With the usual effective coding, let H10(Q)\mathrm{H10}(\Q) be the set of integral polynomials having a rational zero, with the number of variables part of the input. Then H10(Q)\mathrm{H10}(\Q) has Turing degree 0′0', the degree of the halting problem. The same is true for each of the following restricted input problems: \begin{enumerate}[label=(\roman*),leftmargin=*] \item rational solvability for integral polynomials of total degree at most four; \item given a nonempty finite list q1,…,qs∈Z[X1,…,XN]q_1,\ldots,q_s\in\Z[X_1,\ldots,X_N], each of total degree at most two, whether ∑i=1sqi2\sum_{i=1}^s q_i^2 has a zero in QN\Q^N. \end{enumerate} No bound is imposed on the number of variables, the number of summands in (ii), or the coefficient heights.

In plain English

The set H10(Q)\mathrm{H10}(\Q) of integral polynomials with a rational zero has Turing degree 0′0', the degree of the halting problem. The same holds for rational solvability of polynomials of total degree at most four, and for deciding whether a sum of squares of degree-at-most-two integral polynomials has a rational zero, with no bound on variables, summands or coefficient heights.

Why it's here

This upgrades the main undecidability theorem to an exact degree computation and a normal form. The upper bound comes from computable enumerability and the lower bound from a Turing reduction of H10(Z)\mathrm{H10}(\Z) to H10(Q)\mathrm{H10}(\Q) via the main theorem's search. Circuit normalization into quadratic equations, collapsed into one sum of squares, then gives many-one reductions to the quartic and sum-of-squares problems, which therefore also have degree 0′0'.
Classified routine:
Direct consequence of the main theorem's reduction: H10(Q) is c.e. (upper bound), and the main theorem gives a Turing reduction from H10(Z), which has degree 0' by the MRDP theorem (Matiyasevich 1970). The quartic and sum-of-squares forms follow from the standard Skolem-style reduction of a system to quadratic equations, combined into one sum of squares.

Uses

thmHilbert's tenth problem over Q is undecidable

Used by

Nothing in the paper

Inside the proof

claimOracle reduces integer to rational solvabilityclaimH10(Q) has Turing degree 0'claimCircuit normalization into quadratic equationsclaimQuartic and quadratic-sum problems have degree 0'

Sources

PaperOpen
Section
§7 Turing degree and a quartic normal form
Page
—
Label
thm:degree-normal-form
Line
sections/07-consequences.tex:8
Leannot aligned

Phase 2 aligns this node to a Lean declaration.