Family 116Theoretical computer scienceLeanNot yet digested
Uniform black-box noncommutative identity testing across characteristics
For each characteristic, constructs in deterministic polynomial bit time a polynomial-dimensional matrix tuple detecting every nonzero division-free noncommutative formula of bounded size over any field of that characteristic. Rational formulas over ℚ also admit polynomial-size hitting lists whenever they have a defined rational-matrix evaluation.
Manuscripts in this family · 3
Uniform Matrix Hitting Points in Every Positive Characteristic
Oct 4, 2026·uniform-matrix-hitting-points-positive-characteristic.pdf
We construct a single matrix substitution that detects every nonzero size-s division-free noncommutative formula in n variables over every field of a given positive characteristic. One deterministic machine, given a promised prime p in binary and n, s in unary, outputs matrices over 𝔽 of dimension in polynomial bit time. The same tuple works with arbitrary extension-field coefficients, including in characteristic two. The construction also applies to the stated acyclic algebraic path programs.
One Rational Matrix Hitting Point for Noncommutative Formulas
Sep 24, 2026·One-Rational-Matrix-Hitting-Point-for-Noncommutative-Formulas-September-24-2026.pdf
We construct, in deterministic polynomial bit time, one tuple of rational matrices that detects every nonzero polynomial computed by a noncommutative division-free formula of a prescribed size. The matrices have dimension for n variables and formula size s, and the same tuple works over every field of characteristic zero.
Polynomial Hitting Lists for Noncommutative Rational Formulas
Sep 24, 2026·Polynomial-Hitting-Lists-for-Noncommutative-Rational-Formulas-September-24-2026.pdfLean
We construct, in deterministic polynomial bit time, a polynomial-size list of rational matrix tuples for noncommutative rational formulas over ℚ of bounded tree size. Every nonzero admissible formula has a defined, invertible value at one tuple, with no separate bounds on inverse nesting or rational constant heights. Matrix dimensions, entry bit lengths, and total output length are polynomially bounded.