Section 3.1 — is invariant under relabelling the indices
ProvedResultantVNP.charCoeff_perm_invariantalgebraic-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1resultantsvnp
For every , every and every permutation , relabelling the indices of the symmetric tensor by , i.e. substituting , leaves unchanged.
The paper derives this from the invariance of (Lemma 2.8), which must hold in each homogeneous component. It is the invariance used in the proof of Theorem 3.5.
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: indices [n] = {1, …, n} → Fin n (0-based); reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_ResultantVNP_charCoeff
Formal statement
namespace ResultantVNP
/-- **Invariance of `Φ_{n,s}` under relabelling.** `Det_n` is invariant under relabelling the indices by
a permutation `π ∈ S_n`; because the invariance must hold in each homogeneous component, it also
applies to `Φ_{n,s}` for all `s ∈ ℕ`: the substitution `a_{{i,j,k}} ↦ a_{{π(i),π(j),π(k)}}` leaves
`Φ_{n,s}` unchanged.
Bhargav–Curticapean–Jindal–Shukla, *Multivariate Resultants: Complexity and Applications to Real Feasibility*, STOC 2027 submission manuscript (sha256 8827709b…7f8271), Section 3.1, invariance of Φ_{n,s}, p.14 (the two sentences after Definition 3.1).
**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. Stated for every `n` (for `n = 0` it is trivial). -/
theorem charCoeff_perm_invariant (𝓡 : ResultantSystem) (n s : ℕ) (π : Equiv.Perm (Fin n)) :
MvPolynomial.rename (Sym.map π) (charCoeff 𝓡 n s) = charCoeff 𝓡 n s := by sorry
end ResultantVNP
Source
Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission (manuscript sha256 8827709b…7f8271), Section 3.1, invariance of Φ_{n,s} (after Definition 3.1), p.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.