OctoInform Beta

OpenAI preprint, September 2026 · §5. A rational hitting list and its bit complexity · §5

Proposition 5.1 [The hitting property]: Every admissible nonzero formula of size at most ss takes an invertible value at some tuple of the list ℋn,s\mathcal{H}_{n,s}

A rational hitting list for formulas of bounded size.

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

Fix nn and s≥1s\ge1. A noncommutative rational formula in x1,…,xnx_1,\dots,x_n of size at most ss may vanish at many tuples of matrices, or be undefined there because an inverse gate meets a singular matrix. The question is whether a single explicit list of tuples of rational matrices, all of one size, catches every such formula that is not zero, in the strong sense that the formula is defined at some tuple of the list and takes an invertible value there. The theorem below says that a list ℋn,s\mathcal{H}_{n,s}, built from a cyclotomic field and an integer grid and defined in The Generator, does this.

Formulas and Hitting Lists

A rational formula ff in nn variables is a finite tree built from the variables x1,…,xnx_1,\dots,x_n and rational constants by addition f+gf+g, multiplication f⋅gf\cdot g in this order, and inversion f−1f^{-1}.✦ The size |f||f| of ff is its number of vertices: a variable or a constant has size 11, and each gate adds 11 to the sizes of its operands.✦

Let RR be a ring receiving ℚ\mathbb{Q} and let X=(X1,…,Xn)∈RnX=(X_1,\dots,X_n)\in R^n. The evaluation of formulas at XX is the least relation f(X)=vf(X)=v between formulas ff and elements vv of RR closed under the rules xi(X)=Xi,a(X)=a,(f+g)(X)=f(X)+g(X),(f⋅g)(X)=f(X)g(X),f−1(X)=f(X)−1,x_i(X)=X_i,\quad a(X)=a,\quad (f+g)(X)=f(X)+g(X),\quad (f\cdot g)(X)=f(X)\,g(X),\quad f^{-1}(X)=f(X)^{-1},(1)✦ where a constant aa stands for its image in RR and the last rule applies only when f(X)f(X) has a two-sided inverse in RR. At a tuple X∈Matd(ℚ)nX\in\mathrm{Mat}_d(\mathbb{Q})^n the ring is Matd(ℚ)\mathrm{Mat}_d(\mathbb{Q}), a constant aa standing for the scalar matrix aIdaI_d.✦

A formula ff in nn variables is admissible if f(X)=vf(X)=v for some d≥1d\ge1, some tuple X∈Matd(ℚ)nX\in\mathrm{Mat}_d(\mathbb{Q})^n and some matrix vv✦, and nonzero if this holds with v≠0v\neq0✦. A list of tuples ℒ\mathcal{L} in nn variables consists of a dimension d≥1d\ge1 and a finite list of tuples in Matd(ℚ)n\mathrm{Mat}_d(\mathbb{Q})^n.✦ A list of tuples ℒ\mathcal{L} of dimension dd is a hitting list for size ss, written Hit⁡s(ℒ)\operatorname{Hit}_s(\mathcal{L}), if every admissible nonzero formula ff in nn variables with |f|≤s|f|\le s satisfies f(X)=vfor some X∈ℒ and some v∈GLd(ℚ).f(X)=v\quad\text{for some } X\in\mathcal{L} \text{ and some } v\in\mathrm{GL}_d(\mathbb{Q}).(2)✦

The Generator

For e≥0e\ge0 put ℓ=2e\ell=2^e✦, M=2e+1M=2^{e+1}✦ and D=MℓD=M\ell.✦ The cyclotomic field ℛ=ℚ[ξ]/(ξℓ+1)\mathcal{R}=\mathbb{Q}[\xi]/(\xi^\ell+1) is the MM-th cyclotomic field, obtained from ℚ\mathbb{Q} by adjoining a primitive MM-th root of unity ξ\xi✦; its modulus ξℓ+1\xi^\ell+1 is monic✦ of degree ℓ\ell✦, and 1,ξ,…,ξℓ−11,\xi,\dots,\xi^{\ell-1} is its power basis over ℚ\mathbb{Q}.✦ An additive character χ\chi of ℤ/M\mathbb{Z}/M in a field KK is a group homomorphism from ℤ/M\mathbb{Z}/M to the multiplicative group of KK; in ℛ\mathcal{R} it is the one sending kk to ξk\xi^k.✦ The regular representation ρ:ℛ→Matℓ(ℚ)\rho:\mathcal{R}\to\mathrm{Mat}_\ell(\mathbb{Q}) is the ℚ\mathbb{Q}-algebra homomorphism sending each η∈ℛ\eta\in\mathcal{R} to the matrix of multiplication by η\eta in the power basis✦, and its entrywise extension ρM:MatM(ℛ)→MatD(ℚ)\rho_M:\mathrm{Mat}_M(\mathcal{R})\to\mathrm{Mat}_D(\mathbb{Q}) is the ring homomorphism replacing every entry by its ℓ×ℓ\ell\times\ell block.✦

Fix a ℚ\mathbb{Q}-algebra homomorphism σ:ℛ→ℂ\sigma:\mathcal{R}\to\mathbb{C}✦, and let WW be the field of Hahn series with complex coefficients and exponents in ℤ2\mathbb{Z}^2, ordered lexicographically✦. The witness embedding of ℛ\mathcal{R} is the ring homomorphism ι=C∘σ:ℛ→W,\iota=C\circ\sigma:\mathcal{R}\to W,(3)✦ where C:ℂ→WC:\mathbb{C}\to W sends a complex number to the constant series.

Let KK be a field and N≥0N\ge0. The test matrix Ri(t)R_i(t) at the point i∈{0,…,n}i\in\{0,\dots,n\} is the padded Taylor test matrix of order MM at ii with NN kept columns: the M×MM\times M matrix over K[t]K[t], with rows and columns indexed by ℤ/M\mathbb{Z}/M and read in {0,…,M−1}\{0,\dots,M-1\}, with entries Ri(t)jk={∑u=0M−1tu[ζj](ζ−i)M−1−u[ζu](ζ+i)k,k<N,0,k≥N,R_i(t)_{jk}= \begin{cases} \sum_{u=0}^{M-1}t^u\,[\zeta^j](\zeta-i)^{M-1-u}\,[\zeta^u](\zeta+i)^k, & k<N,\\ 0, & k\ge N, \end{cases}(4)✦ with ζ\zeta an indeterminate and [ζm]p[\zeta^m]p the coefficient of ζm\zeta^m in a polynomial pp in ζ\zeta.

For an additive character χ\chi of ℤ/M\mathbb{Z}/M in KK and a,b∈ℤ/Ma,b\in\mathbb{Z}/M, the Weyl monomial DaSbD^aS^b is the matrix over KK indexed by ℤ/M\mathbb{Z}/M whose entry at (j,k)(j,k) is χ(aj)\chi(aj) if j=k+bj=k+b and 00 otherwise, the product of the clock matrix Da=diag(χ(aj))jD^a=\mathrm{diag}(\chi(aj))_j and the power SbS^b of the cyclic shift.✦ The three-parameter lift of a matrix R(t)R(t) over K[t]K[t] indexed by ℤ/M\mathbb{Z}/M is the matrix of polynomials in t,p,rt,p,r over KK R*(t,p,r)=∑a,b∈ℤ/Mcab(t)parbDaSb,cab(t)=1M∑j∈ℤ/Mχ(−aj)R(t)j,j−b,R^*(t,p,r)=\sum_{a,b\in\mathbb{Z}/M}c_{ab}(t)\,p^a r^b\,D^aS^b,\qquad c_{ab}(t)=\frac1M\sum_{j\in\mathbb{Z}/M}\chi(-aj)\,R(t)_{j,\,j-b},(5)✦ the exponents a,ba,b read in {0,…,M−1}\{0,\dots,M-1\}. The pencil lifts are the lifts R0*,…,Rn*R_0^*,\dots,R_n^* of the test matrices.✦

Over ℛ\mathcal{R}, with χ(k)=ξk\chi(k)=\xi^k, a point y∈ℕ3y\in\mathbb{N}^3 gives the matrices Ri*(y)∈MatM(ℛ)R_i^*(y)\in\mathrm{Mat}_M(\mathcal{R}), the pencil lifts evaluated at (t,p,r)=y(t,p,r)=y✦, and the rational matrices Zi(y)=ρM(Ri*(y))Z_i(y)=\rho_M(R_i^*(y)) of size DD, for i=0,…,ni=0,\dots,n✦. The tuple at yy is X(y)=(Z0(y)−1Z1(y),…,Z0(y)−1Zn(y))∈MatD(ℚ)n.X(y)=\bigl(Z_0(y)^{-1}Z_1(y),\dots,Z_0(y)^{-1}Z_n(y)\bigr)\in\mathrm{Mat}_D(\mathbb{Q})^n.(6)✦ For natural numbers NN, ee and HH, the generator output 𝒢N,e,H\mathcal{G}_{N,e,H} is the list of tuples of dimension DD made of the X(y)X(y) for yy running through the grid {1,…,H}3\{1,\dots,H\}^3 in lexicographic order, each kept only when det⁡Z0(y)≠0\det Z_0(y)\neq0.

The parameters of nn and ss are w=n+1,B=2s+1,Δ=2w3B,e=⌊log⁡2(BΔ)⌋,N=M−Δ,H=1+3(s+2)BM3,w=n+1,\quad B=2s+1,\quad \Delta=2w^3B,\quad e=\lfloor\log_2(B\Delta)\rfloor,\quad N=M-\Delta,\quad H=1+3(s+2)BM^3,(7) with M=2e+1M=2^{e+1} the least power of two greater than BΔB\Delta✦, and the hitting list ℋn,s\mathcal{H}_{n,s} is the output 𝒢N,e,H\mathcal{G}_{N,e,H} at these parameters✦.

Pencils and Certificates

An affine form λ\lambda in nn variables is an expression λ0+λ1x1+…+λnxn\lambda_0+\lambda_1x_1+\dots+\lambda_nx_n with rational coefficients✦, and (λ0,…,λn)∈ℚn+1(\lambda_0,\dots,\lambda_n)\in\mathbb{Q}^{n+1} is its coefficient vector✦. In a ring RR receiving ℚ\mathbb{Q}, its evaluation at X∈RnX\in R^n and its homogeneous evaluation at Z=(Z0,…,Zn)∈Rn+1Z=(Z_0,\dots,Z_n)\in R^{n+1} are λ(X)=λ0+∑i=1nλiXi,λh(Z)=∑i=0nλiZi.\lambda(X)=\lambda_0+\sum_{i=1}^n\lambda_iX_i,\qquad \lambda^{\mathrm{h}}(Z)=\sum_{i=0}^n\lambda_iZ_i.(8)

A pencil LL of order qq is a q×qq\times q matrix of affine forms; its coefficient matrices A0,…,An∈Matq(ℚ)A_0,\dots,A_n\in\mathrm{Mat}_q(\mathbb{Q}) collect the coefficients of its entries✦, and L(X)L(X) and Lh(Z)L^{\mathrm{h}}(Z) are the q×qq\times q matrices over RR obtained entrywise. At d×dd\times d matrices, L(X)L(X) is the block matrix A0⊗Id+∑iAi⊗XiA_0\otimes I_d+\sum_iA_i\otimes X_i up to the order of the basis. The one pencil 𝟏\mathbf{1} is the pencil of order 11 whose single entry is the constant form 11.✦

The pencil LfL_f of a formula ff is defined by recursion on ff through block matrices, Lxi=(1−xi01),La=(1−a01),Lf+g=(Lf00Lg),Lf⋅g=(Lf−vfug0Lg),Lf−1=(Lfvfuf0),\begin{gathered} L_{x_i}=\begin{pmatrix}1&-x_i\\0&1\end{pmatrix},\qquad L_a=\begin{pmatrix}1&-a\\0&1\end{pmatrix},\qquad L_{f+g}=\begin{pmatrix}L_f&0\\0&L_g\end{pmatrix},\\ L_{f\cdot g}=\begin{pmatrix}L_f&-v_fu_g\\0&L_g\end{pmatrix},\qquad L_{f^{-1}}=\begin{pmatrix}L_f&v_f\\u_f&0\end{pmatrix}, \end{gathered}(9) where the row ufu_f and the column vfv_f of a formula ff are the rational vectors, of length the order of LfL_f, given by the recursions uxi=ua=(10),uf+g=(ufug),uf⋅g=(uf0),uf−1=(0−1),vxi=va=(01),vf+g=(vfvg),vf⋅g=(0vg),vf−1=(01),\begin{gathered} u_{x_i}=u_a=\begin{pmatrix}1&0\end{pmatrix},\quad u_{f+g}=\begin{pmatrix}u_f&u_g\end{pmatrix},\quad u_{f\cdot g}=\begin{pmatrix}u_f&0\end{pmatrix},\quad u_{f^{-1}}=\begin{pmatrix}0&-1\end{pmatrix},\\ v_{x_i}=v_a=\begin{pmatrix}0\\1\end{pmatrix},\quad v_{f+g}=\begin{pmatrix}v_f\\v_g\end{pmatrix},\quad v_{f\cdot g}=\begin{pmatrix}0\\v_g\end{pmatrix},\quad v_{f^{-1}}=\begin{pmatrix}0\\1\end{pmatrix}, \end{gathered}(10) with the blocks following those of LL, the new index of Lf−1L_{f^{-1}} last. The order of LhL_h is 22 when hh is a variable or a constant, the sum of the orders of LfL_f and LgL_g when hh is f+gf+g or f⋅gf\cdot g, and one more than the order of LfL_f when h=f−1h=f^{-1}.

The certificates h1,…,hmh_1,\dots,h_m of a formula ff are its inverse subformula occurrences h1,…,hm−1h_1,\dots,h_{m-1}, one for each inversion gate, listed in prefix order (a gate before its operands, a left operand before a right one), followed by hm=f−1h_m=f^{-1}.✦

Let KK be a field of characteristic zero with an additive character χ\chi of ℤ/M\mathbb{Z}/M. The certificate matrix PLP_L of a pencil LL of order qq is the matrix of size qMqM over K[t,p,r]K[t,p,r] whose block at (j,k)(j,k) is the lift of the combination of test matrices weighted by the entries at (j,k)(j,k) of the coefficient matrices, PL=[(∑i=0n(Ai)jkRi(t))*]j,k=1q,P_L=\Bigl[\Bigl(\sum_{i=0}^n(A_i)_{jk}\,R_i(t)\Bigr)^{*}\Bigr]_{j,k=1}^{q},(11)✦ and det⁡PL∈K[t,p,r]\det P_L\in K[t,p,r] is the certificate determinant of LL✦. The condition list of ff for NN and ee is the list of certificate determinants over ℛ\mathcal{R}, with χ(k)=ξk\chi(k)=\xi^k, CN,e(f)=(det⁡P𝟏,det⁡PLh1,…,det⁡PLhm).C_{N,e}(f)=\bigl(\det P_{\mathbf{1}},\ \det P_{L_{h_1}},\dots,\det P_{L_{h_m}}\bigr).(12)✦

The Claim

Theorem 1. Let nn and ss be natural numbers with s≥1s\ge1. Then Hit⁡s(ℋn,s).\operatorname{Hit}_s(\mathcal{H}_{n,s}).(13)✦ Let moreover ee, NN and HH be any natural numbers with N≥1N\ge1, M=N+ΔM=N+\Delta, BΔ<MB\Delta<M and 3(s+2)BM2<H3(s+2)BM^2<H, where M=2e+1M=2^{e+1} and BB, Δ\Delta are as in (7). Then Hit⁡s(𝒢N,e,H).\operatorname{Hit}_s(\mathcal{G}_{N,e,H}).(14)✦

In the paper, the result reads: every nonzero admissible formula of size at most ss has a defined, invertible evaluation at a tuple in ℋn,s\mathcal{H}_{n,s}.

What Is Checked

The claim is stated over rational formulas with their size and their evaluation (1) at tuples of rational matrices, admissible and nonzero formulas, lists of tuples with the hitting property (2), and the generator output 𝒢N,e,H\mathcal{G}_{N,e,H}, built from the cyclotomic field ℛ\mathcal{R}, its regular representation and the pencil lifts, with its instance ℋn,s\mathcal{H}_{n,s} at the parameters (7).

For s≥1s\ge1, a formula ff with |f|≤s|f|\le s and any NN and ee, the condition list satisfies |CN,e(f)|≤s+2anddeg⁡p≤3BM2for every p∈CN,e(f),|C_{N,e}(f)|\le s+2\quad\text{and}\quad \deg p\le 3BM^2\ \text{for every } p\in C_{N,e}(f),(15)✦ with deg\deg the total degree. If moreover ff is nonzero, N≥1N\ge1, M=N+ΔM=N+\Delta and BΔ<MB\Delta<M, then p≠0for every p∈CN,e(f).p\neq0\quad\text{for every } p\in C_{N,e}(f).(16)✦

Over a field KK, a nonzero polynomial pp in kk variables whose total degree is less than the size of a finite set S⊆KS\subseteq K satisfies the grid form of the Schwartz-Zippel lemma, p(x)≠0for some x∈Sk.p(x)\neq0\quad\text{for some } x\in S^k.(17)✦ For a finite list PP of nonzero polynomials in kk variables, each of total degree at most dd, with |P|d<|S||P|\,d<|S|, some x∈Sk has p(x)≠0 for every p∈P.\text{some } x\in S^k \text{ has } p(x)\neq0 \text{ for every } p\in P.(18)✦ In three variables over a field of characteristic zero, with |P|d<H|P|\,d<H in place of |P|d<|S||P|\,d<|S|, the point lies in the integer grid: some y∈{1,…,H}3 has p(y)≠0 for every p∈P.\text{some } y\in\{1,\dots,H\}^3 \text{ has } p(y)\neq0 \text{ for every } p\in P.(19)✦ The parameters (7) of nn and ss satisfy 3(s+2)BM2<H.3(s+2)BM^2<H.(20)✦

Let KK be a field of characteristic zero with an additive character χ\chi of ℤ/M\mathbb{Z}/M, LL a pencil of order qq, and y∈K3y\in K^3 a point with det⁡PL(y)≠0\det P_L(y)\neq0. Then Lh(R0*(y),…,Rn*(y))∈GLq(MatM(K)).L^{\mathrm{h}}\bigl(R_0^*(y),\dots,R_n^*(y)\bigr)\in\mathrm{GL}_q\bigl(\mathrm{Mat}_M(K)\bigr).(21)✦ For square matrices Z0,…,ZnZ_0,\dots,Z_n of size mm over KK at which the homogeneous evaluation 𝟏h(Z)\mathbf{1}^{\mathrm{h}}(Z) of the one pencil is invertible, Z0∈GLm(K).Z_0\in\mathrm{GL}_m(K).(22)✦ Over any ℚ\mathbb{Q}-algebra RR, if a point Z∈Rn+1Z\in R^{n+1} has a unit as its coordinate Z0Z_0 and Lh(Z)∈GLq(R)L^{\mathrm{h}}(Z)\in\mathrm{GL}_q(R) for a pencil LL of order qq, then L(Z0−1Z1,…,Z0−1Zn)∈GLq(R).L\bigl(Z_0^{-1}Z_1,\dots,Z_0^{-1}Z_n\bigr)\in\mathrm{GL}_q(R).(23)✦

Let y∈ℕ3y\in\mathbb{N}^3 be a point at which R0*(y)R_0^*(y) is invertible in MatM(ℛ)\mathrm{Mat}_M(\mathcal{R}), and ff a formula with an invertible value at the tuple (R0*(y)−1R1*(y),…,R0*(y)−1Rn*(y))\bigl(R_0^*(y)^{-1}R_1^*(y),\dots,R_0^*(y)^{-1}R_n^*(y)\bigr) over MatM(ℛ)\mathrm{Mat}_M(\mathcal{R}). Then, at the rational tuple (6), f(X(y))=vfor some v∈GLD(ℚ).f\bigl(X(y)\bigr)=v\quad\text{for some } v\in\mathrm{GL}_D(\mathbb{Q}).(24)✦ For y∈{1,…,H}3y\in\{1,\dots,H\}^3 with R0*(y)R_0^*(y) invertible in MatM(ℛ)\mathrm{Mat}_M(\mathcal{R}), the tuple at yy is a tuple of the output: X(y)∈𝒢N,e,H.X(y)\in\mathcal{G}_{N,e,H}.(25)✦