Support theorem
Lax461425.SupportTheorem · concepts/Lax461425/SupportTheorem.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let and with . Then every gate of a reduced matrix-symmetric circuit of orbit size has a support of size , i.e. the circuit has support size .
In the paper, the orbit size is bounded by a function , and . The statement there is that, if and , every gate of a reduced matrix-symmetric circuit of orbit size has a minimal support of size . This is the case of the statement above. Conversely, the statement above for any follows from the paper's for the constant function with value the orbit size, since then . As , the minimal supports exist and are contained in every support of size , so bounding the support size is the same as bounding the size of the minimal supports.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Mathlib.Data.Nat.Choose.Basic |
| 2 | import Lax461425.Supports |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Support theorem |
| 7 | type: theorem |
| 8 | --- |
| 9 | Let and with . Then every gate of a |
| 10 | reduced matrix-symmetric circuit of orbit size has a support of size |
| 11 | , i.e. the circuit has support size . |
| 12 | |
| 13 | In the paper, the orbit size is bounded by a function , |
| 14 | and . The statement there is |
| 15 | that, if and , every gate of a reduced matrix-symmetric |
| 16 | circuit of orbit size has a minimal support of size . This |
| 17 | is the case of the statement above. Conversely, the statement above for |
| 18 | any follows from the paper's for the constant function with value the orbit size, |
| 19 | since then . As , the minimal supports exist and |
| 20 | are contained in every support of size , so bounding the support size is the |
| 21 | same as bounding the size of the minimal supports. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax461425.SupportTheorem |
| 25 | |
| 26 | open 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`. -/ |
| 30 | axiom 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 | |
| 35 | end Lax461425.SupportTheorem |
| 36 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments