Rigidification
Lax461425.Rigidification · concepts/Lax461425/Rigidification.lean · lax-461425
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Lemma
For every matrix-symmetric circuit , there is a reduced matrix-symmetric circuit computing the same polynomial whose size, depth, and orbit size are at most those of .
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax461425.SymmetricFamilies |
| 2 | import Lax461425.MatrixSymmetry |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Rigidification |
| 7 | type: lemma |
| 8 | --- |
| 9 | For every matrix-symmetric circuit , there is a reduced matrix-symmetric circuit |
| 10 | computing the same polynomial whose size, depth, and orbit size are at most those of . |
| 11 | -/ |
| 12 | |
| 13 | open Lax461425.SymmetricFamilies (MatrixPolynomial) |
| 14 | |
| 15 | namespace Lax461425.Rigidification |
| 16 | |
| 17 | open Circuits MatrixSymmetry |
| 18 | |
| 19 | /-- Every matrix-symmetric circuit can be replaced by a reduced matrix-symmetric circuit |
| 20 | computing the same polynomial, without increasing size, depth, or orbit size. -/ |
| 21 | axiom exists_reduced {K : Type*} [CommSemiring K] {n : ℕ} |
| 22 | (C : Circuit (Fin n × Fin n) K) (hsym : IsMatrixSymmetric C) |
| 23 | {p : MatrixPolynomial n K} (hp : C.Computes p) : |
| 24 | ∃ C' : Circuit (Fin n × Fin n) K, |
| 25 | C'.IsReduced ∧ IsMatrixSymmetric C' ∧ C'.Computes p ∧ |
| 26 | C'.size ≤ C.size ∧ C'.depth ≤ C.depth ∧ orbitSize C' ≤ orbitSize C |
| 27 | |
| 28 | end Lax461425.Rigidification |
| 29 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments