Support depth of symmetric formulas
Lax461425.FormulaSupportDepth · concepts/Lax461425/FormulaSupportDepth.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let and with . Every polynomial computed by a matrix-symmetric formula of orbit size is computed by a reduced matrix-symmetric circuit of support size and support depth .
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
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax461425.Supports |
| 2 | import Lax461425.CircuitProperties |
| 3 | import Lax461425.SymmetricFamilies |
| 4 | import Mathlib.Data.Nat.Choose.Basic |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Support depth of symmetric formulas |
| 9 | type: theorem |
| 10 | --- |
| 11 | Let and with . Every polynomial |
| 12 | computed by a matrix-symmetric formula of orbit size is computed by a |
| 13 | reduced matrix-symmetric circuit of support size and support depth |
| 14 | . |
| 15 | |
| 16 | The circuit is the rigidification of the formula, whose support size is bounded by the support |
| 17 | theorem. In a formula, every internal gate has a unique chain of ancestors. A path in the |
| 18 | rigidification with many support-changing wires can be moved by stabilisers so that each such |
| 19 | wire adds a new point to the union of the supports along the path. Lifting the path to the |
| 20 | formula, the gates at its end lie in a gate orbit at least as large as the orbit of this union, |
| 21 | which bounds the number of support-changing wires. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax461425.FormulaSupportDepth |
| 25 | |
| 26 | open Circuits CircuitProperties MatrixSymmetry SymmetricFamilies Supports |
| 27 | |
| 28 | /-- The rigidification of a symmetric formula of small orbit size has bounded support |
| 29 | depth. -/ |
| 30 | axiom 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 | |
| 38 | end Lax461425.FormulaSupportDepth |
| 39 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments