Theorem 1.11 — Non-APS and integral closure are many-one equivalent
OpenAPSCounting893.Main.Supplement.nonaps_equivalent_integralityUnder the published circuit and sparse input promises and coefficient encodings, non-existence of APS and integral-closure membership are equivalent under deterministic polynomial-time many-one reductions:
Both reductions preserve validity and the base coefficient presentation and have fixed machines and polynomial time bounds before all inputs. Algebraic correctness also holds over every algebraically closed field : for an independent , non-APS of is equivalent to integrality of over ; for any target , integrality over is equivalent to non-APS of for all sufficiently large integers . Thus Remark 1.12 is retained without a restriction on characteristic, while binary runtime is asserted for the encoded families. This joins the two decision problems in both directions.
Differences from the source:
- encoding: polynomial-time reductions on the stated inputs → promise reductions between the common encoded SystemInput predicates; reason: the published coefficient presentations, division promises and binary sparse inputs are retained
- encoding: the equivalence works over all algebraically closed fields → fresh-variable correctness and eventual powered-system correctness over every algebraically closed K, together with uniform binary reductions on encoded families; reason: no Turing encoding of arbitrary abstract fields is presumed; the source does not specify one
import Definitions.Def_APSCounting893_Main_Supplement_DecisionProblems set_option autoImplicit false
namespace APSCounting893.Main.Supplement
/-- Theorem 1.11 / Remark 1.12. Abstract fields have algebraic correctness;
ordinary binary computation is asserted on the finitely presented coefficient families. -/
theorem nonaps_equivalent_integrality :
PolynomialManyOne SystemInput.Valid (fun I => ¬ I.APS)
SystemInput.ValidIntegral SystemInput.Integral ∧
PolynomialManyOne SystemInput.ValidIntegral SystemInput.Integral
SystemInput.Valid (fun I => ¬ I.APS) ∧
PoweredAlgebraicReduction ∧
(∀ (K : Type) [Field K] [IsAlgClosed K] (n m : ℕ)
(F : PolynomialMap K n m),
(¬ AlgebraicAPS F) ↔ IntegralOverGenerators (scaledGenerators F) (freshVariable n)) := by sorry
end APSCounting893.Main.Supplement