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

Support theorem

Lax461425.SupportTheorem · concepts/Lax461425/SupportTheorem.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. Then every gate of a reduced matrix-symmetric circuit of orbit size <(nκ)< \binom{n}{\kappa} has a support of size ≤κ−1\leq \kappa - 1, i.e. the circuit has support size ≤κ−1\leq \kappa - 1.

    In the paper, the orbit size is bounded by a function f ⁣:N→Nf \colon \mathbb{N} \to \mathbb{N}, and κf(n)=min⁡{r∈N:(nr)>f(n)}\kappa_f(n) = \min\{r \in \mathbb{N} : \binom{n}{r} > f(n)\}. The statement there is that, if n≥20n \geq 20 and 3κf(n)≤n+23\kappa_f(n) \leq n + 2, every gate of a reduced matrix-symmetric circuit of orbit size ≤f(n)\leq f(n) has a minimal support of size ≤κf(n)−1\leq \kappa_f(n) - 1. This is the case κ=κf(n)\kappa = \kappa_f(n) of the statement above. Conversely, the statement above for any κ\kappa follows from the paper's for the constant function ff with value the orbit size, since then κf(n)≤κ\kappa_f(n) \leq \kappa. As 2(κ−1)<n2(\kappa - 1) < n, the minimal supports exist and are contained in every support of size ≤κ−1\leq \kappa - 1, so bounding the support size is the same as bounding the size of the minimal supports.

    Concept map
    4 concepts
    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 Mathlib.Data.Nat.Choose.Basic
    2import Lax461425.Supports
    3
    4/-!
    5---
    6title: Support theorem
    7type: theorem
    8---
    9Let n≥20n \geq 20 and κ∈N\kappa \in \mathbb{N} with 3κ≤n+23\kappa \leq n + 2. Then every gate of a
    10reduced matrix-symmetric circuit of orbit size <(nκ)< \binom{n}{\kappa} has a support of size
    11≤κ−1\leq \kappa - 1, i.e. the circuit has support size ≤κ−1\leq \kappa - 1.
    12
    13In the paper, the orbit size is bounded by a function f ⁣:N→Nf \colon \mathbb{N} \to \mathbb{N},
    14and κf(n)=min⁡{r∈N:(nr)>f(n)}\kappa_f(n) = \min\{r \in \mathbb{N} : \binom{n}{r} > f(n)\}. The statement there is
    15that, if n≥20n \geq 20 and 3κf(n)≤n+23\kappa_f(n) \leq n + 2, every gate of a reduced matrix-symmetric
    16circuit of orbit size ≤f(n)\leq f(n) has a minimal support of size ≤κf(n)−1\leq \kappa_f(n) - 1. This
    17is the case κ=κf(n)\kappa = \kappa_f(n) of the statement above. Conversely, the statement above for
    18any κ\kappa follows from the paper's for the constant function ff with value the orbit size,
    19since then κf(n)≤κ\kappa_f(n) \leq \kappa. As 2(κ−1)<n2(\kappa - 1) < n, the minimal supports exist and
    20are contained in every support of size ≤κ−1\leq \kappa - 1, so bounding the support size is the
    21same as bounding the size of the minimal supports.
    22-/
    23
    24namespace Lax461425.SupportTheorem
    25
    26open Circuits MatrixSymmetry Supports
    27
    28/-- A reduced matrix-symmetric circuit of orbit size `< n.choose κ` has support size
    29`≤ κ - 1`, provided `n ≥ 20` and `3κ ≤ n + 2`. -/
    30axiom supportSize_le {K : Type*} {n κ : ℕ} (hn : 20 ≤ n) (hκ : 3 * κ ≤ n + 2)
    31 (C : Circuit (Fin n × Fin n) K) (hred : C.IsReduced) (hsym : IsMatrixSymmetric C)
    32 (horb : orbitSize C < n.choose κ) :
    33 supportSize C ≤ κ - 1
    34
    35end Lax461425.SupportTheorem
    36
    Show Proof
    Builds on
    Used by

    none

    From Mathlib

    Discussion

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

    Loading discussion…