Explicit matrix hitting points for noncommutative algebraic branching programs
Abstract
We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size m≥1 and an ABP vertex bound S≥1, we construct one fixed tuple of integer matrices of order R=(m+2)d(d+1)/2, where d=(m+2)S, with entry bit length O(dlog(d+1)). Every nonzero polynomial computed by an ABP with at most S vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to O(m3/2S2). Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic p>binom d2. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.
Related
- Capacities and Hitting Times for Simple and (critical) Branching Random Walk Sausages
- Noncommutative algebraic sets are not generically nc manifolds
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
- Safe Control of Semi-Explicit Differential-Algebraic Systems: Control Barrier Functions with SOS Verification
- Distribution of the First Hitting Point on a Boundary Set for a Random Walk in a Lattice Strip
BibTeX
@misc{lu2026explicit,
title = {{Explicit matrix hitting points for noncommutative algebraic branching programs}},
author = {Zhipeng Lu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37677},
eprint = {2610.37677},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37677},
}
RIS
TY - UNPB
TI - Explicit matrix hitting points for noncommutative algebraic branching programs
AU - Zhipeng Lu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.37677
UR - https://arxiv.org/abs/2610.37677
AB - We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size m≥1 and an ABP vertex bound S≥1, we construct one fixed tuple of integer matrices of order R=(m+2)d(d+1)/2, where d=(m+2)S, with entry bit length O(dlog(d+1)). Every nonzero polynomial computed by an ABP with at most S vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to O(m^3/2S^2). Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic p>binom d2. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.
ER -