Theorem 1.8 — Integral closure membership in CH and non-integrality reduction
OpenAPSCounting893.Main.Supplement.integral_closure_in_chFor valid circuit or sparse inputs over the encoded rational, number or finite fields, let be the first output, let be the remaining outputs, and let . Integral-closure membership has a single fixed-level Counting Hierarchy decider, and non-integrality admits a deterministic polynomial-time many-one reduction to APS:
The decider and reduction work uniformly over all valid inputs, including division gates with the published promises and sparse lists with binary exponents. Integrality is over the described base field and APS over its algebraic closure. There is no restriction on expanded degree, characteristic or separability. This supplies the paper's integral-closure complexity conclusion alongside the referenced APS goal.
Differences from the source:
- encoding: binary circuit and sparse instances and their promises → a common SystemInput wrapper, with f first and valid-source many-one correctness; reason: representation tags, field descriptions and all bit lengths remain charged; invalid inputs impose no correctness requirement
- encoding: membership belongs to CH → existence of a total language in CH agreeing on every valid integral instance; reason: one language, level, machine and polynomial bound precede every input; no particular CH level is asserted
- encoding: Problem 1.2 uses the complex subalgebra on rational input, and Remark 1.9 uses the base field → integrality over the presented base-field subalgebra for all encoded families; reason: integral dependence of these polynomials descends and ascends under scalar extension, so rational inputs give the same decisions
import Definitions.Def_APSCounting893_Main_Supplement_DecisionProblems set_option autoImplicit false
namespace APSCounting893.Main.Supplement
/-- Theorem 1.8, including binary sparse inputs, division promises and Remarks 1.9/7.10.
The language, level, machines and polynomial bounds precede every field and input. -/
theorem integral_closure_in_ch :
(∃ L : Language, InCountingHierarchy L ∧
∀ I : SystemInput, I.ValidIntegral → (L I.encode ↔ I.Integral)) ∧
PolynomialManyOne SystemInput.ValidIntegral (fun I => ¬ I.Integral)
SystemInput.Valid SystemInput.APS := by sorry
end APSCounting893.Main.Supplement