Polynomial Identity Testing with Division: How OpenAI’s Proof Constructs Universal Matrix Hitting Lists

Imagine a sealed box that accepts a tuple of matrices and returns the value of a hidden formula. Some queries fail because an intermediate matrix has no inverse. Which queries can you choose in advance so that every nonzero formula of a given size gives you a decisive answer? OpenAI’s September 24, 2026 preprint gives polynomial identity testing with division a deterministic answer over the rationals. From the number of variables and a tree-size bound alone, it constructs a polynomial-size list of rational matrix tuples. Every admissible nonzero formula has a defined, invertible value on at least one tuple, even when inverses are nested. The preprint appeared in OpenAI’s October mathematics release.

1. What Is Polynomial Identity Testing for Noncommutative Rational Formulas?

A formula is a rooted tree. Leaves hold variables or rational constants, binary gates add or multiply their inputs in order, and unary gates take inverses. Size counts every vertex, including leaves and inverse gates. At a matrix substitution of dimension $d$, a constant $c$ becomes $cI_d$, where $I_d$ is the identity matrix. Every variable receives a square rational matrix of that same dimension.

A formula is admissible if it is defined at some rational matrix tuple of some positive dimension. It is nonzero if some defined rational evaluation yields a nonzero matrix. For admissible formulas, the identity question asks whether every defined evaluation is zero. In black-box polynomial identity testing, the tester queries values and can receive an undefined response. A hitting list lets it schedule all queries in advance, with the same schedule for every formula within the bound.

2. Why Ordinary Substitutions Cannot Detect Noncommutative Identities

The polynomial $x_1x_2-x_2x_1$ vanishes on every scalar pair because scalar multiplication commutes. Matrix multiplication distinguishes the operations described by its two monomials. Put a single one above the diagonal in the first matrix and a single one below the diagonal in the second.

Multiplying in the first order produces a one in the upper-left corner. Reversing the order moves that one to the lower-right corner. The difference is invertible, with determinant $-1$.

These same inputs also show why the domain matters once inverse gates appear. Each input is singular even though their commutator is invertible. An expression that needs to invert one of the inputs would therefore fail on this pair.

3. Why Division Makes Rational Identity Testing Harder

An inverse gate requires its operand to be invertible after all gates below it have been evaluated. Take the formula $x_1x_1^{-1}-1$, with subtraction implemented using addition and multiplication by $-1$. It returns the zero matrix whenever $X_1$ is invertible. At $X_1=0$, evaluating the inverse fails. Replacing the whole formula by the constant zero would change which tuples the tree accepts.

A nested expression such as $(x_1^{-1})^{-1}+1$ has two inverse occurrences. Evaluating the outer inverse requires a value from the inner one first. At a proposed tuple, a defined zero is a valid evaluation that fails to witness nonzeroness. An undefined response supplies no value at all. A rational identity testing list must hit the domain and the nonzero condition at the same point.

4. What Earlier Deterministic Methods Achieved

For division-free formulas and noncommutative algebraic branching programs, Raz and Shpilka gave deterministic polynomial-time tests with access to the computation. Bogdanov and Wee used randomized matrix queries for bounded-degree noncommutative polynomials. Forbes and Shpilka built deterministic quasipolynomial-size matrix hitting sets for noncommutative branching programs, a class that includes division-free formulas.

For rational formulas, Derksen and Makam obtained randomized polynomial-time identity testing. Operator scaling and constructive noncommutative-rank algorithms yielded deterministic polynomial-time white-box tests, with coefficient encodings included in their bit costs. Access to the formula or its coefficients gives those algorithms information a value oracle withholds. Arvind, Chatterjee, and Mukhopadhyay obtained quasipolynomial-size rational matrix hitting sets for unrestricted inverse nesting. Their work already used invertible evaluations. The open construction problem was to generate a coefficient-independent black-box list with polynomial bounds on size, matrix dimension, and the cost of writing it down.

5. The Main Theorem Gives a Polynomial-Size Hitting List

Theorem 1.1 of the paper supplies one deterministic Turing machine $G$ and fixed positive integers $C,k$. For every $n,s\geq 1$, the machine receives $1^n,1^s$, the unary encodings of the number of variables and size bound. It outputs a finite list $\mathcal{H}_{n,s}$ of rational matrix $n$-tuples. Both the generation time in bit operations and the entire binary output length are at most $C(n+s+1)^k$. Entries are encoded with signed binary numerators and positive binary denominators. The construction uses one common positive matrix dimension for the whole list.

For every nonzero admissible formula in $n$ variables with at most $s$ vertices, some listed tuple makes the original tree evaluable and its result invertible. Different formulas can have different successful tuples. Invertibility is stronger than nonzeroness because a nonzero matrix can still have a kernel. Requiring full rank connects the hitting property to determinants, which the proof can preserve through specialization.

6. Encoding Formula Trees as Affine Matrix Pencils

An affine pencil of order $q$ is a square matrix with entries affine in the variables. The coefficients $A_i$ are rational matrices of order $q$. At a dimension-$d$ tuple, tensor products replace each scalar coefficient by the corresponding block multiple of the variable’s matrix or of $I_d$.

For each subtree $h$, the paper constructs a pencil $L_h$ of order $|h|+1$ and constant selectors $u_h,v_h$. When the subtree is defined, its value is $u_hL_h^{-1}v_h$, with the selectors tensored with $I_d$ at a matrix input. A leaf uses an upper-triangular pencil with unit diagonal and upper-right entry $-h$. Addition stacks the two child pencils on the diagonal and selects the sum. Ordered multiplication puts the constant block $-v_fu_g$ above the child pencils, so the selected part of the inverse multiplies the two values in the order $fg$.

At an inverse gate $h=g^{-1}$, the new pencil borders $L_g$ with $v_g$ and $u_g$, with zero in the lower-right block. Once the child is defined, eliminating its invertible block leaves the Schur complement $-g$. The gate pencil is invertible exactly when the required operand is invertible. Bordering the root in the same way checks invertibility of the final value. The proof checks inverse occurrences from leaves upward, using at most $s+1$ certificates of order at most $B=2s+1$.

For the nested example, take $a=x_1^{-1}$, $b=a^{-1}$ and $\Phi=b+1$. At a scalar input $x$, the inverse pencil for $a$ adds a row and column to the two-by-two leaf pencil.

Its determinant is $-x$. The bottom-right entry of its inverse is $-1/x$ for $x\neq 0$, so the negative row selector recovers $1/x$. The outer inverse pencil has determinant $1$. The root augmentation has determinant $-(x+1)$. At zero, the inner inverse pencil supplies the only failed certificate. This is why the proof keeps a pencil for each inverse occurrence.

7. Taylor Reversal, Wronskians, and Small-Subspace Expansion

Write $w=n+1$, $\Delta=2w^3B$, and let $M$ be the smallest power of two greater than $B\Delta$. Set $N=M-\Delta$. The rectangular map $T_i$ sends polynomials of degree less than $N$ to polynomials of degree less than $M$. It expands the input about $z=i$, for $i=0,\ldots,n$. If $c_{ia}(f)$ is the Taylor coefficient at order $a$, the map reverses the exponents and weights each term by $t^a$.

The proof works over the field $F=\mathbb{Q}((t))$ of formal Laurent series. Integral coefficients have no negative powers of $t$, and a unit has a nonzero constant term. An integral input with a unit Taylor coefficient at index at most $A$ has an image whose first nonzero term in $t$ uses only indices at most $A$. After reversal, that term vanishes to order at least $M-1-A$ at $i$. The proof uses reductions of integral vectors to keep the subspace dimensions intact when passing to rational coefficients.

For an $h$-dimensional rational space of polynomials of degree less than $d$, let $d_{ij}$ be its distinct basis vanishing orders at $i$, obtained by Taylor elimination. The Wronskian, a determinant of basis polynomials and their successive derivatives, has order $\sum_j d_{ij}-\binom{h}{2}$ there. Its degree is at most $h(d-1)$, which bounds the total order at the chosen points. Applying this bound to the reduced input and image spaces gives $\dim_F(\sum_iT_iU)>nk$ whenever $U$ has dimension $1\leq k\leq B$. The padding width $\Delta$ gives the reversed terms an extra vanishing margin. If the image span had dimension at most $n\dim_F U$, its largest vanishing orders at the $n+1$ points would already exceed the bound from its Wronskian. The contradiction applies to subspaces chosen after the test maps are fixed, including those whose coefficients depend on $t$.

A kernel vector for $\sum_i A_i\otimes T_i$ would yield a common input subspace that all the $A_i$ send into a strictly smaller output subspace. That shrinkage persists after tensoring with any matrix substitution and contradicts feasibility, meaning the existence of an invertible evaluation over an extension of the rationals. Padding $T_i$ with zero columns gives square matrices $R_i(t)$. Injectivity before padding yields the paper’s near-full rank bound.

8. Division-Algebra Deformation Turns Almost-Full Rank Into Full Rank

The lift uses a primitive $M$th root of unity $\omega$, a diagonal matrix $D_{\omega}$ with entries $\omega^j$, and the cyclic shift $S$. With independent parameters $p,r$, the matrices $pD_{\omega}$ and $rS$ commute up to the factor $\omega$. Localizing at nonzero central polynomials in $p^M,r^M$ gives a finite-dimensional division algebra. Its nonzero elements have inverses. Fourier expansion in diagonal and shift powers lifts each $R_i$ into this algebra and recovers it at $p=r=1$.

A nonzero minor from the padded evaluation survives as a nonzero polynomial in the lift. Block elimination over the division algebra reduces a matrix to identity and zero blocks. Ordinary rank is therefore a multiple of $M$. Since the lifted pencil’s rank lies strictly above $(q-1)M$ and at most $qM$, it must be $qM$. The paper also applies the lift to an initial defined nonzero formula evaluation. The original inverse gates stay defined over the extension, and the lifted nonzero value belongs to the division algebra, so it is invertible. At the original tuple the final matrix may have been singular. The witness for the formula’s certificates lives over the extension field, where the deformation makes the final matrix invertible.

9. Constructing Rational Matrix Hitting Lists From a Fixed Integer Grid

To remove complex coefficients, the generator works in $\mathbb{Q}[\xi]/(\xi^{\ell}+1)$ with $\ell=M/2$. It represents multiplication by each coefficient as a rational matrix in the power basis. Over the complex numbers this representation splits into one block per root of $\xi^{\ell}+1$. All these roots are primitive $M$th roots of unity, and a rational block matrix is invertible exactly when every root block is invertible.

For a fixed formula, take the product of the lifted determinant polynomials for every certificate and every root, including the constant pencil $1$ needed for normalization. Every factor is nonzero and has total degree at most $3BM^2$. The product has degree at most $\frac{3}{2}(s+2)BM^3$, strictly below $H=1+3(s+2)BM^3$. It cannot vanish on the entire grid $\{1,\ldots,H\}^3$. Fix two coordinates and use the univariate root bound on the first. If all grid values vanish, every coefficient vanishes on the remaining grid. Repeating the argument for both remaining coordinates makes the polynomial zero.

At every grid triple the generator forms rational matrices $Z_0,\ldots,Z_n$ via the multiplication representation. It skips singular $Z_0$ and emits the normalized matrices below. Left multiplication by $I_q\otimes Z_0^{-1}$ restores the affine constant term $A_0\otimes I_D$. A grid point where the product survives makes every certificate invertible at once.

10. Why the Construction Is Polynomial-Time Despite Arbitrary Inverse Depth

The generator enumerates a grid in three parameters, regardless of the number of formula variables or inverses. With $m=n+s+1$, the paper obtains the following upper bounds for its explicit construction.

The generator clears the common denominator $M$ and works with integer matrices before normalization. Exact elimination computes determinants with polynomially bounded intermediate bit lengths, and ratios of determinants give the output entries. The formula-specific certificate pencils and determinant product appear only in the proof. The generator never reads the formula, searches for its initial witness, or receives coefficient bit lengths. Large rational constants can change where a hit occurs, while the polynomial degree bound and the grid depend only on size parameters. Evaluating an unknown formula can still cost more as coefficient encodings grow. The exponents describe theoretical upper bounds and give no measured runtime.

11. What the Proof Establishes for Noncommutative Rank and Its Limits

Corollary 5.2 gives a hit for any feasible rational square affine pencil of order at most $B$. Corollary 6.1 extends the method to a rectangular pencil $A$ with $a$ rows, $b$ columns, and $k$ variables. Its noncommutative rank is its rank over the free skew field. The paper pads the pencil with variable blocks so that invertibility of a square completion certifies a chosen rank threshold. At matrix dimension $e$, the threshold $u$ requires rank at least $ue$. The new blocks can fill the missing rows and columns precisely when the evaluated pencil meets that threshold. It then projects the hitting list onto the original variables. Here $A(X)$ is the evaluated $ae$-by-$be$ block matrix and $\mathcal{R}_{a,b,k}$ depends only on the three size parameters.

Exact matrix values or ordinary ranks suffice. The maximum is exact without rounding, although individual ratios can be fractional. The formula theorem covers bounded-size trees over the rationals. Its guarantees leave general arithmetic circuits, which can share intermediate results, and finite fields outside its scope. OpenAI’s Lean documentation identifies the main rational hitting-list theorem, including the machine and encoding bounds, as the formalized result. The rectangular rank identity is a corollary in the paper.

For polynomial identity testing with division, the advance is a universal query schedule whose successful hit respects the original tree’s domain. The test points can be chosen before the coefficients are known because the proof bounds the degrees of the determinant conditions they must satisfy. Explore more proofs in theoretical computer science at Binary Verse AI.