Arithmetic-circuit substitution with a gate-count bound
ProvedResultantVNP.circuit_substitution_boundalgebraic-complexitycircuitsresultants
Let C be a fan-in-two arithmetic circuit over with variables in an arbitrary type , and let be its number of addition and multiplication gates. Let be a polynomial in variables of type for every . Suppose each has an arithmetic circuit with at most gates. Then the polynomial obtained by substituting in the output of C has a circuit D satisfying
Size counts gates only. The assertion imposes no bound on the number of leaf nodes in C and allows repeated variables, arbitrary complex constants, and shared intermediate results. This is a reusable composition estimate for the ResultantVNP.Circuit representation.
Preamble
import Mathlib import Definitions.Def_ResultantVNP_Circuit
Formal statement
namespace ResultantVNP
theorem circuit_substitution_bound {σ τ : Type} (C : Circuit σ)
(f : σ → MvPolynomial τ ℂ) (s : ℕ)
(hf : ∀ x, ∃ D : Circuit τ, D.value = f x ∧ D.size ≤ s) :
∃ D : Circuit τ,
D.value = MvPolynomial.aeval f C.value ∧
D.size ≤ (2 * C.size + 1) * (s + 1) := by
sorry
end ResultantVNPSource
Supporting circuit-composition claim for Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission #1103, Section 3.1 circuit convention, p.14. The explicit bound is a derived auxiliary claim, not a separately numbered statement in the paper. It follows by pruning unused nodes, using at most 2g+1 input leaves, and grafting the substitution circuits. https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1103.pdf