Degree bound for a projective incidence relation
ProvedAPSCounting893.Main.projective_incidence_relation_degree_boundalgebraic-geometryapschow-formselimination-theory
Let have image closure of dimension , suppose the origin is absent from that closure, and put . Let be the affine cone closure
Fix a coordinate for which . For and an matrix , define
There exists a nonzero polynomial in the entries of satisfying
Every row of this parametrized matrix annihilates . This is the incidence-relation form of the Chow-form degree bound used to construct the output-projection certificate. The cone and the incidence matrices are actual polynomial constructions; no avoidance property is assumed.
Preamble
import Definitions.Def_APSCounting893_Main_RandomReduction set_option autoImplicit false open MvPolynomial APSCounting893.Main
Formal statement
theorem APSCounting893.Main.projective_incidence_relation_degree_bound
{n m r : ℕ} (F : PolynomialMap ℂ n m)
(hr : 0 < r) (hrm : r < m)
(hdim : RSCapacity.algDim (imageClosure F) = ((r : ℕ∞) : WithBot ℕ∞))
(h0 : ¬ hasAPS F) (j : Fin m) (hj : F j ≠ 0) :
∃ q : MvPolynomial (Fin (r+1) × Fin m) ℂ,
q ≠ 0 ∧ q.totalDegree ≤ (r+1)*(inputDegree F)^r ∧
∀ z ∈ imageClosure (fun i : Fin m => MvPolynomial.X (0 : Fin (n+1)) * MvPolynomial.rename Fin.succ (F i)),
∀ B : Fin (r+1) × Fin m → ℂ,
eval (fun a => z j*B a - (∑ t : Fin m, z t*B (a.1,t))*(if a.2=j then 1 else 0)) q = 0 := by sorrySource
Jeronimo, Krick, Sabia and Sombra, The computational complexity of the Chow form, arXiv:math/0210009, Section 1.1, pp.6–7 (incidence hypersurface and degree deg(V) in each coefficient block), https://arxiv.org/pdf/math/0210009#page=6; applied to the origin projection in Guo, Saxena and Sinhababu, Theory of Computing 15(16), 2019, proof of Theorem 4.6, p.21, https://theoryofcomputing.org/articles/v015a016/v015a016.pdf; polynomial-image degree bound there is at most d^r. This is the incidence relation underlying Agarwal–Hari–Pandey–Shukla, 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