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

Supports and support depth

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

definition

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

    Definition

    Let CC be a circuit with variables Xn\mathcal{X}_n. For S⊆[n]⊎[n]S \subseteq [n] \uplus [n], let Stab∙(S)≤Γn\mathbf{Stab}^\bullet(S) \leq \Gamma_n be the pointwise stabiliser of SS. The set SS supports a gate gg if every circuit automorphism extending an element of Stab∙(S)\mathbf{Stab}^\bullet(S) fixes gg. If CC is rigid, then Γn\Gamma_n acts on the gates of CC, and this says that Stab∙(S)\mathbf{Stab}^\bullet(S) fixes gg. The support size of CC is the least kk such that every gate of CC has a support of size at most kk.

    Write sup⁡(g)\sup(g) for the intersection of all supports of gg of size at most the support size of CC — a bounded intersection: a support of unbounded size, such as the complement of a single point, trivially has a trivial pointwise stabiliser and so carries no information about gg. If gg has a support SS with ∣SL∣,∣SR∣<n/2|S_L|, |S_R| < n/2, where SLS_L and SRS_R are the two sides of SS, then sup⁡(g)\sup(g) is itself a support of gg, the unique minimal one. A wire from hh to gg is support-changing if sup⁡(h)⊈sup⁡(g)\sup(h) \not\subseteq \sup(g). If the support size of CC is less than n/2n/2, the support depth of CC is the maximum number of support-changing wires on a path. Otherwise, the support depth of CC is its depth. In either case, the support depth is at most the depth.

    Concept map
    3 concepts; 5 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax461425.MatrixSymmetry
    2
    3/-!
    4---
    5title: Supports and support depth
    6type: definition
    7---
    8Let CC be a circuit with variables Xn\mathcal{X}_n. For S⊆[n]⊎[n]S \subseteq [n] \uplus [n], let
    9Stab∙(S)≤Γn\mathbf{Stab}^\bullet(S) \leq \Gamma_n be the pointwise stabiliser of SS. The set SS
    10*supports* a gate gg if every circuit automorphism extending an element of
    11Stab∙(S)\mathbf{Stab}^\bullet(S) fixes gg. If CC is rigid, then Γn\Gamma_n acts on the gates of
    12CC, and this says that Stab∙(S)\mathbf{Stab}^\bullet(S) fixes gg. The *support size* of CC is the
    13least kk such that every gate of CC has a support of size at most kk.
    14
    15Write sup⁡(g)\sup(g) for the intersection of all supports of gg of size at most the support size
    16of CC — a bounded intersection: a support of unbounded size, such as the complement of a
    17single point, trivially has a trivial pointwise stabiliser and so carries no information about
    18gg. If gg has a support SS with ∣SL∣,∣SR∣<n/2|S_L|, |S_R| < n/2, where SLS_L and SRS_R are the two
    19sides of SS, then sup⁡(g)\sup(g) is itself a support of gg, the unique minimal one. A wire from
    20hh to gg is *support-changing* if sup⁡(h)⊈sup⁡(g)\sup(h) \not\subseteq \sup(g). If the support size of CC
    21is less than n/2n/2, the *support depth* of CC is the maximum number of support-changing wires
    22on a path. Otherwise, the support depth of CC is its depth. In either case, the support depth
    23is at most the depth.
    24-/
    25
    26namespace Lax461425.Supports
    27
    28open Circuits MatrixSymmetry
    29
    30variable {K : Type*} {n : ℕ} (C : Circuit (Fin n × Fin n) K)
    31
    32/-- `S` supports `g`: every circuit automorphism extending an element of `Γₙ` that fixes `S`
    33pointwise fixes `g`. -/
    34def IsSupport (g : C.Gate) (S : Set (Fin n ⊕ Fin n)) : Prop :=
    35 ∀ (γ : Γ n) (σ : C.Gate ≃ C.Gate), (∀ x ∈ S, actPoint γ x = x) → Extends C σ (actVar γ) → σ g = g
    36
    37/-- The least `k` such that every gate has a support of size at most `k`. -/
    38noncomputable def supportSize : ℕ :=
    39 sInf {k | ∀ g, ∃ S, IsSupport C g S ∧ S.ncard ≤ k}
    40
    41/-- `sup(g)`, the intersection of all supports of `g` of size at most `supportSize C`. Supports
    42of unbounded size are excluded: e.g. the complement of a single point always has a trivial
    43pointwise stabiliser, hence trivially supports every gate, and intersecting with it would
    44collapse `sup(g)` to the empty set regardless of `g`. -/
    45def minSupport (g : C.Gate) : Set (Fin n ⊕ Fin n) :=
    46 {x | ∀ S, IsSupport C g S → S.ncard ≤ supportSize C → x ∈ S}
    47
    48/-- The number of support-changing wires on the path `p 0, …, p m`. -/
    49noncomputable def supportChanges {m : ℕ} (p : Fin (m + 1) → C.Gate) : ℕ :=
    50 {i : Fin m | ¬ minSupport C (p i.succ) ⊆ minSupport C (p i.castSucc)}.ncard
    51
    52/-- The maximum number of support-changing wires on a path if the support size is less than
    53`n / 2`, and the depth otherwise. -/
    54noncomputable def supportDepth : ℕ :=
    55 if 2 * supportSize C < n then
    56 sSup {c | ∃ (m : ℕ) (p : Fin (m + 1) → C.Gate), C.IsPath p ∧ supportChanges C p = c}
    57 else
    58 C.depth
    59
    60end Lax461425.Supports
    61

    Discussion

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

    Loading discussion…