Valiant's hypothesis is the algebraic analogue of : it asserts that the permanent, and with it every polynomial family defined by exponential sums of easy polynomials, has no polynomial-size arithmetic circuits (Valiant 1979; Bürgisser 2000). Hardness results under this hypothesis tell which natural polynomials are unlikely to be efficiently computable.
The multivariate resultant is a classical object of elimination theory (Gelfand–Kapranov–Zelevinsky 1994; Cox–Little–O'Shea 2005): one polynomial in the coefficients of homogeneous forms in variables whose vanishing decides whether the forms have a common nonzero root. For it is Sylvester's resultant, for linear forms it is the determinant. Its computational complexity matters for polynomial system solving, and Bhargav, Curticapean, Jindal and Shukla (Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission) show that even the resultant of quadratic forms is hard: small circuits for it would collapse VNP to VP.
Let . A system of forms in over has one coefficient variable per pair with . The multivariate resultant is the unique integral polynomial such that (1) exactly when has a solution , (2) , (3) is irreducible in . The resultant of quadratic forms is ; it has variables and degree .
A cubic tensor of dimension defines quadratic forms ; its tensor determinant is . For a symmetric tensor , with one variable per unordered triple of indices, the characteristic coefficient is , where is the diagonal unit tensor.
An arithmetic circuit over has variables and complex constants as leaves and gates that add or multiply two earlier values; its size is the number of gates. A polynomial family is in VP if its number of variables, degree and circuit size are polynomially bounded in , and in VNP if for some and polynomially bounded . A projection substitutes variables or constants for the variables of a polynomial.
The grid assignment sum lives on the toroidal grid with one triangle per position; positions carry disjoint index classes , and .
The paper presents several principal results: algebraic circuit hardness refTheorem 1.4 and VNP-completeness of the characteristic coefficient family refTheorem 1.7; modular and bit hardness refTheorem 1.8, with matching -completeness refTheorem 4.6; sign hardness refTheorem 1.11; and refTheorem 1.13, . The platform permits one goal, so Theorem 1.4 remains the goal while these other principal results are milestones of equal standing.
Milestones for the remaining results in Sections 3–6 and Appendix E were added on 2026-11-16 so that the mission covers every theorem proved in the paper.
Only circuit size is assumed polynomial; the degree is exponential, so the hypothesis does not put the resultant in VP.
Section 3: Algebraic hardness
Section 4: Modular evaluation
Section 5: Hardness of resultant signs
Section 6: Real feasibility
Appendix E: Univariate resultant signs
The theorem places the resultant of quadratic forms among the polynomials whose efficient computation would refute Valiant's hypothesis, although it is not itself in VNP for degree reasons. The same proof gives from quasi-polynomial circuits (Remark 1.5), and Corollary 1.6 transfers the hardness to discriminants of cubic forms. Along the way the paper shows that the coefficient family of the tensor characteristic polynomial is VNP-hard, a new natural VNP-hard family with integer coefficients.
The results are proved on paper in the cited manuscript; none of them, nor the multivariate resultant, VP or VNP, has a machine-checked formalization on this platform. A complete formalization would contain a Lean development of Valiant's classes with p-projections, the classical properties of the resultant (Lemma 2.6, cited from Demazure 2012), and the grid encoding of the permanent. Proving the goal also requires Valiant's VNP-completeness of the permanent and Strassen's homogenization theorem, which are cited and not milestones here.
The obvious route, computing from a circuit for , is the easy half: specialize to , substitute , and extract a homogeneous component. The hard step is to show that this coefficient family encodes the permanent. is defined through a resultant, which has no simple monomial expansion, so it is not visible which monomials of survive on a grid-supported tensor, nor that their common coefficient is nonzero (Theorem 3.5): a cancellation among the many contributions to one coefficient cannot be ruled out by counting alone. The grid side matters as well: the survival argument works for sides of the form (Lemma 3.6), and a naive choice of side does not give it.
The resultant is not constructed. Every statement quantifies over a ResultantSystem: an integral polynomial for every degree vector, required to satisfy the three properties of Definition 2.1 for and positive degrees. By the uniqueness in Definition 2.1 each such system is the resultant, so the statements are the paper's; the alternative of defining the resultant by Classical.choose would give junk without an existence proof. Res, and live in and are mapped to for circuits and projections. Indices are -based (Fin n); unordered triples are Sym (Fin n) 3; is ZMod m; index classes are fibres of a surjective class map.
Circuits are straight-line programs with fan-in two and complex constants, size the number of gates; "polynomially bounded" is . VP and VNP are sets of polynomial families, and the goal is their equality. The circuit hypothesis bounds only the size. Polynomial time in Lemma 3.3 is Mathlib's multi-stack Turing machine model with unary input , and the grid encoding is the explicit construction of Appendix A.1 with the five states per position.
Reusable beyond this mission: the definitions of arithmetic circuits, VP, VNP and p-projections, and the characterization layer of the multivariate resultant. Contributions are welcome on the resultant properties of Lemma 2.6, on the combinatorial Lemmas 3.3, 3.4 and 3.6, and on Valiant's and Strassen's theorems as supporting results.
namespace ResultantVNP
/-- **Theorem 1.4 (Algebraic hardness of resultants).** If the polynomial family `{Res^{(2)}_n}_{n≥1}`
has poly(n)-size arithmetic circuits over `ℂ`, then `VP = VNP`.
Bhargav–Curticapean–Jindal–Shukla, *Multivariate Resultants: Complexity and Applications to Real Feasibility*, STOC 2027 submission manuscript (sha256 8827709b…7f8271), Theorem 1.4, 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. `Res^{(2)}_n ∈ ℤ[u]` is mapped to `ℂ[u]`; "poly(n)-size" is `HasPolySizeCircuits` (size only, no
degree bound). `VP = VNP` is the equality of the two classes of polynomial families of Section 3.1. -/
theorem theorem_1_4 (𝓡 : ResultantSystem)
(h : HasPolySizeCircuits (fun n => MvPolynomial.map (Int.castRingHom ℂ) (quadRes 𝓡 n))) :
VP = VNP := by sorry
end ResultantVNP
Algebraic hardness of resultants. If the polynomial family of resultants of quadratic forms in variables has poly()-size arithmetic circuits over , then
Only the circuit size is assumed polynomial: has degree , so it is not itself in VP or VNP. The theorem says that small circuits for the resultant would refute Valiant's hypothesis .
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.