Theorem 7.8 — Integrality iff the powered system has no APS
OpenAPSCounting893.Main.Supplement.integral_iff_powered_nonapsalgebraic-geometrycomplexity-theoryintegral-closurep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For complex polynomials , let , and . For every integer set and , where is independent. Then
The bound is computed from the data without an integrality assumption or a supplied certificate. Every powered generator and both last outputs occur. This is the companion theorem underlying the forward decision reduction.
Differences from the source:
- encoding: an integer D at least the displayed nonnegative bound → D is a natural number satisfying the same bound, and M=D+1; reason: the bound is positive, so this represents exactly all source integers in its stated range
- encoding: the powered tuple in C[x,u] → Fin (m+2) outputs and the last independent variable u; reason: the formula is u times fi to the power M, including zero targets and generators under the source conventions
Preamble
import Definitions.Def_APSCounting893_Main_Supplement_Certificates set_option autoImplicit false
Formal statement
namespace APSCounting893.Main.Supplement
/-- Theorem 7.8: every D above the bound, defined independently of integrality. -/
theorem integral_iff_powered_nonaps (n m : ℕ) (F : PolynomialMap ℂ n m)
(f : Polynomials ℂ n) (D : ℕ) (hD : certificateBound F f ≤ D) :
IntegralOverGenerators F f ↔ ¬ hasAPS (poweredSystem F f (D + 1)) := by sorry
end APSCounting893.Main.Supplement
Source
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla, STOC 2027 submission #893 (October 2026), Theorem 7.8, p. 31