is_ncabp_hitting_tuple
Given a field F and natural numbers m, S, R, a tuple of matrices T : Fin m → Matrix (Fin R) (Fin R) F is an ncABP hitting tuple if for every A : NcABP F m S, (FreeAlgebra.lift F T) (ncabp_eval_poly A) = 0 if and only if ncabp_eval_poly A = 0.
Statement
def is_ncabp_hitting_tuple {F : Type*} [Field F] (m S R : ℕ) (T : Fin m → Matrix (Fin R) (Fin R) F) : Prop
- Defined in
- arXiv:2610.37677, Theorem 1.1
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 5
- AffineFormAn affine linear form parameterized by a type F and an arity m : ℕ consists of a constant term c0 : F and a tuple of linear coefficients c…
- affine_form_to_free_algebraGiven a commutative semiring F, a natural number m, and an affine form a : AffineForm F m, affine_form_to_free_algebra a is the element of…
- NcABPAn affine noncommutative algebraic branching program (ncABP) parameterized by a type F with zero and parameters m, S : ℕ consists of a…
- ncabp_matrixGiven a commutative semiring F, parameters m, S : ℕ, and an ncABP A : NcABP F m S, ncabp_matrix A is the transition matrix in Matrix (Fin…
- ncabp_eval_polyGiven a commutative semiring F, parameters m, S : ℕ, and an ncABP A : NcABP F m S, ncabp_eval_poly A is the polynomial in FreeAlgebra F…
Read back from the Lean
For a field F, natural numbers m, S, and R, and a family of R × R matrices T : Fin m → Matrix (Fin R) (Fin R) F, is_ncabp_hitting_tuple m S R T is defined as the proposition that for every non-commutative algebraic branching program A : NcABP F m S, the evaluation of the non-commutative polynomial computed by A (ncabp_eval_poly A) at T via the canonical algebra homomorphism FreeAlgebra.lift F T is equal to 0 if and only if ncabp_eval_poly A is equal to 0 in FreeAlgebra F (Fin m).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A tuple of R × R matrices is a hitting point of order R for ncABPs with S vertices. -/ def is_ncabp_hitting_tuple {F : Type*} [Field F] (m S R : ℕ) (T : Fin m → Matrix (Fin R) (Fin R) F) : Prop := ∀ (A : NcABP F m S), (FreeAlgebra.lift F T) (ncabp_eval_poly A) = 0 ↔ ncabp_eval_poly A = 0