memspanhom. A polynomial computed by a reduced matrix-symmetric circuit of support
size ≤k and support depth ≤Δ is a linear combination of homomorphism polynomials of
patterns of Δ-forestwidth at most k−1.
Applies PatternsInductionMain.existsphi (lem:induction) at g:=C.out. Since
minSupportCC.out=∅ (PatternsSupportBasic.minSupportout), supOfhrighnC.out=∅ too
(supOfeqminSupport), so leftCardhrighnC.out=rightCardhrighnC.out=0; the witness
φ, lifted from depth scCC.out to Δ (sclesupportDepth, hdepth, spanTPmono), is
evaluated at the (unique, since the arities are 0) canonical enumerations, giving p
(computesAtunique, since C.Computesp unfolds to C.ComputesAtC.outp). Every generator
labelledHomKGn of spanTPKΔkn(Finset.univ:Finset(Fin0⊕Fin0)), evaluated at any
point, is exactly the unlabelled homomorphism polynomial homKG.Fn
(labelledHomeqhomofzero, since the defining if-condition of labelledHom is vacuously
true at arity (0,0)), and G∈TΔ,k(0,0) is exactly ForestwidthLEΔ(k−1)G.F
(PatternsLabelledUnlabelled.inClassofPatterniff, using G=ofPatternG.F since both label
maps out of Fin0 are forced to be Fin.elim0); evalmemspanhom packages this as a
Submodule.spaninduction argument, stated for an arbitrary arity (ℓ,r) with ℓ=r=0 as
hypotheses (rather than literal Fin0s) so that it can be substed in directly against
leftCardhrighnC.out/rightCardhrighnC.out, with no further reindexing needed.