claimroutineinferred_dep

Quartic and quadratic-sum problems have degree 0'

Reduces H10(Q) many-one to quartic and sum-of-squares problems, degree

0'

finishes the restricted-degree statements

Claim·§7 Turing degree and a quartic normal form·inside corDegree 0' for rational solvability and quartic forms

Statement (paper)

Let

S_2

denote the list problem in (ii) and

H_{\le4}

the problem in (i). Sending

f

to the list

(q_1,\ldots,q_s)

, and then expanding the squared sum

\sum_{i=1}^s q_i^2

, gives computable many-one reductions

\mathrm{H10}(\Q)\le_{\mathrm m}S_2\le_{\mathrm m}H_{\le4}

, where the expanded polynomial has integral coefficients and total degree at most four. Since both

S_2

and

H_{\le4}

are computably enumerable, both have Turing degree

0'

In plain English

Mapping

f

to the list

(q_1,\ldots,q_s)

and then to the expanded polynomial

\sum_i q_i^2

gives computable many-one reductions

\mathrm{H10}(\Q)\le_{\mathrm m}S_2\le_{\mathrm m}H_{\le4}

, with the expanded polynomial integral of total degree at most four. Since

S_2

and

H_{\le4}

are computably enumerable, both have Turing degree

0'

Why it's here

This finishes the parent theorem for (i) and (ii). The circuit normalization claim supplies the equivalence between a zero of

f

and a zero of

\sum_i q_i^2

. Both restricted problems then many-one reduce from

\mathrm{H10}(\Q)

, which has degree

0'

by the earlier claim, and they are computably enumerable, so each is bounded above by

0'

and also has degree

0'

Classified routine:

Direct bookkeeping consequence of the circuit normalization claim and the degree-0' claim for H10(Q): the standard sum-of-squares trick combines quadratic equations into one quartic, and any c.e. set that a 0'-complete set many-one reduces to has degree 0'.

Uses

claimH10(Q) has Turing degree 0'claimCircuit normalization into quadratic equations

Used by

Nothing in the paper

Sources

PaperOpen

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

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Many-one reductions to restricted problems give degree 0'" rests on claim-thm-degree-normal-form-2
info
inferred_dep
outline: "Many-one reductions to restricted problems give degree 0'" rests on claim-thm-degree-normal-form-3