Theorem 1.4, tensor-determinant clause — poly-size circuits for symmetric imply
ProvedResultantVNP.theorem_1_4_symmetric_tensoralgebraic-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1resultantsvnp
In fact, the same conclusion as Theorem 1.4 already holds if poly()-size arithmetic circuits over exist for the family of tensor determinants restricted to symmetric tensors of order three (one variable per unordered triple of indices): then .
Differences from the source:
- encoding: the multivariate resultant Res, the unique integral polynomial with the three properties of Definition 2.1 (existence and uniqueness cited from [GKZ94]) → an arbitrary ResultantSystem 𝓡 (integral polynomials satisfying the three properties for n ≥ 1 and positive degrees), quantified universally; reason: existence is cited, not proved in the paper; by uniqueness every resultant system is the resultant on every admissible degree vector, so the statement is the paper's
- encoding: poly(n)-size arithmetic circuits over ℂ → HasPolySizeCircuits: ∃ c, ∀ n ≥ 1, a fan-in-two circuit with complex constants and at most c·n^c + c gates computes the polynomial; reason: Section 3.1 conventions; c·n^c + c dominates every polynomial; size only, as printed
- encoding: VP and VNP → sets of PolyFamily (number of variables, p_n over Fin (nvars n)); VNP with g_n on exactly nvars n + q n variables; reason: Section 3.1 definitions
Preamble
import Mathlib import Definitions.Def_ResultantVNP_symTensorDet import Definitions.Def_ResultantVNP_HasPolySizeCircuits import Definitions.Def_ResultantVNP_VNP
Formal statement
namespace ResultantVNP
/-- **Theorem 1.4, tensor-determinant clause.** The same conclusion `VP = VNP` already holds if
poly(n)-size circuits exist for the family of tensor determinants `{Det_n(A)}_{n≥1}` restricted to
symmetric tensors `A` of order three.
Bhargav–Curticapean–Jindal–Shukla, *Multivariate Resultants: Complexity and Applications to Real Feasibility*, STOC 2027 submission manuscript (sha256 8827709b…7f8271), Theorem 1.4, tensor-determinant clause, p.6 (proof p.17).
**Formalization Note** The resultant is taken from an arbitrary `ResultantSystem` `𝓡`; by the uniqueness in Definition 2.1 it is the multivariate resultant wherever the paper uses it. Symmetric tensors have one variable per unordered triple of indices (`symTensorDet`). -/
theorem theorem_1_4_symmetric_tensor (𝓡 : ResultantSystem)
(h : HasPolySizeCircuits (fun n => MvPolynomial.map (Int.castRingHom ℂ) (symTensorDet 𝓡 n))) :
VP = VNP := by sorry
end ResultantVNP
Source
Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission (manuscript sha256 8827709b…7f8271), Theorem 1.4, tensor-determinant clause, p.6 (proof p.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.