Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Arithmetic-circuit substitution with a gate-count bound

Proved
ResultantVNP.circuit_substitution_bound

by gjindal · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-complexitycircuitsresultants

Let C be a fan-in-two arithmetic circuit over C\mathbb CC with variables in an arbitrary type σ\sigmaσ, and let ggg be its number of addition and multiplication gates. Let fxf_xfx​ be a polynomial in variables of type τ\tauτ for every x∈σx\in\sigmax∈σ. Suppose each fxf_xfx​ has an arithmetic circuit with at most sss gates. Then the polynomial obtained by substituting x↦fxx\mapsto f_xx↦fx​ in the output of C has a circuit D satisfying

D(y)=C((fx(y))x∈σ),size⁡(D)≤(2g+1)(s+1).D(\mathbf y)=C((f_x(\mathbf y))_{x\in\sigma}),\qquad \operatorname{size}(D)\le (2g+1)(s+1).D(y)=C((fx​(y))x∈σ​),size(D)≤(2g+1)(s+1).

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 ResultantVNP
Source
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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me