Characterisation of bounded-depth matrix-symmetric circuits
Lax461425.BoundedDepthCharacterisation · concepts/Lax461425/BoundedDepthCharacterisation.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let be a field of characteristic zero. Let , , and . For a polynomial , the following are equivalent:
- is computed by a reduced matrix-symmetric circuit of support size and support depth .
- is a linear combination of homomorphism polynomials for patterns with .
The implication from 1 to 2 is the theorem on homomorphism polynomials from symmetric circuits. For the implication from 2 to 1, one constructs a circuit for every pattern in the linear combination as in the theorem on circuits for patterns of bounded forestwidth, multiplies the output gates by the coefficients, adds an output sum gate, and rigidifies.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Mathlib.LinearAlgebra.Span.Defs |
| 2 | import Lax461425.Supports |
| 3 | import Lax461425.Forestwidth |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Characterisation of bounded-depth matrix-symmetric circuits |
| 8 | type: theorem |
| 9 | --- |
| 10 | Let be a field of characteristic zero. Let , , and |
| 11 | . For a polynomial , the following are |
| 12 | equivalent: |
| 13 | |
| 14 | 1. is computed by a reduced matrix-symmetric circuit of support size and support |
| 15 | depth . |
| 16 | 2. is a linear combination of homomorphism polynomials for patterns with |
| 17 | . |
| 18 | |
| 19 | The implication from 1 to 2 is the theorem on homomorphism polynomials from symmetric |
| 20 | circuits. For the implication from 2 to 1, one constructs a circuit for every pattern in the |
| 21 | linear combination as in the theorem on circuits for patterns of bounded forestwidth, |
| 22 | multiplies the output gates by the coefficients, adds an output sum gate, and rigidifies. |
| 23 | -/ |
| 24 | |
| 25 | namespace Lax461425.BoundedDepthCharacterisation |
| 26 | |
| 27 | open Circuits MatrixSymmetry Supports HomomorphismPolynomials Forestwidth |
| 28 | |
| 29 | /-- A polynomial is computed by a reduced matrix-symmetric circuit of support size `≤ k` and |
| 30 | support depth `≤ Δ` if, and only if, it is a linear combination of homomorphism polynomials of |
| 31 | patterns of `Δ`-forestwidth at most `k - 1`. -/ |
| 32 | axiom characterisation {K : Type*} [Field K] [CharZero K] {Δ k n : ℕ} (hΔ : 1 ≤ Δ) |
| 33 | (hk : 2 ≤ k) (hn : 2 * k + 1 ≤ n) (p : MvPolynomial (Fin n × Fin n) K) : |
| 34 | (∃ C : Circuit (Fin n × Fin n) K, |
| 35 | C.Computes p ∧ C.IsReduced ∧ IsMatrixSymmetric C ∧ |
| 36 | supportSize C ≤ k ∧ supportDepth C ≤ Δ) ↔ |
| 37 | p ∈ Submodule.span K {q | ∃ F : Pattern, ForestwidthLE Δ (k - 1) F ∧ hom K F n = q} |
| 38 | |
| 39 | end Lax461425.BoundedDepthCharacterisation |
| 40 |
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments