Uniform identity testing for noncommutative formulas

← All digests

Family 116 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

Two algebraic expressions may look different while computing exactly the same object. Identity testing asks whether their difference is identically zero. When multiplication is noncommutative, matrix substitutions preserve information that scalar substitutions erase. Family 116 claims small deterministic collections of such substitutions that work universally for every formula up to a given size.

1. The question

For ordinary numbers, $xy-yx=0$. For matrices, multiplication order matters, and $XY-YX$ can be nonzero. An identity test that substitutes only numbers would therefore miss a genuinely nonzero noncommutative expression.

Random matrix substitutions can often detect nonzero expressions. The harder goal is to construct a guaranteed test deterministically, using only a bound on formula size and the number of variables, before seeing any coefficients.

The family claims one polynomial-dimensional matrix tuple for division-free formulas in characteristic zero, another construction in every positive characteristic, and polynomial-size hitting lists for rational formulas over $\mathbb Q$. Rational formulas allow inverses, so the test must also respect where the original expression is defined.

2. Background and essential definitions

Words replace ordinary monomials

In a noncommutative polynomial, $x_1x_2$ and $x_2x_1$ are different words. Multiplication concatenates words in order. A polynomial is a finite linear combination of these words, with scalar coefficients from a field.

A division-free formula is a rooted tree with variable or scalar leaves and binary addition or ordered multiplication gates. Tree structure matters: shared subexpressions in a general circuit can encode more work than a formula of the same stated size.

Size counts every vertex, including leaves. A small formula can still expand into exponentially many words. The ordered product of many copies of $x_1+x_2$, for example, makes an independent choice of letter at every position.

Hitting points and black-box access

A tuple $T=(T_1,\ldots,T_n)$ of square matrices is a hitting point for a class if every nonzero polynomial $f$ in the class satisfies

$$f(T_1,\ldots,T_n)\ne0.$$

A hitting list permits several tuples and requires at least one successful evaluation. Scalars in the formula are interpreted as scalar multiples of the identity matrix.

A white-box algorithm can examine the formula’s internal gates. A black-box algorithm receives evaluations without inspecting that structure. A universal hitting construction is especially strong: it chooses its tests independently of the particular formula or its coefficients.

Characteristic and rational expressions

The characteristic of a field is zero if repeated addition of one never gives zero, and is a prime $p$ otherwise. The rational numbers have characteristic zero; arithmetic modulo a prime has characteristic $p$.

A rational formula also has inverse gates. A matrix evaluation is defined only when every inverted intermediate matrix is invertible. Algebraic cancellation does not remove these domain requirements: $x^{-1}-x^{-1}$ is zero wherever defined, but its original expression is still undefined at a singular matrix.

The rational manuscript calls a formula admissible if it has at least one defined evaluation on rational matrices of some positive dimension. It is nonzero if some defined rational evaluation is nonzero.

3. Development history and previous partial results

Nisan’s 1991 work connected noncommutative computational complexity with ranks of coefficient matrices. Ordered words admit linear-algebraic representations that do not behave like ordinary commutative monomials.

Raz and Shpilka gave deterministic polynomial-time identity testing for noncommutative formulas and algebraic branching programs when their descriptions are available. Thus the new family is not the first deterministic test for this model; the challenge is universal black-box evaluation.

Bogdanov and Wee developed randomized matrix-evaluation tests. Forbes and Shpilka constructed deterministic quasipolynomial-size hitting sets for noncommutative branching programs under a field-size condition. Quasipolynomial means a running time like an exponential of a fixed power of the logarithm, generally larger than polynomial.

For rational formulas, Hrubeš and Wigderson developed reductions to linear-matrix singularity. Operator scaling and constructive noncommutative-rank algorithms subsequently supplied deterministic polynomial-time methods using the given coefficients.

Arvind, Chatterjee, and Mukhopadhyay obtained deterministic quasipolynomial hitting sets for rational formulas with unrestricted inverse nesting. They already account for matrix evaluation domains; unrestricted nesting is not itself the new feature here.

The manuscripts claim polynomial bounds for coefficient-independent test generation. They also distinguish formula size from sparsity: a test efficient in the number of expanded words need not be efficient in the size of a compact formula.

4. What the new manuscripts claim

M2 treats characteristic zero. Given positive integers $n,s$, it constructs rational matrices in deterministic polynomial bit time, with dimension

$$d\le2ns^2,$$

such that one tuple detects every nonzero division-free formula of size at most $s$ in $n$ variables. The same tuple works over every characteristic-zero coefficient field, with rational entries interpreted through the natural embedding.

M1 treats positive characteristic. Given a promised prime $p$ in binary and $n,s$ in unary, one machine outputs a tuple over $\mathbb F_p$ of dimension

$$d=O(n^3s^6)$$

in bit time polynomial in $n+s+\log p$. It works over every extension field of that characteristic, including characteristic two and with no assumption that $p$ exceeds the formula size.

Both papers also treat their stated acyclic algebraic path-program models, where one sums ordered products along directed paths. Their precise edge-label and size conventions remain relevant; the family does not extend these claims to arbitrary shared circuits.

M3 treats rational formulas over $\mathbb Q$. It constructs a polynomial-size list of rational matrix tuples, with polynomial dimensions, entry lengths, and total output length. Every nonzero admissible size-$s$ formula has a defined evaluation with invertible value at some tuple.

That last conclusion is stronger than merely obtaining a nonzero matrix. No separate bound on inverse depth or rational constant height is imposed on the formulas detected. The polynomial bit bound concerns generating the list, not evaluating an unknown expression containing arbitrarily long constants.

5. Why the advance matters

Importance: 4/5, provisional. Deterministic identity testing is a central derandomization problem in algebraic complexity. Universal black-box tests replace random trial substitutions with a fixed, efficiently generated collection guaranteed to expose every nonzero formula in the stated class.

The field coverage is substantive. A characteristic-zero construction based on dividing by integers may collapse modulo a small prime. M1 claims a separate construction that works uniformly without excluding such primes.

For rational expressions, preserving all inverse-domain conditions makes the test useful for the actual expression rather than only an abstractly equivalent rational function. The bounded-size list must supply a point where the full computation is defined.

The rating reflects the methodological breadth across these formula models. It is not a claim that every form of polynomial identity testing, especially general commutative circuit testing, has thereby been derandomized.

6. The main idea

Encode many words in one power series

M2 associates each ordered word with an iterated integral, interpreted as a formal power series. Formal means that coefficients are manipulated algebraically; convergence of a numerical integral is not needed for the final matrix construction.

The encoding is faithful: distinct words are linearly independent in the required sense. A nonzero polynomial therefore becomes a nonzero series. The challenge is that its first nonzero coefficient might, in principle, occur very late.

A size-$s$ formula has a small acyclic path representation. This converts the associated series into an entry of a finite differential system. A bound on the order of vanishing limits how many initial coefficients can be zero.

Truncating after polynomially many coefficients therefore preserves nonvanishing. The integration operators on this finite coefficient space are rational matrices, producing the universal tuple without knowing the formula.

Replace differentiation in small characteristic

Ordinary differentiation annihilates $z^p$ in characteristic $p$, and formal integration would require divisions that may be invalid. M1 instead uses a multiplicative shift

$$\sigma(g)(z)=g(tz),$$

where $t$ is an indeterminate. On the coefficient of $z^r$, the difference $\sigma-1$ acts by multiplication by $t^r-1$, which remains nonzero in every characteristic.

The paper establishes a corresponding vanishing-order bound, truncates the series, and then removes the indeterminate by representing multiplication in a finite truncated algebra with matrices over the prime field. This preserves bounded-degree information without assuming a conveniently large finite extension.

Certify every inverse simultaneously

M3 translates a rational formula into a bounded collection of affine matrix pencils—matrices whose entries are affine-linear expressions in the variables. Their simultaneous invertibility certifies both the domain conditions and invertibility of the final value.

The construction first uses subspace expansion to make ranks nearly full. A division-algebra lift forces the remaining ranks into multiples of a block size, turning a sufficiently small rank deficit into full rank.

Finally, bounded-degree determinant conditions are specialized on a fixed small integer grid. At least one grid point preserves all required nonvanishing conditions. Rational matrix representations remove auxiliary algebraic constants, giving the explicit list.

Formula-specific witnesses are used in the argument that the list works. The generator does not search for or receive those witnesses.

7. Scope, limitations, and open questions

The polynomial resource guarantees refer to test construction and output size. Evaluation over an unspecified coefficient field is an exact operation with its own representation costs. Arbitrarily large rational constants cannot be processed for free simply because the list is small.

The division-free guarantees cover their stated characteristics, whereas the rational-formula list is asserted over $\mathbb Q$. It should not be transferred to finite fields without a corresponding theorem.

Admissibility is part of M3’s promise. Undefined evaluations must be reported as such, rather than interpreted as zero. Testing arbitrary shared circuits or removing model restrictions remains outside the family claims.

8. Sources and further reading

M2 gives the characteristic-zero power-series construction; M1 explains the shift replacement required in positive characteristic. M3 states the rational-expression domain conventions and the separate cost of evaluating coefficients. Their introductions provide the white-box versus black-box comparisons needed to interpret the advance.

Source manuscripts

• M1. OpenAI, Uniform Matrix Hitting Points in Every Positive Characteristic (October 4, 2026).
• M2. OpenAI, One Rational Matrix Hitting Point for Noncommutative Formulas (September 24, 2026).
• M3. OpenAI, Polynomial Hitting Lists for Noncommutative Rational Formulas (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.