OctoInform Beta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Polynomial hitting lists for rational formulas]: A Turing machine, given 1n01s1^n01^s, writes in polynomially many steps rational matrix tuples hitting every admissible nonzero formula of size at most ss

Noncommutative rational formulas have polynomial-time hitting lists.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A rational formula in noncommuting variables x1,…,xnx_1,\dots,x_n is built from the variables and rational constants by sums, products and inverses, and it is evaluated by substituting square matrices for the variables. An inverse gate that meets a singular matrix leaves the formula undefined there: (x1x2−x2x1)−1(x_1x_2-x_2x_1)^{-1} has no value at any pair of scalars and has values at pairs of 2×22\times2 matrices. Black-box identity testing asks for a finite list of matrix tuples, depending only on nn and a size bound ss, at one of which every nonzero formula of size at most ss is defined and invertible. The question is whether a deterministic machine can write such a list in time polynomial in nn and ss.

Formulas and Their Values

A rational formula ff in nn variables is a tree whose leaves are variables x1,…,xnx_1,\dots,x_n or rational constants aa and whose inner vertices are sums g+hg+h, products g⋅hg\cdot h in that order, and inverses g−1g^{-1}, for formulas gg and hh.✦ Its size |f||f| is its number of vertices: |xi|=|a|=1,|g+h|=|g⋅h|=|g|+|h|+1,|g−1|=|g|+1.|x_i| = |a| = 1,\qquad |g+h| = |g\cdot h| = |g|+|h|+1,\qquad |g^{-1}| = |g|+1.(1)✦

Let RR be a ring with a ring homomorphism from ℚ\mathbb Q, and X∈RnX\in R^n. The relation “ff has the value vv at XX” is defined by induction on ff: the variable xix_i has the value XiX_i and a constant has its image in RR; if gg and hh have the values uu and vv, then g+hg+h and g⋅hg\cdot h have the values u+vu+v and uvuv; if gg has a value uu and u′∈Ru'\in R satisfies uu′=u′u=1uu' = u'u = 1, then g−1g^{-1} has the value u′u'.✦ At a tuple X∈Matd(ℚ)nX\in\mathrm{Mat}_d(\mathbb Q)^n of d×dd\times d rational matrices the values are taken in Matd(ℚ)\mathrm{Mat}_d(\mathbb Q), with ℚ\mathbb Q as the scalar matrices.✦

A formula ff is admissible if it has a value at some tuple in Matd(ℚ)n\mathrm{Mat}_d(\mathbb Q)^n with d≥1d\ge1.✦ A formula ff is nonzero if it has a nonzero value at some tuple in Matd(ℚ)n\mathrm{Mat}_d(\mathbb Q)^n with d≥1d\ge1.✦

A list ℋ\mathcal H of nn-tuples is a dimension d≥1d\ge1 together with a finite sequence of nn-tuples of d×dd\times d rational matrices: ℋ=(d;X(1),…,X(L)),d≥1,X(1),…,X(L)∈Matd(ℚ)n.\mathcal H = \bigl(d;\ X^{(1)},\dots,X^{(L)}\bigr),\qquad d\ge1,\quad X^{(1)},\dots,X^{(L)}\in\mathrm{Mat}_d(\mathbb Q)^n.(2)✦ A list ℋ\mathcal H of nn-tuples hits size ss if every admissible nonzero formula in nn variables of size at most ss has, at some tuple of ℋ\mathcal H, a value that is an invertible matrix.✦

Machines and Encodings

The tape alphabet is Γ={0,1,2,3}\Gamma = \{0,1,2,3\}: 00 is the blank, 11 and 22 stand for the binary digits 00 and 11, and 33 is a work symbol.✦ A Turing machine GG over Γ\Gamma with states 0,…,m0,\dots,m is a partial transition function δG:{0,…,m}×Γ⇀{0,…,m}×({left,right}∪Γ);\delta_G : \{0,\dots,m\}\times\Gamma\ \rightharpoonup\ \{0,\dots,m\}\times \bigl(\{\mathrm{left},\mathrm{right}\}\cup\Gamma\bigr);(3)✦ in state qq reading γ\gamma it halts if δG(q,γ)\delta_G(q,\gamma) is undefined, and otherwise enters the new state and either moves its head one cell or writes the given symbol.

A configuration κ\kappa of GG is a state with a tape and a head position, and stepG(κ)\mathrm{step}_G(\kappa) is the configuration after one transition, undefined when GG halts at κ\kappa.✦ For a number τ\tau of transitions and a configuration κ\kappa of GG, the configuration runG(τ,κ)\mathrm{run}_G(\tau,\kappa) reached from κ\kappa after τ\tau transitions is defined by recursion on τ\tau: runG(0,κ)=κ,runG(τ+1,κ)=runG(τ,stepG(κ)),\mathrm{run}_G(0,\kappa) = \kappa,\qquad \mathrm{run}_G(\tau+1,\kappa) = \mathrm{run}_G\bigl(\tau,\mathrm{step}_G(\kappa)\bigr),(4)✦ with runG(τ+1,κ)\mathrm{run}_G(\tau+1,\kappa) undefined when stepG(κ)\mathrm{step}_G(\kappa) is.

The input on integers nn and ss is the word in(n,s)=2⋯2⏟n12⋯2⏟s,\mathrm{in}(n,s) = \underbrace{2\cdots2}_{n}\ 1\ \underbrace{2\cdots2}_{s},(5)✦ the string 1n01s1^n01^s in the symbols of the binary digits, and init(w)\mathrm{init}(w) is the configuration in the initial state, state 00, with the word ww on the tape from the head rightwards and blanks elsewhere.

A natural number aa with binary digits ϵ0,…,ϵλ−1\epsilon_0,\dots,\epsilon_{\lambda-1}, least significant first, λ=0\lambda = 0 for a=0a = 0, has the self-delimiting encoding ⟨a⟩=1λ0ϵ0ϵ1⋯ϵλ−1.\langle a\rangle = 1^\lambda\,0\,\epsilon_0\epsilon_1\cdots\epsilon_{\lambda-1}.(6)✦ A rational number q=p/rq = p/r in lowest terms with r≥1r\ge1 is encoded by a sign bit followed by its numerator and denominator: ⟨q⟩=σ⟨|p|⟩⟨r⟩,σ=1 if q<0,σ=0 if q≥0.\langle q\rangle = \sigma\,\langle |p|\rangle\,\langle r\rangle,\qquad \sigma = 1 \text{ if } q<0,\quad \sigma = 0 \text{ if } q\ge0.(7)✦ A tuple in Matd(ℚ)n\mathrm{Mat}_d(\mathbb Q)^n is encoded by the encodings of the entries of its nn matrices in turn, each matrix row by row✦, and a list ℋ\mathcal H as in (2) by the word ⟨ℋ⟩=⟨d⟩⟨L⟩⟨X(1)⟩⋯⟨X(L)⟩,\langle\mathcal H\rangle = \langle d\rangle\,\langle L\rangle\,\langle X^{(1)}\rangle\cdots \langle X^{(L)}\rangle,(8)✦ of length |⟨ℋ⟩||\langle\mathcal H\rangle|.

The word ⟨ℋ⟩¯\overline{\langle\mathcal H\rangle} is ⟨ℋ⟩\langle\mathcal H\rangle written in the symbols of the binary digits.✦ A machine GG outputs ℋ\mathcal H from in(n,s)\mathrm{in}(n,s) within β\beta transitions if there are τ≤β\tau\le\beta and a configuration κ\kappa with runG(τ,init(in(n,s)))=κ,stepG(κ)undefined,tape of κ from the head rightwards=⟨ℋ⟩¯000⋯.\mathrm{run}_G\bigl(\tau,\mathrm{init}(\mathrm{in}(n,s))\bigr) = \kappa,\qquad \mathrm{step}_G(\kappa)\ \text{undefined},\qquad \text{tape of } \kappa \text{ from the head rightwards} = \overline{\langle\mathcal H\rangle}\,0\,0\,0\cdots.(9)✦

The Explicit List

For n,s≥1n,s\ge1 the explicit list ℒn,s\mathcal L_{n,s} is built from the parameters w=n+1,B=2s+1,Δ=2w3B,e=⌊log⁡2(BΔ)⌋,M=2e+1,N=M−Δ,ℓ=M/2,D=Mℓ,H=1+3(s+2)BM3,\begin{gathered} w = n+1,\qquad B = 2s+1,\qquad \Delta = 2w^3B,\qquad e = \lfloor\log_2(B\Delta)\rfloor, \qquad M = 2^{e+1},\\ N = M-\Delta,\qquad \ell = M/2,\qquad D = M\ell,\qquad H = 1+3(s+2)BM^3, \end{gathered}(10)

Let KK be a field and Pd(K)P_d(K) the space of polynomials in XX over KK of degree below dd, and let tt be a further indeterminate. The Taylor test TaT_a at a point a∈Ka\in K is the linear map PN(K)→PM(K)[t]P_N(K)\to P_M(K)[t] with Tap=∑r=0M−1trpr(X−a)M−1−rfor p=∑rpr(X−a)r∈PN(K),T_a\,p = \sum_{r=0}^{M-1} t^r\,p_r\,(X-a)^{M-1-r}\qquad \text{for } p = \sum_r p_r\,(X-a)^r\in P_N(K),(11) and its matrix Ra(t)R_a(t) is the M×MM\times M matrix over K[t]K[t], rows and columns indexed by ℤ/M\mathbb Z/M, whose column j<Nj<N is the coefficient vector of TaXjT_aX^j and whose columns j≥Nj\ge N are zero. Over ℚ\mathbb Q, for integers aa and tt, the entry of Ra(t)R_a(t) in row ii and column j<Nj<N is the integer ∑r(M−1−ri)(−a)M−1−r−i(jr)aj−rtr\sum_{r}\binom{M-1-r}{i}(-a)^{M-1-r-i}\binom{j}{r}a^{j-r}t^r.

Over a field KK with an additive character χ\chi of ℤ/M\mathbb Z/M, the Weyl monomials are the M×MM\times M matrices DaSbD^aS^b, a,b∈ℤ/Ma,b\in\mathbb Z/M, with (DaSb)ij=χ(ai)(D^aS^b)_{ij} = \chi(ai) when i=j+bi = j+b and 00 otherwise.✦ A matrix R(t)R(t) over K[t]K[t] indexed by ℤ/M\mathbb Z/M has the Fourier coefficient polynomials ca,b(t)=M−1∑j∈ℤ/Mχ(−aj)R(t)j,j−bc_{a,b}(t) = M^{-1}\sum_{j\in\mathbb Z/M}\chi(-aj)\,R(t)_{j,\,j-b}✦, and its lift is the matrix over K[x0,x1,x2]K[x_0,x_1,x_2] R*(x0,x1,x2)=∑a,b∈ℤ/Mca,b(x0)x1ax2bDaSb,R^*(x_0,x_1,x_2) = \sum_{a,b\in\mathbb Z/M} c_{a,b}(x_0)\,x_1^{a}x_2^{b}\,D^aS^b,(12)✦ with the exponents a,ba,b read in {0,…,M−1}\{0,\dots,M-1\}.

The field ℛ=ℚ[ξ]/(ξℓ+1)\mathcal R = \mathbb Q[\xi]/(\xi^\ell+1) is the MM-th cyclotomic field, with the additive character χ(c)=ξc\chi(c) = \xi^c of ℤ/M\mathbb Z/M.✦ The regular representation ρ:ℛ→Matℓ(ℚ)\rho:\mathcal R\to\mathrm{Mat}_\ell(\mathbb Q) of ℛ\mathcal R sends zz to the matrix of multiplication by zz in the power basis 1,ξ,…,ξℓ−11,\xi,\dots,\xi^{\ell-1}; on ξc\xi^c, 0≤c<M0\le c<M, it is the signed permutation matrix PcP_c with (Pc)ij=(−1)⌊(c+j)/ℓ⌋ if c+j≡i(mod⁡ℓ),(Pc)ij=0 otherwise.(P_c)_{ij} = (-1)^{\lfloor (c+j)/\ell\rfloor}\ \text{ if } c+j\equiv i \pmod\ell,\qquad (P_c)_{ij} = 0\ \text{ otherwise}.(13)✦ The entrywise extension ρM:MatM(ℛ)→MatD(ℚ)\rho_M:\mathrm{Mat}_M(\mathcal R)\to\mathrm{Mat}_D(\mathbb Q) of ρ\rho replaces each entry zz at (u,v)(u,v) by the block ρ(z)\rho(z) in rows uℓ,…,uℓ+ℓ−1u\ell,\dots,u\ell+\ell-1 and columns vℓ,…,vℓ+ℓ−1v\ell,\dots,v\ell+\ell-1.

With K=ℛK = \mathcal R, let Ri*R_i^* be the lift of Ri(t)R_i(t) for the points i=0,…,ni = 0,\dots,n✦, and Zi(x)=ρM(Ri*(x))∈MatD(ℚ)Z_i(x) = \rho_M\bigl(R_i^*(x)\bigr)\in\mathrm{Mat}_D(\mathbb Q) at a point x=(x0,x1,x2)x = (x_0,x_1,x_2) with positive integer coordinates.✦ The list ℒn,s\mathcal L_{n,s} runs over the grid {1,…,H}3\{1,\dots,H\}^3 in lexicographic order: ℒn,s=(D;(Z0(x)−1Z1(x),…,Z0(x)−1Zn(x))for x∈{1,…,H}3 with det⁡Z0(x)≠0).\mathcal L_{n,s} = \Bigl(D;\ \bigl(Z_0(x)^{-1}Z_1(x),\dots,Z_0(x)^{-1}Z_n(x)\bigr) \ \text{for } x\in\{1,\dots,H\}^3 \text{ with } \det Z_0(x)\ne0\Bigr).(14)✦

The list ℒn,sℤ\mathcal L^{\mathbb Z}_{n,s} is formed over the same grid from integer matrices. For i=0,…,ni = 0,\dots,n the matrix Ui(x)∈MatD(ℤ)U_i(x)\in\mathrm{Mat}_D(\mathbb Z) has at (u,v)∈(ℤ/M)2(u,v)\in(\mathbb Z/M)^2 the ℓ×ℓ\ell\times\ell block Ui(x)uv=∑a,h∈ℤ/MRi(x0)h,h−u+vx1ax2u−vPa(u−h),U_i(x)_{uv} = \sum_{a,h\in\mathbb Z/M} R_i(x_0)_{h,\,h-u+v}\,x_1^{a}x_2^{u-v}\,P_{a(u-h)},(15)✦ with Ri(x0)R_i(x_0) the integer Taylor matrix and exponents and subscripts read in {0,…,M−1}\{0,\dots,M-1\}. The division-free determinant det⁡∘A\det^\circ A of a d×dd\times d integer matrix AA is (−1)d−1(-1)^{d-1} times the top-left entry of Ad−1A_{d-1}, where A0=AA_0 = A and Aν+1A_{\nu+1} is obtained from AA and AνA_\nu by one elimination stage.✦ The list ℒn,sℤ\mathcal L^{\mathbb Z}_{n,s} has dimension DD and keeps, in lexicographic order, the grid points with det⁡∘U0(x)≠0\det^\circ U_0(x)\ne0; there it gives the tuple whose ii-th matrix has at (j,j′)(j,j') the Cramer quotient det∘(U0(x) with column j replaced by column j′ of Ui(x))det∘U0(x).\frac{\det^\circ\bigl(U_0(x)\text{ with column } j \text{ replaced by column } j' \text{ of } U_i(x)\bigr)}{\det^\circ U_0(x)}.(16)

The output constant CoutC_{\mathrm{out}} is defined through two others: Clog=64+64+3⋅16⋅24577,Cbit=4(2562+256Clog+1)+3,Cout=(2⋅256+3)+(2⋅245773+3)+245773⋅2562Cbit.\begin{gathered} C_{\log} = 64+64+3\cdot16\cdot24577,\qquad C_{\mathrm{bit}} = 4\,(256^2+256\,C_{\log}+1)+3,\\ C_{\mathrm{out}} = (2\cdot256+3)+(2\cdot24577^3+3)+24577^3\cdot256^2\,C_{\mathrm{bit}}. \end{gathered}(17)

The Claim

Theorem 1. There are a Turing machine GG over Γ\Gamma and positive integers CC and kk such that, for all integers n,s≥1n,s\ge1 and with β=C(n+s+1)k\beta = C(n+s+1)^k, some list ℋ\mathcal H of nn-tuples of d×dd\times d rational matrices satisfies d≤β,|⟨ℋ⟩|≤β,G outputs ℋ from in(n,s) within β transitions,ℋ hits size s.d\le\beta,\qquad |\langle\mathcal H\rangle|\le\beta,\qquad G \text{ outputs } \mathcal H \text{ from } \mathrm{in}(n,s) \text{ within } \beta \text{ transitions},\qquad \mathcal H \text{ hits size } s.(18)✦

In the paper, the result reads: there are a deterministic Turing machine GG and positive integers CC and kk such that, given 1n1^n and 1s1^s with n,s≥1n,s\ge1, GG outputs a finite list ℋn,s\mathcal H_{n,s} of nn-tuples of rational square matrices in at most C(n+s+1)kC(n+s+1)^k bit operations, the whole output, with signed binary numerators and positive binary denominators, has at most C(n+s+1)kC(n+s+1)^k bits, and every nonzero admissible rational formula Φ\Phi in nn variables of size at most ss has a defined evaluation with invertible value at some tuple of ℋn,s\mathcal H_{n,s}, the same list serving all such formulas whatever the bit lengths of their constants or their inverse depth, and GG receiving no formula, oracle, randomness or advice.

What Is Checked

The theorem (18) is stated over rational formulas with their size and values, the admissible and nonzero formulas, lists of tuples (2) and the hitting property, Turing machines (3) run as in (4) from the input (5), and output within a bound (9) in the encoding (8) built on (6) and (7).

The library proves that the modulus ξℓ+1\xi^\ell+1 of ℛ\mathcal R is a monic polynomial✦ of degree ℓ\ell✦. Of the list ℒn,sℤ\mathcal L^{\mathbb Z}_{n,s} it proves that, for all n,s≥1n,s\ge1, D≤256(n+s+1)10,|⟨ℒn,sℤ⟩|≤Cout(n+s+1)104,ℒn,sℤ hits size s,D\le256\,(n+s+1)^{10},\qquad |\langle\mathcal L^{\mathbb Z}_{n,s}\rangle|\le C_{\mathrm{out}}\,(n+s+1)^{104},\qquad \mathcal L^{\mathbb Z}_{n,s} \text{ hits size } s,(19)✦ and that there are a Turing machine GG and positive integers CC and kk with G outputs ℒn,sℤ from in(n,s) within C(n+s+1)k transitions, for all n,s≥1.G \text{ outputs } \mathcal L^{\mathbb Z}_{n,s} \text{ from } \mathrm{in}(n,s) \text{ within } C(n+s+1)^k \text{ transitions, for all } n,s\ge1.(20)✦ It also proves that a Turing machine GG and positive integers C,kC,k as in (20) give a Turing machine and positive constants as in the theorem: some G and C,k≥1 output ℒn,sℤ within C(n+s+1)k transitions for all n,s≥1⇒some G and C,k≥1 satisfy the theorem.\text{some } G \text{ and } C,k\ge1 \text{ output } \mathcal L^{\mathbb Z}_{n,s} \text{ within } C(n+s+1)^k \text{ transitions for all } n,s\ge1 \;\Longrightarrow\; \text{some } G \text{ and } C,k\ge1 \text{ satisfy the theorem}.(21)✦