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

Support depth of symmetric formulas

Lax461425.FormulaSupportDepth · concepts/Lax461425/FormulaSupportDepth.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 n≥20n \geq 20 and κ∈N\kappa \in \mathbb{N} with 3κ≤n+23\kappa \leq n + 2. Every polynomial computed by a matrix-symmetric formula of orbit size <(nκ)< \binom{n}{\kappa} is computed by a reduced matrix-symmetric circuit of support size ≤κ−1\leq \kappa - 1 and support depth ≤2κ\leq 2\kappa.

    The circuit is the rigidification of the formula, whose support size is bounded by the support theorem. In a formula, every internal gate has a unique chain of ancestors. A path in the rigidification with many support-changing wires can be moved by stabilisers so that each such wire adds a new point to the union of the supports along the path. Lifting the path to the formula, the gates at its end lie in a gate orbit at least as large as the orbit of this union, which bounds the number of support-changing wires.

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

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax461425.Supports
    2import Lax461425.CircuitProperties
    3import Lax461425.SymmetricFamilies
    4import Mathlib.Data.Nat.Choose.Basic
    5
    6/-!
    7---
    8title: Support depth of symmetric formulas
    9type: theorem
    10---
    11Let n≥20n \geq 20 and κ∈N\kappa \in \mathbb{N} with 3κ≤n+23\kappa \leq n + 2. Every polynomial
    12computed by a matrix-symmetric formula of orbit size <(nκ)< \binom{n}{\kappa} is computed by a
    13reduced matrix-symmetric circuit of support size ≤κ−1\leq \kappa - 1 and support depth
    14≤2κ\leq 2\kappa.
    15
    16The circuit is the rigidification of the formula, whose support size is bounded by the support
    17theorem. In a formula, every internal gate has a unique chain of ancestors. A path in the
    18rigidification with many support-changing wires can be moved by stabilisers so that each such
    19wire adds a new point to the union of the supports along the path. Lifting the path to the
    20formula, the gates at its end lie in a gate orbit at least as large as the orbit of this union,
    21which bounds the number of support-changing wires.
    22-/
    23
    24namespace Lax461425.FormulaSupportDepth
    25
    26open Circuits CircuitProperties MatrixSymmetry SymmetricFamilies Supports
    27
    28/-- The rigidification of a symmetric formula of small orbit size has bounded support
    29depth. -/
    30axiom exists_reduced {K : Type*} [CommSemiring K] {n κ : ℕ} (hn : 20 ≤ n)
    31 (hκ : 3 * κ ≤ n + 2) (C : Circuit (Fin n × Fin n) K) (hformula : IsFormula C)
    32 (hsym : IsMatrixSymmetric C) (horb : orbitSize C < n.choose κ)
    33 {p : MatrixPolynomial n K} (hp : C.Computes p) :
    34 ∃ C' : Circuit (Fin n × Fin n) K,
    35 C'.Computes p ∧ C'.IsReduced ∧ IsMatrixSymmetric C' ∧
    36 supportSize C' ≤ κ - 1 ∧ supportDepth C' ≤ 2 * κ
    37
    38end Lax461425.FormulaSupportDepth
    39
    Show Proof

    Discussion

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

    Loading discussion…