Supports and support depth
Lax461425.Supports · concepts/Lax461425/Supports.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Let be a circuit with variables . For , let be the pointwise stabiliser of . The set supports a gate if every circuit automorphism extending an element of fixes . If is rigid, then acts on the gates of , and this says that fixes . The support size of is the least such that every gate of has a support of size at most .
Write for the intersection of all supports of of size at most the support size of — 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 . If has a support with , where and are the two sides of , then is itself a support of , the unique minimal one. A wire from to is support-changing if . If the support size of is less than , the support depth of is the maximum number of support-changing wires on a path. Otherwise, the support depth of is its depth. In either case, the support depth is at most the depth.
Concept map
Lean source view on GitHub
| 1 | import Lax461425.MatrixSymmetry |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Supports and support depth |
| 6 | type: definition |
| 7 | --- |
| 8 | Let be a circuit with variables . For , let |
| 9 | be the pointwise stabiliser of . The set |
| 10 | *supports* a gate if every circuit automorphism extending an element of |
| 11 | fixes . If is rigid, then acts on the gates of |
| 12 | , and this says that fixes . The *support size* of is the |
| 13 | least such that every gate of has a support of size at most . |
| 14 | |
| 15 | Write for the intersection of all supports of of size at most the support size |
| 16 | of — a bounded intersection: a support of unbounded size, such as the complement of a |
| 17 | single point, trivially has a trivial pointwise stabiliser and so carries no information about |
| 18 | . If has a support with , where and are the two |
| 19 | sides of , then is itself a support of , the unique minimal one. A wire from |
| 20 | to is *support-changing* if . If the support size of |
| 21 | is less than , the *support depth* of is the maximum number of support-changing wires |
| 22 | on a path. Otherwise, the support depth of is its depth. In either case, the support depth |
| 23 | is at most the depth. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax461425.Supports |
| 27 | |
| 28 | open Circuits MatrixSymmetry |
| 29 | |
| 30 | variable {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` |
| 33 | pointwise fixes `g`. -/ |
| 34 | def 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`. -/ |
| 38 | noncomputable 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 |
| 42 | of unbounded size are excluded: e.g. the complement of a single point always has a trivial |
| 43 | pointwise stabiliser, hence trivially supports every gate, and intersecting with it would |
| 44 | collapse `sup(g)` to the empty set regardless of `g`. -/ |
| 45 | def 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`. -/ |
| 49 | noncomputable 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. -/ |
| 54 | noncomputable 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 | |
| 60 | end Lax461425.Supports |
| 61 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments