Proof of `Characterisation of symmetric VP`
groundedproofs/Lax461425Proofs/SymVPCharacterisation.lean · lax-461425
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
consists of the families spanned by homomorphism polynomials of patterns of bounded treewidth. For large , the support theorem bounds the support size of a rigidified circuit, and the bounded-depth characterisation (with the support depth as depth bound) applies; for the finitely many remaining , matrix-invariance and the general homomorphism spanning theorem suffice. Conversely, a common depth bound for the finitely many patterns in each linear combination gives circuits via the bounded-depth characterisation, while finitely many exceptional indices are covered by symmetric ABPs.