AFTD Auto-Formalizing Theoretical Domains

is_ncabp_hitting_tuple

def

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
See it in the graphDiscuss this resultChallenge it