AFTD Auto-Formalizing Theoretical Domains

ncabp_eval_poly

def

Given 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 (Fin m) defined as the (A.source, A.sink) entry of the sum ∑ k ∈ Finset.range (S + 1), (ncabp_matrix A) ^ k.

Statement

def ncabp_eval_poly {F : Type*} [CommSemiring F] {m S : ℕ} (A : NcABP F m S) :
    FreeAlgebra F (Fin m)
Defined in
arXiv:2610.37677, Section 1.1 and Section 3.2
Verified
30 Oct 2026
Axioms
none listed
Built on 4
  • 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…
Used by 2
  • ncabp_eval_poly_zero_directionGiven a field F, natural numbers m, S, R, a matrix tuple T : Fin m → Matrix (Fin R) (Fin R) F, and an ncABP A : NcABP F m S such that…
  • is_ncabp_hitting_tupleGiven 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…

Read back from the Lean

Given a commutative semiring F, natural numbers m and S, and a non-commutative arithmetic branching program A : NcABP F m S, ncabp_eval_poly A is the element of FreeAlgebra F (Fin m) defined as the (A.source, A.sink) entry of the matrix sum $\sum_{k=0}^{S} M^k$, where $M$ is the ncabp_matrix A (an $S \times S$ matrix with entries 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

/-- The noncommutative polynomial in FreeAlgebra F (Fin m) computed by an ncABP. -/
def ncabp_eval_poly {F : Type*} [CommSemiring F] {m S : ℕ} (A : NcABP F m S) :
    FreeAlgebra F (Fin m) := open BigOperators in (∑ k ∈ Finset.range (S + 1), (ncabp_matrix A ^ k)) A.source A.sink
See it in the graphDiscuss this resultChallenge it