AFTD Auto-Formalizing Theoretical Domains

ncabp_eval_poly_zero_direction

theoremverified

Given 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 ncabp_eval_poly A = 0, the evaluation (FreeAlgebra.lift F T) (ncabp_eval_poly A) equals 0.

Statement

theorem ncabp_eval_poly_zero_direction {F : Type*} [Field F] (m S R : ℕ)
    (T : Fin m → Matrix (Fin R) (Fin R) F) (A : NcABP F m S) (hA : ncabp_eval_poly A = 0) :
    (FreeAlgebra.lift F T) (ncabp_eval_poly A) = 0
Source
arXiv:2610.37677, Theorem 1.1
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
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 any field $F$, any natural numbers $m$, $S$, and $R$, any map $T : \text{Fin } m \to \text{Matrix } (\text{Fin } R) (\text{Fin } R) F$, and any non-commutative algebraic branching program $A$ over $F$ with $m$ variables and $S$ vertices (NcABP F m S): if the polynomial evaluated by $A$, $\text{ncabp\_eval\_poly}(A)$, is equal to $0$ in $\text{FreeAlgebra } F (\text{Fin } m)$, then the image of $\text{ncabp\_eval\_poly}(A)$ under the algebra homomorphism $\text{FreeAlgebra.lift } F\ T$ is the zero matrix in $\text{Matrix } (\text{Fin } R) (\text{Fin } R) F$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem establishes that evaluating a vanishing ncABP polynomial at any tuple of matrices produces the zero matrix. The argument substitutes the hypothesis that the polynomial is zero into the evaluation expression. Because the evaluation map is an algebra homomorphism from the free algebra to the matrix algebra, it preserves zero, immediately yielding the zero matrix.

  1. It suffices to show that the evaluation homomorphism maps 0 to the zero matrix.

    Rewriting with the hypothesis that the polynomial vanishes (hA : ncabp_eval_poly A = 0) replaces the polynomial in the evaluation expression with 0, transforming the goal into ((FreeAlgebra.lift F) T) 0 = 0.

    line 5

      rw [hA]
  2. The evaluation homomorphism maps 0 to the zero matrix.

    Because FreeAlgebra.lift F T is an algebra homomorphism, it is a zero-preserving map. Applying map_zero closes the goal.

    line 6

    uses map_zero

      exact map_zero _
map_zero
A homomorphism between structures with zero sends zero to zero: f(0) = 0.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Evaluating a vanishing ncABP polynomial at any matrix tuple produces the zero matrix. -/theorem ncabp_eval_poly_zero_direction {F : Type*} [Field F] (m S R : ℕ)    (T : Fin m → Matrix (Fin R) (Fin R) F) (A : NcABP F m S) (hA : ncabp_eval_poly A = 0) :    (FreeAlgebra.lift F T) (ncabp_eval_poly A) = 0 := by  rw [hA]  exact map_zero _
See it in the graphDiscuss this resultChallenge it