Proposition 3.14 — Reduce inputs while preserving APS
ProvedAPSCounting893.Main.reduce_inputs_preserving_apsalgebraic-geometryapscomplexity-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let have nonconstant coordinates, image dimension , and . Let be finite and nonempty. Sample all coefficients of affine equations independently from , parametrize the resulting plane, and, if , sample linear combinations of the outputs. Then
An unsuccessful parametrization is part of the failure event. The output is the actual composed and projected map , with both directions of APS preservation retained.
Differences from the source:
- encoding: random affine sections and optional output projection → cardinality ratio on a finite product sample space, using a selected rational affine parametrization; reason: all coefficients are independent and uniform, and unused output coefficients when m=r+1 do not change the probability
Preamble
import Definitions.Def_APSCounting893_Main_RandomReduction set_option autoImplicit false
Formal statement
namespace APSCounting893.Main
theorem reduce_inputs_preserving_aps (n m r : ℕ) (F : PolynomialMap ℂ n m)
(hnonconstant : ∀ i, 0 < (F i).totalDegree)
(hdim : RSCapacity.algDim (imageClosure F) = ((r : ℕ∞) : WithBot ℕ∞))
(hr : 1 ≤ r) (hrm : r < m) (B : Finset ℚ) (hB : B.Nonempty) :
reductionSuccessProbability (r := r) F B ≥
1 - ((2 * (n - r) * inputDegree F ^ m + (r + 1) * inputDegree F ^ r : ℕ) : ℝ) /
(B.card : ℝ) := by sorry
end APSCounting893.Main
Source
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla, STOC 2027 submission #893 (October 2026), Proposition 3.14, p. 14, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.