claimroutineinferred_dep

H10(Q) has Turing degree 0'

Shows H10(Q) has Turing degree 0′0'
exact degree feeding the restricted cases
Claim·§7 Turing degree and a quartic normal form·inside corDegree 0' for rational solvability and quartic forms

Statement (paper)

The set H10(Q)\mathrm{H10}(\Q) has Turing degree 0′0': the halting set is many-one reducible to H10(Z)\mathrm{H10}(\Z), the sets H10(Z)\mathrm{H10}(\Z) and H10(Q)\mathrm{H10}(\Q) are computably enumerable and hence Turing reducible to the halting set, and together with H10(Z)≤TH10(Q)\mathrm{H10}(\Z)\le_{\mathrm T}\mathrm{H10}(\Q) this gives that H10(Q)\mathrm{H10}(\Q) has the degree of the halting problem.

In plain English

The set H10(Q)\mathrm{H10}(\Q) of integral polynomials with a rational zero has the Turing degree of the halting problem, 0′0'.

Why it's here

The upper bound holds because H10(Z)\mathrm{H10}(\Z) and H10(Q)\mathrm{H10}(\Q) are computably enumerable, so both are Turing reducible to the halting set. For the lower bound, the halting set many-one reduces to H10(Z)\mathrm{H10}(\Z) (the classical MRDP theorem), and the previous claim gives H10(Z)≤TH10(Q)\mathrm{H10}(\Z)\le_{\mathrm T}\mathrm{H10}(\Q). Chaining these gives the degree 0′0', which the restricted versions (i) and (ii) later inherit.
Classified routine:
Direct consequence of the preceding claim (H10(Z) ≤_T H10(Q)) combined with the MRDP theorem (Matiyasevich 1970; Davis–Putnam–Robinson) giving K ≤_m H10(Z), and the standard observation that c.e. sets are Turing reducible to the halting set.

Uses

claimOracle reduces integer to rational solvability

Used by

claimQuartic and quadratic-sum problems have degree 0'

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "H10(Q) has Turing degree 0'" rests on claim-thm-degree-normal-form-1