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

Characterisation of bounded-depth matrix-symmetric circuits

Lax461425.BoundedDepthCharacterisation · concepts/Lax461425/BoundedDepthCharacterisation.lean · lax-461425

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Let K\mathbb{K} be a field of characteristic zero. Let Δ≥1\Delta \geq 1, k≥2k \geq 2, and n≥2k+1n \geq 2k + 1. For a polynomial p∈K[Xn]p \in \mathbb{K}[\mathcal{X}_n], the following are equivalent:

    1. pp is computed by a reduced matrix-symmetric circuit of support size ≤k\leq k and support depth ≤Δ\leq \Delta.
    2. pp is a linear combination of homomorphism polynomials hom⁡F,n\hom_{F,n} for patterns FF with fwΔ(F)≤k−1\mathrm{fw}_\Delta(F) \leq k - 1.

    The implication from 1 to 2 is the theorem on homomorphism polynomials from symmetric circuits. For the implication from 2 to 1, one constructs a circuit for every pattern in the linear combination as in the theorem on circuits for patterns of bounded forestwidth, multiplies the output gates by the coefficients, adds an output sum gate, and rigidifies.

    Concept map
    6 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Mathlib.LinearAlgebra.Span.Defs
    2import Lax461425.Supports
    3import Lax461425.Forestwidth
    4
    5/-!
    6---
    7title: Characterisation of bounded-depth matrix-symmetric circuits
    8type: theorem
    9---
    10Let K\mathbb{K} be a field of characteristic zero. Let Δ≥1\Delta \geq 1, k≥2k \geq 2, and
    11n≥2k+1n \geq 2k + 1. For a polynomial p∈K[Xn]p \in \mathbb{K}[\mathcal{X}_n], the following are
    12equivalent:
    13
    141. pp is computed by a reduced matrix-symmetric circuit of support size ≤k\leq k and support
    15 depth ≤Δ\leq \Delta.
    162. pp is a linear combination of homomorphism polynomials hom⁡F,n\hom_{F,n} for patterns FF with
    17 fwΔ(F)≤k−1\mathrm{fw}_\Delta(F) \leq k - 1.
    18
    19The implication from 1 to 2 is the theorem on homomorphism polynomials from symmetric
    20circuits. For the implication from 2 to 1, one constructs a circuit for every pattern in the
    21linear combination as in the theorem on circuits for patterns of bounded forestwidth,
    22multiplies the output gates by the coefficients, adds an output sum gate, and rigidifies.
    23-/
    24
    25namespace Lax461425.BoundedDepthCharacterisation
    26
    27open Circuits MatrixSymmetry Supports HomomorphismPolynomials Forestwidth
    28
    29/-- A polynomial is computed by a reduced matrix-symmetric circuit of support size `≤ k` and
    30support depth `≤ Δ` if, and only if, it is a linear combination of homomorphism polynomials of
    31patterns of `Δ`-forestwidth at most `k - 1`. -/
    32axiom characterisation {K : Type*} [Field K] [CharZero K] {Δ k n : ℕ} (hΔ : 1 ≤ Δ)
    33 (hk : 2 ≤ k) (hn : 2 * k + 1 ≤ n) (p : MvPolynomial (Fin n × Fin n) K) :
    34 (∃ C : Circuit (Fin n × Fin n) K,
    35 C.Computes p ∧ C.IsReduced ∧ IsMatrixSymmetric C ∧
    36 supportSize C ≤ k ∧ supportDepth C ≤ Δ) ↔
    37 p ∈ Submodule.span K {q | ∃ F : Pattern, ForestwidthLE Δ (k - 1) F ∧ hom K F n = q}
    38
    39end Lax461425.BoundedDepthCharacterisation
    40
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…