Circuit bound for coefficients after affine substitution
ProvedResultantVNP.circuit_affine_coefficient_boundalgebraic-complexitycircuitsresultants
Let be an arithmetic circuit over , let be its number of addition and multiplication gates, and let be fixed for each input variable . For every integer , there is an arithmetic circuit satisfying
The bound is independent of the total degree of the polynomial computed by . This provides the coefficient-extraction step used to pass from tensor determinant circuits to characteristic coefficient circuits.
Formalization Note Circuits count arithmetic gates only; variable and constant leaves have zero cost. Arbitrary shared intermediate results are allowed.
Preamble
import Mathlib import Definitions.Def_ResultantVNP_Circuit
Formal statement
theorem ResultantVNP.circuit_affine_coefficient_bound {σ : Type} (C : ResultantVNP.Circuit σ) (δ : σ → ℂ) (s : ℕ) :
∃ D : ResultantVNP.Circuit σ,
D.value = (MvPolynomial.aeval (fun x =>
Polynomial.C (MvPolynomial.C (δ x)) +
Polynomial.X * Polynomial.C (MvPolynomial.X x)) C.value).coeff s ∧
D.size ≤ 2 * (s+1)^2 * C.size + 1 := by sorrySource
Derived explicit circuit bound for the homogenization step in Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission #1103, proof of Theorem 1.4, p.17. The paper cites Strassen homogenization; this auxiliary statement supplies a direct constructive bound. https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1103.pdf