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

Proof of `Homomorphism polynomials from symmetric circuits`

groundedproofs/Lax461425Proofs/PatternsFromCircuits.lean · lax-461425

What this proof establishes

no assumptions

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

memspanhommem_span_hom. A polynomial computed by a reduced matrix-symmetric circuit of support size ≤k≤ k and support depth ≤Δ≤ Δ is a linear combination of homomorphism polynomials of patterns of ΔΔ-forestwidth at most k−1k - 1.

Applies PatternsInductionMain.existsphiPatternsInductionMain.exists_phi (lem:inductionlem:induction) at g:=C.outg := C.out. Since minSupportCC.out=∅minSupport C C.out = ∅ (PatternsSupportBasic.minSupportoutPatternsSupportBasic.minSupport_out), supOfhrighnC.out=∅supOf hrig hn C.out = ∅ too (supOfeqminSupportsupOf_eq_minSupport), so leftCardhrighnC.out=rightCardhrighnC.out=0leftCard hrig hn C.out = rightCard hrig hn C.out = 0; the witness φφ, lifted from depth scCC.outsc C C.out to ΔΔ (sclesupportDepthsc_le_supportDepth, hdepthhdepth, span𝔗Pmonospan𝔗P_mono), is evaluated at the (unique, since the arities are 00) canonical enumerations, giving pp (computesAtuniquecomputesAt_unique, since C.ComputespC.Computes p unfolds to C.ComputesAtC.outpC.ComputesAt C.out p). Every generator labelledHomKGnlabelledHom K G n of span𝔗PKΔkn(Finset.univ:Finset(Fin0⊕Fin0))span𝔗P K Δ k n (Finset.univ : Finset (Fin 0 ⊕ Fin 0)), evaluated at any point, is exactly the unlabelled homomorphism polynomial homKG.Fnhom K G.F n (labelledHomeqhomofzerolabelledHom_eq_hom_of_zero, since the defining ifif-condition of labelledHomlabelledHom is vacuously true at arity (0,0)(0,0)), and G∈𝒯Δ,k(0,0)G ∈ 𝒯^{Δ,k}(0,0) is exactly ForestwidthLEΔ(k−1)G.FForestwidthLE Δ (k - 1) G.F (PatternsLabelledUnlabelled.inClassofPatterniffPatternsLabelledUnlabelled.inClass_ofPattern_iff, using G=ofPatternG.FG = ofPattern G.F since both label maps out of Fin0Fin 0 are forced to be Fin.elim0Fin.elim0); evalmemspanhomeval_mem_span_hom packages this as a Submodule.spaninductionSubmodule.span_induction argument, stated for an arbitrary arity (ℓ,r)(ℓ, r) with ℓ=r=0ℓ = r = 0 as hypotheses (rather than literal Fin0Fin 0s) so that it can be substsubsted in directly against leftCardhrighnC.outleftCard hrig hn C.out/rightCardhrighnC.outrightCard hrig hn C.out, with no further reindexing needed.