Output-projection certificate preserving dimension and APS
ProvedAPSCounting893.Main.output_projection_nonvanishing_certificatealgebraic-geometryapsgeneric-projections
Let be a polynomial map with image closure of dimension . Set . There is a nonzero polynomial in the entries of an coefficient matrix such that
For every rational matrix with , let . Then
This is the geometric nonvanishing certificate behind the output-reduction probability bound in Theorem 3.13 and Proposition 3.14. Nonvanishing over a finite rational grid yields the stated exceptional probability by the polynomial zero bound.
Preamble
import Definitions.Def_APSCounting893_Main_RandomReduction set_option autoImplicit false open MvPolynomial
Formal statement
theorem APSCounting893.Main.output_projection_nonvanishing_certificate
{n m r : ℕ} (F : APSCounting893.Main.PolynomialMap ℂ n m)
(hrpos : 0 < r) (hrm : r < m)
(hdim : RSCapacity.algDim (APSCounting893.Main.imageClosure F) = ((r : ℕ∞) : WithBot ℕ∞)) :
∃ p : MvPolynomial (Fin (r+1) × Fin m) ℂ,
p ≠ 0 ∧ p.totalDegree ≤ (r+1)*(APSCounting893.Main.inputDegree F)^r ∧
∀ A : Fin (r+1) × Fin m → ℚ,
eval (fun a => (A a : ℂ)) p ≠ 0 →
RSCapacity.algDim (APSCounting893.Main.imageClosure
(fun i : Fin (r+1) => ∑ j : Fin m, MvPolynomial.C (A (i,j) : ℂ) * F j)) = ((r : ℕ∞) : WithBot ℕ∞) ∧
(APSCounting893.Main.hasAPS F ↔ APSCounting893.Main.hasAPS
(fun i : Fin (r+1) => ∑ j : Fin m, MvPolynomial.C (A (i,j) : ℂ) * F j)) := by sorrySource
Agarwal, Hari, Pandey and Shukla, Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy, STOC 2027 submission #893, Theorem 3.13 and Proposition 3.14, pp.13–14, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf; the projective avoidance argument is Guo, Saxena and Sinhababu, Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity, Theory of Computing 15(16), 2019, Theorem 4.6 and Lemmas 4.7–4.12, pp.18–21, https://theoryofcomputing.org/articles/v015a016/v015a016.pdf; Chow-form incidence and multidegree: Jeronimo, Krick, Sabia and Sombra, The computational complexity of the Chow form, arXiv:math/0210009, Section 1.1, pp.6–7, https://arxiv.org/pdf/math/0210009.