While this submission is a draft, it cannot be used by other submissions.

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.

Read the Lean proof on GitHub

Description

symVPsymVP consists of the families spanned by homomorphism polynomials of patterns of bounded treewidth. For large nn, 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 nn, 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.